Codeforces Round #631 (Div. 2) 部分题解

$A .$
题意： 从 $1$ 开始可以走到的最远的数，有 $x$ 的补救机会，即某个数不存在可以用补上。

代码：

#include<bits/stdc++.h>
using namespace std;

int T, n, x;
int q[210];

int main()
{
	scanf("%d", &T);
	while(T--) {
		memset(q, 0, sizeof q);
		scanf("%d%d", &n, &x);
		for(int i = 1; i <= n; i++) {
			int t; scanf("%d", &t);
			q[t] = 1;
		}
		
		for(int i = 1; i < 210; i++) {
			if(!q[i]){
				if(x) q[i] = 1, x--;
				else {
					printf("%d\n", i - 1);
					break;
				}
			}
		}
	}
}

$B .$
题意： 给定一个序列，寻找所有的划分点使得划分后的两部分均为全排列
题解： 先枚举左边所有的合法状态（仅左边为全排列），再枚举右边的合法状态，若两个合法状态正好可以组成给定序列，则是答案。

题解：

#include<bits/stdc++.h>
using namespace std;
#define mem(a, n) memset(a, 0, (n + 1) * sizeof(int))
const int N = 2e5 + 10;
int q[N];
int n, T, now;
int l[N];
int h[N];

int main()
{
	scanf("%d", &T);
	while(T--) {
		vector<pair<int, int> > ans; 
		scanf("%d", &n);
		for(int i = 1; i <= n; i++) scanf("%d", &q[i]);
		mem(l, n);
		
		mem(h, n); now = 0;
		for(int i = 1; i <= n; i++) {
			h[q[i]]++;
			if(h[q[i]] > 1) break;
			while(h[now + 1]) now++;
			if(now == i) l[now] = 1;
		}
		
		mem(h, n); now = 0;
		for(int i = n; i >= 1; i--) {
			h[q[i]]++;
			if(h[q[i]] > 1) break;
			while(h[now + 1]) now++;
			if(now == n - i + 1) {
				if(l[n - now]) ans.push_back({n - now, now});
			}
		}
		
		int len = ans.size();
		printf("%d\n", len);
		for(int i = 0; i < len; i++)
			printf("%d %d\n", ans[i].first, ans[i].second);
	}
	
	return 0;
}

$C .$
题意： 给定一个长度为 $n$ 的格子， $m$ 次操作每次可以染色 $l_{i}$ 个格子，每次染色的起点可以是 $[1, n - l_{i} + 1]$ 中任意移动，问使得 $m$ 次操作后每个颜色都存在的，所有格子都被染色了的，每次操作染色起点位置。
题解： 开始先贪心将第 $k$ 操作的起点设为 $k$ 。对于第 $m$ 次操作，如果其最后染色终点未在第 $n$ 个格子，则将其起点向右移至覆盖第 $n$ 个格子，然后对于第 $m - 1$ 次操作，如果其染色终点未和第 $m$ 次操作的起点衔接，依然将其向右移至两者衔接，其余类似~。
当所有操作染色总数小于 $n$ ，那么无法染完所有格子。
当第 $k$ 次操作格子位置超过 $n$ ，那么不符合起点在 $[1, n - l_{k} + 1]$ 的条件。

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int M = 100010;
int l[M];
int res[M];
int n, m;

int main()
{
	scanf("%d%d", &n, &m);
	
	ll sum = 0;
	for(int i = 1; i <= m; i++) {
		scanf("%d", &l[i]);
		sum += l[i];
	}
	
	if(sum < n) return 0 * printf("-1\n");
	for(int i = 1; i <= m; i++) {
		res[i] = i;
		if(i + l[i] - 1 > n) return 0 * printf("-1\n");
	}
	int last = n;
	for(int i = m; i >= 1; i--) {
		if(i + l[i] - 1 < last) {
			res[i] = last - l[i] + 1;
			last = res[i] - 1;
		} 
		else break;
	}
	
	for(int i = 1; i <= m; i++) printf("%d%c", res[i], " \n"[i == m]);
	return 0;
}

$D .$
题意： 给定严格递增的序列 $a$ ， $b_{i} = b_{i - 1} \oplus a_{i}$ ，问使得 $b$ 递增的 $a$ 序列有多少。
题解： 由于是严格递增，故每个最高位只能出现一次。
枚举每个最高位出现的次数：
$1 : 1$
$2 : 2$
$3 : 4$
$4 : 8$
$\dots$
$k : d - 2^{k} + 1$
$f [i] [j]$ 表示前 $i$ 组中选择了 $j$ 组数的方案总数。
状态转移为 $f [i] [j] = f [i - 1] [j - 1] \times c n t [i] + f [i - 1] [j]$

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 32;
int T, d;
ll mod, cnt[N], f[N];
int main()
{
	scanf("%d", &T);
	while(T--) {
		memset(cnt, 0, sizeof cnt);
		memset(f, 0, sizeof f);
		scanf("%d%lld", &d, &mod);
		int t = 1, g = 0;
		while(true) {
			if(d - t > 0) {
				cnt[++g] = t;
				d -= t;
				t <<= 1;
			}
			else break;
		}
		cnt[++g] = d;
		
		f[0] = 1;
		for(int i = 1; i <= g; i++)
			for(int j = i; j >= 1; j--)
				f[j] = (f[j - 1] * cnt[i] + f[j]) % mod;
		ll res = 0;
		for(int i = 1; i <= g; i++) res = (res + f[i]) % mod;
		printf("%lld\n", res);
	}
	
	return 0;
}