找个下午打了场CF，结果被某uranus吊打......一千多名，过弱。
T1，一眼二分了，后来发现题解是O(1)的hhh
T2，题意精炼一下就是让你找一个串的循环节个数，直接n²枚举.....
T3，给你一个ab串，你依次考虑每个前缀，选择reverse这个前缀或者不操作。输出方案使得最后的字典序最小。
手玩一下就能发现，一定能构造出最小字典序，所有a都在b前面。
具体操作是每个整段的结尾字符那里翻转。
T4，给你10个1e5的排列，你需要从每个中提取连续的一段，使得这十段相同。求方案数。
考虑KMP(????)，就是我们线性的扫描第一个串，把它分成若干段十个串都相同的段，这样每段都可以拿公式计算。
第一次交的时候一个中间变量没开long long挂了，太SB了。
T5，题意有点长......就是给你n个人，你要把这n个人两两组队(就是n(n-1)/2次)各一次，每次解决两个任务a，b。
每个人解决a，b问题都有个代价。组队时一人解决一道题，会自动选择总代价最小的解决方案，代价累加到两个人身上。
问你这么多次下来每个人的总代价。
把式子min(A + b, B + a)变形一下：min(b - a, B - A) + a + A
然后就比较显然了.....显然可以用前缀和但是我SB的用了树状数组，不过复杂度一样。
贴个考场代码吧。
1 #include2 3 inline void read(int &x) { 4 x = 0; 5 char c = getchar(); 6 while(c < '0' || c > '9') { 7 c = getchar(); 8 } 9 while(c >= '0' && c <= '9') {10 x = (x << 3) + (x << 1) + c - 48;11 c = getchar();12 }13 return;14 }15 16 typedef long long LL;17 const int N = 300010;18 19 LL xi[N], yi[N], dt[N], X[N], ans[N];20 int n, pos[N]; 21 22 struct TA {23 LL ta[N];24 inline void add(int i, LL v) {25 for(; i <= n; i += i & (-i)) {26 ta[i] += v;27 }28 return;29 }30 inline LL getsum(int i) {31 LL ans = 0;32 for(; i > 0; i -= i & (-i)) {33 ans += ta[i];34 }35 return ans;36 }37 inline LL ask(int l, int r) {38 if(r < l) {39 return 0;40 }41 if(l <= 1) { 42 return getsum(r);43 }44 return getsum(r) - getsum(l - 1);45 }46 }cnt, sum;47 48 int main() {49 50 int m;51 scanf("%d%d", &n, &m);52 LL tot = 0;53 for(int i = 1; i <= n; i++) {54 scanf("%lld%lld", &xi[i], &yi[i]);55 dt[i] = yi[i] - xi[i];56 X[i] = dt[i];57 tot += xi[i];58 }59 60 std::sort(X + 1, X + n + 1);61 int xx = std::unique(X + 1, X + n + 1) - X - 1;62 63 64 for(int i = 1; i <= n; i++) {65 int p = std::lower_bound(X + 1, X + xx + 1, dt[i]) - X;66 pos[i] = p;67 cnt.add(p, 1);68 sum.add(p, dt[i]);69 }70 71 for(int i = 1; i <= n; i++) {72 int p = pos[i];73 ans[i] += sum.ask(1, p) - dt[i];74 ans[i] += cnt.ask(p + 1, n) * dt[i];75 ans[i] += tot - xi[i] + xi[i] * (n - 1);76 }77 for(int i = 1, x, y; i <= m; i++) {78 scanf("%d%d", &x, &y);79 ans[x] -= std::min(xi[x] + yi[y], xi[y] + yi[x]);80 ans[y] -= std::min(xi[x] + yi[y], xi[y] + yi[x]);81 }82 83 for(int i = 1; i <= n; i++) {84 printf("%lld ", ans[i]);85 }86 87 return 0;88 }
当时境况比较尴尬，写出来时发现比赛刚结束68s......
第一次交很SB的把long long用%d输出了。
最后1104名......F题听说很有趣，以后来填。
F 题意：给定n个数，从中选出尽量少的数，使得gcd为1。
不存在方案输出-1。n，值域<=300000。
解：正解是：有个结论，如果存在合法解，那么一定有一组合法解的个数不超过7。不会证...
然后设f[i][j]表示选i个数，gcd为j的方案数。
f[i][j] = C(sumj, i) - ∑f[i][j * d]
然后求出一个最小的i使得f[i][1] > 0即可。
1 #include2 #include 3 4 typedef long long LL; 5 const int N = 300010, lm = 300000; 6 const LL mo[] = { 998244353, (LL)(1e9 + 7)}; 7 8 int sum[N], bin[N], n; 9 LL f[10][N], nn[N], invn[N], inv[N], MO;10 11 inline LL C(int n, int i) {12 return nn[n] * invn[i] % MO * invn[n - i] % MO;13 }14 15 inline int cal(int turn) {16 MO = mo[turn];17 for(int i = 2; i <= lm; i++) {18 nn[i] = nn[i - 1] * i % MO;19 inv[i] = (MO - inv[MO % i]) * (MO / i) % MO;20 invn[i] = invn[i - 1] * inv[i] % MO;21 }22 for(int i = 1; i <= 7; i++) {23 for(int j = lm; j >= 1; j--) {24 if(sum[j] < i) {25 continue;26 }27 f[i][j] = C(sum[j], i);28 for(int k = 2; k * j <= lm; k++) {29 f[i][j] = (f[i][j] - f[i][j * k] + MO) % MO;30 }31 //printf("f %d %d = %d \n", i, j, f[i][j]);32 }33 }34 for(int i = 1; i <= 7; i++) {35 if(f[i][1]) {36 return i;37 }38 }39 return -1;40 }41 42 int main() {43 nn[0] = inv[0] = invn[0] = 1;44 nn[1] = inv[1] = invn[1] = 1;45 int n;46 scanf("%d", &n);47 for(int i = 1, x; i <= n; i++) {48 scanf("%d", &x);49 bin[x]++;50 }51 for(int i = 1; i <= lm; i++) {52 for(int j = 1; j * i <= lm; j++) {53 sum[i] += bin[i * j];54 }55 }56 57 int a = cal(0), b = cal(1);58 int ans = std::min(a, b);59 if(ans == -1) {60 printf("%d", std::max(a, b));61 }62 else {63 printf("%d", std::min(a, b));64 }65 return 0;66 }
反演+二分解法：
首先二分答案，然后用反演求:选出k个，gcd为1的方案数。如果大于0就可行。
1 #include2 3 const int N = 300010, MO = 998244353; 4 5 int p[N], top, miu[N], bin[N], fac[N], inv[N], invn[N]; 6 bool vis[N]; 7 8 inline int C(int n, int m) { 9 if(m > n || n < 0 || m < 0) return 0;10 return 1ll * fac[n] * invn[m] % MO * invn[n - m] % MO;11 }12 13 inline void getp(int n) {14 miu[1] = 1;15 for(int i = 2; i <= n; i++) {16 if(!vis[i]) {17 p[++top] = i;18 miu[i] = -1;19 }20 for(int j = 1; j <= top && i * p[j] <= n; j++) {21 vis[i * p[j]] = 1;22 if(i % p[j] == 0) {23 miu[i * p[j]] = 0;24 break;25 }26 miu[i * p[j]] = -miu[i];27 }28 }29 return;30 }31 32 inline int check(int k) {33 int ans = 0;34 for(int i = 1; i < N; i++) {35 (ans += miu[i] * C(bin[i], k)) %= MO;36 ans = (ans + MO) % MO;37 }38 return ans;39 }40 41 int main() {42 getp(N - 1);43 inv[0] = fac[0] = invn[0] = 1;44 inv[1] = fac[1] = invn[1] = 1;45 for(int i = 2; i < N; i++) {46 fac[i] = 1ll * fac[i - 1] * i % MO;47 inv[i] = 1ll * inv[MO % i] * (MO - MO / i) % MO;48 invn[i] = 1ll * invn[i - 1] * inv[i] % MO;49 }50 int n;51 scanf("%d", &n);52 for(int i = 1, x; i <= n; i++) {53 scanf("%d", &x);54 bin[x]++;55 }56 for(int i = 1; i < N; i++) {57 for(int j = i << 1; j < N; j += i) {58 (bin[i] += bin[j]) %= MO;59 }60 }61 62 int l = 1, r = n + 1;63 while(l < r) {64 int mid = (l + r) >> 1;65 if(check(mid)) {66 r = mid;67 }68 else {69 l = mid + 1;70 }71 }72 if(r == n + 1) printf("-1\n");73 else printf("%d\n", r);74 return 0;75 }