[NOIP2011] 普及组

数字反转

小模拟

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 using namespace std;

 int main(){

     int i,n;

     char a[];

     scanf("%s",&a);

     n=strlen(a);

     int t1=;

     int t2=;

     if (a[]=='-') {

        printf("-");

        t1++;

     }

     t2=n-;

     for(i=n-;i>=;i--) if(a[i]=='')

         t2--;

         else break;

     for(i=t2;i>=t1;i--) cout<<a[i];

     return ;

 }

数字反转

统计单词数

将待匹配字符串前后加空格，样本字符串前后加空格，这样无脑find就可以找出所有单词

 #include<iostream>

 #include<cstdio>

 #include<string>

 #include<cstring>

 using namespace std;

 string s,sf;

 int t;//计数器；

 int main(){

     getline(cin,sf);

     getline(cin,s);

     int j;

     for(j=;j<=sf.size();j++)sf[j]=tolower(sf[j]);

     for(j=;j<=s.size();j++)s[j]=tolower(s[j]);

     sf=' '+sf+' ';

     s=' '+s+' ';

     int posi=-;

     int fpos=;

     if(s.find(sf)==string::npos){cout<<"-1"; return ;}

     fpos=s.find(sf);

     while(s.find(sf,posi+)!=string::npos){

         posi=s.find(sf,posi+);

         t++;

     }

     cout<<t<<" "<<fpos;

     return ;

 }

统计单词数

瑞士轮

按照题目要求排序，每次模拟完都要排一次序。

直接sort会T

原本有序的序列，比赛完积分只加0或1，仍然是有序的，此时用归并排序只要O(n)复杂度。

 /*by SilverN*/

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 const int mxn=;

 int n,r,q;

 struct node{

     int pw;

     int score;

     int num;

 }a[mxn],w[mxn],f[mxn];//所有人 胜者 败者

 int cmp(node a,node b){

     if(a.score!=b.score) return a.score>b.score;

     return a.num<b.num;

 }

 int main(){

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

     n=n*;

     int i,j;

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

         scanf("%d",&a[i].score);

     }

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

         scanf("%d",&a[i].pw);

         a[i].num=i;

     }

     sort(a+,a+n+,cmp);

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

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

             if(a[j].pw>a[j+].pw){

                 w[(j+)>>]=a[j];

                 f[(j+)>>]=a[j+];

             }

             else{

                 w[(j+)>>]=a[j+];

                 f[(j+)>>]=a[j];

             }

             w[(j+)>>].score++;

         }

         merge(w+,w+n/+,f+,f+n/+,a+,cmp);

     }

     printf("%d\n",a[q].num);

     return ;

 }

表达式的值

一边用栈计算表达式，计算过程中DP（其实是递推）

 /*by SilverN*/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<vector>

 using namespace std;

 const int mod=;

 const int mxn=;

 int f[mxn][],ntp=;

 int n;

 char st[mxn];int ctop=;

 char s[mxn];

 int cmp(char x){

     if(!ctop)return ;

     if(st[ctop]=='(')return ;

     if(st[ctop]=='*')return ;

     if(x=='*')return ;

     if(st[ctop]=='+')return ;

     return ;

 }

 void clc(char x){

     int xa=f[ntp][],xb=f[ntp--][];//0 1

     int ya=f[ntp][],yb=f[ntp--][];//0 1

     int resa=,resb=;

     if(x=='+'){

         (resa+=xa*ya)%=mod;

         (resb+=xa*yb)%=mod;

         (resb+=xb*yb)%=mod;

         (resb+=xb*ya)%=mod;

     }

     else{

         (resb+=(xb*yb))%=mod;

         (resa+=xa*yb+xb*ya)%=mod;

         (resa+=xa*ya)%=mod;

     }

     f[++ntp][]=resa;

     f[ntp][]=resb;

     return;

 }

 int main(){

     scanf("%d",&n);

     scanf("%s",s+);

     s[]='(';

     s[++n]=')';

     int i,j;

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

 //        printf("%d %c\n",i,s[i]);

 //        for(j=1;j<=4;j++)printf("%d %d\n",f[j][0],f[j][1]);

 //        for(j=1;j<=4;j++)printf("%c ",st[j]);

 //        printf("\n");

         if(s[i]=='('){

             st[++ctop]=s[i];

             continue;

         }

         if(s[i-]!=')'){

             f[++ntp][]=;

             f[ntp][]=;

         }

         if(s[i]=='+'){

             while(cmp(st[ctop]))clc(st[ctop--]);

             st[++ctop]=s[i];

         }

         else if(s[i]=='*'){

             while(cmp(st[ctop]))clc(st[ctop--]);

             st[++ctop]=s[i];

         }

         else if(s[i]==')'){

             while(ctop && st[ctop]!='('){

                 clc(st[ctop--]);

             }

             ctop--;

         }

     }

     printf("%d\n",f[][]);

     return ;

 }