https://codeforces.com/contest/1365

E. Maximum Subsequence Value

 

题意：给定一个数列，选出一个子序列，对于每一位，如果序列中这一位为0的数个数小于3，则序列的值中这一位为1。要求选出的子序列值最大。

子序列大小最多为3。

对于多于3个的子序列，假设该序列的值第i位为1，即第i位最多有2个为0，由鸽巢原理，子序列中任意3个数组成的序列值第i位同样为1。所以任意3个都和序列有同样的值。

那么刚开始选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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
const ll mod = 1e9 + 7;
int n;
ll a[N], ans;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			for (int k = j; k <= n; k++) {
				ll tmp = (a[i] | a[j] | a[k]);
				ans = max(ans, tmp);
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

 

F. Swaps Again

 

题意：给定一个数列，和一个目标数列，要求每次操作任选一个长度相同的前缀和后缀交换位置，问任意次操作后能否达到目标。

第1位和第n位对应，第2位和第n-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
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
const ll mod = 1e9 + 7;
int T;
int a[N], b[N], n;
typedef pair<int, int>pii;
vector<pii>va, vb;
bool ck() {
	int n = (int)va.size();
	for (int i = 0; i < n; i++) {
		if (va[i] != vb[i])return false;
	}
	return true;
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		va.clear(); vb.clear();
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
		}
		for (int i = 1; i <= n; i++)scanf("%d", &b[i]);
		for (int i = 1; i <= (n + 1) / 2; i++) {
			int x = min(a[i], a[n - i + 1]), y = max(a[i], a[n - i + 1]);
			va.push_back(pii(x, y));
			x = min(b[i], b[n - i + 1]), y = max(b[i], b[n - i + 1]);
			vb.push_back(pii(x, y));
		}
		sort(va.begin(), va.end());
		sort(vb.begin(), vb.end());
		if (!ck())puts("No");
		else puts("Yes");
	}
	return 0;
}

 

G. Secure Password

 

题意：又是交互题。评测机有一个数列，问除了第 i 个数之外所有的数的或。每次询问可以得到询问的序列的或。1≤n≤10001\le n\le 1000，询问次数不超过13。

和上次题目很像，上次是最大值，这次是或。但是做法完全不同。这次并不能二分。

考虑下标。预先询问一些序列的或。对于下标 i ，需要用预先询问过的这些序列拼出覆盖除了 i 以外的所有下标，由于是或，所以重复了没关系。

对于下标 i ，如果有下标 j 的二进制是它的子集，由于下标都不相同，所以一定存在某一位在 i 中是1，而在 j 中是0；而如果下标 j 不是 i 的子集，则一定有某一位在 j 中是1，而在 i 中是0。

所以预先对于每一个二进制位，询问在这一位是0的所有数的或，询问在这一位是1的所有下标的或。再对每个下标 i ，遍历它的二进制位，如果该位是1，则答案或上该位是0的询问结果；如果该位是0，则答案或上该位是1的询问结果，这样一定能覆盖到所有除了 i 以外的下标。并且一定不包含 i 。

但是这样询问次数为 2log，还是不行。

询问这一位是1的所有下标的或仅仅是由于下标 j 的二进制可能是 i 的子集，之前把下标自身作为id，而如果重新给每个下标分配一个id，且保证不存在有包含关系的id，不就可以去掉这种情况了？

怎么分配又是个问题。

根据Sperner引理，从n个元素的集合中选出几个子集（可以不相交），且任意两个没有包含关系，最多选出 Cnn/2C_n^{n/2} 满足条件的子集。长度相等的子集显然不会有包含关系，如果只选长度为 k 的子集，有 CnkC_n^k 种选法，也就是能选出 CnkC_n^k 个子集。而由组合数的知识得到 k=n/2k=n/2 时最大。但这只是方便记忆，并不是证明！

把二进制位数视为集合大小n，某个数第 i 位为1，则视为它代表的子集包含 i 。

13次询问，每次询问一个二进制位，所以最多可以有13个二进制位。那么可以选出 C136>1000C_{13}^6>1000 个子集用来分配，也就足够分配了。

给每个下标分配一个13位的id，其中恰有6位是1。预处理，对于每一个二进制位，询问所有id中该位为1的数的或。再对于第 i 个数，它的答案或上它的id中为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
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, Q = 13, cnt, id[N];
ll x[100];
vector<int> vc[100];
void query(int d){
    if(vc[d].empty())return;
    cout << "? " << (int)vc[d].size();
    for(int v:vc[d])cout << " " << v;
    cout << endl;
    cin >> x[d];
}
int main(){
    scanf("%d", &n);
    for (int i = 0; i < (1 << Q) && cnt < n; i++){
        if(__builtin_popcount(i) != Q / 2)continue;
        id[++cnt] = i;
    }
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < Q; j++){
            if (id[i] >> j & 1)vc[j].push_back(i);
        }
    }
    for (int i = 0; i < Q; i++)query(i);
    cout << "!";
    for (int i = 1; i <= n; i++){
        ll ans = 0;
        for (int j = 0; j < Q; j++){
            if ((id[i] >> j & 1) == 0){
                ans |= x[j];
            }
        }
        cout << " " << ans;
    }
    cout << endl;
    return 0;
}