A.
因为字符串不可以交叉，其实容易解
把不同字符的可用区域看成一个区间，用类似于链表的方法连接起来
查询的就是查询到的链表数量/4（当然右区间必须属于y）
区间查询用倍增或线段树都可以
//倍增#include#include char s[100005];int m, n, pe, pa, ps, py, dep;int pre[100005], ed[100005];int fa[100005][20];int main() { scanf("%s", s); scanf("%d", &m); n = strlen(s); for (int i = 0; i < n; ++i) { if (s[i] == 'e') { pre[i + 1] = py; pe = i + 1; } if (s[i] == 'a') { pre[i + 1] = pe; pa = i + 1; } if (s[i] == 's') { pre[i + 1] = pa; ps = i + 1; } if (s[i] == 'y') { pre[i + 1] = ps; py = i + 1; } ed[i + 1] = py; } for (int i = 1; i <= n; ++i) fa[i][0] = pre[i]; for (dep = 1; 1 << dep < n; ++dep); for (int i = 1; i < dep; ++i) for (int j = 1; j <= n; ++j) fa[j][i] = fa[fa[j][i - 1]][i - 1]; for (; m--;) { int l, r; scanf("%d%d", &l, &r); int x = ed[r]; int res = 1; for (int i = dep - 1; i >= 0; --i) { if (fa[x][i] >= l) { x = fa[x][i]; res += 1 << i; } } printf("%d\n", res / 4); } return 0;}
B.
给一堆点，要求连最小生成树，注：边的权值是两边点的权值异或和。
对整个点集合的权值建0/1 trie树
可以把一个结点当成对应的点集合
如果此点只有1子树则此结点集合就是下面一层那点的
否则此点对应连接左右两子树对应集合的最小权值边
trie树碰到有左右子树的，对1个子树暴力查询另1子树的元素，得到最小异或和权值o(nlogm)
如果没有想到把2个子树以o(n)的时间合并的方法就老实1个1个合并先
再说可能时间也不够
但是真的没想到有人真的就把2个子树以o(n)的时间合并了
整个合并也不是不可以，不过这样就要搞vector储存每一层的结点可能性（跟我那时想到一块去了。。。只不过我怕复杂度太高不敢下码）
并且如果能找到异或位0的位置就必须置一样
#includeusing namespace std;typedef long long ll;int n, tot;ll ans;int a[4000009][2];int num[4000009];int dp[400009], dd[400009];int dp1[400009], dd1[400009];void add(int x){ int q = 0; ++num[0]; for(int i = 30; ~i; --i) { bool w = x >> i & 1; if(!a[q][w]) { a[q][w] = ++tot; } ++num[q = a[q][w]]; }}void zz(int x, int t){ if(t == -1)return ; int l = a[x][0], r = a[x][1]; if(l && num[l] > 1)zz(l, t - 1); if(r && num[r] > 1)zz(r, t - 1); if(!l || !r)return ; if(num[l] && num[r]) { int q = 1 << t, *q1 = dp, *w1 = dd, *q2 = dp1, *w2 = dd1, num1 = 1, num2; q1[0] = l; w1[0] = r; for(int i = t - 1; ~i; --i) { bool f = 1; for(int j = 0; j < num1; ++j) { if((a[q1[j]][0]&&a[w1[j]][0]&&num[a[q1[j]][0]] && num[a[w1[j]][0]]) || (a[q1[j]][1]&&a[w1[j]][1]&&num[a[q1[j]][1]] && num[a[w1[j]][1]])) { f = 0; break; } } num2 = 0; for(int j = 0; j < num1; ++j) { if(a[q1[j]][0]&&a[w1[j]][f]&&num[a[q1[j]][0]] && num[a[w1[j]][f]]) { q2[num2] = a[q1[j]][0]; w2[num2++] = a[w1[j]][f]; } if(a[q1[j]][1]&&a[w1[j]][1 ^ f]&&num[a[q1[j]][1]] && num[a[w1[j]][1 ^ f]]) { q2[num2] = a[q1[j]][1]; w2[num2++] = a[w1[j]][1 ^ f]; } } swap(q1, q2); swap(w1, w2); swap(num1, num2); if(f)q |= 1 << i; } ans += q; }}int main(){ ans=0; scanf("%d", &n); for(int i = 0; i < n; ++i) { int p; scanf("%d", &p); add(p); } zz(0, 30); printf("%lld\n", ans);}
C.
给m个空环，其中第i个长度为si，把1~sum(s)这些数填上去，要求相邻数互质，并输出具体排布，填不下去则输出"QQ"
还好题目的复杂度较低。。。
不能做到偶数之间至少隔1格，环就不能填，否则肯定能填上环（别问我怎么知道的，我也是靠直觉，n~n+1个奇数肯定能对上n个互质的偶数）
先看m个环能否容下总的偶数个数，不能就是无解。
然后这题是special judge，可以随便组。
我的方法：先把1~sum(s)这些数链按照题目给的环长切成对应环（gcd(n,n+1)==1，所以相邻数肯定互质）
然后看那几个环头尾是否互质，不是则遍历左边的环，找出交换数后两个环继续满足互质链的位置，然后交换。
查找次数可达2000*500*6=6000000，实际第2个环可能交换不了那么多次，第3、4也不用整个环都遍历一次
D.
给多个点，对任意2个点连边（不与点或线相交），谁先画不了谁输，问谁能在最佳策略下赢
其实不管怎么连都是三角剖分，所以不存在什么需要博弈论的东西
求三角剖分后总的边数是否偶数即可
发现一个凸包多加点使其仍为凸包，相当于向外多加2条边；在凸包内部加点，相当于加3条边
然后规律就出来了
E.
一个n*m棋盘，问能走遍棋盘的骑士棋种类数（只有一次向xy两轴走至少1格并不走出棋盘的骑士）
可以知道不能走所有格的骑士有这些情况：
设dx<=dy，n<=m
gcd(dx,dy)!=1 骑士只能走指定的格集合
(dx+dy)%2==0 那些(x+y)%2==1的点走不到
dy>m/2 骑士不能走2个方向，使得一些点走不到
dx+dy>n 中间区域无法到达
老规矩，用莫比乌斯容斥
由于还有奇偶判定，直接算还是有些麻烦
祭出公式：1<=k<=min(m,n) miu(k)*f(floor(m/k),floor(n.k))
其中f(m,n)就是不包括dx dy不互质，除去上述无法走全棋盘的骑士种类数
由于处于gcd(dx,dy)%2==0的格子肯定会被除去，上述公式的k是不算偶数的
f(m,n) o(1)求出，答案因为floor()可以归并某些答案的关系，可以o(sqrt(min(m,n)))
F.
求f(f(n))%20160519，其中f(0)=0 f(1)=1 f(i)=f(i-1)+f(i-2)
fib数列其实有循环节的，当运行到f(k-1)%k==k-1 f(k)==1 那循环节就是k
顺带补下这种数列的循环节知识：
当模数是质数模5余1或4，则这种数是5的二次剩余，则循环节是p-1的因子
当模数是质数模5余2或3，则这种数是5的二次非剩余，则循环节是2p+2的因子
当模数是合数，p=p1^a1*p2^a2*.....
可以想到积性函数，循环节是lcm(p1^(a1-1)*(p1的对应循环节数)*p2^(a2-1)*(p2的对应循环节数)*...)
lcm(...)是里面所有数的最小公倍数
然后快速幂一波AC
H.
题意：只有'A'-'Z'的字符串*s对应hash函数是这样得到的：h=0;for(i=0;i<n;i++)h=((h*p)+s[i])%m，给n,m,p问长度为n的字符串会哈希冲突的对数
用数位dp的思想可以知道，设dp(n,h)是长度n且哈希值为h的字符串个数，则dp(n,h)=for(i=0;i<m;i++)d(n1,i)*d(n-n1,(h-i*p^n1)mod m)
把第1维相同的值组成一个向量，可以发现其实就是多项式乘法
但是不可能真的就n次递推，那样o(nm*logn)超时
但是我们会发现，这个式子可以当成向量卷积
所以拆分dp的方法可以像快速幂一样，储存第1维是2^n的向量就可以，然后结果向量看当前n扫描到的2进制位是1是0决定乘不乘
多项式乘法可以FFT（喂精度被你吃了？）NTT（用CRT合并2个小素数模下结果就可以，或者直接long long快速乘）=>o(nlogmlogn)
I.
题意：求出[l,r]所有单调不递增||单调不递减数
数位dp，没得说的，注意常数太大，o(10logn)会超时
所以就愉快地记忆化搜索，把指定位置是包括0~9位的全部填上
或者直接开场直接处理9、99、999...这些数的对应计数
这样就可以o(logn)胡搞了
果然不应该搞这么久的。。。比赛哪有那么多时间给你搞
以上是标准做法，已AC，我的非主流做法在下：
我是想用前缀和把搜索过程的复杂度压缩一下的，结果WA
大神求教
#include#include #include #include #include #include #include #include
J.
题意。。。实在难以描述，看https://acm.bnu.edu.cn/v3/statments/taiwan2016.pdf吧
这题一看像是多项式乘法，但是下面的不是加而是取其最大，所以什么fft，nft都可以歇歇了
其实也不难想到解法，把最大数填上对应位置，之后从大到小填，碰到已填元素就跳过
直到整个表都填满为止
为什么这样看似o(n^2)的解法不会超时。。。我也不知道。。。
写时SB了，数组开成10^5结果老RE
#include#include #include #include #include #include #include #include