https://www.luogu.org/problem/lists?name=&orderitem=pid&tag=33%2C83
T1:玩具谜题
题解：
沙茶模拟
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=1e5+,INF=1e9+;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,a,s;
struct toy{
int d;
char s[];
}t[N];
int main(){
n=read();m=read();
for(int i=;i<n;i++){t[i].d=read();scanf("%s",t[i].s);}
int now=;
while(m--){ //printf("now %d\n",now);
a=read();s=read();
if(t[now].d==){
if(a==) now=(now-s+n)%n;
else now=(now+s)%n;
}else{
if(a==) now=(now+s)%n;
else now=(now-s+n)%n;
}
}
printf("%s",t[now].s);
return ;
}
mengbier
T2:天天爱跑步
题解：
现在基本上能想出思路，但是写了三节课...............
对于一个点j，能被他观察到的也就是他的子树中 ds-dj=wj或者dt-dj=len(s,t)-wj
就是 ds=dj+wj或dt-len(s,t)=dj-wj
只有j是改变的，然后只要找每个点的子树中满足那两个条件的端点个数就可以了
统计个数直接开个权值数组，遇到s或t就加，遇到lca就减(之外的节点不可能被这个lca的s和t贡献了)
对于一条路线，在S和T分别打两个tag，并在lca处回收tag
因为一个节点会被多次，所以每个节点u开一个链表，保存有那些s是u，那些t是u，那些lca是u
但是这样lca(s,t)这个点就不会受到s或t的贡献了(加了后又回收了)，所以把s或t的回收放在fa[lca]就可以了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=3e5+,M=3e5+,INF=1e9+,B=3e5+;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} int n,m,u,v,w[N],s,t;
struct edge{
int v,ne;
}e[M<<];
int cnt,h[N];
inline void ins(int u,int v){
cnt++;
e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
cnt++;
e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;
}
struct thing{
int w,ne;
}e1[N],e2[N],e3[N],e4[N];
int cnt1,cnt2,cnt3,cnt4,h1[N],h2[N],h3[N],h4[N];
inline void ins1(int u,int v,int w){
cnt1++;
e1[cnt1].w=w;e1[cnt1].ne=h1[u];h1[u]=cnt1;
cnt3++;
e3[cnt3].w=w;e3[cnt3].ne=h3[v];h3[v]=cnt3;
}
inline void ins2(int u,int v,int w){
cnt2++;
e2[cnt2].w=w;e2[cnt2].ne=h2[u];h2[u]=cnt2;
cnt4++;
e4[cnt4].w=w;e4[cnt4].ne=h4[v];h4[v]=cnt4;
}
int vis[N],deep[N],fa[N][];
void dfs(int u){
vis[u]=;
for(int j=;j<=;j++)
fa[u][j]=fa[fa[u][j-]][j-]; for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(vis[v]) continue;
fa[v][]=u;
deep[v]=deep[u]+;
dfs(v);
}
}
int lca(int x,int y){
if(deep[x]<deep[y]) swap(x,y);
int bin=deep[x]-deep[y];
for(int i=;i<=;i++)
if((<<i)&bin) x=fa[x][i]; for(int i=;i>=;i--)
if(fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
}
if(x==y) return x;
else return fa[x][];
}
int c1[N<<],c2[N<<];
int ans[N];
void dfsSol(int u,int fa){
int p1=w[u]+deep[u],p2=deep[u]-w[u]+B;
ans[u]-=c1[p1]+c2[p2];
for(int i=h[u];i;i=e[i].ne)
if(e[i].v!=fa) dfsSol(e[i].v,u);
for(int i=h1[u];i;i=e1[i].ne) c1[e1[i].w]++;
for(int i=h3[u];i;i=e3[i].ne) c1[e3[i].w]--;
for(int i=h2[u];i;i=e2[i].ne) c2[e2[i].w]++;
for(int i=h4[u];i;i=e4[i].ne) c2[e4[i].w]--;
ans[u]+=c1[p1]+c2[p2];
}
int main(){
freopen("in.txt","r",stdin);
n=read();m=read();
for(int i=;i<=n-;i++) u=read(),v=read(),ins(u,v);
for(int i=;i<=n;i++) w[i]=read();
dfs();
for(int i=;i<=m;i++){
s=read();t=read();
int a=lca(s,t),len=deep[s]+deep[t]-deep[a]-deep[a];
ins1(s,fa[a][],deep[s]);
ins2(t,a,deep[t]-len+B);
//printf("lca %d %d %d %d %d\n",i,s,t,a,len);
}
dfsSol(,);
for(int i=;i<n;i++) printf("%d ",ans[i]);printf("%d",ans[n]);
}
天天是谁
T3:换教室
题解：
真的是道好水的DP：f[i][j][0/1]表示到了时间段i申请了j次，转移看这次和上次申请成不成功行了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int NN=,N=;
const double INF=1e9+;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int tn,tm,n,m,c[NN],d[NN],g[N][N],u,v,w;
double k[NN];
void floyd(){
for(int k=;k<=n;k++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
} double f[NN][NN][];
void dp(){
for(int i=;i<=tn;i++)
for(int j=;j<=tm;j++) f[i][j][]=f[i][j][]=INF;
f[][][]=;
for(int i=;i<=tn;i++)
for(int j=;j<=tm;j++){//printf("hi %d %d %.2f %.2f\n",i,j,f[i][j][0],f[i][j][1]);
f[i][j][]=min(f[i-][j][]+g[c[i-]][c[i]],
f[i-][j][]+g[d[i-]][c[i]]*k[i-]+g[c[i-]][c[i]]*(-k[i-]));
if(j>) f[i][j][]=f[i-][j-][]+g[c[i-]][d[i]]*k[i]+g[c[i-]][c[i]]*(-k[i]);
if(j>) f[i][j][]=min(f[i][j][],f[i-][j-][]+k[i-]*(g[d[i-]][d[i]]*k[i]+g[d[i-]][c[i]]*(-k[i]))+
(-k[i-])*(g[c[i-]][d[i]]*k[i]+g[c[i-]][c[i]]*(-k[i])));
}
double ans=INF;
for(int j=;j<=tm;j++) ans=min(ans,min(f[tn][j][],f[tn][j][]));
printf("%.2f",ans);
}
int main(){
//freopen("in.txt","r",stdin);
tn=read();tm=read();n=read();m=read();
for(int i=;i<=tn;i++) c[i]=read();
for(int i=;i<=tn;i++) d[i]=read();
for(int i=;i<=tn;i++) scanf("%lf",&k[i]);
for(int i=;i<=n;i++) for(int j=i+;j<=n;j++) g[i][j]=g[j][i]=INF;
for(int i=;i<=m;i++){
u=read();v=read();w=read();
if(u!=v) g[u][v]=g[v][u]=min(g[u][v],w);
}
floyd();
dp();
}
啦啦啦期望