您的位置: 首页 > IT文章 > noip2014 提高组

noip2014 提高组

分类: IT文章 • 2022-05-06 18:16:42

T1 生活大爆炸版石头剪刀布题目传送门

就是道模拟题咯

#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int a,b,n;
int x[251],y[251],g[251],f[251];
int w[6][6]={{2,0,1,1,0},{1,2,0,1,0},{0,1,2,0,1},{0,0,1,2,1},{1,1,0,0,2}};
int main()
{
    n=read();
    int la=read(),lb=read();
    for(int i=0;i<la;i++) x[i]=read();
    for(int i=0;i<lb;i++) y[i]=read();
    for(int i=0;i<n;i++) g[i]=x[i%la],f[i]=y[i%lb];
    for(int i=0;i<n;i++){
        if(w[g[i]][f[i]]==0) b++;
        if(w[g[i]][f[i]]==1) a++;
    }
    printf("%d %d
",a,b);
    return 0;
}

View Code

T2 联合权值题目传送门

易证明和某一个点相连接的点他们之间的距离就是2 所以我们可以枚举每一个点求值当然一个一个点去求值太慢

这个时候我们发现了一个神奇的东西他叫做——加法结合律！问题就完美解决了.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=450007,mod=10007;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int n,first[M],cnt,ans,mx,w[M];
struct node{int to,next;}e[M];
void ins(int a,int b){cnt++; e[cnt].to=b; e[cnt].next=first[a]; first[a]=cnt;}
void insert(int a,int b){ins(a,b); ins(b,a);}
void dfs(int x){
    int mx1=0,mx2=0,sum=0;
    for(int i=first[x];i;i=e[i].next){
        int now=e[i].to;
        sum=(sum+w[now])%mod;
        if(w[now]>mx1) mx2=mx1,mx1=w[now];
        else if(w[now]>mx2) mx2=w[now];
    }
    mx=max(mx,mx1*mx2);
    for(int i=first[x];i;i=e[i].next){
        int now=e[i].to;
        ans=(ans+w[now]*((sum-w[now])%mod+mod)%mod)%mod;
    }
}
int main()
{
    int x,y;
    n=read();
    for(int i=1;i<n;i++) x=read(),y=read(),insert(x,y);
    for(int i=1;i<=n;i++) w[i]=read();
    for(int i=1;i<=n;i++) dfs(i);
    printf("%d %d
",mx,ans);
    return 0;
}

View Code

T3 飞扬的小鸟题目传送门

这就是道dp然而看了眼题解自己YY了半天才Ac......主要还是细节处理的问题吧?码力太差
首先很容易想到o（nm*m)的算法直接推出答案但是明显会超时很容易得到f[i][j]=min{f[i-1][j-k*x]+k}
那较小的点会被计算很多次我们可以由每个点的下面f【i】【j-x】的点推出答案仍为最优解这样就可以得出新的方程f[i][j]=min{f[i-1][j-x],f[i][j-x]}
复杂度降下来了就可以写了当然还可以由上方下降得到所以我们可以分两次递推得出答案还有游戏到高度为M的时候不会结束所以还得特殊考虑
最后这个游戏不是codevs那里的东东嘛？

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxN=15007,maxM=1507,inf=1000000000;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int f[maxN][maxM];
int n,m,k,x[maxN],y[maxN];
int down[maxN],up[maxN];
int main()
{
    n=read(); m=read(); k=read();
    for(int i=0;i<=n;i++) down[i]=0,up[i]=m+1;
    for(int i=0;i<n;i++) x[i]=read(),y[i]=read();
    for(int i=1;i<=k;i++){
        int p=read();
        down[p]=read(); up[p]=read();
    }
    for(int i=1;i<=n;i++) 
     for(int j=0;j<=m;j++)
      f[i][j]=inf;
    f[0][0]=inf;//for(int i=1;i<=n;i++,printf("
")) for(int j=1;j<=m;j++) printf("[%d] ",f[i][j]);
    //for(int i=1;i<=n;i++) printf("[%d %d]
",down[i],up[i]);
    //for(int i=0;i<n;i++) printf("[%d %d]
",x[i],y[i]);
    for(int i=1;i<=n;i++){
        for(int j=x[i-1];j<=m;j++) f[i][j]=min(f[i-1][j-x[i-1]]+1,f[i][j-x[i-1]]+1);
        for(int j=m-x[i-1];j<=m;j++) f[i][m]=min(f[i][m],f[i][j]+1),f[i][m]=min(f[i][m],f[i-1][j]+1);
        for(int j=down[i]+1;j<=up[i]-1;j++) if(j+y[i-1]<=m) f[i][j]=min(f[i][j],f[i-1][j+y[i-1]]);
        for(int j=1;j<=down[i];j++) f[i][j]=inf;;
        for(int j=up[i];j<=m;j++) f[i][j]=inf;
    }
    int ans=inf,cnt=k;
    for(int i=n;i;i--){
     for(int j=down[i]+1;j<=up[i]-1;j++) ans=min(ans,f[i][j]);
     if(ans<inf) break;
     if(up[i]!=m+1) cnt--;
    }
    if(cnt==k) printf("1
%d",ans);
    else printf("0
%d",cnt);
    return 0;
}

View Code

T4 无线网络发射器选址题目传送门

枚举计算比较大小没什么好说的吧

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int d,n,ans,sum;
int map[155][155];
int main()
{
    int x,y,k;
    d=read(); n=read();
    for(int i=1;i<=n;i++) x=read(),y=read(),k=read(),map[x][y]=k;
    for(int i=0;i<=128;i++)
     for(int j=0;j<=128;j++){
         int now=0;
         for(int x=max(0,i-d);x<=min(i+d,128);x++)
          for(int y=max(0,j-d);y<=min(j+d,128);y++)
           now+=map[x][y];
         if(ans<now) ans=now,sum=0;
         if(ans==now) sum++;
     }
    printf("%d %d
",sum,ans);
    return 0;
}

View Code

T5 寻找道路题目传送门

首先可以顺着终点反向bfs一波记录那些点是可以到达终点的

然后枚举每一个点看他的出边所指向的点是否能到达终点就好了

然后顺着可以走的点走一波spfa就解决问题了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=20007,maxN=400007,inf=0x3f3f3f3f;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int first[M],book[M];
int d[M],h[M],cnt,S,T;
int n,m,q[M],use[M];
struct node{int to,next;}e[maxN];
void insert(int a,int b){cnt++; e[cnt].to=b; e[cnt].next=first[a]; first[a]=cnt;}
int sum,last[M];
struct note{int to,next;}e1[maxN];
void ins(int a,int b){sum++; e1[sum].to=b; e1[sum].next=last[a]; last[a]=sum;}
void bfs(){
    int head=0,tail=1;
    h[T]=1;
    while(head!=tail){
        int x=q[head++];
        for(int i=last[x];i;i=e1[i].next){
            int now=e1[i].to;
            if(!h[now]){h[now]=1; q[tail++]=now;}
        }
    }
    //for(int i=1;i<=n;i++) printf("[%d] ",h[i]); printf("
");
    use[T]=use[S]=1;
//    for(int x=1;x<=n;x++,printf("
"))
//     for(int i=first[x];i;i=e[i].next) printf("[%d] ",e[i].to);
    for(int x=1;x<=n;x++){
        int now=0;
        for(int i=first[x];i;i=e[i].next){
            now=e[i].to;
             if(!h[now]) break;
         }
         if(!h[now]) continue;
         use[x]=1;
    }
    //for(int i=1;i<=n;i++) printf("[%d] ",use[i]); printf("
");
}
void spfa(){
    memset(d,0x3f,sizeof(d));
    int head=0,tail=1;
    d[S]=0; q[head]=S; book[S]=1;
    while(head!=tail){
        int x=q[head++]; book[x]=0; if(head>M) head=0; 
        for(int i=first[x];i;i=e[i].next){
            int now=e[i].to; if(!use[now]) continue;
            //printf("[%d]
",now);
            if(d[now]>d[x]+1){
                d[now]=d[x]+1;
                if(!book[now]){q[tail++]=now; book[now]=1; if(tail>M) tail=0;}
            }
        }
    }
}
int main()
{
    int x,y;
    n=read(); m=read();
    for(int i=1;i<=m;i++){
        x=read(); y=read(); 
        if(x!=y) insert(x,y),ins(y,x);
    }
    S=read(); T=read();
    q[0]=T; bfs();
    spfa(); 
    if(d[T]<inf) printf("%d
",d[T]);
    else printf("-1
");
    return 0;
}

View Code

T6 解方程题目传送门

这道题确实难我是照着黄学长的思路来的神犇传送门

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int mod[5]={11261,19997,22877,21893,14843};
int n,m,len,sum;
int ans[1000005];
int a[5][105],pre[5][105],res[5][30005];
char s[10005];
int calc(int k){
    int sum=0;
    for(int i=0;i<=n;i++) sum=(sum+a[k][i]*pre[k][i])%mod[k];
    if(sum<0) sum+=mod[k];
    return sum; 
}
int pd(int x){
    for(int k=0;k<5;k++)
     if(res[k][x%mod[k]]) return 0;
    return 1;
}
int main()
{
    n=read(); m=read();
    for(int i=0;i<=n;i++){
        scanf("%s",s+1); len=strlen(s+1);
        bool f=0;
        for(int k=0;k<5;k++){
            if(s[1]=='-') f=1,a[k][i]=0;
            else a[k][i]=s[1]-'0';
        }
        for(int k=0;k<5;k++){
            for(int j=2;j<=len;j++) a[k][i]=(a[k][i]*10+s[j]-'0')%mod[k];
            if(f) a[k][i]=-a[k][i];
        }
    }
    for(int k=0;k<5;k++){
        for(int x=1;x<mod[k];x++){
            pre[k][0]=1;
            for(int i=1;i<=n;i++) pre[k][i]=(pre[k][i-1]*x)%mod[k];
            res[k][x]=calc(k);
        }
    }
    for(int i=1;i<=m;i++) if(pd(i)) ans[++sum]=i;
    printf("%d
",sum);
    for(int i=1;i<=sum;i++) printf("%d
",ans[i]);
    return 0;
}

View Code

noip2014 提高组

相关推荐