第一次AK耶，虽然AK了还是1000多名就是咯……
因为是unrate的场，所以理所当然是倒过来做。不过题解还是正着写。
https://codeforces.com/contest/1352
A - Sum of Round Numbers
模拟一下。
B - Same Parity Summands
题意：把一种正整数 (n) ，分为恰好 (k) 个奇偶性相同的非负整数。
题解：奇偶性相同，又要非负，所以理所当然是尽可能拆1或者尽可能拆2分别试一下。
*C - K-th Not Divisible by n
题意：找出第 (k) 个不被 (n) 整除的数。
题解：前 (k-1) 个数占有 (t=lfloorfrac{k-1}{n-1} floor) 个“组”，每组就是 (1,2,3,...,n-1) 这些不被 (n) 整除的数，那么剩下的 (k-t) 个数肯定就从 (t*n) 开始数。
D - Alice, Bob and Candies
模拟一下。
E - Special Elements
排序之后二分，感觉复杂度很勉强。复杂度 (O(n^2logn)) 。
下面的代码里面隐藏了一个越界访问（top为0的时候仍然访问top），不过好在初始值为0而题目的值都是正整数。
int a[8005];
int sum[8005];
int vis[8005];
int res[8005];
void TestCase() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
sum[i] = sum[i - 1] + a[i];
vis[i] = 0;
}
for(int i = 1; i <= n; ++i) {
int top = 0;
for(int j = 1; j <= i - 1; ++j)
res[++top] = sum[i] - sum[j - 1];
sort(res + 1, res + 1 + top);
for(int j = 1; j <= n; ++j) {
if(vis[j] == 0) {
if(a[j] > res[top])
continue;
if(*lower_bound(res + 1, res + 1 + top, a[j]) == a[j])
vis[j] = 1;
}
}
}
int cnt = 0;
for(int i = 1; i <= n; ++i)
cnt += vis[i];
printf("%d
", cnt);
return;
}
其实查找一个数是否存在不需要保证有序性。值域太小了所以直接类似桶排序一样搞就好了。复杂度 (O(n^2)) 快到离谱。
int a[8005];
bool vis[8005];
void TestCase() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
vis[i] = 0;
}
int sum = 0;
for(int i = 1; i <= n; ++i) {
sum += a[i];
int tmp = sum;
for(int j = 1; j <= i - 1; ++j) {
if(1 <= tmp && tmp <= n)
vis[tmp] = 1;
tmp -= a[j];
}
}
int cnt = 0;
for(int i = 1; i <= n; ++i)
cnt += vis[a[i]];
printf("%d
", cnt);
return;
}
*F - Binary String Reconstruction
实话说这个div4还挺有意思的，比div3好玩。
题意：给三个数字 (n_0,n_1,n_2) ，构造一个"01"字符串，使得相邻两位恰好有 (i) 个'1'的恰好有 (n_i) 个。
题解：一开始想错了，还好用的assert直接RE了能够知道是assert错了。一开始认为构造是全'0'或者全'1'，然后两头最多分别加一个相反的字符。
后来一想，直接放"010101"就可以无穷构造出相邻两位恰好有 (1) 个'1'的。所以就是先放全'0'，再放全'1'，中间就夹了有可能存在的一个"01"，然后最后就一直按照与末位相反不断延长。
G - Special Permutation
题意：构造一个 ([1,n]) 的排列，使得临位的差的绝对值至少为2至多为4。
题解：显然太短的答案是不存在的，直接输出非法。
然后看看“临位的差的绝对值至少为2”，容易想到就按奇偶分别搞一下。
比如n=8，先构造为：
1 3 5 7 8 6 4 2
比如n=9，先构造为：
1 3 5 7 9 8 6 4 2
问题出在中间的奇偶分界的位置，发现n=9只需要把第一个偶数和第二个偶数换一下，但是n=8是要把最后一个奇数和倒数第二个奇数换一下。
容易知道这就是正确的构造。