cf563_div2 A~D

link

A

给2n个数,排列一下使得前半段的和不等于后半段的和

1
2
3
4
5
6
7
8
9
10
inputCopy
3
1 2 2 1 3 1
outputCopy
2 1 3 1 1 2
inputCopy
1
1 1
outputCopy
-1

瞎搞一下就好了

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
#include <bits/stdc++.h>
using namespace std;
vector<int > v,x;
bool used[3000];
int n;
int main() {
cin>>n;
long long s = 0;
for(int i = 1; i <= 2*n; ++i) {
int t; cin>> t;
v.push_back(t);
s += t;
}
sort(v.begin(),v.end());
long long e = 0;
for(int i = 0; i < v.size() && e < s / 2 && x.size() < n; ++i) {
if(e + v[i] == s / 2) continue;
e += v[i];
used[i] = 1;
x.push_back(v[i]);
}
if(x.size() < n ) {
puts("-1");
return 0;
}
bool flag = 0;
for(int i = 0; i < v.size(); ++i) {
if(used[i]) continue;
if(flag) cout<<" ";
else flag = 1;
cout<<v[i];
}
for(int i = 0; i < x.size(); ++i) {
cout<<" "<<x[i];
}
}

B 思维

给定一个n个数,可以将任意两个和为奇数的数进行任意次交换。求经过若干次操作后字典序最小的排列。

1
2
3
4
5
6
7
8
9
10
inputCopy
3
4 1 7
outputCopy
1 4 7
inputCopy
2
1 1
outputCopy
1 1

很显然,所有数都是奇数或者偶数肯定一次也换不了,原样输出。当两个数为一奇一偶时可以换,如果是两偶or两奇的话,可以找一个奇/偶数当中转。比如a,b为偶,c为奇,a和c换,c和b换,a和b换,最终相当于a和b换。所以任意两数换都是可以的。排序后直接输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v;
int n,x;
bool fin = 1;
scanf("%d",&n);
for(int i = 1; i <= n; ++i) {
int t; scanf("%d",&t);
if(i == 1) x = t % 2;
if(t % 2 != x) fin = 0;
v.push_back(t);
}
if(fin) {
for(int i = 0; i < n; ++i)
printf("%d ",v[i]);
return 0;
}
std::sort(v.begin(),v.end());
for(int i = 0; i < n; ++i)
printf("%d ",v[i]);
return 0;
}

C 思维

构造一个位置2~n共n-1的序列an,其中若任意i,j是互质的,则ai != aj,求任意一个max{a[i]}最小的序列。

1
2
3
4
5
6
7
8
inputCopy
4
outputCopy
1 2 1
inputCopy
3
outputCopy
2 1

首先,质数p和任意一个<p的数都互质,所以ap = max{a[1~(p-1)]} + 1。对于合数,它的值可以是它的因数的位置的数的任意一个,因为和它互质的数肯定和它没有大于1的公因子,所以说它们位置的数都不等于它的因数位置的数。

还有,6和9不是互质的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int ans[100005];
int main()
{
int n,c=0;
scanf("%d",&n);
for (int i=2;i<=n;i++)
{
if (!ans[i])
{
ans[i]=++c;
for (int j=i;j<=n;j+=i)
ans[j]=ans[i];
}
printf("%d ",ans[i]);
}
}

D 前缀和 异或

给定一个n和x,构造一个an序列,1 <= ai < 2^n,其中任意子段的异或和不等于x或者0。且an长度尽可能长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inputCopy
3 5
outputCopy
3
6 1 3
inputCopy
2 4
outputCopy
3
1 3 1
inputCopy
1 1
outputCopy
0

其实这题就是用了任意两个前缀异或和的元素可以表示任意一段子段的异或和,从而将对子段的异或和的限制转化为对两个前缀异或和元素的限制。

设bn是an的前缀异或和,首先bn肯定也是小于2^n的。子段异或和不等于0就相当于b里任意两个元素异或和不相等。这样的话bn最多有(2^n)-1个。

任意子段的异或和不等于x就相当于任意bi,bj,bi ^ bj != x。换句话说当bi ^ bj = x时只能bi,bj选一个。而bj = bi ^ x。所以枚举bi并标记bj,最后输出ai = bj ^ bj-1就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
bool ex[1<<19];
int main() {
int n,x;
cin>>n>>x;
vector<int> v({0});
ex[0] = 1,ex[x] = 1;
for(int i = 1; i < (1<<n); ++i) {
if(ex[i]) continue;
v.push_back(i);
ex[i ^ x] = 1;
}
printf("%d\n",v.size() - 1);
for(int i = 1; i < v.size(); ++i)
printf("%d ",v[i] ^ v[i - 1]);
return 0;
}

E dp

不会

F

不会