noip2015
神奇的幻方
一个模拟 不肖细说
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
rd(n);
for(int i=1,x=1,y=(n+1)>>1;i<=n*n;++i){
mp[x--][y++]=i;
if(!x) (y>n)?(x=2,y=n):x=n;
else if(y>n) y=1;
else if(mp[x][y]) x+=2,--y;
}
for(int i=1;i<=n;++i,puts(""))
for(int j=1;j<=n;++j) printf("%d ",mp[i][j]);
return 0;
}
信息传递
tarjan？
int head[N],tot=0;
struct edge{int v,nxt;}e[N];
void add(int u,int v){e[++tot]=(edge){v,head[u]},head[u]=tot;}
void tarjan(int u){
dfn[u]=low[u]=++idx;
s.push(u),inst[u]=1;
for(int i=head[u],v;i;i=e[i].nxt)
if(!dfn[v=e[i].v]) tarjan(v),low[u]=Min(low[u],low[v]);
else if(inst[v]&&dfn[v]<low[u]) low[u]=dfn[v];
if(dfn[u]==low[u]){
int v;++Bcnt;
do{
v=s.top(),s.pop();
++sz[Bcnt],inst[v]=0,bl[v]=Bcnt;
}while(v!=u);
}
}
int main(){
rd(n);
for(int i=1,v;i<=n;++i) rd(v),add(i,v);
for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
for(int i=1;i<=Bcnt;++i)
if(sz[i]>1) ans=Min(ans,sz[i]);
printf("%d",ans);
return 0;
}
斗地主
不想写 lxy一点也不想写
有时间来练练搜索叭==
跳石头
二分
bool check(int x){
for(int i=0;i<=n;i++){
int tot=1;
while(use[i+tot]) ++tot;
while(a[i+tot]-a[i]<x&&i+tot<=n+1){
use[i+tot]=1,tot++,cnt++;
if(cnt>m) return 0;
}
i+=(tot-1);
}
return 1;
}
int main(){
l=rd(),n=rd(),m=rd();
mn=inf,a[0]=mx=0,a[n+1]=l;
for(int i=1;i<=n;i++) rd(a[i]);
mx=l,mn=0;
while(mn<=mx){
mid=(mx+mn)>>1;
memset(use,0,sizeof(use));cnt=0;
if(check(mid)) mn=mid+1;
else mx=mid-1;
}
printf("%d",mn-1);
return 0;
}
子串
加了滚动数组优化
(f[i][j][k][0/1])表示当前考虑到(A)串第(i)位不选/选 匹配到(B)串第(j)位用了(A)串(k)个子串的方案数
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
rd(n),rd(m),rd(K);
scanf("%s%s",a+1,b+1);
f[0][0][0][0]=f[1][0][0][0]=1;
for(int i=1,nw=1;i<=n;++i,nw^=1)
for(int j=1;j<=m;++j)
for(int k=1;k<=K;++k)
if(a[i]==b[j])
f[nw][j][k][0]=(f[nw^1][j][k][0]+f[nw^1][j][k][1])%P,
f[nw][j][k][1]=(f[nw^1][j-1][k][1]+(f[nw^1][j-1][k-1][0]+f[nw^1][j-1][k-1][1])%P)%P;
else f[nw][j][k][0]=(f[nw^1][j][k][0]+f[nw^1][j][k][1])%P,f[nw][j][k][1]=0;
printf("%d",(f[n&1][m][K][0]+f[n&1][m][K][1])%P);
return 0;
}
运输计划
二分+LCA+树上差分
struct node{int x,y,lca,dis;}q[M];
int tot=0,head[N];
struct edge{int v,w,nxt;}e[N<<1];
void add(int u,int v,int w){e[++tot]=(edge){v,w,head[u]},head[u]=tot;}
int dis[N],val[N],dep[N],f[N][20];
void dfs(int u,int ff){
for(int i=head[u],v;i;i=e[i].nxt)
if((v=e[i].v)!=ff) dis[v]=dis[f[v][0]=u]+(val[v]=e[i].w),dep[v]=dep[u]+1,dfs(v,u);
}
void doubling(){
for(int j=1;j<=19;++j)
for(int i=1;i<=n;++i)
if(dep[i]>=1<<j) f[i][j]=f[f[i][j-1]][j-1];
}
int LCA(int x,int y){
if(dep[x]>dep[y]) swap(x,y);
for(int i=19;i>=0;--i)
if(dep[f[y][i]]>=dep[x]) y=f[y][i];
if(x==y) return x;
for(int i=19;i>=0;--i)
if(f[x][i]^f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int mxl,mxw,cnt[N];
void dfs2(int u,int ff){
for(int i=head[u],v;i;i=e[i].nxt)
if((v=e[i].v)!=ff) dfs2(v,u),cnt[u]+=cnt[v];
}
bool check(int mid){
memset(cnt,0,sizeof(cnt)),mxl=mxw=0;
for(int i=1;i<=m;++i)
if(q[i].dis>mid) ++cnt[q[i].x],++cnt[q[i].y],cnt[q[i].lca]-=2,mxl=Max(mxl,q[i].dis),++cnt[0];
dfs2(1,0);
for(int i=2;i<=n;++i)
if(cnt[i]==cnt[0]) mxw=Max(mxw,val[i]);
return mxl-mxw<=mid;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
rd(n),rd(m);
for(int i=1,u,v,w;i<n;++i) rd(u),rd(v),rd(w),add(u,v,w),add(v,u,w);
dep[1]=1,dfs(1,0),doubling();
int l=0,r,mid,ans;
for(int i=1,x,y,lca;i<=m;++i) rd(x),rd(y),lca=LCA(x,y),q[i]=(node){x,y,lca,dis[x]+dis[y]-(dis[lca]<<1)},r=Max(r,q[i].dis);
while(l<=r){
mid=l+r>>1;
if(check(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
printf("%d",ans);
return 0;
}