T1 出师表
source:洛谷P4216
这是一种题解没有的O(mlogn) 做法。
首先第一步转化。设这是第x 个任务，若 opt 为 1，危险值大于 c 的只有可能在第 x−c−1 个任务以前出现。
于是题目就变成了在某一时刻单点加和在某一时刻链上查询，离线即可去掉“某一时刻”。
单点加和链上查询，大家用的应该都是树剖，复杂度是 O(log2n) 的。然而使用 DFS 序和差分，将单点加转化为子树加，将链上查询转化为单点查询。
具体来说就是设一个 s[u]表示节点 u 到根节点有多少个节点是危险的，那么单点加就可以变成子树加，在 DFS 序上就是区间加。
链上查询只需要查询 u,v,LCA(u,v),f[LCA(u,v)]，也就是单点查。
区间加单点查，树状数组上！
极短的代码：
#include<cstdio>
#include<vector>
const int M=2e5+5;
int n,m,dfc,d[M],f[M],dfn[M],siz[M],son[M],top[M];
int BIT[M];int opt[M],x[M],y[M],ans[M];
std::vector<int>G[M],id[M];
void DFS1(int u){
dfn[u]=++dfc;d[u]=d[f[u]]+1;siz[u]=1;
for(int&v:G[u]){
DFS1(v);siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void DFS2(int u,int tp){
top[u]=tp;if(!son[u])return;DFS2(son[u],tp);
for(int&v:G[u])if(v!=son[u])DFS2(v,v);
}
inline int LCA(int u,int v){
while(top[u]^top[v]){
if(d[top[u]]>d[top[v]])u=f[top[u]];
else v=f[top[v]];
}
return d[u]>d[v]?v:u;
}
inline int dis(const int&u,const int&v){
return d[u]+d[v]-(d[LCA(u,v)]<<1)+1;
}
inline void Add(int x,const int&val){
for(;x<=n;x+=1<<__builtin_ctz(x))BIT[x]+=val;
}
inline int Query(int x){
int ans=0;
for(;x>=1;x-=1<<__builtin_ctz(x))ans+=BIT[x];
return ans;
}
inline int Q(const int&x,const int&y){
int lca=LCA(x,y);
return Query(dfn[x])+Query(dfn[y])-Query(dfn[lca])-Query(dfn[f[lca]]);
}
signed main(){
register int i,k;
scanf("%d",&n);
for(i=1;i<=n;++i)scanf("%d",f+i),G[f[i]].push_back(i);
for(i=1;f[i];i=f[i]);
DFS1(i);DFS2(i,i);
scanf("%d",&m);
for(i=1;i<=m;++i){
scanf("%d",opt+i);
if(opt[i]==1){
scanf("%d%d%d",x+i,y+i,&k);
if(k<i)id[i-k-1].push_back(i);
}
if(opt[i]==2){
scanf("%d",x+i);
}
}
for(i=1;i<=m;++i){
if(opt[i]==2){
Add(dfn[x[i]],1);Add(dfn[x[i]]+siz[x[i]],-1);
}
for(int&v:id[i])ans[v]=Q(x[v],y[v]);
if(opt[i]==1){
printf("%d %d\n",dis(x[i],y[i]),ans[i]);
}
}
}
T2 滕王阁序
source:洛谷P1852跳跳棋
不得不说，这题建模极为抽象了，出题人太神了。看了好多篇题解才懂，自己也写一篇比较详细的吧
相信大家都玩过跳棋，有一个规则想必大家都知道，就是一次跳跃不能跳过两颗棋子
这个限制是解决这题的关键，有了这个限制，可以看出，对于两边的棋子，只能跳到其余两颗的中间，同样的中间的棋子也只能跳到两边
为了方便，我们将三个棋子标号，分别为x,y,z，且x<y<z。
移动棋子无非就四种讨论
(x,y,z)⟹(2x−y,x,z)
(x,y,z)⟹(x,z,2z−y)
(x,y,z)⟹(y,2y−x,z)
(x,y,z)⟹(x,2y−z,y)
因为有了不能一次跳过两颗棋的限制，所以第三种情况和第四种情况必然起了冲突
不妨设d1=y−x,d2=z−y，易得
d1<d2:则(x,y,z)⟹(y,2y−x,z)
d1>d2:则(x,y,z)⟹(x,2y−z,y)
也就是说我们对于每种状态只有三种转移方式
我们再看看这三个式子，可以发现，对于第一种和第二种情况，我们将中间的点向两边跳，相当于扩大了边界。而第三种两边向里面跳则恰恰相反，是将边界缩小了
是不是很像一棵二叉树？
现在可能还不够明显，我们再接下去推
有一个很显然的性质，边界不可能无限变小。也就是说缩着缩着会遇到一种情况不能再缩了，我们来思考一下什么情况不能再缩了
观察式子：
d1<d2:则(x,y,z)⟹(y,2y−x,z)
d1>d2:则(x,y,z)⟹(x,2y−z,y)
惊奇的发现，我们这样讨论漏了一种情况，d1=d2
这个非常好理解，如果d1=d2，那么x必然会与z跳到同一个点，而这是不符合题目描述的。所以当d1=d2时，这个状态只能由中间向两边跳，也就是只有两个转移状态，想想这个状态在二叉树中像什么？没错，根节点我们就这样找到了，二叉树的形态就像下图所示：
可以发现，对于每一组(x,y,z)都有唯一对应的一个根，而且二叉树之间的任意一组(x,y,z)都可以互相转化，而且转化的操作次数就等于两个状态在树上的距离
所以如果初始(x,y,z)的树根和目标(x,y,z)的树根不相同，那么就是No，因为无论怎么跳都出不去这棵树的范围，而根不同则说明树不同
所以对于初始(x,y,z)和目标(x ,y,z)，我们只要求出它们的LCA，答案就是初始点到LCA的距离+ LCA到目标点的距离
不过因为范围太大，树无法存下，普通的LCA求法树剖、倍增等已经无法使用了
我们先不急着求LCA，来想想另一个问题
初始状态：(1,10,11)
目标状态：(1,2,3)
人脑模拟一下程序，d1>d2，转换成(1,9,10)，(d1>d2)，转换成(1,8,9)，d1>d2，转换成(1,7,8),⋯⋯
如果改成(1,inf−1,inf)呢？
显然要T飞
不过我们发现，一直在重复一个操作，所以可以将这些操作压缩
我们只讨论d1>d2的情况，d1<d2其实差不多
易发现，要连续跳(d1−1)/d2次同样的操作（每一次跳d2的距离，但又不能超越或跳到x，也就是总距离为(d1−1)，总次数故为(d1−1)/d2）
设：d3=(d1−1)/d2
所以最后是(x,y−d3⋅d1,z−d3⋅d1)
这样我们就大大的压缩了路径，但这样又有什么用呢？我们回到树上来
因为路径被压缩了，所以我们可以换种方法求LCA
方便起见，我们先将初始状态跳到和目标状态在树中的高度一致（如果目标状态高度更高我们就换一下，在树中的距离是没有方向的）
也是初始状态要向上跳DepT−DepS次（Dep表示深度，S和T分别表示起始状态和目标状态），而跳跃的操作我们就可以用压缩路径快速实现
好了，现在两个状态高度相同了
有个显然的性质，如果两个状态同时向上跳x次所跳到的节点相同，那么同时向上跳x+1次所跳到的节点也相同，也就是说明满足单调性。所以我们可以用二分来枚举最小的x满足了两个状态同时向上跳x次所跳到的节点相同，所以LCA就是两个同时向上跳x次所跳到的节点
然后就愉快的AC了
码量小但细节是真的多，思维难度也很好，总而言之就是一道质量非常高的建模LCA+二分的题目
如果有哪步我打错了，或者有一些没有理解的地方，欢迎私信或留言！
参考代码：
#include<bits/stdc++.h>
using namespace std;
int Cnt,Ans,d1,d2,d3,x,y,z,L,R,X,Y,Z,tot,a[5];
struct lc{
int x,y,z,tot;
}A,B;
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-f;ch=getchar();}
while (ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
inline void Dfs(int x,int y,int z){
tot=0;
while (1){
d1=y-x,d2=z-y;
if (d1==d2) break;
if (d1>d2) d3=(d1-1)/d2,tot+=d3,y-=d3*d2,z-=d3*d2;
else d3=(d2-1)/d1,tot+=d3,x+=d3*d1,y+=d3*d1;
}
if (A.x||A.y) B=(lc){x,y,z,tot};
else A=(lc){x,y,z,tot};
}
inline void Swap(){
swap(x,X),swap(y,Y),swap(z,Z);
swap(A.x,B.x),swap(A.y,B.y),swap(A.z,B.z),swap(A.tot,B.tot);
}
inline bool check(int T,int x,int y,int z,int X,int Y,int Z){
tot=T;
while (tot){
d1=y-x,d2=z-y;
if (d1==d2) break;
if (d1>d2) d3=min((d1-1)/d2,tot),tot-=d3,y-=d3*d2,z-=d3*d2;
else d3=min((d2-1)/d1,tot),tot-=d3,x+=d3*d1,y+=d3*d1;
}
tot=T;
while (tot){
d1=Y-X,d2=Z-Y;
if (d1==d2) break;
if (d1>d2) d3=min((d1-1)/d2,tot),tot-=d3,Y-=d3*d2,Z-=d3*d2;
else d3=min((d2-1)/d1,tot),tot-=d3,X+=d3*d1,Y+=d3*d1;
}
return X==x&&Y==y&&Z==z;
}
int main(){
for (int i=1;i<=3;i++) a[i]=read();
sort(a+1,a+4);x=a[1],y=a[2],z=a[3];
for (int i=1;i<=3;i++) a[i]=read();
sort(a+1,a+4);X=a[1],Y=a[2],Z=a[3];
Dfs(x,y,z);Dfs(X,Y,Z);
if (A.x!=B.x||A.y!=B.y||A.z!=B.z){printf("NO");return 0;}
if (A.tot<B.tot) Swap();
Ans=tot=A.tot-B.tot;
while (tot){
d1=y-x,d2=z-y;
if (d1==d2) break;
if (d1>d2) d3=min((d1-1)/d2,tot),tot-=d3,y-=d3*d2,z-=d3*d2;
else d3=min((d2-1)/d1,tot),tot-=d3,x+=d3*d1,y+=d3*d1;
}
L=0,R=B.tot;
while (L<=R){
int mid=L+R>>1;
if (check(mid,x,y,z,X,Y,Z)) Cnt=mid,R=mid-1;
else L=mid+1;
}
printf("YES\n%d",Ans+Cnt*2);
return 0;
}
先放T1和T2其他等会再放
T3见手青的幻觉
自己玩去
T4蜀道难
source:洛谷P2329
这题的总体思路是：二分答案+贪心+dfs验证 首先，二分答案是不用说的，就看贪心和dfs验证。 如果要使得John得到至少m个木材，那么当然是选择最短的啦。所以可以提前把John需要的木材按规格从小到大排序，这就是贪心。
然后dfs就是如果能提供的木材有比John需要的第x根木材的规格大的（或相等的），那么就试试把这根木材中John需要的部分卖给他。不过……
第一行为整数m(m<= 50)表示木材店老板可以提供多少块木材给约翰。
这么大的数，不超时才怪勒！所以我们需要剪枝。有两个剪枝：
可行性剪枝，如果剩余的木材都不够John的需要，则return，所以这里需要用到前缀和，还要一个变量存储浪费的木材（即连最短的一根木材都不够）
去重，如果两根木材的规格相同，则可以去重。
有了这两个剪枝，就可以玄学地过了这题了！
上代码！
#include<bits/stdc++.h>
using namespace std;
int n,m,a[55],b[1100];
int w,l,r,mid,tot,sum[1100];//w是多余的木材，tot是总共能提供的木材的量，sum是John需要的木材的前缀和
bool dfs(int x,int l)
{
if(tot-w<sum[mid]) return 0;//第一个剪枝
if(x==0) return 1;//x=0表示还需要0根，也就是可以满足条件了，那么返回true
bool f=0;
for(int i=l;i<=n;i++)
if(a[i]>=b[x])//如果第i根木材可以满足John需要的第x根木材，dfs
{
a[i]-=b[x];
if(a[i]<b[1]) w+=a[i];
if(b[x-1]==b[x]) f=dfs(x-1,i);//去重
else f=dfs(x-1,1);
if(a[i]<b[1]) w-=a[i];
a[i]+=b[x];
if(f) return 1;
}
return 0;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
tot+=a[i];
}
cin>>m;
for(int i=1;i<=m;i++) cin>>b[i];
sort(b+1,b+m+1);//排序
for(int i=1;i<=m;i++) sum[i]=sum[i-1]+b[i];//计算前缀和，注意一定要在排序后计算哦！
while(sum[m]>tot&&m) m--;//如果选最短的m根都超出了能提供的木材的范围，则一定不可行
l=0,r=m;
while(l<=r)//二分
{
mid=(l+r)/2;
if(dfs(mid,1)) l=mid+1;
else r=mid-1;
}
cout<<l-1;
return 0;
}
T5 琵琶行
source:洛谷P3276
假设当前到了x的子树，现在是合并 x的第k个子树
f[x][j] 表示x的前k-1个子树该覆盖的完全覆盖，而且还能向上覆盖j层的最小代价
这个向上是针对x来说的，即可以向x的祖先方向再覆盖j层
对于第k个子树的意义就是，兄弟子树放置的守卫可以帮x的第k个子树覆盖前j层（第1层为x的子节点）
那么相应的就要有一个状态来表示这个 可以让兄弟子树 帮忙覆盖 的前j层
g[x][j] 表示还需要覆盖x的前k个子树中的前j层，且第j层以下该覆盖的完全覆盖（第1层为x）的最小代价
状态转移：
设x的第k个子节点为y
向x的上方覆盖j层，只需要x的子节点中有一个子节点z能向上覆盖j+1层 即可
所以f的转移有两种：z是前k-1个子节点中的，z是第k个子节点
f[x][j]=min（f[x][j]+g[y][j] ，f[y][j+1]+g[x][j+1]）
g[x][j]+=g[y][j-1]
但是有可能x 再向上恰好覆盖j层的代价要小于再向上恰好覆盖j-1层的代价
即覆盖的更多代价反而要小
所以将f的状态定义改为 向上覆盖至少j层的最小代价
同理，g的状态定义改为还需要覆盖至多j层的最小代价
对f[x][]做一个后缀最小值，g[x][]做一个前缀最小值
代码
#include<cstdio>
#include<iostream>
using namespace std;
#define N 500001
int d;
int w[N];
bool use[N];
int front[N],to[N<<1],nxt[N<<1],tot;
int f[N][22],g[N][22];
void read(int &x)
{
x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}
void add(int u,int v)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;
}
void dfs(int x,int fa)
{
for(int i=1;i<=d;++i) f[x][i]=w[x];
if(use[x]) g[x][0]=f[x][0]=w[x];
f[x][d+1]=1e9;
int t;
for(int i=front[x];i;i=nxt[i])
{
t=to[i];
if(t!=fa)
{
dfs(t,x);
for(int j=0;j<=d;++j) f[x][j]=min(f[x][j]+g[t][j],f[t][j+1]+g[x][j+1]);
for(int j=d;j>=0;--j) f[x][j]=min(f[x][j],f[x][j+1]);
g[x][0]=f[x][0];
for(int j=1;j<=d;++j) g[x][j]+=g[t][j-1];
for(int j=1;j<=d;++j) g[x][j]=min(g[x][j],g[x][j-1]);
}
}
}
int main()
{
int n,m,x;
read(n); read(d);
for(int i=1;i<=n;++i) read(w[i]);
read(m);
while(m--) { read(x); use[x]=true; }
int u,v;
for(int i=1;i<n;++i)
{
read(u); read(v);
add(u,v);
}
dfs(1,0);
printf("%d",g[1][0]);
return 0;
}
T6 普洱茶饼的打包
自己玩去
T7将进酒
source: 洛谷P4138
其实这是一道很好的背包题
费用是一维————————挂钩
但是我没有敢压缩状态，所以开了二维数组
f[i][j]表示前i件物品在有j个挂钩的情况下的最大价值
然后状态转移为f[i][j]=max(f[i-1][j],f[i-1][j-w[i]+1]+v[i])
这是错的
因为j-w[i]+1可能是个负数，没有意义，这时候就要考虑这物品直接挂在手机上即j=1，也就需要我们把j-w[i]和0取最大值保证有意义
所以正解方程为f[i][j]=max(f[i-1][j],f[i-1][max(j-w[i].a,0)+1]+w[i].b);//这里的a是钩子，b是价值
为什么我用结构体呢？
并不是我闲的*疼，而是我们要进行一个排序让钩子多的在前面先计算，这个因为把钩子少的先计算很有可能多次挂在手机上没有意义
然后赋初值
我们应该把不可能的情况赋成极小值即
for(int i=0;i<=n;i++) f[0][i]=MAXN,f[i][n+1]=MAXN;
然后f[0][1]=0这是初始状态
下面贴AC代码
#include<bits/stdc++.h>//注意万能头比赛不能用
using namespace std;
const int MAXN=-1000000000;
int f[3010][3010];//蒙的数据范围
struct wu{
int a,b;
}w[3010];
bool cmp(wu i,wu j){
return i.a>j.a;
}
int ans=-2147483647;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) scanf("%d%d",&w[i].a,&w[i].b);
sort(w+1,w+1+n,cmp);
for(int i=0;i<=n;i++) f[0][i]=MAXN,f[i][n+1]=MAXN;
f[0][1]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
f[i][j]=max(f[i-1][j],f[i-1][max(j-w[i].a,0)+1]+w[i].b);
}
}
for(int i=0;i<=n;i++) ans=max(ans,f[n][i]);//每个钩子都有可能
cout<<ans;
return 0;
}
T8 梦游天姥吟留别
source:洛谷P14406
#include <bits/stdc++.h>
using namespace std;
map<char,int>mp;
int sum[1<<21+1][3],ans=1e9;
inline int query(int i,int k){
if(k==0)return 0;
int l2=pow(4,k-1);
int x1=l2-(sum[l2+i-1][0]-sum[i-1][0]);//不为J的个数
int x2=l2-(sum[l2*2+i-1][1]-sum[i+l2-1][1]);//不为O的个数
int x3=l2-(sum[l2*3+i-1][2]-sum[i+l2*2-1][2]);//不为I的个数
int x4=query(i+l2*3,k-1);//第k-1级不合法的个数
return x1+x2+x3+x4;
}
signed main(){
mp['J']=0,mp['O']=1,mp['I']=2;
int k,len;
cin>>k;
len=pow(4,k);
for(int i=1;i<=len;i++){
char ch;
cin>>ch;
for(int j=0;j<3;j++)
sum[i][j]=sum[i-1][j];
sum[i][mp[ch]]++;
}
for(int i=1;i<=len;i++)
for(int j=0;j<3;j++)
sum[i+len][j]=sum[len][j]+sum[i][j];
for(int i=1;i<=len;i++)
ans=min(ans,query(i,k));
cout<<ans;
return 0;
}
T9 阿房宫赋
source: 洛谷P3645
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=j;i<=k;i++)
#define dFor(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
#define MAXN 30005
int n,m;
vector<int> v[MAXN];
struct Node{
int x,y,s;
};
bitset<MAXN> b[MAXN];
bool check(int x,int y){
return b[x].test(y);
}
bool vis[MAXN];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
int t=-1;
deque<Node> q;
For(i,0,m-1){
int x,y;
cin>>x>>y;
v[x].push_back(y);
if(i==0){
q.push_back({x,y,0});
}
if(i==1){
t=x;
}
}
while(!q.empty()){
int x=q.front().x,y=q.front().y,s=q.front().s;
if(x==t){
cout<<s<<endl;
return 0;
}
q.pop_front();
if(check(x,y)){
continue;
}
b[x].set(y);
if(!vis[x]){
for(int i:v[x]){
if(!check(x,i)){
q.push_front({x,i,s});
}
}
vis[x]=1;
}
if(x-y>=0&&!check(x-y,y)){
q.push_back({x-y,y,s+1});
}
if(x+y<n&&!check(x+y,y)){
q.push_back({x+y,y,s+1});
}
}
cout<<-1<<endl;
return 0;
}
T10
source:洛谷P3531
#include<bits/stdc++.h>
using namespace std;
int c[26][1000001],n,a[1000001],d[26];
long long f[1000001];
int lowbit(int x){
return x&(-x);
}
void insert(int x){
int i;
for(i=x;i<=n;i+=lowbit(i))f[i]++;
}
long long query(int x){
int i;
long long ans=0;
for(i=x;i;i-=lowbit(i))ans+=f[i];
return ans;
}
int main(){
long long ans=0;
int i;
char s[1000001],s1[1000001];
scanf("%d",&n);
scanf("%s",s);
scanf("%s",s1);
for(i=0;i<n;i++)
c[s[i]-'A'][++c[s[i]-'A'][0]]=i;
for(i=0;i<n;i++){
a[i+1]=c[s1[i]-'A'][++d[s1[i]-'A']]+1;
}
for(i=1;i<=n;i++){
//printf("%d\n",i);
ans+=query(n)-query(a[i]-1);
//printf("%d\n",i);
insert(a[i]);
}
printf("%lld",ans);
}
T11
自己玩去
## T1 出师表
source:[洛谷P4216](https://www.luogu.com.cn/problem/P4216)
这是一种题解没有的$ O(m\log n)$ 做法。
首先第一步转化。设这是第$ x $ 个任务，若 $ opt $ 为 $ 1 $，危险值大于 $ c $ 的只有可能在第 $ x-c-1 $ 个任务以前出现。
于是题目就变成了在某一时刻单点加和在某一时刻链上查询，离线即可去掉“某一时刻”。
单点加和链上查询，大家用的应该都是树剖，复杂度是 $ O(\log^2n) $ 的。然而使用 DFS 序和差分，将单点加转化为子树加，将链上查询转化为单点查询。
具体来说就是设一个 $ s[u] $表示节点 $ u $ 到根节点有多少个节点是危险的，那么单点加就可以变成子树加，在 DFS 序上就是区间加。
链上查询只需要查询 $u,v,LCA(u,v),f[LCA(u,v)] $，也就是单点查。
区间加单点查，树状数组上！
极短的代码：
```
#include<cstdio>
#include<vector>
const int M=2e5+5;
int n,m,dfc,d[M],f[M],dfn[M],siz[M],son[M],top[M];
int BIT[M];int opt[M],x[M],y[M],ans[M];
std::vector<int>G[M],id[M];
void DFS1(int u){
dfn[u]=++dfc;d[u]=d[f[u]]+1;siz[u]=1;
for(int&v:G[u]){
DFS1(v);siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void DFS2(int u,int tp){
top[u]=tp;if(!son[u])return;DFS2(son[u],tp);
for(int&v:G[u])if(v!=son[u])DFS2(v,v);
}
inline int LCA(int u,int v){
while(top[u]^top[v]){
if(d[top[u]]>d[top[v]])u=f[top[u]];
else v=f[top[v]];
}
return d[u]>d[v]?v:u;
}
inline int dis(const int&u,const int&v){
return d[u]+d[v]-(d[LCA(u,v)]<<1)+1;
}
inline void Add(int x,const int&val){
for(;x<=n;x+=1<<__builtin_ctz(x))BIT[x]+=val;
}
inline int Query(int x){
int ans=0;
for(;x>=1;x-=1<<__builtin_ctz(x))ans+=BIT[x];
return ans;
}
inline int Q(const int&x,const int&y){
int lca=LCA(x,y);
return Query(dfn[x])+Query(dfn[y])-Query(dfn[lca])-Query(dfn[f[lca]]);
}
signed main(){
register int i,k;
scanf("%d",&n);
for(i=1;i<=n;++i)scanf("%d",f+i),G[f[i]].push_back(i);
for(i=1;f[i];i=f[i]);
DFS1(i);DFS2(i,i);
scanf("%d",&m);
for(i=1;i<=m;++i){
scanf("%d",opt+i);
if(opt[i]==1){
scanf("%d%d%d",x+i,y+i,&k);
if(k<i)id[i-k-1].push_back(i);
}
if(opt[i]==2){
scanf("%d",x+i);
}
}
for(i=1;i<=m;++i){
if(opt[i]==2){
Add(dfn[x[i]],1);Add(dfn[x[i]]+siz[x[i]],-1);
}
for(int&v:id[i])ans[v]=Q(x[v],y[v]);
if(opt[i]==1){
printf("%d %d\n",dis(x[i],y[i]),ans[i]);
}
}
}
```
## T2 滕王阁序
source:[洛谷P1852跳跳棋](https://www.luogu.com.cn/problem/P1852)
不得不说，这题建模极为抽象了，出题人太神了。看了好多篇题解才懂，自己也写一篇比较详细的吧
相信大家都玩过跳棋，有一个规则想必大家都知道，就是一次跳跃不能跳过两颗棋子
这个限制是解决这题的关键，有了这个限制，可以看出，对于两边的棋子，只能跳到其余两颗的中间，同样的中间的棋子也只能跳到两边
为了方便，我们将三个棋子标号，分别为x,y,z，且x<y<z。
移动棋子无非就四种讨论
$(x,y,z)⟹(2x−y,x,z) $
$(x,y,z)⟹(x,z,2z−y) $
$(x,y,z)⟹(y,2y−x,z) $
$(x,y,z)⟹(x,2y−z,y) $
因为有了不能一次跳过两颗棋的限制，所以第三种情况和第四种情况必然起了冲突
不妨设d1=y−x,d2=z−y，易得
$d1<d2:则 (x,y,z)⟹(y,2y−x,z) $
$d1>d2:则 (x,y,z)⟹(x,2y−z,y) $
也就是说我们对于每种状态只有三种转移方式
我们再看看这三个式子，可以发现，对于第一种和第二种情况，我们将中间的点向两边跳，相当于扩大了边界。而第三种两边向里面跳则恰恰相反，是将边界缩小了
是不是很像一棵二叉树？
现在可能还不够明显，我们再接下去推
有一个很显然的性质，边界不可能无限变小。也就是说缩着缩着会遇到一种情况不能再缩了，我们来思考一下什么情况不能再缩了
观察式子：
$d1<d2:则 (x,y,z)⟹(y,2y−x,z)$
$d1>d2:则 (x,y,z)⟹(x,2y−z,y)$
惊奇的发现，我们这样讨论漏了一种情况，d1=d2
这个非常好理解，如果d1=d2，那么x必然会与z跳到同一个点，而这是不符合题目描述的。所以当d1=d2时，这个状态只能由中间向两边跳，也就是只有两个转移状态，想想这个状态在二叉树中像什么？没错，根节点我们就这样找到了，二叉树的形态就像下图所示：
可以发现，对于每一组(x,y,z)都有唯一对应的一个根，而且二叉树之间的任意一组(x,y,z)都可以互相转化，而且转化的操作次数就等于两个状态在树上的距离
所以如果初始(x,y,z)的树根和目标(x,y,z)的树根不相同，那么就是No，因为无论怎么跳都出不去这棵树的范围，而根不同则说明树不同
所以对于初始(x,y,z)和目标(x ,y,z)，我们只要求出它们的LCA，答案就是初始点到LCA的距离+ LCA到目标点的距离
不过因为范围太大，树无法存下，普通的LCA求法树剖、倍增等已经无法使用了
我们先不急着求LCA，来想想另一个问题
初始状态：(1,10,11)
目标状态：(1,2,3)
人脑模拟一下程序，d1>d2，转换成(1,9,10)，(d1>d2)，转换成(1,8,9)，d1>d2，转换成(1,7,8),⋯⋯
如果改成(1,inf−1,inf)呢？
显然要T飞
不过我们发现，一直在重复一个操作，所以可以将这些操作压缩
我们只讨论d1>d2的情况，d1<d2其实差不多
易发现，要连续跳(d1−1)/d2次同样的操作（每一次跳d2的距离，但又不能超越或跳到x，也就是总距离为(d1−1)，总次数故为(d1−1)/d2）
设：d3=(d1−1)/d2
所以最后是(x,y−d3⋅d1,z−d3⋅d1)
这样我们就大大的压缩了路径，但这样又有什么用呢？我们回到树上来
因为路径被压缩了，所以我们可以换种方法求LCA
方便起见，我们先将初始状态跳到和目标状态在树中的高度一致（如果目标状态高度更高我们就换一下，在树中的距离是没有方向的）
也是初始状态要向上跳DepT−DepS次（Dep表示深度，S和T分别表示起始状态和目标状态），而跳跃的操作我们就可以用压缩路径快速实现
好了，现在两个状态高度相同了
有个显然的性质，如果两个状态同时向上跳x次所跳到的节点相同，那么同时向上跳x+1次所跳到的节点也相同，也就是说明满足单调性。所以我们可以用二分来枚举最小的x满足了两个状态同时向上跳x次所跳到的节点相同，所以LCA就是两个同时向上跳x次所跳到的节点
然后就愉快的AC了
码量小但细节是真的多，思维难度也很好，总而言之就是一道质量非常高的建模LCA+二分的题目
如果有哪步我打错了，或者有一些没有理解的地方，欢迎私信或留言！
参考代码：
```c++
#include<bits/stdc++.h>
using namespace std;
int Cnt,Ans,d1,d2,d3,x,y,z,L,R,X,Y,Z,tot,a[5];
struct lc{
int x,y,z,tot;
}A,B;
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-f;ch=getchar();}
while (ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
inline void Dfs(int x,int y,int z){
tot=0;
while (1){
d1=y-x,d2=z-y;
if (d1==d2) break;
if (d1>d2) d3=(d1-1)/d2,tot+=d3,y-=d3*d2,z-=d3*d2;
else d3=(d2-1)/d1,tot+=d3,x+=d3*d1,y+=d3*d1;
}
if (A.x||A.y) B=(lc){x,y,z,tot};
else A=(lc){x,y,z,tot};
}
inline void Swap(){
swap(x,X),swap(y,Y),swap(z,Z);
swap(A.x,B.x),swap(A.y,B.y),swap(A.z,B.z),swap(A.tot,B.tot);
}
inline bool check(int T,int x,int y,int z,int X,int Y,int Z){
tot=T;
while (tot){
d1=y-x,d2=z-y;
if (d1==d2) break;
if (d1>d2) d3=min((d1-1)/d2,tot),tot-=d3,y-=d3*d2,z-=d3*d2;
else d3=min((d2-1)/d1,tot),tot-=d3,x+=d3*d1,y+=d3*d1;
}
tot=T;
while (tot){
d1=Y-X,d2=Z-Y;
if (d1==d2) break;
if (d1>d2) d3=min((d1-1)/d2,tot),tot-=d3,Y-=d3*d2,Z-=d3*d2;
else d3=min((d2-1)/d1,tot),tot-=d3,X+=d3*d1,Y+=d3*d1;
}
return X==x&&Y==y&&Z==z;
}
int main(){
for (int i=1;i<=3;i++) a[i]=read();
sort(a+1,a+4);x=a[1],y=a[2],z=a[3];
for (int i=1;i<=3;i++) a[i]=read();
sort(a+1,a+4);X=a[1],Y=a[2],Z=a[3];
Dfs(x,y,z);Dfs(X,Y,Z);
if (A.x!=B.x||A.y!=B.y||A.z!=B.z){printf("NO");return 0;}
if (A.tot<B.tot) Swap();
Ans=tot=A.tot-B.tot;
while (tot){
d1=y-x,d2=z-y;
if (d1==d2) break;
if (d1>d2) d3=min((d1-1)/d2,tot),tot-=d3,y-=d3*d2,z-=d3*d2;
else d3=min((d2-1)/d1,tot),tot-=d3,x+=d3*d1,y+=d3*d1;
}
L=0,R=B.tot;
while (L<=R){
int mid=L+R>>1;
if (check(mid,x,y,z,X,Y,Z)) Cnt=mid,R=mid-1;
else L=mid+1;
}
printf("YES\n%d",Ans+Cnt*2);
return 0;
}
```
# 先放T1和T2其他等会再放
## T3见手青的幻觉
自己玩去
## T4蜀道难
source:[洛谷P2329](https://www.luogu.com.cn/problem/P2329)
这题的总体思路是：二分答案+贪心+dfs验证 首先，二分答案是不用说的，就看贪心和dfs验证。 如果要使得John得到至少m个木材，那么当然是选择最短的啦。所以可以提前把John需要的木材按规格从小到大排序，这就是贪心。
然后dfs就是如果能提供的木材有比John需要的第x根木材的规格大的（或相等的），那么就试试把这根木材中John需要的部分卖给他。不过……
第一行为整数m(m<= 50)表示木材店老板可以提供多少块木材给约翰。
这么大的数，不超时才怪勒！所以我们需要剪枝。有两个剪枝：
可行性剪枝，如果剩余的木材都不够John的需要，则return，所以这里需要用到前缀和，还要一个变量存储浪费的木材（即连最短的一根木材都不够）
去重，如果两根木材的规格相同，则可以去重。
有了这两个剪枝，就可以玄学地过了这题了！
上代码！
```c++
#include<bits/stdc++.h>
using namespace std;
int n,m,a[55],b[1100];
int w,l,r,mid,tot,sum[1100];//w是多余的木材，tot是总共能提供的木材的量，sum是John需要的木材的前缀和
bool dfs(int x,int l)
{
if(tot-w<sum[mid]) return 0;//第一个剪枝
if(x==0) return 1;//x=0表示还需要0根，也就是可以满足条件了，那么返回true
bool f=0;
for(int i=l;i<=n;i++)
if(a[i]>=b[x])//如果第i根木材可以满足John需要的第x根木材，dfs
{
a[i]-=b[x];
if(a[i]<b[1]) w+=a[i];
if(b[x-1]==b[x]) f=dfs(x-1,i);//去重
else f=dfs(x-1,1);
if(a[i]<b[1]) w-=a[i];
a[i]+=b[x];
if(f) return 1;
}
return 0;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
tot+=a[i];
}
cin>>m;
for(int i=1;i<=m;i++) cin>>b[i];
sort(b+1,b+m+1);//排序
for(int i=1;i<=m;i++) sum[i]=sum[i-1]+b[i];//计算前缀和，注意一定要在排序后计算哦！
while(sum[m]>tot&&m) m--;//如果选最短的m根都超出了能提供的木材的范围，则一定不可行
l=0,r=m;
while(l<=r)//二分
{
mid=(l+r)/2;
if(dfs(mid,1)) l=mid+1;
else r=mid-1;
}
cout<<l-1;
return 0;
}
```
## T5 琵琶行
source:[洛谷P3276](https://www.luogu.com.cn/problem/P3267)
假设当前到了x的子树，现在是合并 x的第k个子树
f[x][j] 表示x的前k-1个子树该覆盖的完全覆盖，而且还能向上覆盖j层的最小代价
这个向上是针对x来说的，即可以向x的祖先方向再覆盖j层
对于第k个子树的意义就是，兄弟子树放置的守卫可以帮x的第k个子树覆盖前j层（第1层为x的子节点）
那么相应的就要有一个状态来表示这个 可以让兄弟子树 帮忙覆盖 的前j层
g[x][j] 表示还需要覆盖x的前k个子树中的前j层，且第j层以下该覆盖的完全覆盖（第1层为x）的最小代价
状态转移：
设x的第k个子节点为y
向x的上方覆盖j层，只需要x的子节点中有一个子节点z能向上覆盖j+1层 即可
所以f的转移有两种：z是前k-1个子节点中的，z是第k个子节点
f[x][j]=min（f[x][j]+g[y][j] ，f[y][j+1]+g[x][j+1]）
g[x][j]+=g[y][j-1]
但是有可能x 再向上恰好覆盖j层的代价要小于再向上恰好覆盖j-1层的代价
即覆盖的更多代价反而要小
所以将f的状态定义改为 向上覆盖至少j层的最小代价
同理，g的状态定义改为还需要覆盖至多j层的最小代价
对f[x][]做一个后缀最小值，g[x][]做一个前缀最小值
代码
```c++
#include<cstdio>
#include<iostream>
using namespace std;
#define N 500001
int d;
int w[N];
bool use[N];
int front[N],to[N<<1],nxt[N<<1],tot;
int f[N][22],g[N][22];
void read(int &x)
{
x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}
void add(int u,int v)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;
}
void dfs(int x,int fa)
{
for(int i=1;i<=d;++i) f[x][i]=w[x];
if(use[x]) g[x][0]=f[x][0]=w[x];
f[x][d+1]=1e9;
int t;
for(int i=front[x];i;i=nxt[i])
{
t=to[i];
if(t!=fa)
{
dfs(t,x);
for(int j=0;j<=d;++j) f[x][j]=min(f[x][j]+g[t][j],f[t][j+1]+g[x][j+1]);
for(int j=d;j>=0;--j) f[x][j]=min(f[x][j],f[x][j+1]);
g[x][0]=f[x][0];
for(int j=1;j<=d;++j) g[x][j]+=g[t][j-1];
for(int j=1;j<=d;++j) g[x][j]=min(g[x][j],g[x][j-1]);
}
}
}
int main()
{
int n,m,x;
read(n); read(d);
for(int i=1;i<=n;++i) read(w[i]);
read(m);
while(m--) { read(x); use[x]=true; }
int u,v;
for(int i=1;i<n;++i)
{
read(u); read(v);
add(u,v);
}
dfs(1,0);
printf("%d",g[1][0]);
return 0;
}
```
## T6 普洱茶饼的打包
自己玩去
## T7将进酒
source: [洛谷P4138](https://www.luogu.com.cn/problem/P4138)
其实这是一道很好的背包题
费用是一维————————挂钩
但是我没有敢压缩状态，所以开了二维数组
f[i][j]表示前i件物品在有j个挂钩的情况下的最大价值
然后状态转移为f[i][j]=max(f[i-1][j],f[i-1][j-w[i]+1]+v[i])
这是错的
因为j-w[i]+1可能是个负数，没有意义，这时候就要考虑这物品直接挂在手机上即j=1，也就需要我们把j-w[i]和0取最大值保证有意义
所以正解方程为f[i][j]=max(f[i-1][j],f[i-1][max(j-w[i].a,0)+1]+w[i].b);//这里的a是钩子，b是价值
为什么我用结构体呢？
并不是我闲的*疼，而是我们要进行一个排序让钩子多的在前面先计算，这个因为把钩子少的先计算很有可能多次挂在手机上没有意义
然后赋初值
我们应该把不可能的情况赋成极小值即
for(int i=0;i<=n;i++) f[0][i]=MAXN,f[i][n+1]=MAXN;
然后f[0][1]=0这是初始状态
下面贴AC代码
```c++
#include<bits/stdc++.h>//注意万能头比赛不能用
using namespace std;
const int MAXN=-1000000000;
int f[3010][3010];//蒙的数据范围
struct wu{
int a,b;
}w[3010];
bool cmp(wu i,wu j){
return i.a>j.a;
}
int ans=-2147483647;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) scanf("%d%d",&w[i].a,&w[i].b);
sort(w+1,w+1+n,cmp);
for(int i=0;i<=n;i++) f[0][i]=MAXN,f[i][n+1]=MAXN;
f[0][1]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
f[i][j]=max(f[i-1][j],f[i-1][max(j-w[i].a,0)+1]+w[i].b);
}
}
for(int i=0;i<=n;i++) ans=max(ans,f[n][i]);//每个钩子都有可能
cout<<ans;
return 0;
}
```
## T8 梦游天姥吟留别
source:[洛谷P14406](https://www.luogu.com.cn/problem/P14406)
```c++
#include <bits/stdc++.h>
using namespace std;
map<char,int>mp;
int sum[1<<21+1][3],ans=1e9;
inline int query(int i,int k){
if(k==0)return 0;
int l2=pow(4,k-1);
int x1=l2-(sum[l2+i-1][0]-sum[i-1][0]);//不为J的个数
int x2=l2-(sum[l2*2+i-1][1]-sum[i+l2-1][1]);//不为O的个数
int x3=l2-(sum[l2*3+i-1][2]-sum[i+l2*2-1][2]);//不为I的个数
int x4=query(i+l2*3,k-1);//第k-1级不合法的个数
return x1+x2+x3+x4;
}
signed main(){
mp['J']=0,mp['O']=1,mp['I']=2;
int k,len;
cin>>k;
len=pow(4,k);
for(int i=1;i<=len;i++){
char ch;
cin>>ch;
for(int j=0;j<3;j++)
sum[i][j]=sum[i-1][j];
sum[i][mp[ch]]++;
}
for(int i=1;i<=len;i++)
for(int j=0;j<3;j++)
sum[i+len][j]=sum[len][j]+sum[i][j];
for(int i=1;i<=len;i++)
ans=min(ans,query(i,k));
cout<<ans;
return 0;
}
```
## T9 阿房宫赋
source: [洛谷P3645](https://www.luogu.com.cn/problem/P3645)
```c++
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=j;i<=k;i++)
#define dFor(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
#define MAXN 30005
int n,m;
vector<int> v[MAXN];
struct Node{
int x,y,s;
};
bitset<MAXN> b[MAXN];
bool check(int x,int y){
return b[x].test(y);
}
bool vis[MAXN];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
int t=-1;
deque<Node> q;
For(i,0,m-1){
int x,y;
cin>>x>>y;
v[x].push_back(y);
if(i==0){
q.push_back({x,y,0});
}
if(i==1){
t=x;
}
}
while(!q.empty()){
int x=q.front().x,y=q.front().y,s=q.front().s;
if(x==t){
cout<<s<<endl;
return 0;
}
q.pop_front();
if(check(x,y)){
continue;
}
b[x].set(y);
if(!vis[x]){
for(int i:v[x]){
if(!check(x,i)){
q.push_front({x,i,s});
}
}
vis[x]=1;
}
if(x-y>=0&&!check(x-y,y)){
q.push_back({x-y,y,s+1});
}
if(x+y<n&&!check(x+y,y)){
q.push_back({x+y,y,s+1});
}
}
cout<<-1<<endl;
return 0;
}
```
## T10
source:[洛谷P3531](https://www.luogu.com.cn/problem/P3531)
```c++
#include<bits/stdc++.h>
using namespace std;
int c[26][1000001],n,a[1000001],d[26];
long long f[1000001];
int lowbit(int x){
return x&(-x);
}
void insert(int x){
int i;
for(i=x;i<=n;i+=lowbit(i))f[i]++;
}
long long query(int x){
int i;
long long ans=0;
for(i=x;i;i-=lowbit(i))ans+=f[i];
return ans;
}
int main(){
long long ans=0;
int i;
char s[1000001],s1[1000001];
scanf("%d",&n);
scanf("%s",s);
scanf("%s",s1);
for(i=0;i<n;i++)
c[s[i]-'A'][++c[s[i]-'A'][0]]=i;
for(i=0;i<n;i++){
a[i+1]=c[s1[i]-'A'][++d[s1[i]-'A']]+1;
}
for(i=1;i<=n;i++){
//printf("%d\n",i);
ans+=query(n)-query(a[i]-1);
//printf("%d\n",i);
insert(a[i]);
}
printf("%lld",ans);
}
```
## T11
自己玩去
