首页 > 代码库 > [NOIP2012] 普及组

[NOIP2012] 普及组

寻宝

大模拟

 1 #include<iostream> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 int n,m; 6 int ro[10500][150];//牌子  7 int ru[10500][150];//本房间上楼  8 int h[20000]={0}; 9 int sx=0;10 int start;11 int lv;12 int main(){13 14     int i,j;15     scanf("%d%d",&n,&m);16     for(i=1;i<=n;i++)17       for(j=0;j<m;j++){18           scanf("%d%d",&ru[i][j],&ro[i][j]);19           h[i]+=ru[i][j];20       }21     scanf("%d",&start);22 //    printf("%d\n",n);23     for(lv=1;lv<=n;lv++){24         int x=ro[lv][start];25         sx+=x;26 //        printf("test %d\n",sx);27         x=x%h[lv]+h[lv];28         x=x-ru[lv][start];29         while(x>0){30             start++;31             start%=m;32             x-=ru[lv][start];33         }34         //lv++;35     }36     sx%=20123;37     printf("%d",sx);38     return 0;39 }

 

 

摆花

分组背包

 1 #include<iostream> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 long long f[200]; 6 int a[200];//第i种花数  7 int main(){ 8     int n,m; 9     scanf("%d%d",&n,&m);10     int i,j;11     for(i=1;i<=n;i++)scanf("%d",&a[i]);12     f[0]=1;13     for(i=1;i<=n;i++){14         for(j=m;j>=1;j--){15             int mi=min(a[i],j);16             for(int c=1;c<=mi;c++)17                f[j]=(f[j]+f[j-c])%1000007;18         }19     }20     f[m]%=1000007;21 //    printf("%d",f[m]);22     cout<<f[m];23     return 0;24 }

 

 

质因数分解

暴力枚举判断即可。

很久以前的代码风格,有些诡异

#include<iostream>#include<cmath>#include<algorithm>using namespace std;int n;int c,sq;int x,y;bool pd(int p){    int i,sqt=sqrt(p);    for(i=2;i<=sqt;i++){        if(p%i==0)return 0;    }    return 1;}int main(){    scanf("%d",&n);    c=n/2;    sq=sqrt(n);    int i,j;    if((c&1)==0)c+=1;    for(i=2;i<=sq;i++)      if(pd(i)){          int d=n/i;          if(i*d==n){              printf("%d",d);              return 0;          }      }    return 0;}

 

 

文化之旅

floyd

↑不是正解,只是因为数据水才混了过去

 1 #include<iostream> 2 #include<algorithm> 3 #include<cmath> 4 using namespace std; 5 const int inf=10000000; 6 int c[5000]; 7 int fl[300][300]; 8 int mp[300][300]; 9 //int DFS(){10     11 //}12 int main(){13     int i,j,n,k,m,s,t;14     //in15     scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);16     for(i=1;i<=n;i++){17         scanf("%d",&c[i]);18     }19     for(i=1;i<=k;i++)20      for(j=1;j<=k;j++)21        scanf("%d",&fl[i][j]);22     for(i=1;i<=n;i++)23      for(j=1;j<=n;j++){24          if(i!=j)25          mp[i][j]=inf;26      }27     for(i=1;i<=m;i++){28         int u,v,d;29         scanf("%d%d%d",&u,&v,&d);30         mp[u][v]=min(mp[u][v],d);31         mp[v][u]=mp[u][v];32     }33     for(i=1;i<=n;i++)34      for(j=1;j<=n;j++){35          if(fl[c[i]][c[j]]==1)mp[j][i]=inf;36      }37     for(k=1;k<=n;k++)38       for(i=1;i<=n;i++)39         for(j=1;j<=n;j++){40             if(mp[i][k]+mp[k][j]<mp[i][j]){41                 mp[i][j]=mp[i][k]+mp[k][j];42             }43         }44     if(mp[s][t]==inf)printf("-1");45     else printf("%d",mp[s][t]);46     return 0;47     48 }

 

[NOIP2012] 普及组