CF2179 Round 1071 Div3 个人题解

A

容易猜到答案就是 $kx + 1$

条件翻译一下就是 $s_i \neq s_{i + tx}$ ，其中 $i + tx \le n$ 。容易发现这种不等关系长度最多为 $k$ ，否则一定存在相等。所以当 $n = kx + 1$ 时， $s_1$ 开头的不等关系一定完蛋。

B

枚举删掉哪一个就行，注意细节。

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N = 2e5 + 5;
25
int T, n, a[N];
26
void solve() {
27
    cin >> n;
28
    int sum = 0;
29
    for(int i = 1;i <= n;i++) {
30
        cin >> a[i];
31
        if(i != 1) sum += abs(a[i] - a[i - 1]);
32
    }
33
    int ans = sum, k = 0;
34
    a[n + 1] = 0;
35
    for(int i = 1;i <= n;i++) {
36
        int t = sum - (i != 1) * abs(a[i] - a[i-1]) - (i != n) * abs(a[i + 1] - a[i]) + (i != n && i != 1) * abs(a[i + 1] - a[i - 1]);
37
        ans = min(ans, t);
38
    }
39
    cout << ans << endl;
40
}
41
signed main() {
42
    ios::sync_with_stdio(0);
43
    cin.tie(0);
44
    cout.tie(0);
45
    cin >> T;
46
    while(T--) solve();
47
    return 0;
48
}

C

做出如下观察：

$k_{\max} \ge \min_{i = 1}^n\{{a_i}\}$ 。取等时，显然要把所有数都变成 $0$ ，于是其它数自己模自己即可。
当取 $k > \min_{i = 1}^n\{{a_i}\}$ 时，这个 $\min$ 的值依然不变，于是我们需要把其它所有数都变成这个 $\min$ 。取模选的 $x$ 自然是越大越好，对于一个非最小值的 $a_j$ ，最大的 $x$ 是 $a_j - \min$ ，于是乎我们对这些值取最小，就能得到最大的 $k$

注意后者求出的 $k$ 可能小于 $\min_{i = 1}^n\{{a_i}\}$ ，所以二者取较大就是答案。

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N = 2e5 + 5;
25
int T, n, a[N];
26
// 读错题了qwq
27
void solve() {
28
    cin >> n;
29
    for(int i = 1;i <= n;i++) cin >> a[i];
30
    sort(a + 1, a + n + 1);
31
    int ans = a[1];
32
    int mn = 1e9;
33
    for(int i = 2;i <= n;i++) {
34
        mn = min(mn, a[i] - a[1]);
35
    }
36
    cout << max(mn, ans) << endl;
37
}
38
signed main() {
39
    ios::sync_with_stdio(0);
40
    cin.tie(0);
41
    cout.tie(0);
42
    cin >> T;
43
    while(T--) solve();
44
    return 0;
45
}

D

注意到和式的每一项单调不增，我们考虑让其每次减小都只减小 $1$ ，然后在贡献值不变的情况下，按照字典序贪心放进去即可。

那么第一个数一定是 $2^n - 1$ 。接下来一定会减少一个 $1$ ，为了最小化字典序，应当去掉最高位的 $1$ 。以此类推，这个过程是 $O(n)$ 的。

设去掉最后一个 1 的结果为 $x$ ，从小到大把&上 $x$ popcount 不变的数扔进去，一定是字典序最小的方案。

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N = (1 << 16) + 5;
25
int T, n, a[N];
26
bool v[N];
27
vector<int> ans;
28
void solve() {
29
    cin >> n;
30
    for(int i = 0;i < (1 << n);i++) {
31
        a[i] = i;
32
        v[i] = 0;
33
    }
34
    int U = (1 << n) - 1;
35
    ans.clear();
36
    v[U] = 1;
37
    ans.pb(U);
38
    int x = U;
39
    for(int i = n - 1;i >= 0;i--) if(x & (1 << i)) {
40
        x -= (1 << i);
41
        ans.pb(x);
42
        v[x] = 1;
43
        for(int i = 0;i <= U;i++) if(!v[i]) {
44
            if(__builtin_popcount(x & i) != __builtin_popcount(x)) continue;
45
            ans.pb(i);
46
            v[i] = 1;
47
        }
48
    }
49
    for(int i = 0;i <= U;i++) if(!v[i]) ans.pb(i);
50
    for(auto x : ans) cout << x << " ";
51
    cout << endl;
52
}
53
signed main() {
54
    ios::sync_with_stdio(0);
55
    cin.tie(0);
56
    cout.tie(0);
57
    cin >> T;
58
    while(T--) solve();
59
    return 0;
60
}

E

待补

F

待补

Nanami^2

A

B

C

D

E

F

觉得这篇文章怎么样？

分享这篇文章

评论区

搜索结果

标签

分类

搜索结果

标签

分类

A

B

C

D

E

F

觉得这篇文章怎么样？

分享这篇文章

评论区