Codeforces-Round#580(Div.2)解题报告

A - Choose Two Numbers
给出两个数组,长度分别为$ n、m(1 \le n \le 100、1 \le m \le 100)$,找出两个分别属于两个数组的数,使得它们的和不在两个数组里

暴力

裸暴力,手滑了两发白给。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n,m;
int a[300],b[300];
bool mp[1000];

int main() {
mst(mp,0);
ios::sync_with_stdio(0);
cin>>n;
for(int i = 1;i <= n;i++) cin>>a[i],mp[a[i]] = 1;
cin>>m;
for(int i = 1;i <= m;i++) cin>>b[i],mp[b[i]] = 1;
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
if(mp[a[i] + b[j]] == 0) {
cout<<a[i]<<" "<<b[j]<<endl;
return 0;
}
}
}
return 0;
}

B - Make Product Equal One
给定一个数组$a$,其长度为$n$,每次可以花费1的代价使得一个数加1或者减1,求出最小的代价使得变化后所有数的乘积为1

贪心
会影响最终数值的是-1的地方,那么先统计一下小于等于-1以及等于0的数有多少个
先把小于等于-1的数变到-1的代价求出来,以及大于等于1的数变到1的代价求出来
最后再判断小于等于-1的数的个数是不是奇数,以及等于0的数是不是大于0,分类讨论一下即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int n;
ll a[maxn];
ll ans = 0;
int cnt1 = 0,cnt2 = 0;

int main() {
ios::sync_with_stdio(0);
cin>>n;
for(int i = 1; i<= n;i++) {
cin>>a[i];
if(a[i] <= -1) {
cnt1 ++;
ans += (-1LL) - a[i];
}
else if(a[i] == 0) cnt2++;
else {
ans += a[i] - 1LL;
}
}
if(cnt1 % 2 == 1) {
if(cnt2 > 0) ans += cnt2;
else ans += 2;
}
else ans += cnt2;
cout<<ans<<"\n";
return 0;
}

C - Almost Equal
给出一个数$n(1 \le n \le 1e5)$,然后问能不能将$1 - 2n$的$2n$个数排成一个环,使得在环上任意取$n$个连续的数所得到的和$sum_i$两两之间的差值小于等于1,如果可以,输出环的方案

数学
一开始看了样例猜了一下是不是只有n = 1和n = 3的情况下才能得到。。交了一发的确WA了
然后冷静分析.jpg
这$2n$个数每个数在加的情况下最多只能被取到$n$次,而且最后连续的$n$个数的和的情况就只有$x、x+1$的形式
那么可以得到一个方程$nx + n(x + 1) = n^2 \cdot (1 + 2n)$
得到$x = \frac {n - 1} {2} + n ^ 2$
也就是说只有在n是奇数的情况下才可以得到这个环,偶数的时候直接输出NO
那么在奇数的情况下,按照样例的方式构造答案即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
int n;
int ans[2 * maxn];
int pos1,pos2;

void check() {
for(int i = 1;i <= 2 * n;i++) {
int tmp = 0,pos;
for(int j = 0;j < n;j++) {
pos = i + j;
if(pos > 2 * n) pos = pos % (2 * n);
tmp += ans[pos];
}
cout<<tmp<<endl;
};
}

int main() {
ios::sync_with_stdio(0);
cin>>n;
if(n % 2 == 0) cout<<"NO\n";
else {
cout<<"YES\n";
pos1 = 2;
pos2 = n + 1;
for(int i = 2;i < 2 * n;i += 2) {
int x = i / 2;
if(x % 2 == 1) {
ans[pos2++] = i;
ans[pos2++] = i + 1;
}
else {
ans[pos1++] = i;
ans[pos1++] = i + 1;
}
}
ans[1] = 1;
ans[2 * n] = 2 * n;
cout<<1;
for(int i = 2;i <= 2 * n;i++) cout<<" "<<ans[i];
cout<<"\n";
}
return 0;
}

D - Shortest Cycle
给出$n(1 \le n \le 1e5)$个数$a_i(1 \le a_i \le 1e18)$,如果两个数$a_i$和$a_j$的与运算不为0的话,这两个数之间就存在一条边,求出最小的环的长度

dfs 位运算

本来一开始都快想到正解了但是又想偏了。。想了个假算法
最开始的想法:
考虑到如果暴力建边的话就是$n^2$的,但是可以利用位的信息来建图,可以降到$O(64n)$建图
两个数之间有路径,也就是说它们在某个位上同时为1,那么就可以开一个不定长数组,表示某一位上为1的数的编号,按位运算就可以得到这个数组
每次遍历的时候可以之间遍历这个数组得到当前点连接的边,就可以dfs一下。。
但是我TLE11。。改了之后又WA12
极限提交但是没过,白给。
然后看了一下别人的代码。。。特判了某个位为1的个数大于等于3的时候直接输出3,然后小于200的时候直接暴力建图跑bfs。。这里没想到
那么也就是说只要大于$64 \cdot 3$的情况下,暴力建图是可行的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
int n;
ll a[maxn];
int cnt[100];
vector<ll> all;
ll dist[200][200],ans = INF;
ll mp[200][200];

void floyd() {
for(int k = 0;k < (int)all.size();k++) {
for(int i = 0;i < k;i++) {
for(int j = i + 1;j < k;j++) {
ans = min(ans,dist[i][j] + mp[i][k] + mp[j][k]);
}
}
for(int i = 0;i < (int)all.size();i++) {
for(int j = 0;j < (int)all.size();j++) {
dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);
}
}
}
}

int main() {
ios::sync_with_stdio(0);
cin>>n;
for(int i = 1;i <= n;i++) {
cin>>a[i];
ll tmp = a[i];
for(int j = 0;tmp != 0;j++) {
if(tmp & 1) cnt[j]++;
tmp >>= 1;
}
if(a[i] != 0) all.push_back(a[i]);
}
for(int i = 0;i <= 64;i++) {
if(cnt[i] >= 3) {
cout<<"3\n";
return 0;
}
}
for(int i = 0;i < (int)all.size();i++) {
for(int j = 0;j < i;j++) {
if((all[i] & all[j]) != 0) {
dist[i][j] = dist[j][i] = 1;
mp[i][j] = mp[j][i] = 1;
}
else {
dist[i][j] = dist[j][i] = INF;
mp[i][j] = mp[j][i] = INF;
}
}
}
floyd();
if(ans == INF) cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}