B - Reverse Game（博弈论）

这道题的关键是转化为把1全部放到右边游戏就结束了

所以每次操作可以使得1左1个或者2个

那么就可以转化为取石子的模型，n个石子，每次取1个或2个

判断是不是3的倍数就行了

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;int main()
{string s;cin >> s;int len = s.size();long long sum = 0, cnt = 0;rep(i, 0, len)if(s[i] == '1'){sum += len - i - 1;cnt++;}sum -= cnt * (cnt - 1) / 2;if((sum % 3) == 0) puts("Bob");else puts("Alice");return 0;
}

M - Mistake（贪心）

是一个很巧妙的贪心

把每个数分配到当前能分配到的最小的编号里去

依照这种方式构造的答案是最完善的，又保证有解

所以输入的图白给了

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 5e5 + 10;
int a[N], n, m, k;int main()
{scanf("%d%d%d", &n, &k, &m);while(m--){int a, b;scanf("%d%d", &a, &b);}_for(i, 1, n * k){int x; scanf("%d", &x);printf("%d ", ++a[x]);}return 0;
}

Shuffle Cards（stl rope）

这道题就是用平衡树做的

但是有一个骚方法，用stl容器 rope

其内部是平衡树实现的

这个容器是用来处理字符串的，可以在logn内实现区间插入，区间删除，区间替换

数组查询O（1）删除O（n）

链表查询O（n）删除O（1）

而这个容器，也就是平衡树，是查询O（logn）删除O（logn）

首先要加头文件注意万能头不包括，还要加一个using namespace

#include <ext/rope>
using namespace __gnu_cxx;

操作如下

参考[rope大法好] STL里面的可持久化平衡树--rope - viv - 博客园

rope<int> r, x;
r.push_back(x)     // 在末尾添加x
r.insert(pos,x)    // 在pos插入x 区间插入
r.erase(pos,x)     // 从pos开始删除x个 区间删除
r.replace(pos,x)   // 从pos开始换成x 区间替换
r.substr(pos,x)    // 提取pos开始x个

此题AC代码，直接提取区间相加就好了

#include <bits/stdc++.h>
#include <ext/rope>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
using namespace __gnu_cxx;int main()
{rope<int> r;int n, m;scanf("%d%d", &n, &m);_for(i, 1, n) r.push_back(i);while(m--){int a, b;scanf("%d%d", &a, &b);r = r.substr(a - 1, b) + r.substr(0, a - 1) + r.substr(a + b - 1, n - a - b + 1);}rep(i, 0, n) printf("%d ", r[i]); puts("");return 0;
}

E Sort String(哈希 + 输出优化)

其实就是迅速处理出这个字符串之前有没有出现过

套路是哈希配合unordered_map

我交了一发T了

这个输出巨大，所以我就加了一个输出优化

输出优化其实很简单，就是用putchar

把数拆成一位一位的然后用putchar输出

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef unsigned long long ull;
const int N = 2e6 + 10;
const int base = 131;
unordered_map<ull, int> mp;
vector<int> ans[N];
ull Hash[N], p[N];
char s[N];
int n;ull get_hash(int l, int r)
{return Hash[r] - Hash[l - 1] * p[r - l + 1]; 
}int w[60];
void write(int x)
{int t = 0;while(x){w[++t] = x % 10;x /= 10;}if(!t) putchar('0');for(int i = t; i >= 1; i--) putchar(w[i] + '0');}int main()
{scanf("%s", s + 1);n = strlen(s + 1);_for(i, 1, n) s[n + i] = s[i];p[0] = 1;     //不要漏这句_for(i, 1, 2 * n) {p[i] = p[i - 1] * base;Hash[i] = Hash[i - 1] * base + s[i];}int cnt = 0;_for(i, 1, n){ull cur = get_hash(i, i + n - 1);if(!mp[cur]) mp[cur] = ++cnt;ans[mp[cur]].push_back(i - 1);}write(cnt); puts("");_for(i, 1, cnt){write(ans[i].size()); putchar(' ');for(auto x: ans[i]) write(x), putchar(' ');puts("");}return 0;
}

E Sort String(KMP循环节)

这题还有一种做法

如果满足相等，一定是是有循环节

证明比较感性用纸笔画一画

所以用kmp判断循环节就可以了

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e6 + 10;
int Next[N], n, num, cnt;
char s[N];void get_next()
{Next[0] = -1;int i = 0, j = -1;while(i < n){if(j == -1 || s[i] == s[j]){i++; j++;Next[i] = j;}else j = Next[j];}
}int main()
{scanf("%s", s);n = strlen(s);get_next();if(n % (n - Next[n])) num = 1;else num = n / (n - Next[n]);cnt = n / num;printf("%d\n", cnt);_for(i, 1, cnt){printf("%d ", num);_for(j, 0, num - 1) printf("%d ", i - 1 + cnt * j);puts("");}return 0;
}

J.farm(哈希 + 随机化)

这道题看到一个很骚的做法

就是如果没有枯萎，那么把施肥的种类加起来模花的种类等于0

但是数字很小的时候就不行比如1 + 2 = 3 和3

那么我们可以用哈希，映射到一个很大的值，就很难出现这种情况

为了大且随机，我们可以用随机化，也就是乘以一个rand

之前比赛有一道构造题，数据范围很小，可以在很短的时间内验证，因此可以随机化构造答案

随机化是个方法