点分治模板

poj 1741

1.选取一个点,把无根树变成有根树。通过树形dp的方式选择。用son记录点的子树大小,用F算出最大的子树,当F[x]<F[root]时,更换root.

2.再次通过dfs处理树上的deep和距离。

3.处理连通块中通过根节点的路径。减去同一子树内部的路径。

4.递归。

bzoj 2152
同上模板,只需要计算dist%3==0的点对,用一个数组记录%3以后的距离。

bzoj 2445

bzoj 2445
求n个点的symmetric labeled clique的个数,然后求m的次方。
答案就是\(m^{\sum_{x|n}\frac{n!}{(x!)^{\frac{n}{x}}{\frac{n}{x}}!}}\).
求这个,首先减少次方数,p=999999599是一个质数。
\(m^{p-1}\equiv 1 (\% p)\),则只需求指数%(p-1)。
但是不容易一下求出阶乘。
注意到\(999999599=2*13*5281*7283\),可以利用威尔逊定理。
\(p\)为素数时,\((p-1)!\equiv -1(\% p)\)。
那么有\(n! \equiv (-1)^{\frac{n}{p}}*(n\% p)!*\frac{n}{p}!\).
那么可以分别求指数对于\(2\)、\(13\)、\(5281\)、\(7283\)的余。
最后可以用中国剩余定理进行合并,出模(p-1)意义下的指数值(注意exgcd出来的值的正负)。
最后做一次快速幂。

bzoj 5047

bzoj 5047
bzoj九月月赛题。
动态边权的最短路问题。
枚举边权会死超时,可是细想,可以预处理的呀。
设cost[i]表示时间为i的时候最早到的时间,那么dist[now]时刻到的话,通过这条边,最早到的时间就是dist[now]+cost[now%c]-(now%c).
枚举时间,然后倒着取最小值就行了。

Codeforces Round #435 (Div. 2)

A. Mahmoud and Ehab and the MEX
给一个n元素的非负整数集,每次操作可以选择增加或删除一个数,问最少需要几次操作,使得比x小的数都在集合中,且x本身不能出现在集合中。用set模拟。

B. Mahmoud and Ehab and the bipartiteness
给一个二分图,且这个二分图是一个数的结构,问最多加几条边,使得这个图还是二分图。
最多是|s| * |t| – (n-1),用二分图染色计算|s|,|t|即可。

C. Mahmoud and Ehab and the xor
求n个数,使得这n个数的异或和为x。不存在输出“NO”,否则输出“YES” 以及n个数(任意一种情况)
NO 只有一种情况,n = 2, x = 0;
令\(pw = 2 ^ {17}, pw > 10 ^ {5}\) 然后我们从1,一直输出到n-3; 异或具有的性质是\(a \oplus b \oplus b = a\) 令他们的异或和为y。如果x=y,那么输出 \(pw, pw*2, (pw*2) \oplus pw\)
如果x!=y,那么输出 \(0, pw, pw \oplus x \oplus y\)。

D. Mahmoud and Ehab and the binary string
交互题,注意刷新,在不超过十五次的询问下,找出字符串的任意一组0和1的位置,每次询问会得到询问串与原串的汉明距离,保证输出至少存在一个1和一个0。
设每次询问得到的结果是有多少个正确的位置, 即 n-汉明距离。
先问1111…得到ans1,第二次问01111…得到ans2,如果ans1>ans2,那么第一个位置一定是1,否则是0,然后二分的在剩余长度里去找另一个数。

2017 ACM/ICPC Asia Regional Qingdao Online

1001 Apple
设三点式解圆方程,因为会爆所以用了java的分数类。

1003 The Dominator of Strings
AC自动机搞,加骚读入。PS:据说kmp直接就能过了。

1007 Zuma
首先预处理出每一段一样的长度和类型,会使后面的dp更简洁。
设\(f[l][r]\)表示区间\([l,r]\)消掉的最少步数。
首先\(i\)跟\(i+1\)必定不同色,所以\(f[l][r]=min(f[l][i]+f[i+1][r])\)。
如果区间左右断点一样的话,考虑最左端和最右端可以在最后的时候合并,那么\(f[l][r]=min(f[l+1][r-1]+cost)\).
然后考虑枚举中间可以作为连接的点,考虑这样的一个形态:最左端是1个,最右端随便,此时可以考虑以一个中间点合并时先连接左边,在连接右边一起消除。反之右边为1同理.即\(f[l][r]=min(f[l+1][i-1]+f[i+1][r-1]+cost)\).

1008 Chinese Zodiac
if判断。

1009 Smallest Minimum Cut
括弧··容量乘以(变数+1)+1 然后把dinic的板子改成LL 直接跑答案就行了。
答案mod(边数+1)+1就行了.

1010 Brute Force Sorting
每一次把其中不符合要求的数删去,对于删去的数,影响的只是前者和后者,在后续的判断中,只需要把前后仍在数组中的加在队列里判断。

1011 A Cubic number and A Cubic Number
\(p=x^3-y^3=(x-y)(x^2+xy+y^2)\).
显然\(x-y=1\),然后二分check。

2017 ACM-ICPC 亚洲区(西安赛区)网络赛

B Coin
\(\frac{(\frac{q}{p}+\frac{p-q}{p})^k+(-\frac{q}{p}+\frac{p-q}{p})^k}{2}\).求快速幂和逆元。

C Sum
其实输出233个1000000就可以了、或者233个9?

E Maximum Flow
找规律得到。在\(2^k\)的时候会突变。
大概是\(\sum_{i=1}^{2^i\leq n-1}(4^{i-1}+1)*\left \lfloor \frac{n+2^{i-1}+1}{2^i} \right \rfloor\).

F Trig Function
\(cos nx = \sum_{k=0}^{n} g(n,k)\frac{n(n+k-2)!!}{k!(n-k)!!}cos^k x\)。
其中,
$$g(n,k)=\left\{\begin{matrix}
(-1)^{\frac{n-k}{2}}|n\% 2=k\% 2\\
0|others
\end{matrix}\right.$$.

G Xor
大致思路是,一开始可以预处理出到根间隔为k=1,2..,300以内的小数据。小数据查询的时候,从a开始,看a到根余几,把这些的异或和弄出来,再在根到b上弄出余(k-moda)的。
大数据直接暴力lca跑。
贴一份cww的代码。

I Barty’s Computer
I好像就是个暴力啊。。。

矩阵优化DP

bzoj 4417

按照其给定的棋盘走法,每次走奇数步。那么有\(f_{i,j}=f_{i-1,j\pm 1}+f_{i-3,j\pm 1}+f_{i-5,j\pm 1}…\),
即\(f_{i,j}=f_{i-1,j\pm 1}+f_{i-2,j}\)。

定义矩阵列:\(j \in [0,n-1]\)列表示\(f_{i-1,j}\),\(j \in [n,2n-1]\)列表示\(f_{i-2,j}\)。
\(j \in [0,n-1]\)行表示\(f_{i,j}\),\(j \in [n,2n-1]\)行表示\(f_{i-1,j}\)。
从\(f_{i-2} \rightarrow f_{i}\)转移斜对角线为1。从\(f_{i-1} \rightarrow f_{i-1}\)斜对角线为1。
从\(f_{i-1} \rightarrow f_{i}\)有\(base[i][i-1~i+1]\)为1。
那么矩阵就可以实现转移了。

bzoj 4870
题意:求\(\sum \textrm{C}_{nk}^{ik+r}\)。
设矩阵表示模k余r的和。\(f[i][j]=f[i-1][j]+f[i-1][(j-1+k)\% k]\)。
改改矩阵乘法就好了。

三次剩余

51nod 1039
求\(x^3\equiv a(\% P)\)
1.\(a=0\)或者\(p\leq 3\),\(res=a\)。
2.\(p \% 3 \neq 1\),\(res=a^{\left \lfloor \frac{2p-1}{3} \right \rfloor}\)。
3.剩下的情况不满足\(a^{\left \lfloor \frac{p-1}{3} \right \rfloor}\equiv 1(\% p)\)则无解。
4.随机一个\(u\{ x,y,z\} \in \Re\),\(v=u^{\frac{p-1}{3}}\)。若仅有\(v.y\neq 0\),\(v.y\)模\(p\)意义下的逆元就是其中一组答案。
设\(\epsilon = \frac{-1+\sqrt{-3}}{2}\),即\(\epsilon ^3\equiv 1(\% p)\).
\(a_1=(x_1,y_1\epsilon ,z_1\epsilon ^2)\),\(a_2=(x_2,y_2\epsilon ,z_2\epsilon ^2)\)。
\(a_1\cdot a_2\)有\(x=x_1x_2+y_1z_2+z_1y_2\)同理其他。

N次剩余

51nod 1038
题意:
求\(X^A \equiv B (\% P)\)所有小于p的X。

1.先求出\(P\)的原根\(g\)。
2.设\(x=g^y\),\(B=g^t\)。那么原式化为:\(g^{yA} \equiv g^t(\% P)\)。根据费马小定理化为\(yA\equiv t(\% P-1)\)。
3.\(B\equiv g^t(\% P)\)通过BSGS求出\(t\)。
4.通过扩展欧几里得求线性同余方程最简解,然后扩展。