A - Alexey and Train
模拟，没啥需要讲的，按照题目写就行了。
#include <bits/stdc++.h> #define Mid (l + r << 1) #define lson (rt << 1) #define rson (rt << 1 | 1) using namespace std; int read() { char c; int num, f = 1; while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0'; while(c = getchar(), isdigit(c)) num = num * 10 + c - '0'; return f * num; } const int N = 309; int n, a[N], b[N], tim[N]; void work() { n = read(); for(int i = 1; i <= n; i++) { a[i] = read(); b[i] = read(); } for(int i = 1; i <= n; i++) tim[i] = read(); int now = a[1] + tim[1]; for(int i = 2; i <= n; i++) { if(now + (b[i - 1] - a[i - 1] + 1) / 2 >= b[i - 1]) { now = now + (b[i - 1] - a[i - 1] + 1) / 2; } else now = b[i - 1]; now += a[i] - b[i - 1] + tim[i]; } printf("%d ", now); } signed main() { int Case = read(); while(Case--) work(); return 0; }
B - Napoleon Cake
题意：
有一个n层的楼，对于每个(i∈[1,n])，有一个(a_i)表示从i往下数(a_i)个刷上了颜色，问每层楼有没有颜色。
题解：
当然可以用线段树，但是有(O(n))的差分做法，而且代码量少。
因为不是在线询问，对于每个(a_i)，在差分数组上打上标记就可以实现区间修改了，最后询问的时候求一下前缀和就行。
#include <bits/stdc++.h> #define Mid (l + r << 1) #define lson (rt << 1) #define rson (rt << 1 | 1) using namespace std; int read() { char c; int num, f = 1; while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0'; while(c = getchar(), isdigit(c)) num = num * 10 + c - '0'; return f * num; } const int N = 2e5 + 1009; int n, a[N], f[N]; void work() { n = read(); for(int i = 0; i <= n; i++) f[i] = 0; for(int i = 1; i <= n; i++) { a[i] = read(); f[(i - a[i] + 1) > 0 ? (i - a[i] + 1) : 1] += 1; f[i + 1] -= 1; } for(int i = 1; i <= n; i++) { f[i] += f[i - 1]; if(f[i] > 0) printf("1 "); else printf("0 "); } printf(" "); } signed main() { int Case = read(); while(Case--) work(); return 0; }
C - Going Home
题意：
给定一列数(f)，要求找出四个不一样的(a,b,c,d)使得(f_a + f_b=f_c + f_d)，如果没有输出(no)。
(f_ile 2.5 imes 10^6)
题解：
发现(f_a + f_b)是不超过(5 imes 10^6)的，我们可以开个桶存下所有的(f_a + f_b)，只要一个桶里面的数量大于4，那么一定有解。
证明：
有四对数，则情况有以下两种：
(A):((x, y),(x, z), (z, y), (任意))这样子最后一对一定可以跟前面配对。
(B):((x, y),(x, z), (x, p), (x, q))虽然这四个不能匹配，但是发现都(f_x+f_i)都等于一个数(t)，也就是说明(f_y=f_z=f_p=f_q)这样就可以取(f_y+f_z=f_p + f_q)
于是，最多枚举(2 imes 10^7)个数，一定存在答案。
暴力枚举就行了。
不过我考场上的做法是直接暴力，有可能被卡，谨慎参考以下代码。
#include <bits/stdc++.h> #define Mid (l + r << 1) #define lson (rt << 1) #define rson (rt << 1 | 1) using namespace std; int read() { char c; int num, f = 1; while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0'; while(c = getchar(), isdigit(c)) num = num * 10 + c - '0'; return f * num; } const int N = 5e6 + 1009; int n, a[N]; struct node { int x, y; }; vector<node> f[N]; signed main() { n = read(); for(int i = 1; i <= n; i++) a[i] = read(); for(int l = 1; l <= n; l++) { for(int i = 1; i + l <= n; i++) { int p = a[i] + a[i + l]; f[p].push_back((node){i, i + l}); for(int k = 0; k < f[p].size(); k++) { if(f[p][k].x == i || f[p][k].y == i) continue; if(f[p][k].x == i + l || f[p][k].y == i + l) continue; printf("YES "); printf("%d %d %d %d ", f[p][k].x, f[p][k].y, i, i + l); return 0; } } } printf("NO "); return 0; }
D - Two chandeliers
题意：
两队人同时循环报数，每次报数的人假如颜色不一样就计一次贡献，问第(k)次贡献产生的时候报到了几。
两队个队伍内部没有重复颜色。
题解：
看官方Tutorial给的是CRT，但是我没有用CRT也水过去了。
考场上没看见颜色各不同结果挂了，要注意审题啊
我们先交换(n,m)使得(mle n)，这样之后我们可以考虑假如(b)数组第(1)个和(a)数组第(i)个同时开始报数，(b)报回到(1)产生几个贡献。
这是可以(O(n))处理出来的，方法如下。
我们把(b)数组里面的数与下标进行映射，这样可以把(b)数组的颜色换成(0, 1, 2, ..., m - 1)，然后考虑(a)数组内部的贡献。
(a)数组的第(i)位仅仅不会对从(i - a[i])开始的匹配产生贡献，这样我们就可以统计出从第(i)个位置开始匹配，不能产生贡献的位置个数，(m-cnt[i])就是产生的贡献个数。
这样结束后，我们一步的跨度就是(m)了，但是还是会超时，因为可能(k)很大，而(m)很小。
这时候我们考虑利用最小公倍数去优化枚举。
两列数匹配的循环节是最小公倍数，我们只需要计算最小公倍数匹配的贡献，然后剩下的部分暴力匹配就行了。
那么最小公倍数的匹配时间复杂度是多少呢？
最小公倍数最坏情况下为(n imes m)，每次跨越(m)，最多循环(n)步就可以求出来了。
接下来的就暴力了。
#include <bits/stdc++.h> #define int long long #define Mid (l + r << 1) #define lson (rt << 1) #define rson (rt << 1 | 1) using namespace std; int read() { char c; int num, f = 1; while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0'; while(c = getchar(), isdigit(c)) num = num * 10 + c - '0'; return f * num; } const int N = 5e5 + 1009; int n, m, k, a[N], b[N], f[N * 2]; int cnt[N], lcm; int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);} int cal(int k) { int q = 0, now = 1, p = 1, tot = 0; while(q < k) { if(q + cnt[now] >= k)break; q += cnt[now]; now = (now - 1 + m) % n + 1; tot += m; } while(q < k) { q += (a[now] != b[p]); now = now % n + 1; p = p % m + 1; tot++; } return tot; } int cal1(int k) { int tt = k / m, q = 0; for(int i = 1, now = 1; i <= tt; i++) { q += cnt[now]; now = (now - 1 + m) % n + 1; } return q; } signed main() { n = read(); m = read(); k = read(); if(n <= m) { swap(n, m); for(int i = 1; i <= m; i++) b[i] = read(); for(int i = 1; i <= n; i++) a[i] = read(); } else { for(int i = 1; i <= n; i++) a[i] = read(); for(int i = 1; i <= m; i++) b[i] = read(); } memset(f, -1, sizeof(f)); for(int i = 1; i <= m; i++) f[b[i]] = i - 1; for(int i = 1; i <= n; i++) { if(f[a[i]] != -1) { cnt[(i - f[a[i]] - 1 + n) % n + 1]++; } } for(int i = 1; i <= n; i++) cnt[i] = m - cnt[i]; int p = n / gcd(n, m) * m; int tt = cal1(p), ans = 0; ans += (k - 1) / tt * p; k = (k - 1) % tt + 1; ans += cal(k); printf("%lld ", ans); return 0; } /* cnt[i]表示从i开始匹配，能有多少个匹配上 */