CF1554

B Cobb

题目大意

给定一个长度为 $n$ 的序列 $\{a_1,a_2,\cdots ,a_n\}$ 和 $k$，当 $1\leqslant i < j \leqslant n$ 时，求最大的 $i\cdot j-k\cdot(a_i|a_j)$ 的值，也就是求

$$max\{i\cdot j - k\cdot (a_i|a_j):1\leqslant i < j \leqslant n\} \\$$

取值范围：$2 \leqslant n\leqslant 10^5, 1\leqslant k \leqslant min(n, 100)$

思考

注意到 $k\leqslant 100$ 这个奇葩取值范围，就肯定猜到和暴力枚举 $k$ 这个范围有关，比赛时往这方向想了，但没有从最值条件上考虑导致没有弄出来。

令 $f(i,j)=i\cdot j-k\cdot(a_i|a_j)$

观察式子 $i\cdot j-k\cdot(a_i|a_j)$

第一项 $max\{i\cdot j\}=(n-1)\cdot n$，第二项 $max\{k\cdot(a_i|a_j)\}=k\cdot 2n$，发现第一项大小远超第二项

所以我们直接考虑最大的第一项，也就是 $i=n-1,j=n$ 时

$f(n-1,n)\geqslant (n-1)\cdot n-k\cdot 2n=n^2-2kn-n$

考虑当 $j=n$ 时，如果 $\exists i,f(i,n) > f(n-1,n)$，考虑 $i$ 的最大取值范围

即 $max\{f(i,n)\} > min\{f(n-1,n)\}$

有 $i\cdot n > n^2-2kn-n \Rightarrow i > n-2k-1 \Rightarrow i \geqslant n-2k$

故 $i\in[n-2k,n]$，也就是说 $i$ 的取值只有 $2k$ 种，那么我们只需要在区间 $[n-2k,n]$ 中枚举 $i,j$ 即可，复杂度 $O(k^2)$

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n, k;
		cin >> n >> k;
		vi a(n);
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		int ans = -9e18;
		for (int i = max(0ll, n-2*k); i < n; i++) {
			for (int j = i+1; j < n; j++) {
				ans = max(ans, (i+1) * (j+1) - (a[i] | a[j]) * k);
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

C Mikasa

题目大意

给定 $n,m(0\leqslant n, m \leqslant 10^9)$ 求出在集合 $S=\{n\oplus 0, n\oplus 1, \cdots, n\oplus m\}$ 中没有出现过的最小的非负整数，数学化表达就是求

$$min\{k\in \mathbb{N} : k \notin S\}$$

思路

考试是死磕了一个半小时还没弄出来，结束后又弄了半个小时才做出来，主要原因是想直接分类讨论出来，但其实可以通过转换问题从而简化问题，所以并没有必要去讨论

先分析问题

若 $k\in S$，则 $\exists x \leqslant m$，使 $n\oplus x=k \iff n\oplus k=x$，于是有 $0\leqslant n\oplus k\leqslant m$，所以问题转换为求最小的 $k$ 使得 $n\oplus k\geqslant m+1$，也就是求

$$min\{k\in \mathbb{N}:n\oplus k\geqslant m+1\}$$

注意这里取 $\geqslant$ 而不是 $>$，因为我们容易修改 $k$ 使得式子两边值相等，所以取等时可以减少讨论。

这里问题就变得很简单了。。。可以自己思考下

我们从二进制上来分析问题，令 $M=m+1$, $n_i, M_i, k_i$ 表示 $n, M, k$ 二进制下的第 $i$ 位值

下面从高位到低位讨论 $n, M$ 在第 $i$ 位不同取值时，$k$ 对应的取值:

1. $n_i=M_i\Rightarrow k_i=0$
2. $n_i=0\ and\ M_i=1\Rightarrow k_i=1$
3. $n_i=1\ and\ M_i=0\Rightarrow \forall j\leqslant i,k_j=0$，不用再对低位进行讨论了

抓住要求 $k$ 尽可能小这个性质，原因不难解释，可以自己手玩一下。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n, m;
		cin >> n >> m;
		m++;
		int ans = 0;
		for (int i = 31; i >= 0; i--) {
			if ((n >> i & 1) == 0 && (m >> i & 1) == 1) {
				ans |= 1ll << i;
			} else if ((n >> i & 1) == 1 && (m >> i & 1) == 0) {
				break;
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

D Diane

题目大意

要求构造一个长度为 $n$ 的字符串S，满足他的任意子串s在原串S中出现次数为奇数

思路

考验构造能力

先手玩一下aaaaaa的每个子串出现次数：a=6,aa=5,aaa=4,aaaa=3,aaaaa=2,aaaaaa=1，容易发现奇偶性是一偶一奇

再玩一下aaaaa：a=5,aa=4,aaa=3,aaaa=2,aaaaa=1，发现奇偶性是一奇一偶

我们又知道：奇+偶=奇

那么如果我们把他们联合起来是什么效果，中间有一个其他字符截断

aaaaaabaaaaa：a=11,aa=9,aaa=7,aaaa=5,aaaaa=3,aaaaaa=1，这样不就满足条件了？

令aa...a串长度为 $l$，如果令 $l_1=\left\lfloor\frac{n}{2}\right\rfloor, l_2=l_1-1$

那么构造为 $\begin{matrix}\underbrace{aa\ldots a}b\underbrace{aa\ldots a}\\l_1\qquad\ \ \ l_2\end{matrix}$ (n为偶) 或 $\begin{matrix}\underbrace{aa\ldots a}bc\underbrace{aa\ldots a}\\l_1\qquad\quad\ l_2\end{matrix}$ (n为奇)

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		if (n == 1) {
			putchar('a');
			putchar('\n');
			continue;
		}
		int k = n / 2;
		for (int i = 0; i < k; i++) {
			putchar('a');
		}
		for (int i = 0; i < n - k - (k-1); i++) {
			putchar('a'+i+1);
		}
		for (int i = 0; i < k-1; i++) {
			putchar('a');
		}
		putchar('\n');
	}
	return 0;
}