【NOIP】提高组2014

Day1

T1(暴力)：大水题

#include<cstdio>

const int ok[][]={

 ,,,,,

 ,,,,,

 ,,,,,

 ,,,,,

 ,,,,,

};

int a[],b[];

int main()

{

    int n,na,nb;

    scanf("%d%d%d",&n,&na,&nb);

    for(int i=;i<=na;i++)scanf("%d",&a[i]);

    for(int i=;i<=nb;i++)scanf("%d",&b[i]);

    int nowa=,nowb=,ansa=,ansb=;

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

     {

         nowa++;nowb++;

         if(nowa>na)nowa=;

         if(nowb>nb)nowb=;//printf("now=%d,nowa=%d,nowb=%d",i,nowa,nowb);

         ansa+=ok[a[nowa]][b[nowb]];

         ansb+=ok[b[nowb]][a[nowa]];

     }

    printf("%d %d",ansa,ansb);

    return ;

}

T2（奇怪方法||树形DP）：

（1）学自http://blog.csdn.net/kqzxcmh/article/details/41552045

因为有联合权值的两点之间距离为2，所以必然有一个点是两点之间的中转点。

又因为这是一颗树，所以不可能两点之间同时有两个中转点（无环）。

所以扫描1..n，如果点i的周围有点a,b,c，则它们之间两两距离为2，产生的联合权值为

ab+ac+ba+bc+ca+cb=(a+b+c)^2-a^2-b^2-c^2(配方)

以此求和，最大值在枚举每个点的同时选取最大值和次大值相乘求出。

#include<cstdio>

using namespace std;

struct edge{int from;int obj;}e[];

int w[],head[],n,cnt=;

void insert(int u,int v)

{cnt++;e[cnt].obj=v;e[cnt].from=head[u];head[u]=cnt;}

int main()

{

    scanf("%d",&n);

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

     {

         int u,v;

         scanf("%d%d",&u,&v);

         insert(u,v);

         insert(v,u);

     }

    for(int i=;i<=n;i++)scanf("%d",&w[i]);

    long long ans=,max=;

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

     {

         long long max1=,max2=,sum=;

         for(int j=head[i];j>;j=e[j].from)

          {

              int now=e[j].obj;//printf("[%d]%d ",i,now);

              ans=(ans-1ll*w[now]*w[now])%;

              sum+=w[now];//printf("sum=%d ",sum);

              if(w[now]>max1)max1=w[now];

              else

                 if(w[now]>max2)max2=w[now];

          }

         ans=(ans+sum*sum)%;//printf("ans=%d ",ans);

         if(max1*max2>max)max=max1*max2;

     }

    printf("%lld %lld",max,ans);

    return ;

}

（2）学自http://www.cnblogs.com/JSZX11556/p/4907703.html

mx[x]表示x的叶子(仅指x的儿子，即只有一层)中的最大的权值

sum[x]表示x的叶子（同上）中的权值之和

在树上DFS

对于每个节点x，每处理完一个叶子后就计算一次mx[x]和sum[x]

这样处理的话，(a数组表示权值)max( a[x]*mx[e[i].to] , mx[x]*a[e[i].to] )就包含了所有最大值情况。

a[x]*mx[e[i].to]即当前x节点的权值乘叶子节点的叶子中的最大权值（儿子的儿子）

mx[x]*a[e[i].to]即当前x节点的叶子中两两相乘的最大权值（由于每处理完一条边就计算一次mx[x]），所以最大权值一定能被计算到

同理，a[x]*sum[e[i].to]和a[e[i].to]*sum[x]可以包含所有联合权值的情况，即计算权值总和。

具体可见代码。

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=,mod=;

struct edge{int from;int to;}e[maxn];

int a[maxn],sum[maxn],mx[maxn],cnt,head[maxn],ans,maxs,n;

void insert(int u,int v)

{

cnt++;e[cnt].from=head[u];e[cnt].to=v;head[u]=cnt;

cnt++;e[cnt].from=head[v];e[cnt].to=u;head[v]=cnt;

}

void dfs(int x,int fa)

{

    mx[x]=sum[x]=;

    for(int i=head[x];i;i=e[i].from)

     if(e[i].to!=fa)

      {

        int now=e[i].to;

        dfs(now,x);

        maxs=max(maxs,max(a[x]*mx[now],mx[x]*a[now]));

        ans=(ans+a[x]*sum[now]+a[now]*sum[x])%mod;

        (sum[x]+=a[now])%=mod;

        mx[x]=max(mx[x],a[now]);

      }

}

int main()

{

    scanf("%d",&n);

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

     {

         int u,v;

         scanf("%d%d",&u,&v);

         insert(u,v);

     }

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    dfs(,);

    printf("%d %d",maxs,ans*%mod);

    return ;

}

T3（背包DP）：

调了好久……

完全背包问题，应该从小到大DP

f[i][j]表示当前小鸟横坐标为i，纵坐标为j的最小点击屏幕数

状态转移方程：f[i][j]=min(f[i-1][j-up[i-1]]+1,f[i][j-up[i-1]]+1,f[i][j+down[i-1]])

最重要的一个问题：因为如果不点击屏幕让bird下落的话，f[i][j]=f[i][j-up[i-1]]的转移就不合法。

因此，要先计算上升的f值，再计算下落的f值，使转移合法。

注意顶部不会上升，要特判

可知bird无法前进时必定在柱子处，所以每次判断一下死亡

因为f[i]的状态只与f[i-1]有关，所以可用滚动数组优化内存，但注意每次DP要初始化

总之各种细节……T_T

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=,maxm=,inf=0x3f3f3f3f;

int f[][maxm],n,m,k,x,up[maxn],down[maxn],high[maxn],low[maxn],cnt;

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    for(int i=;i<n;i++)scanf("%d%d",&up[i],&down[i]);

    for(int i=;i<=n;i++)high[i]=m+,low[i]=;

    for(int i=;i<=k;i++){

        int xx;

        scanf("%d",&xx);

        scanf("%d%d",&low[xx],&high[xx]);

    }

    x=;for(int i=;i<=m;i++)f[][i]=;

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

     {

         x=-x;

         memset(f[x],0x3f,sizeof(f[x]));

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

          if(j-up[i-]>)

           f[x][j]=min(f[-x][j-up[i-]],f[x][j-up[i-]])+;

         for(int j=m-up[i-];j<=m;j++)

          f[x][m]=min(f[x][m],min(f[x][j],f[-x][j])+);

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

          if(j+down[i-]<=m)

           f[x][j]=min(f[x][j],f[-x][j+down[i-]]);

         for(int j=;j<=low[i];j++)f[x][j]=inf;

         for(int j=high[i];j<=m;j++)f[x][j]=inf;

         bool t=;

         for(int j=low[i]+;j<high[i];j++)

          if(f[x][j]<)t=;

         if(!t){printf("0\n%d",cnt);return ;}

         if(high[i]<=m)cnt++;

     }

    int ans=inf;

    for(int i=low[n]+;i<high[n];i++)ans=min(ans,f[x][i]);

    printf("1\n%d",ans);

    return ;

}

一年后二刷，发现挺水的。

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

using namespace std;

const int maxn=,maxm=,inf=0x3f3f3f3f;

int min(int a,int b){return a<b?a:b;}

int max(int a,int b){return a<b?b:a;}

int read(){

    char c;int s=,t=;

    while(!isdigit(c=getchar()))if(c=='-')t=-;

    do{s=s*+c-'';}while(isdigit(c=getchar()));

    return s*t;

}

int f[][maxm],n,m,kind,X[maxn],y[maxn];

struct cyc{int x,down,up;}p[maxn];

bool cmp(cyc a,cyc b){return a.x<b.x;}

int main(){

    n=read();m=read();kind=read();

    for(int i=;i<=n;i++)X[i]=read(),y[i]=read();

    for(int i=;i<=kind;i++){

        p[i].x=read();p[i].down=read();p[i].up=read();

    }

    sort(p+,p+kind+,cmp);

    memset(f,0x3f,sizeof(f));

    int x=;

    for(int i=;i<=m;i++)f[x][i]=;

    int tot=;

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

        x=-x;

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

            if(j-X[i]>)f[x][j]=min(f[x][j-X[i]],f[-x][j-X[i]])+;else f[x][j]=inf;

        }

        for(int j=m-X[i]+;j<=m;j++)f[x][m]=min(f[x][m],min(f[x][j],f[-x][j])+);

        for(int j=;j<=m-y[i];j++)f[x][j]=min(f[x][j],f[-x][j+y[i]]);

        if(tot<=kind&&p[tot].x==i){

            bool ok=;

            for(int j=p[tot].down+;j<=p[tot].up-;j++)if(f[x][j]<inf)ok=;

            if(!ok){printf("0\n%d",tot-);return ;}

            for(int j=;j<=p[tot].down;j++)f[x][j]=inf;

            for(int j=p[tot].up;j<=m;j++)f[x][j]=inf;

            tot++;

        }

    }

    int ans=inf;

    for(int i=;i<=m;i++)ans=min(ans,f[x][i]);

    printf("1\n%d",ans);

    return ;

}

Day2

T1:数据很小，枚举每个公共场所暴力计算即可

#include<cstdio>

long long mp[][];

int x[],y[],d,n,x1,x2,y1,y2;long long k[],ans,ansnum;

int main()

{

    scanf("%d%d",&d,&n);

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

     scanf("%d%d%lld",&x[i],&y[i],&k[i]);//printf("%lld",k[i]);

     if(x[i]-d<)x1=;else x1=x[i]-d;

     if(x[i]+d>)x2=;else x2=x[i]+d;

     if(y[i]-d<)y1=;else y1=y[i]-d;

     if(y[i]+d>)y2=;else y2=y[i]+d;//printf("%d %d %d %d\n",x1,x2,y1,y2);

     for(int xx=y1;xx<=y2;xx++)

      for(int yy=x1;yy<=x2;yy++)

       mp[xx][yy]+=k[i];

    }

    ans=;

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

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

      if(mp[i][j]>ans)ans=mp[i][j],ansnum=;

       else if(mp[i][j]==ans)ansnum++;

    printf("%lld %lld",ansnum,ans);

    return ;

}

T2(bfs+spfa)：

先建反向图，从终点开始跑一遍BFS，计算出终点可以到达的点（即原图中可以到达终点的点）

然后在反向图中，对于终点不可到达点，将它们出边所指向的点标为false

然后在原图跑最短路，跳过false的点即可

#include<cstdio>

#include<cstring>

struct edge{int from;int to;}e[],e1[];

bool vis[],ok[],yes[];

int head[],head1[],dist[],x,y,cnt,cnt1,s,t,n,m,q[];

void insert(int x,int y)

{

    cnt++;e[cnt].from=head[x];e[cnt].to=y;head[x]=cnt;

    cnt1++;e1[cnt1].from=head1[y];e1[cnt1].to=x;head1[y]=cnt1;

}

void bfs()

{

    memset(vis,,sizeof(vis));

    vis[t]=;int l=,r=;q[]=t;

    while(l<=r)

     {

         int nowq=q[l++];ok[nowq]=;

         for(int i=head1[nowq];i!=;i=e1[i].from)

          {

              int now=e1[i].to;

              if(!vis[now]){q[++r]=now;vis[now]=;}

          }

     }

}

void spfa()

{

    memset(vis,,sizeof(vis));

    memset(dist,,sizeof(dist));

    int l=,r=;q[]=s;

    dist[s]=;vis[s]=;

    while(l<=r)

     {

         int nowq=q[l++];

         for(int i=head[nowq];i!=;i=e[i].from)

          {

              int now=e[i].to;

              if(yes[now]&&!vis[now]&&dist[nowq]+<dist[now])

               {

                   dist[now]=dist[nowq]+;

                   q[++r]=now;

                   vis[now]=;

               }

          }

         vis[nowq]=;

     }

}

int main()

{

    scanf("%d%d",&n,&m);cnt=;

    for(int i=;i<=m;i++)scanf("%d%d",&x,&y),insert(x,y);

    scanf("%d%d",&s,&t);

    bfs();

    memset(yes,,sizeof(yes));

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

     if(!ok[i])

      for(int j=head1[i];j!=;j=e1[j].from)yes[e1[j].to]=;

//    for(int i=1;i<=n;i++)printf("%d %d\n",i,yes[i]);

    if(!yes[s]){printf("-1");return ;}

    spfa();

    if(dist[t]>)printf("-1");else printf("%d",dist[t]);

    return ;

}

T3(数学题)：

学自：http://www.cnblogs.com/JSZX11556/p/4907703.html

QAQ……数学渣各种悲伤

原理：当f(x) = 0时, f(x) mod p = 0. 那么当f(x) mod p = 0时，f(x)就有可能=0.

所以我们可以写个素数筛取几个大质数，对1..m中的数计算f(x) mod p，当多个质数计算出来的结果均为0时，f(x)=0。

优化一下，我们可以只计算1..p-1的结果，对于p..m上的数，f(x)mod p=f(x%p) mod p

#include<cstdio>

#include<cctype>

const int p[]={,,,,};

const int maxn=,maxm=,pn=;

int a[pn][maxn],f[pn][],ans[maxm],ret[pn],n,m,ansnum=;

void read(int x)

{

    bool F=;

    char c=getchar();

    for(;!isdigit(c);c=getchar())if(c=='-')F=;

    for(int i=;i<pn;i++)ret[i]=;

    for(;isdigit(c);c=getchar())

     for(int i=;i<pn;i++)

      ret[i]=(ret[i]*+c-'')%p[i];

    for(int i=;i<pn;i++)

     a[i][x]=F?ret[i]:p[i]-ret[i];//printf("%d\n",a[i][x]);

}

int calc(int x,int y)

{

    int v=;

    for(int i=n;i;i--)

     v=(v+a[x][i])*y%p[x];

    if((v+=a[x][])>=p[x])v-=p[x];

    return v;

}

int main()

{

    scanf("%d%d",&n,&m);

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

    for(int i=;i<pn;i++)

     for(int j=;j<p[i];j++)

      f[i][j]=calc(i,j);

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

     {

         bool t=;

         for(int j=;j<pn;j++)

           if(f[j][i%p[j]])t=;

          if(t)ans[++ansnum]=i;

     }

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

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

    return ;

}

巴特西

【NOIP】提高组2014

最新文章

热门文章