A
只需输出任意一个不小于 $x$ 的数即可。
#include<cstdio>
using namespace std;
int T;
inline void solve() {
int x;
scanf("%d", &x);
printf("%d\n", x);
}
int main() {
scanf("%d", &T);
while(T--) solve();
return 0;
}
B
算一下，假设只有 $a_x$ 不变成相反数，那么和 $s=a_x\times2-\sum a_i$，后面一项是固定的，要让 $s$ 最大只需让 $a_x$ 最大，所以选最大的那个即可。
#include<cstdio>
#include<algorithm>
using namespace std;
int T, a1, a2, a3, a4, a5, a6, a7;
inline void solve() {
scanf("%d%d%d%d%d%d%d", &a1, &a2, &a3, &a4, &a5, &a6, &a7);
printf("%d\n", max({a1, a2, a3, a4, a5, a6, a7})*2-a1-a2-a3-a4-a5-a6-a7);
}
int main() {
scanf("%d", &T);
while(T--) solve();
return 0;
}
C
其实看样例就能发现了。
也可以这么贪心的考虑：我们从大到小考虑每个数，尽可能让大的数成为中位数。首先最大的 $3n$ 一定没法是中位数，那么我们考虑 $3n-1$ 这个数，要成为中位数就得和 $3n$ 在同一组。接着，$3n-2$ 这个数又一定没办法是中位数了，此时最优的做法就是单开一组，这样可以让 $3n-3$ 成为中位数。这样一直下去，发现最大的 $2n$ 个数刚好两两分成了 $n$ 组，所有中位数已经确定了，那剩下的 $n$ 个数随便分就好。
#include<cstdio>
using namespace std;
int T, n;
inline void solve() {
scanf("%d", &n);
for(register int i=1; i<=n; ++i) {
printf("%d %d %d ", i, n+i*2-1, n+i*2);
}
puts("");
}
int main() {
scanf("%d", &T);
while(T--) solve();
return 0;
}
D
打开这一题的想法，既然要让 gcd 各不相同，那我们考虑先定下 gcd 再去生成序列。
假设前两个 gcd 是 $p,q$。
要满足 $a_1,a_2$ 的 gcd 是 $p$，要满足 $a_1,a_2$ 都是 $p$ 的倍数且 $\frac{a_1}p,\frac{a_2}p$ 互质，同时还要满足 $a_2,a_3$ 是 $q$ 的倍数，$\frac{a_2}q,\frac{a_3}q$ 互质。
注意到，$a_2$ 同时是 $p,q$ 的倍数。容易想到，只需要 $p,q$ 互质，让 $a_2=pq$，这是最简单的情况。
我们不妨找来 $n-1$ 个不同的质数 $p_1,p_2,\cdots,p_{n-1}$，并令 $p_0=p_n=1$，然后构造 $a_i=p_{i-1}p_i$，就满足条件了：$\gcd(a_i,a_{i+1})=\gcd(p_{i-1}p_i,p_ip_{i+1})=p_i$。
注意，要准备 1e4 个质数，而 1e5 以内的质数只有九千多个，所以要多跑一些，但多跑的一些要注意质数桶要开够。因为这个挂了一发。。。
#include<cstdio>
using namespace std;
int T, n, prime[100005], vis[200005], cnt;
inline void solve() {
scanf("%d", &n);
printf("1 2 ");
for(int i=1; i<=n-2; ++i) {
printf("%lld ", 1ll*prime[i]*prime[i+1]);
}
puts("");
}
int main() {
for(int i=2; i<=150000; ++i) {
if(!vis[i]) prime[++cnt] = i;
for(int j=1; j<=cnt&&i*prime[j]<=150000; ++j) {
vis[i*prime[j]] = 1;
if(i%prime[j] == 0) break;
}
}
scanf("%d", &T);
while(T--) solve();
return 0;
}
E
其实看到异或就能直接注意到，做两轮会抵消掉。看不出来的话，手玩两轮也够找到规律。
最后剩下的哪个数，一定就是倒数两个数的异或，所以直接 $O(n^2)$ 扫一遍取最大值就行。
#include<cstdio>
#include<algorithm>
#define N 3110
using namespace std;
int T, n, a[N];
inline void solve() {
int ans = 0;
scanf("%d", &n);
for(int i=1; i<=n; ++i) {
scanf("%d", &a[i]);
for(int j=1; j<i; ++j)
ans = max(ans, a[i]^a[j]);
}
printf("%d\n", ans);
}
int main() {
scanf("%d", &T);
while(T--) solve();
return 0;
}
F
这里称子树大小为奇数/偶数的节点为奇节点/偶节点。先研究一下 $x,y$ 不合法的情况。
对一棵树做研究，我们发现，如果一个节点的子树大小 $siz_u=1+\sum siz_v$ 是偶数，说明 $\sum siz_v$ 是奇数，说明他有奇数个奇节点儿子。
也就是说，每个偶节点，都对应至少一个奇节点儿子。
所以一定满足 $y\ge x$。除此之外，我们还可以直接通过 $x+y$ 的奇偶性判断根节点的奇偶性，如果根节点是偶节点但 $x=0$ 则也不合法。
剩余的情况，我们发现，按照我们证明的那样的方式去构造即可：首先扣去根节点本身，然后对每个偶节点，给他挂上一个奇节点儿子之后挂到根节点下，最后剩下的奇节点直接挂在根节点下即可。
#include<cstdio>
using namespace std;
int T, x, y;
inline void solve() {
scanf("%d%d", &x, &y);
if((x+y)%2) --y;
else --x;
if(x<0 || y<0) puts("NO");
else if(x > y) puts("NO");
else {
puts("YES");
int cnt=1;
while(x--) printf("%d %d\n%d %d\n", 1, cnt+1, cnt+1, cnt+2), cnt+=2, y--;
while(y--) printf("%d %d\n", 1, ++cnt);
}
}
int main() {
scanf("%d", &T);
while(T--) solve();
return 0;
}
G
仔细分析题目条件会发现，第 $i$ 个人在 $b_i$ 时坐下，必然是因为以下其中一种情况：
- 在 $b_i-1$ 前他就有邻居已经坐下，而 $b_i-1$ 时刚好坐下的人数超过或等于 $a_i$
- $a_i$ 在 $b_i-1$ 前就已经满足，但第 $b_i-1$ 时他的邻居才坐下
- 在 $b_i-1$ 时，他邻居坐下，同时满足了 $a_i$
由于在 $b_i-1$ 时已经坐下的人数是已知的，所以可以发现每个人属于哪种情况，只对他的邻居是否坐下有要求。如果 $b_i-1$ 前已经有 $x$ 个人坐下，第 $b_i-1$ 时坐下了 $d$ 个人：
- 第一种情况，要求有邻居在 $b_i-1$ 前就已经坐下，且 $a_i$ 的范围是 $[x+1,x+d]$
- 第二种情况，要求刚好在 $b_i-1$ 时才有邻居坐下，且 $a_i$ 的范围是 $[1,x]$
- 第三种情况，要求刚好在 $b_i-1$ 时才有邻居坐下，且 $a_i$ 的范围是 $[x+1,x+d]$
第二种和第三种情况其实可以合并一下，变成两种可能性：
- 如果 $b_i-1$ 时才有邻居坐下，即 $\min(b_{i-1},b_{i+1})=b_i-1$，则 $a_i\in[1,x+d]$
- 否则 $a_i\in[x+1,x+d]$
可以发现，每个人的 $a_i$ 的可能性，既不会受到其他人的 $a_i$ 的影响（因为他们什么时候坐下是固定了的），也不会影响其他人，所以直接把所有人的 $a_i$ 的情况数量乘起来就好了。
为了便于计算每一轮的人数变化，我们可以按坐下时间排个序。可以用桶排，也可以直接 sort 然后用双指针同时处理同一个时间坐下的人。不要忘记题目要求取模。
#include<cstdio>
#include<algorithm>
#define N 200005
using namespace std;
const int p = 676767677;
int T, n, m, tm[N], a[N];
long long ans;
inline int getNei(int x) {
int res = tm[x] + 1;
if(x != 1) res = min(res, tm[x-1]);
if(x != n) res = min(res, tm[x+1]);
return res;
}
inline void solve() {
scanf("%d%d", &n, &m);
ans = 1ll;
for(int i=1; i<=n; ++i) {
scanf("%d", &tm[i]);
a[i] = i;
}
sort(a+1, a+1+n, [&](int x, int y) {
return tm[x] < tm[y];
});
for(int i=1, j=1, lst=0; i<=n; lst=j-i+1, i=j=j+1) {
while(j<n && tm[a[j+1]]==tm[a[i]]) ++j;
if(!tm[a[i]]) continue;
for(int k=i; k<=j; ++k) {
int nei = getNei(a[k]);
if(nei >= tm[a[k]]) {
puts("0");
return;
}
if(nei == tm[a[k]]-1) ans *= i-1;
else ans *= lst;
ans %= p;
}
}
printf("%lld\n", ans);
}
int main() {
scanf("%d", &T);
while(T--) solve();
return 0;
}
附录
原题链接
https://codeforces.com/contest/2218
参考文献
版权信息
本文原载于reincarnatey.net，遵循CC BY-NC-SA 4.0协议，复制请保留原文出处。