NOIP2015 提高组合集

NOIP 2015 提高组合集

D1 T1 神奇的幻方

题目让你干啥你就干啥，让你咋走你就咋走就完事儿了

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 50

using namespace std;

struct Node

{

    int x,y;

}a[N*N];

int ans[N][N];

int main()

{

    int n; cin >> n ;

    a[1].x=1; a[1].y=n/2+1; ans[1][n/2+1]=1;

    for(int i=2;i<=n*n;i++)

    {

        if(a[i-1].x==1&&a[i-1].y!=n)

        {

            ans[n][a[i-1].y+1]=i;

            a[i].x=n; a[i].y=a[i-1].y+1;

        }

        else if(a[i-1].x!=1&&a[i-1].y==n)

        {

            ans[a[i-1].x-1][1]=i;

            a[i].x=a[i-1].x-1; a[i].y=1;

        }

        else if(a[i-1].x==1&&a[i-1].y==n)

        {

            ans[a[i-1].x+1][a[i-1].y]=i;

            a[i].x=a[i-1].x+1; a[i].y=a[i-1].y;

        }

        else

        {

            if(!ans[a[i-1].x-1][a[i-1].y+1])

            {

                ans[a[i-1].x-1][a[i-1].y+1]=i;

                a[i].x=a[i-1].x-1; a[i].y=a[i-1].y+1;

            }

            else

            {

                ans[a[i-1].x+1][a[i-1].y]=i;

                a[i].x=a[i-1].x+1; a[i].y=a[i-1].y;

            }

        }

    }

    for(int i=1;i<=n;i++)

    {

        for(int j=1;j<=n;j++) printf("%d ",ans[i][j]);

        puts("");

    }

}

D1 T2 信息传递

由题目的描述，我们发现这是一个基环内向森林。题目中问的是最多进行多少局，等价于求基环内向森林中所有基环的最小值。模拟即可。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 200001

using namespace std;

int a[N],f[N],v[N];

inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}

int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}

int main()

{

    int n=rd(),p,t,ans=0x7f7f7f7f;

    for(int i=1;i<=n;i++) a[i]=rd();

    for(int i=1;i<=n;i++)

    {

        v[i]=1,t=i,p=a[i];

        while(f[p]!=i)

        {

            if(f[p]!=0&&f[p]<i) break;

            v[p]=v[t]+1,f[t]=i;

            t=p,p=a[t];

        }

        if(f[p]==i&&ans>v[t]+1-v[p]) ans=v[t]+1-v[p];

    }

    printf("%d",ans);

    return 0;

}

D1 T3 斗地主

挖坑代填

D2 T1 跳石头

二分答案，二分出最大可能值，然后暴力验证

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int L,n,m,a[50010];

inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}

int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}

int check(int dist)

{

    int last=0,cnt=0;

    for(int i=1;i<=n;i++)

    {

        if(a[i]-last<dist)cnt++;

        else last=a[i];

    }

    if(L-last<dist) cnt++;

    return cnt<=m;

}

int main()

{

    L=rd(),n=rd(),m=rd(); for(int i=1;i<=n;i++) a[i]=rd();

    sort(a+1,a+1+n);

    int l=1,r=L+1;

    while(l+1<r)

    {

        int mid=(l+r)>>1;

        if(check(mid))l=mid;

        else r=mid;

    }

    printf("%d\n",l);

}

D2 T2 子串

动态规划

f[i][j][k]表示当前：A串枚举到了i，B串枚举到了j，已经找到了k个串切使用了a[i]的方案数。

g[i][j][k]................................不管使不使用a[i]的方案数。

然后因为空间问题，f[i][j][k]，i压滚动。

转移sb

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define mod 1000000007

#define N 210

using namespace std;

int f[2][N][N],g[2][N][N];

char s1[10010],s2[10010];

int main()

{

    int n,m,k; cin >> n >> m >> k ; scanf("%s%s",s1+1,s2+1);

    int pre=1;

    g[1][0][0]=1;

    for(int i=1;i<=n;i++)

    {

        // puts("Fuck");

        pre^=1;

        g[pre][0][0]=1;

        for(int j=1;j<=m;j++)

        {

            for(int l=1;l<=k;l++)

            {

                if(s1[i]==s2[j]) (f[pre][j][l]=g[pre^1][j-1][l-1]+f[pre^1][j-1][l])%=mod;

                else f[pre][j][l]=0;

                (g[pre][j][l]=f[pre][j][l]+g[pre^1][j][l])%=mod;

                // if(f[pre][j][l]) printf("%d %d %d\n",i,j,l);

            }

        }

    }

    printf("%d\n",g[pre][m][k]);

    return 0;

}

D2 T3 运输计划

一眼二分答案，关键是怎么验证。首先，我们对于每次询问，都记录出：这个询问在不建立虫洞的情况下的长度。

紧接着根据我们二分出的mid，对于一次距离大于mid的询问树上查分，记录每条边被多少询问累计过。

然后我们边权下放到点权，对于每条被所有大于mid的询问经过的边，我们判断：是不是长度最长的询问减去这条边对应的边权在mid内即可。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 300010

#define M 300010

using namespace std; int n,m;

inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}

int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+c-'0',c=nc(); return x;}

struct Line {int x,y,v,lca;}L[M]; inline bool cmp(const Line &x,const Line &y) {return x.v<y.v;}

int dis[N],size[N],dic[N],o[N],dep[N],f[N][30],cnt;

int to[N<<1],val[N<<1],nxt[N<<1],head[N],tot; int udr[N],top[N];

inline void add(int x,int y,int z) {to[++tot]=y; val[tot]=z; nxt[tot]=head[x]; head[x]=tot;}

void dfs(int pos,int fa)

{

    dic[++cnt]=pos;

    f[pos][0]=fa; for(int i=1;i<=25;i++) f[pos][i]=f[f[pos][i-1]][i-1];

    size[pos]=1; dep[pos]=dep[fa]+1; for(int i=head[pos];i;i=nxt[i]) if(to[i]!=fa)

    {

        dis[to[i]]=dis[pos]+val[i];

        dfs(to[i],pos); udr[i]=to[i],top[to[i]]=val[i];

    }

    dic[++cnt]=pos;

}

int lca(int x,int y)

{

    if(dep[x]<dep[y]) swap(x,y);

    for(int i=25;~i;i--)

    {

        if(dep[f[x][i]]>=dep[y]) x=f[x][i];

    }

    if(x==y) return x;

    for(int i=25;~i;i--)

    {

        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];

    }

    return f[x][0];

}

void dfs_check(int pos,int fa)

{

    for(int i=head[pos];i;i=nxt[i]) if(to[i]!=fa)

    {

        dfs_check(to[i],pos); o[pos]+=o[to[i]];

    }

}

bool check(int x)

{

    memset(o,0,sizeof o);

    int begin;

    for(int i=1;i<=m;i++) if(L[i].v>x) {begin=i; break;}

    // printf("%d\n",begin);

    for(int i=begin;i<=m;i++)

    {

        o[L[i].x]++; o[L[i].y]++; o[L[i].lca]-=2;

    }

    dfs_check(1,1);

    for(int i=2;i<=n;i++)

    {

        if(o[i]>=m-begin+1&&L[m].v-top[i]<=x)

        {

            // printf("%d %d %d %d\n",i,L[m].v,top[i],x);

            return true;

        }

    }

    return false;

}

void test()

{

    puts("Fuck"); for(int i=1;i<=n;i++) printf("%d ",top[i]); puts("");

}

void test1()

{

    puts("Shit"); for(int i=1;i<=m;i++) printf("%d ",L[i].v); puts("");

}

int main()

{

    n=rd(),m=rd(); int x,y,z; for(int i=1;i<n;i++) x=rd(),y=rd(),z=rd(),add(x,y,z),add(y,x,z);

    dfs(1,1);

    // test();

    for(int i=1;i<=m;i++)

    {

        L[i].x=rd(),L[i].y=rd();

        L[i].lca=lca(L[i].x,L[i].y);

        L[i].v=dis[L[i].x]+dis[L[i].y]-2*dis[L[i].lca];

    }

    sort(L+1,L+m+1,cmp);

    // test1();

    int l=0,r=L[m].v+1;

    while(l<r)

    {

        int mid=(l+r)>>1;

        if(check(mid)) r=mid-1;

        else l=mid+1;

    }

    // if(m==1&&L[1])

    for(int i=r-1;i<=L[m].v;i++)

    {

        if(!check(i)) continue;

        printf("%d\n",i);

        return 0;

    }

    puts("0");

}

/*

6 3

1 2 3

1 6 4

3 1 7

4 3 6

3 5 5

3 6

2 5

4 5

*/

巴特西

NOIP2015 提高组合集

最新文章

热门文章