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;
}