「补题」联赛模拟乱写

建设城市

题目本质上求的是 (sum a_i=m, a_ile k) 的方案数

那么 (dp) 的做法很显然

然后考虑咋做 (nle 10^9) 的部分

这时候需要再去看一遍题目，发现 (n>m) 的时候无解

用隔板法来解决剩下的问题

如果没有限制的话那么 (inom {m-1}{n-1})

然后容斥： $ans=sum_{i=0}^n (-1)^i inom{m-i imes k-1}{n-1}inom ni $

复兴了隔板法

军训队列

题目中条件给到了一共的身高可能只有 (6000) 种

那么离散化之后套一个 (Theta(n^2 k)) 的 (dp) 就行了

(@ZZ\_zuozhe) 使用了斜率优化的手段 (orz)

山屋惊魂

模拟即可

我写了两天，交出了 (13k) 的代码

彩球问题

设 (f_{i,j,k,x}) 为可以放 (i) 个个数为 (1) 的小球， (j) 个个数为 $2 $ 的小球，(k) 个个数为 (3) 的小球

那么枚举上次拿了多少小球可以得到转移方程

直接记搜上去即可

游戏

带悔贪心随便写一下就行了

发现并不是很能写动，然后就换成了匈牙利过掉了

嘟嘟噜

约瑟夫问题

由原来的公式得到 (x+(m-1)\%(n-i+1)+1)

当然，这里的 (n-i+1) 通常比 (m) 要大，那么有些加法是没有啥用处的，那咱乘法优化一下这个过程就行了

（其实个人不是很喜欢这种题目，当然，公式记好就成了）

天才绅士少女助手克里斯蒂娜

推式子有

[sum_{lle i<jle r} |v_i imes v_j|^2=sum_{i=l}^{r-1}v_{i}^2sum_{j=i+1}^r v_{j}^2 ]

然后发现自己 (naive) 了，应该是向量乘法

那么换掉

[sum_{i=l}^{r-1} sum_{j=i+1}^r (x_iy_j-x_jy_i)^2 ]

[sum_{i=l}^{r-1} sum_{j=i+1}^r (x_i^2y_j^2+x_j^2y_i^2-2x_ix_jy_iy_j) ]

[sum_{i=l}^{r}sum_{j=l}^r x_i^2y_j^2-x_ix_jy_iy_j ]

拆开维护上去就行了

学习了向量乘法的公式：(|A imes B|=x_Ay_B-x_By_A)

凤凰院凶真

(LCIS,nle 5000)

看完题目发现自己连基础 (dp) 都不会

首先研究一下发现 (LIS) 是有 (Theta(nlog n)) 的做法的（离散化+线段树）

这问题就转化成了 (i>k,j>l,a_i=b_j,a_k=b_l,a_i>a_k) 的多维偏序

那么解决这种问题就是把所有的 (a_i=b_j) 的点扔到直角坐标系里面，然后 (K-D Tree)

然后发现问题出现在点的数量其实是 (O(n^2)) 的

那么乱搞开始，找到一些数值相同的点扔掉坐标系里面

然后做一个三维偏序那样子就行了

方案直接在 (BIT) 的时候记个 (las) 啥的就成了

写出来好像不难，但是并不会保证坐标系里面的点数不爆炸

然后滚去想 (dp)

(f_{i,j}) 为 (A) 到 (i) 但是不必须选，(B) 到 (j) 同时必须选 (j) 的方案数

写成如下这样就行了：

	for(reg int i=1;i<=n;++i) 
        {
            int mx=0,pos=0; 
            for(reg int j=1;j<=m;++j) 
            {
                f[i][j]=f[i-1][j];
                if(a[i]>b[j]&&v<f[i-1][j]) v=f[i-1][j],pos=j;
                if(a[i]==b[j]) f[i][j]=v+1,pre[i][j]=pos
            }
        }

山洞

首先一个 (naive) 的 (dp)

(f_{i,j}) 为走了 (i) 步之后到 (j) 点的方案数

转移就是 (f_{i+1,j+i+1}+=f_{i,j},f_{i+1,j-(i+1)}+=f_{i,j})

这里第二维显然要取模

这个 (m) 就是矩阵快速幂咯

发现这个每次的转移的系数位置不一样

然后发现这个如果 (i>n) 之后的每步和 (i\%n) 效果是一样的

那还是能转移的

如果直接快速幂 (Theta(n^3log m)) 显然是要爆掉的

然而我们只关注第一行的所有内容，就是说做完预处理的 (f_{n,i}) 是我们需要维护的

同时我们转移出来的 (f_{n,i}) 是以 (1) 号点为起始点，如果要考虑以其它点为启示的点的话直接平移

这东西整出来叫循环矩阵……

乘法的时候展开就行了

学习了：循环矩阵科技

beauty

考虑这个 (sum dis) 的构成

大概是经过一条边有多少次然后求和

求出来当前点的子树里面有多少个关键点

最多可能有 (min(c_x,2k-c_x)) 次经过这条边

那么盲猜一波

[ans=sum_{i=1}^nmin(c_i,2k-c_i) ]

（就过了）

其实证明好像并不是很麻烦，找到重心之后按照 (dfn) 序排上

不一样的子树里面的点进行匹配即可

chinese

观察一下这题目给的式子：

[sum_{i=0}^{nm} f_{i} imes i ]

这东西有啥含义呀？

就是对于一张 (n imes m-k) 格式的棋盘，总共有多少个炼字

那么对于一个位置是炼字，当且仅当行列的值都比它小

那么计数咯，数有 (n-1+m-1) 值域是 (val-1)

那么答案就是

[sum_{i=2} ^k (n+m-2) ^{i-1} imes k^{nm-n-m+1} imes nm ]

physics

首先要先处理完所有的修改之后变成逆序做正修改

这样的话答案是单调不降的

悬线法预处理出来答案之后的最后问题就是如何快速处理修改操作

复兴：悬线法（虽然现在看来就是个简单 dp）

具体写一下咯：模拟算出来 (up_{i,j},down_{i,j})，单调栈算 (left_{i,j},right_{i,j})

发现判断答案是不是可行的时候只需要考虑改变的部分就好了

那么单调队列维护一下即可

简单计算

[sum_{i=0}^q lfloor frac {iq} p floor ]

[sum_{i=0} ^{frac p 2}lfloor frac {qi} p floor +lfloor frac {q(p-i)} p floor ]

然后发现这里需要考虑奇偶性，很麻烦，那么式子乘二

然后就成了

[frac{sum_{i=0} ^plfloor frac {qi} p floor+lfloor frac {q(p-i)} p floor }2 ]

那么提出来化简就有

[frac{(p+1)q -sum_{i=0}^p [p mid (qi)]}2 ]

考虑后面的东西怎么做

其本质就是用 (i) 补齐 (p) 有 (q) 没有的因子

即 (p/gcd(p,q))

而在 (0 o p) 中这样的数有几个呢？

[frac{p}{frac{p}{gcd(p,q)}}=gcd(p,q) ]

[sum_{i=0}^q lfloor frac {iq} p floor=frac{(p+1)q-p+gcd(p,q)}2 ]

关于上边的东西的奇偶性，直接分类讨论一下就能证了

感觉

[sum_{i=0}^p [p mid (qi)]=gcd(p,q) ]

的结论挺棒的

求和

套路差分一下，问题转化成求(sumlimits_{i=1}^n sumlimits_{j=1}^m d_{i,j})

答案显然为 (frac{nm(n+m)}2)

（第一行的和是 (frac{m(m+1)}2)，后面每行增量 (m) 直接求和）

记得处理一下爆 (long long) 的事

（这俩题式子爽呀！）

分组配对

因为无论怎么配对都不能超出那个 (M)，由排序不等式，最大的和最大的配即可

然后不难想到二分，发现不能维护增加的人，就弃了

然后去颓了题解，发现这东西居然可以在外层套倍增，然后感觉有所收获

具体而言就是如果

check(i,i+(1<<j)-1)&&!check(i,i+(1<<(j+1))-1)

那么就有 (targetin [2^j+1,2^{j+1}-1])

(orz)

学到了：外层倍增优化内层二分复杂度

城市游戏

首先设 (f_{i}) 为 (i o n) 的答案

(ans=f_1,f_n=0)

转移就是

[f_{i}=minmax_{(i,j)in E}(f_j+len_{i,j},g_{i o n ,(i,j)}) ]

(g_{i o n,(i,j)}) 即删掉 ((i,j)) 后 (i) 到 (n) 的距离

求一下 (g) 进行转移即可

这其实是另一道题目

---

Luogu 2934

首先维护上一个最短路树，然后考虑每个非树上的边((x,y))对答案的影响

对 (x) 到 (y) 的路径上的点进行 (ans_i=min(ans_i,d_x+d_y+w_{(x,y)}-d_i)) 即可

这东西用树剖会相当好写

那咱写个鬼的并查集

并查集的做法是按照 (d_x+d_y+w_{(x,y)}) 排序

用并查集维护是否更新，每条非树边更新路径上的点值

---

不太难的题目吧，但是上来可能不会想到用dp……

Walk

往约数里面扔边，然后求一下联通块直径就行了

Simple

不是 (gcd(n,m)) 的倍数的数字肯定拼不出来

然后把 (m,n,q) 同时干掉 (gcd(n,m))

因为 (xn+ym) 在 (gcd(n,m)=1) 的时候最大拼不出来的数字是 (nm-n-m)

那么每次减掉 (m) 看有多少个 同余数 即可

数论调参

Weed

维护的内容就是每个后缀操作的剩余值，剩下的金珂拉或者还有几个没有吞掉

然后发现又是 (push\_up) (log n) 化的题目

子数里面二分来维护删除操作

获得了一个启示：不太好写这东西只能在写了之后说，因为没写之前啥都不好写

Drink

维护一个十字链表，就是那种记录上下左右的 (nxt) 的那个

对于修改操作，修改边上的点的前后左右

对于内部点，可以通过外部点算得到

其实并不清楚怎么个算法，所以没写

但是学到了十字链表的思想

简单的序列

足够简单，(dp) 即可

设 (f_{i,j,0/1}) 为当前考虑了 (i) 位，左括号减去右括号数目为 (j) ，是否添加了整串

这里转移分为几种

(1.) 添加一个左括号 (f_{i,j,0/1}+=f_{i-1,j-1,0/1})

(2.) 添加一个右括号 (f_{i,j,0/1}+=f_{i-1,j+1,0/1})

(3.) 添加一串 (f_{i,j-sum,1}+=f_{i,j,0})

写就行了（然后咱写不出来就又自闭了，(dp) 调参局）

好像有卡特兰数做法？

设左边有x个右括号，R+y个左括号

易得方案数为C(x+y+R,x)-C(x+y+R,x-1),右边同理。

简单的期望

这东西真的巧妙诶

发现加法只会对后面的几位产生贡献，那么设 (f_{i,j,k,0/1}) 表示计算 (i) 次之后最后 (8) 位为 (j) 同时八位之后 (k) 位是 (0/1) 的概率

转移考虑进行 (+1) 操作还是 ( imes 2) 操作

其实个人感觉写成那种这行向下一行转移的式子会相对清晰一点……

然后分着转移，先转移加法的，再转移乘法的

一些收获：如果发现比较奇怪的数据范围，那么考虑是不是有些性质，比如 (+1) 只会影响 (8) 位，同时还有一些类似的比如只记录后 (n) 位的状态之类的

有一说一，今年初赛的那个程序补全题目的思路是真的很不错

简单的操作

观察一下第二组样例发现如果图上存在三元环是无解的

然后手玩发现奇环无解，偶环无所谓

（这时候发现这图可能不联通，那么一样做就行了）

手玩树的部分发现可以通过一些手段留下来树的直径，然后又在树上面加了几个边发现并不影响

树上的部分直接删掉根和叶子就行了

联通块里面的可以被删成偶环+链的形式，这样的话也能删成树上

多个联通块里面就连直径就行了

只要是最长的树上简单路径就行

然后发现不会写最长链，就写了个 (n) 遍 (spfa)

阴阳