[NOIP2013] 普及组

计数问题

纯模拟

 #include<cstdio>

 #include<iostream>

 using namespace std;

 int main(){

     int n,x;

     cin>>n>>x;

     int i,c=;

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

         int a=i;

         while(a!=){

             if(a%==x)c++;

             a/=;

         }

     }

     cout<<c;

     return ;

 }

计数问题

表达式求值

模拟计算，扫一遍出解

 /*NOIP2013普及组t2 洛谷P1981 表达式求值*/

 /**/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 char last;

 char c;

 int x=;

 int a=,b=;

 int sum=;

 int main(){

     int i,j;

     bool flag=;

     do{

         if(cin>>c);

         else{

             flag=;

             c='+';

         }

         if(c>='' && c<='')x=x*+c-'';

         else{

             a=x;

             x=;

         }

         if(c=='*'){

             last=;

             b=(a*b)%;

         }

         if(c=='+'){

             if(last){

                 a=(a*b)%;

                 sum=(sum+a)%;

                 b=;

                 last=;

             }

             else sum+=a;

         }

     }while(flag==);

     printf("%d",sum%);

     return ;

 }

表达式求值

小朋友的数字

线性DP

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const long long inf=;

 int n,p,a[];

 long long su[]={};//特征值

 long long scoremx=-inf;//前排最大分数

 long long dmx=-inf;

 long long ans=-inf;

 int sum1(){

     int i,j;

     long long s=;

     long long mx=-inf;

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

         if(s+a[i]>mx)mx=s+a[i];

         su[i]=mx;

         if(s+a[i]>) s+=a[i];

         else s=;

     }

     //

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

         su[i]%=p<<;

     }

     return ;

 }

 int main(){

     int i,j;

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

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

     sum1();

     long long score;

 //

     scoremx=su[];

     score=su[];

     dmx=score+su[];

 //end

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

         score=dmx;

         if(dmx>scoremx)scoremx=dmx;

         if(su[i]+score>dmx)dmx=su[i]+score;

     }

     printf("%d",scoremx%p);

     return ;

 }

小朋友的数字

车站分级

从已知的低级站向高级站连边，跑拓扑排序得出层级关系

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int n,m;

 int a;//[第i趟车次的停靠站数]

 int s[];//[第i趟车次停靠的站]

 int mp[][]={};

 int book[];

 int r[],c[];

 int st[];

 int ans=;

 void rd(){

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

     int i,j,k;

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

         memset(book,,sizeof(book));

         scanf("%d",&a);

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

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

             book[s[j]]=;

         }

         for(k=s[];k<=s[a];k++)//遍历从始发站到终点站

         {

             if(!book[k])

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

                 if(!mp[k][s[j]])//从低级连到高级可过，从高级连到低级超时

                 {

                  mp[k][s[j]]=;

                  r[s[j]]++;}

         }

     }

 }

 int main(){

 //    freopen("level.in","r",stdin);

 //    freopen("level.out","w",stdout);

     rd();

     int i,j;

     int top=;

     memset(book,,sizeof(book));

     while(){

         ans++;

         top=;

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

             if(!r[i] && !book[i])

             {

                 top++;

                 st[top]=i;

                 book[i]=;

             }

         if(!top)break;

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

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

               if(mp[st[i]][j]){

                   mp[st[i]][j]=;

                   r[j]--;

               }

           }

         if(!top)break;

     }

     printf("%d",ans-);

     return ;

 }