小模拟
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5 int main(){ 6 int i,n; 7 char a[12]; 8 scanf("%s",&a); 9 n=strlen(a); 10 int t1=0; 11 int t2=0; 12 if (a[0]=='-') { 13 printf("-"); 14 t1++; 15 } 16 t2=n-1; 17 for(i=n-1;i>=0;i--) if(a[i]=='0') 18 t2--; 19 else break; 20 for(i=t2;i>=t1;i--) cout<<a[i]; 21 return 0; 22 }
将待匹配字符串前后加空格，样本字符串前后加空格，这样无脑find就可以找出所有单词
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 using namespace std; 6 string s,sf; 7 int t;//计数器； 8 int main(){ 9 getline(cin,sf); 10 getline(cin,s); 11 int j; 12 for(j=0;j<=sf.size();j++)sf[j]=tolower(sf[j]); 13 for(j=0;j<=s.size();j++)s[j]=tolower(s[j]); 14 sf=' '+sf+' '; 15 s=' '+s+' '; 16 int posi=-1; 17 int fpos=0; 18 if(s.find(sf)==string::npos){cout<<"-1"; return 0;} 19 fpos=s.find(sf); 20 while(s.find(sf,posi+1)!=string::npos){ 21 posi=s.find(sf,posi+1); 22 t++; 23 } 24 cout<<t<<" "<<fpos; 25 return 0; 26 }
按照题目要求排序，每次模拟完都要排一次序。
直接sort会T
原本有序的序列，比赛完积分只加0或1，仍然是有序的，此时用归并排序只要O(n)复杂度。
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=210000; 9 int n,r,q; 10 struct node{ 11 int pw; 12 int score; 13 int num; 14 }a[mxn],w[mxn],f[mxn];//所有人 胜者 败者 15 int cmp(node a,node b){ 16 if(a.score!=b.score) return a.score>b.score; 17 return a.num<b.num; 18 } 19 int main(){ 20 scanf("%d%d%d",&n,&r,&q); 21 n=n*2; 22 int i,j; 23 for(i=1;i<=n;i++){ 24 scanf("%d",&a[i].score); 25 } 26 for(i=1;i<=n;i++){ 27 scanf("%d",&a[i].pw); 28 a[i].num=i; 29 } 30 sort(a+1,a+n+1,cmp); 31 32 for(i=1;i<=r;i++){ 33 for(j=1;j<=n;j+=2){ 34 if(a[j].pw>a[j+1].pw){ 35 w[(j+1)>>1]=a[j]; 36 f[(j+1)>>1]=a[j+1]; 37 } 38 else{ 39 w[(j+1)>>1]=a[j+1]; 40 f[(j+1)>>1]=a[j]; 41 } 42 w[(j+1)>>1].score++; 43 } 44 merge(w+1,w+n/2+1,f+1,f+n/2+1,a+1,cmp); 45 } 46 printf("%d ",a[q].num); 47 return 0; 48 }
表达式的值
一边用栈计算表达式，计算过程中DP（其实是递推）
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mod=10007; 10 const int mxn=100010; 11 int f[mxn][2],ntp=0; 12 int n; 13 char st[mxn];int ctop=0; 14 char s[mxn]; 15 int cmp(char x){ 16 if(!ctop)return 0; 17 if(st[ctop]=='(')return 0; 18 if(st[ctop]=='*')return 1; 19 if(x=='*')return 1; 20 if(st[ctop]=='+')return 0; 21 return 0; 22 } 23 void clc(char x){ 24 int xa=f[ntp][0],xb=f[ntp--][1];//0 1 25 int ya=f[ntp][0],yb=f[ntp--][1];//0 1 26 int resa=0,resb=0; 27 if(x=='+'){ 28 (resa+=xa*ya)%=mod; 29 (resb+=xa*yb)%=mod; 30 (resb+=xb*yb)%=mod; 31 (resb+=xb*ya)%=mod; 32 } 33 else{ 34 (resb+=(xb*yb))%=mod; 35 (resa+=xa*yb+xb*ya)%=mod; 36 (resa+=xa*ya)%=mod; 37 } 38 f[++ntp][0]=resa; 39 f[ntp][1]=resb; 40 return; 41 } 42 int main(){ 43 scanf("%d",&n); 44 scanf("%s",s+1); 45 s[0]='('; 46 s[++n]=')'; 47 int i,j; 48 for(int i=0;i<=n;i++){ 49 // printf("%d %c ",i,s[i]); 50 // for(j=1;j<=4;j++)printf("%d %d ",f[j][0],f[j][1]); 51 // for(j=1;j<=4;j++)printf("%c ",st[j]); 52 // printf(" "); 53 if(s[i]=='('){ 54 st[++ctop]=s[i]; 55 continue; 56 } 57 if(s[i-1]!=')'){ 58 59 f[++ntp][0]=1; 60 f[ntp][1]=1; 61 } 62 if(s[i]=='+'){ 63 while(cmp(st[ctop]))clc(st[ctop--]); 64 st[++ctop]=s[i]; 65 } 66 else if(s[i]=='*'){ 67 while(cmp(st[ctop]))clc(st[ctop--]); 68 st[++ctop]=s[i]; 69 } 70 else if(s[i]==')'){ 71 while(ctop && st[ctop]!='('){ 72 clc(st[ctop--]); 73 } 74 ctop--; 75 } 76 } 77 printf("%d ",f[1][0]); 78 return 0; 79 }