一些题
模拟赛遇到的trick，有意思的，有启发的题，不一定很难。
蜀道难
噫吁嚱，危乎高哉！蜀道之难，难于上青天！蚕丛及鱼凫，开国何茫然！尔来四万八千岁，不与秦塞通人烟。西当太白有鸟道，可以横绝峨眉巅。地崩山摧壮士死，然后天梯石栈相钩连。上有六龙回日之高标，下有冲波逆折之回川。黄鹤之飞尚不得过，猿猱欲度愁攀援。青泥何盘盘，百步九折萦岩峦。扪参历井仰胁息，以手抚膺坐长叹。
问君西游何时还？畏途巉岩不可攀。但见悲鸟号古木，雄飞雌从绕林间。又闻子规啼夜月，愁空山。蜀道之难，难于上青天，使人听此凋朱颜！连峰去天不盈尺，枯松倒挂倚绝壁。飞湍瀑流争喧豗，砯崖转石万壑雷。其险也如此，嗟尔远道之人胡为乎来哉！
剑阁峥嵘而崔嵬，一夫当关，万夫莫开。所守或匪亲，化为狼与豺。朝避猛虎，夕避长蛇；磨牙吮血，杀人如麻。锦城虽云乐，不如早还家。蜀道之难，难于上青天，侧身西望长咨嗟！
连通块
有一棵 \(n\) 个节点的树，他现在要对这棵树做 \(m\) 次操作，每次操作如下
-
删除树上的一条边
-
查询在节点 \(u\) 目前所在的连通块内，离 \(u\) 最远的点的距离。两点之间的距离定义为两点之间简单路径的边数。
树的直径的性质
-
直径的端点一定是树的叶子节点。
-
从树上任意一节点出发，与它距离最远的节点一定是直径的一个端点。
-
在树上增加一个叶子节点，最多改变树的直径的一个端点。
-
设两棵树的直径端点分别为 $ (u,v) 和 (x,y) $ ，将两棵树合并后的直径端点仍在这四点中。
-
如果一棵树有多条直径，它们一定交与一个节点，且这个交点是每条直径的中点。
考虑求树的直径：
-
贪心。由性质2，任由一点开始求最远点，两边DFS即可。
-
DP。求该子树中的最长链和次长链。
再来看这道题，我们把操作离线，反向操作，就成为合并子树问题。由性质2可知，我们只需要知道直径端点就能求出最大距离。再由兴致4，很容易维护树的直径。
CODE
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int n,m,a,b,cnt,head[N],fa[N];
bool p[N],vis[N],vs[N];
int dad[N],siz[N],depth[N],son[N],top[N];
int fir[N],sec[N],maxn[N],maxx[N],ans[N];
struct node{
int x,y,dis;
};
struct edge{
int to,nxt;
}e[N<<1];
struct query{
int opt,x;
}q[N];
bool cmp(node i,node j){
return i.dis>j.dis;
}
inline void add(int u,int v){
cnt++;
e[cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int find(int x){
if(x==fa[x])return x;
else return fa[x]=find(fa[x]);
}
void dfs(int u,int f){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f)continue;
if(!p[i>>1]){
int fx=find(u),fy=find(v);
if(fx!=fy)fa[fx]=fy;
}
dfs(v,u);
}
}
void dfs1(int u,int f){
depth[u]=depth[f]+1;
siz[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f)continue;
dad[v]=u;
dfs1(v,u);
if(siz[son[u]]<siz[v])son[u]=v;
siz[u]+=siz[v];
}
}
void dfs2(int u,int t){
top[u]=t;
if(son[u]){
dfs2(son[u],t);
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==dad[u]||v==son[u])continue;
dfs2(v,v);
}
}
int LCA(int x,int y){
int fx=top[x],fy=top[y];
while(fx!=fy){
if(depth[fx]<depth[fy]){
y=dad[fy];
}
else{
x=dad[fx];
}
fy=top[y];fx=top[x];
}
if(depth[x]<depth[y])return x;
else return y;
}
void dfs3(int rt,int u,int f){
fir[u]=u;
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
if(p[i>>1])continue;
int v=e[i].to;
if(v==f)continue;
if(vis[v])continue;
dfs3(rt,v,u);
if(maxn[v]+1>maxn[u]){
maxn[u]=maxn[v]+1;
fir[u]=fir[v];
}
}
}
void dfs4(int rt,int u,int f){
sec[u]=u;
vs[u]=1;
for(int i=head[u];i;i=e[i].nxt){
if(p[i>>1])continue;
int v=e[i].to;
if(v==f)continue;
if(vs[v])continue;
dfs4(rt,v,u);
if(maxx[v]+1>maxx[u]){
maxx[u]=maxx[v]+1;
sec[u]=sec[v];
}
}
}
int Dis(int x,int y){
return depth[x]+depth[y]-depth[LCA(x,y)]*2;
}
signed main()
{
freopen("block.in","r",stdin);
freopen("block.out","w",stdout);
scanf("%d%d",&n,&m);
cnt=1;
for(int i=1;i<=n;i++){
fa[i]=i;
}
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
for(int i=1;i<=m;i++){
scanf("%d%d",&q[i].opt,&q[i].x);
if(q[i].opt==1){
p[q[i].x]=1;
}
}
dfs(1,0);
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=n;i++){
if(!vis[i]){
int anc=find(i);
dfs3(anc,anc,0);
dfs4(anc,fir[anc],0);
sec[anc]=sec[fir[anc]];
}
}
for(int i=m;i>=1;i--){
if(q[i].opt==1){
int x=(e[q[i].x<<1].to),y=(e[q[i].x<<1|1].to);
int fx=find(x),fy=find(y);
node d[6];
d[0]={fir[fx],sec[fx],Dis(fir[fx],sec[fx])};
d[1]={fir[fx],fir[fy],Dis(fir[fx],fir[fy])};
d[2]={fir[fx],sec[fy],Dis(fir[fx],sec[fy])};
d[3]={sec[fx],fir[fy],Dis(sec[fx],fir[fy])};
d[4]={sec[fx],sec[fy],Dis(sec[fx],sec[fy])};
d[5]={fir[fy],sec[fy],Dis(fir[fy],sec[fy])};
int dis=0;
for(int j=0;j<6;j++){
if(dis<d[j].dis){
dis=d[j].dis;
fir[fy]=d[j].x;
sec[fy]=d[j].y;
}
}
fa[fx]=fy;
}
else{
int fx=find(q[i].x);
ans[i]=max(Dis(q[i].x,fir[fx]),Dis(q[i].x,sec[fx]));
}
}
for(int i=1;i<=m;i++){
if(q[i].opt==2)printf("%d\n",ans[i]);
}
}
Wallpaper Collection
设 $ dp_{i,j,k} $ 为第 \(i\) 行，所选区间为 $ [j,k] $ 最大价值，转移时用滚动数组和一些优化，就可做到 $ O(n^3) $ 。
改变DP状态：我们发现相邻两行所选区间必须有交集，想象一个学长在矩阵上走动，他走过的路径刚好符合以上定义。设 $ dp{i,j} $ 为学长在第 \(i\) 行，第一次走到的是第 \(j\) 格的最大价值，加一些优化就可以 $ O(n^2) $ 。
进击的巨人
一个 $ O(n^2) $ 的做法：对于每一个位置 \(i\) ，枚举 $ j \le i $ ，计算 $ [j,i] $ 都是1的概率，进而可以算出期望。因为赛时数据水，$ n\le 1e4 $ ， $ O(n^2) $ 就跑过来了。
设 $ [L,R] $ 都是1，那么 $ [L-1,R] $ 都没有被损坏，防御值为 $ (R-L+1)^k $ 。
二项式定理展开得到：
\[(R-L+1)^k = \sum _ { i=0 } ^k \binom{k}{i} \times R^i \times (-L+1)^{ k-i } \]记前 \(i\) 个位置?的个数为 \(s_i\) ,位置 \(i\) 的答案为：
\[\sum _{ j=1 }^i \frac{1}{ 2^{ s_i -s_j } } \times \sum _{p=0}^k \binom{k}{p} \times i^p \times (-j+1)^{k-p} \]\[= \frac{1}{ 2^{s_i} } \times \sum _{p=0}^k \binom{k}{p} \times i^p \times \sum_{j=1}^{i} (-j+1)^{k-p} \times 2^{s_j} \]发现这个东西极好维护,复杂度 $ O(NK) $ 。
魔卡少女樱
$ a_i \not\equiv a_{i+1} \pmod 3 $ 。差分的思路显然， $ a_{i+1}-a_i>0 \ \And a_{i+1}-a_i \not\equiv 0 \pmod 3 $ 。我们先考虑差分结果只有1，2的情况，枚举填 \(k\) 个2， $ n-1-k $ 个1，这里方案数为：设填2则 \(x_i\) 值为1，填1则 $ x_i $ 值为0，$ \sum x=k $ ，有 $ \dbinom{n+k-2}{n-2} $ 种。
当前 $ a_n= n-1+k $，对于剩下的 $ m-a_n $ 没有使用，我们可以填进 $ a_1 $ ，也可以三个一组加到差分数上（正确性显然）。
设填 \(k\) 个2，枚举 $ a_1 $，三个一组加，共有 $ t= \left \lfloor \frac{m-(n-1+k)-a_1} {3} \right \rfloor $ 组 。方案数为 $ \sum_{i=0}^{t} \dbinom{ n+i-2 }{ n-2 } $
最终答案
\[\sum_{ k=0 }^{n-1} \sum_{ a_1=0 }^{ m-n-k+1 } \sum_{ i=0 }^{ m-n-k+1-a_1 } \dbinom{ n+i-2 }{ n-2 } \]枚举就得到 $ O(n^3) $ 做法，加一堆前缀和优化就做到 $ O(n) $
《阿房宫赋》
六王毕，四海一；蜀山兀，阿房出。覆压三百余里，隔离天日。骊山北构而西折，直走咸阳。二川溶溶，流入宫墙。五步一楼，十步一阁；廊腰缦回，檐牙高啄；各抱地势，钩心斗角。盘盘焉，囷囷焉，蜂房水涡，矗不知其几千万落！长桥卧波，未云何龙？复道行空，不霁何虹？高低冥迷，不知西东。歌台暖响，春光融融；舞殿冷袖，风雨凄凄。一日之内，一宫之间，而气候不齐。
妃嫔媵嫱，王子皇孙，辞楼下殿，辇来于秦，朝歌夜弦，为秦宫人。明星荧荧，开妆镜也；绿云扰扰，梳晓鬟也；渭流涨腻，弃脂水也；烟斜雾横，焚椒兰也。雷霆乍惊，宫车过也；辘辘远听，杳不知其所之也。一肌一容，尽态极妍，缦立远视，而望幸焉；有不见者，三十六年。燕、赵之收藏，韩、魏之经营，齐、楚之精英，几世几年，剽掠其人，倚叠如山。一旦不能有，输来其间。鼎铛玉石，金块珠砾，弃掷逦迤，秦人视之，亦不甚惜。
嗟乎！一人之心，千万人之心也。秦爱纷奢，人亦念其家；奈何取之尽锱铢，用之如泥沙？使负栋之柱，多于南亩之农夫；架梁之椽，多于机上之工女；钉头磷磷，多于在庾之粟粒；瓦缝参差，多于周身之帛缕；直栏横槛，多于九土之城郭；管弦呕哑，多于市人之言语。使天下之人，不敢言而敢怒；独夫之心，日益骄固。戍卒叫，函谷举；楚人一炬，可怜焦土。
呜呼！灭六国者，六国也，非秦也。族秦者，秦也，非天下也。嗟乎！使六国各爱其人，则足以拒秦；使秦复爱六国之人，则递三世可至万世而为君，谁得而族灭也？秦人不暇自哀，而后人哀之；后人哀之而不鉴之，亦使后人而复哀后人也。