[NOIP2012] 普及组

寻宝

大模拟

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 int n,m;

 int ro[][];//牌子

 int ru[][];//本房间上楼

 int h[]={};

 int sx=;

 int start;

 int lv;

 int main(){

     int i,j;

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

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

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

           scanf("%d%d",&ru[i][j],&ro[i][j]);

           h[i]+=ru[i][j];

       }

     scanf("%d",&start);

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

     for(lv=;lv<=n;lv++){

         int x=ro[lv][start];

         sx+=x;

 //        printf("test %d\n",sx);

         x=x%h[lv]+h[lv];

         x=x-ru[lv][start];

         while(x>){

             start++;

             start%=m;

             x-=ru[lv][start];

         }

         //lv++;

     }

     sx%=;

     printf("%d",sx);

     return ;

 }

摆花

分组背包

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 long long f[];

 int a[];//第i种花数

 int main(){

     int n,m;

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

     int i,j;

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

     f[]=;

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

         for(j=m;j>=;j--){

             int mi=min(a[i],j);

             for(int c=;c<=mi;c++)

                f[j]=(f[j]+f[j-c])%;

         }

     }

     f[m]%=;

 //    printf("%d",f[m]);

     cout<<f[m];

     return ;

 }

质因数分解

暴力枚举判断即可。

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

#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=;i<=sqt;i++){

        if(p%i==)return ;

    }

    return ;

}

int main(){

    scanf("%d",&n);

    c=n/;

    sq=sqrt(n);

    int i,j;

    if((c&)==)c+=;

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

      if(pd(i)){

          int d=n/i;

          if(i*d==n){

              printf("%d",d);

              return ;

          }

      }

    return ;

}

文化之旅

floyd

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

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int inf=;

 int c[];

 int fl[][];

 int mp[][];

 //int DFS(){

 //}

 int main(){

     int i,j,n,k,m,s,t;

     //in

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

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

         scanf("%d",&c[i]);

     }

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

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

        scanf("%d",&fl[i][j]);

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

      for(j=;j<=n;j++){

          if(i!=j)

          mp[i][j]=inf;

      }

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

         int u,v,d;

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

         mp[u][v]=min(mp[u][v],d);

         mp[v][u]=mp[u][v];

     }

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

      for(j=;j<=n;j++){

          if(fl[c[i]][c[j]]==)mp[j][i]=inf;

      }

     for(k=;k<=n;k++)

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

         for(j=;j<=n;j++){

             if(mp[i][k]+mp[k][j]<mp[i][j]){

                 mp[i][j]=mp[i][k]+mp[k][j];

             }

         }

     if(mp[s][t]==inf)printf("-1");

     else printf("%d",mp[s][t]);

     return ;

 }