A题：外教 Michale 变身大熊猫
题目链接：https://nanti.jisuanke.com/t/39611
题解：
1#include<bits/stdc++.h> 2using namespace std; 3typedef long long LL; 4const int maxx = 5e5+10; 5const int mod = 998244353; 6struct node{LL len,num;}tree[maxx]; 7int a[maxx],s[maxx]; 8LL len1[maxx],len2[maxx],num1[maxx],num2[maxx]; 9LL dp[maxx]; 10int n; 11LL inv(LL x) 12{ 13 LL b=mod-2,ans=1; 14 while(b) 15 { 16 if(b&1)ans=(ans*x)%mod; 17 x=(x*x)%mod; 18 b>>=1; 19 } 20 return ans; 21} 22void up(int x,node t) 23{ 24 for(int i=x;i<=n;i+=(i&(-i))) 25 { 26 if(tree[i].len<t.len)tree[i]=t; 27 else if(tree[i].len==t.len)tree[i].num+=t.num,tree[i].num%=mod; 28 //注意这里也要取一下模 29 } 30} 31node getmax(int x) 32{ 33 node res; 34 res.len=0;res.num=1; 35 for(int i=x;i>0;i-=(i&(-i))) 36 { 37 if(res.len<tree[i].len)res=tree[i]; 38 else if(res.len==tree[i].len)res.num+=tree[i].num,res.num%=mod; 39 //注意这里也要取一下模 40 } 41 return res; 42} 43int main() 44{ 45 scanf("%d",&n); 46 for(int i=1;i<=n;i++) 47 { 48 scanf("%d",&a[i]); 49 s[i]=a[i]; 50 tree[i].len=tree[i].num=0; 51 } 52 sort(s+1,s+1+n); 53 int t=unique(s+1,s+1+n)-s; 54 node ans; 55 ans.len=ans.num=0; 56 int sum=0; 57 for(int i=1;i<=n;i++) 58 { 59 a[i]=lower_bound(s+1,s+t,a[i])-s;//离散化 60 node temp=getmax(a[i]-1); 61 temp.len++; 62 up(a[i],temp); 63 len1[i]=temp.len;num1[i]=temp.num; 64 //cout<<len1[i]<<' '<<num1[i]<<endl; 65 if(ans.len<temp.len)ans=temp; 66 else if(ans.len==temp.len)ans.num+=temp.num,ans.num%=mod; 67 sum=max(sum,a[i]); 68 } 69 for(int i=1;i<=n;i++) 70 tree[i].len=tree[i].num=0; 71 for(int i=n;i>=1;i--) 72 { 73 a[i]=a[i]*(-1)+sum+1; 74 //cout<<a[i]<<endl; 75 node temp=getmax(a[i]-1); 76 temp.len++; 77 up(a[i],temp); 78 len2[i]=temp.len;num2[i]=temp.num; 79 //cout<<len2[i]<<' '<<num2[i]<<endl; 80 } 81 LL q=inv(ans.num); 82 for(int i=1;i<=n;i++) 83 { 84 if(len1[i]+len2[i]==ans.len+1)printf("%lld ",num1[i]*num2[i]%mod*q%mod); 85 else printf("0 "); 86 } 87 return 0; 88}
View Code
B题：个性化评测系统
题目链接：https://nanti.jisuanke.com/t/39612
直接暴力，枚举每一张牌判断可不可以胡，判断的时候要先枚举对子并删去再判断可不可行，有一种可行就说明这张牌可以胡
1#include<bits/stdc++.h> 2using namespace std; 3int ff(int *a) 4{ 5 for(int i=1;i<=7;i++) 6 if(a[i]==1||a[i]==2)return 0; 7 return 1; 8} 9int f(int *a) 10{ 11 int s[20]; 12 for(int i=1;i<=9;i++) 13 s[i]=a[i]; 14 for(int j=1;j<=7;j++) 15 { 16 if(s[j]>=3)s[j]-=3; 17 if(s[j]==1) 18 { 19 if(s[j+1]&&s[j+2]) 20 { 21 s[j+1]--;s[j+2]--; 22 } 23 else return 0; 24 } 25 if(s[j]==2) 26 { 27 if(s[j+1]>=2&&s[j+2]>=2) 28 { 29 s[j+1]-=2;s[j+2]-=2; 30 } 31 else return 0; 32 } 33 } 34 if(s[8]==1||s[8]==2||s[9]==1||s[9]==2)return 0; 35 return 1; 36} 37int see(int *a,int *b,int *c,int *d) 38{ 39 int s[20],p[20],m[20],z[20]; 40 int flag; 41 for(int i=1;i<=9;i++) 42 { 43 for(int j=1;j<=9;j++) 44 { 45 s[j]=a[j];p[j]=b[j];m[j]=c[j];z[j]=d[j]; 46 } 47 if(s[i]>=2)s[i]-=2;//枚举并删去对子 48 if(f(s)&&f(p)&&f(m)&&ff(z))return 1; 49 } 50 for(int i=1;i<=9;i++) 51 { 52 for(int j=1;j<=9;j++) 53 { 54 s[j]=a[j];p[j]=b[j];m[j]=c[j];z[j]=d[j]; 55 } 56 if(p[i]>=2)p[i]-=2; 57 if(f(s)&&f(p)&&f(m)&&ff(z))return 1; 58 } 59 for(int i=1;i<=9;i++) 60 { 61 for(int j=1;j<=9;j++) 62 { 63 s[j]=a[j];p[j]=b[j];m[j]=c[j];z[j]=d[j]; 64 } 65 if(m[i]>=2)m[i]-=2; 66 if(f(s)&&f(p)&&f(m)&ff(z))return 1; 67 } 68 for(int i=1;i<=9;i++) 69 { 70 for(int j=1;j<=9;j++) 71 { 72 s[j]=a[j];p[j]=b[j];m[j]=c[j];z[j]=d[j]; 73 } 74 if(z[i]>=2)z[i]-=2; 75 if(f(s)&&f(p)&&f(m)&&ff(z))return 1; 76 } 77 return 0; 78} 79int main() 80{ 81 char ch[5]; 82 while(cin>>ch) 83 { 84 int s[20]={0},p[20]={0},m[20]={0},z[20]={0}; 85 if(ch[1]=='s')s[ch[0]-'0']++; 86 if(ch[1]=='p')p[ch[0]-'0']++; 87 if(ch[1]=='m')m[ch[0]-'0']++; 88 if(ch[1]=='z')z[ch[0]-'0']++; 89 for(int i=2;i<=13;i++) 90 { 91 cin>>ch; 92 if(ch[1]=='s')s[ch[0]-'0']++; 93 if(ch[1]=='p')p[ch[0]-'0']++; 94 if(ch[1]=='m')m[ch[0]-'0']++; 95 if(ch[1]=='z')z[ch[0]-'0']++; 96 } 97 for(int i=1;i<=9;i++) 98 { 99 if(m[i]>=4)continue; 100 m[i]++; 101 if(see(s,p,m,z))printf("%dm\n",i); 102 m[i]--; 103 } 104 for(int i=1;i<=9;i++) 105 { 106 if(s[i]>=4)continue; 107 s[i]++; 108 if(see(s,p,m,z))printf("%ds\n",i); 109 s[i]--; 110 } 111 for(int i=1;i<=9;i++) 112 { 113 if(p[i]>=4)continue; 114 p[i]++; 115 if(see(s,p,m,z))printf("%dp\n",i); 116 p[i]--; 117 } 118 for(int i=1;i<=7;i++) 119 { 120 if(z[i]>=4)continue; 121 z[i]++; 122 if(see(s,p,m,z))printf("%dz\n",i); 123 z[i]--; 124 } 125 } 126 return 0; 127} 128/*3m 3m 3m 4m 5m 6m 6m 6m 1z 1z 1z 2z 2z 1291p 1p 1p 4p 5p 6p 9p 9p 9p 8p 8p 8p 8p 1301s 1s 1s 1s 2s 2s 2s 2s 3p 3p 3p 5p 5p 1311s 1s 2s 3s 5s 5s 6s 6s 7s 7s 7s 8s 9s 1321s 1s 1s 2s 3s 4s 5s 6s 7s 8s 9s 9s 9s*/
View Code
D题：“星云系统”
题目链接：https://nanti.jisuanke.com/t/39614
第一种解法：用单调栈
1#include<bits/stdc++.h> 2using namespace std; 3stack<char>q; 4char a[5000010],b[5000010]; 5int main() 6{ 7 scanf("%s",a); 8 int s=strlen(a); 9 int k; 10 scanf("%d",&k); 11 q.push(a[0]); 12 for(int i=1;i<s;i++) 13 { 14 while(!q.empty()) 15 { 16 char t=q.top(); 17 if(t<=a[i]) 18 { 19 //q.push(a[i]); 20 break; 21 } 22 else 23 { 24 if(s-i+q.size()>k)q.pop(); 25 else break; 26 } 27 } 28 q.push(a[i]); 29 } 30 int t=0; 31 while(!q.empty()) 32 { 33 b[++t]=q.top();q.pop(); 34 } 35 for(int i=t;i>t-k;i--) 36 printf("%c",b[i]); 37 return 0; 38}
View Code
第二种解法：用26个vector存字母位置然后暴力，好像叫序列自动机
1#include<bits/stdc++.h> 2using namespace std; 3const int maxx = 5e6+10; 4vector<int>q[30]; 5char a[maxx]; 6int pos[30],len; 7int find(int i,int s)//pos[i]用来标记用过的位置 8{ 9 while(q[i][pos[i]]<s && pos[i]<q[i].size()) 10 pos[i]++; 11 return q[i][pos[i]]; 12} 13void dfs(int s,int k)//s为当前位置 14{ 15 if(!k)return; 16 for(int i=0;i<26;i++) 17 { 18 int t=find(i,s); 19 if(t>=s&&len-t+1>=k) 20 { 21 printf("%c",i+'a'); 22 dfs(t+1,k-1); 23 return; 24 } 25 } 26} 27int main() 28{ 29 for(int i=0;i<26;i++)q[i].push_back(0); 30 scanf("%s",a+1); 31 len=strlen(a+1); 32 for(int i=1;i<=len;i++) 33 q[a[i]-'a'].push_back(i); 34 int k; 35 scanf("%d",&k); 36 dfs(1,k); 37 return 0; 38}
View Code
E题：撑起信息安全“保护伞
题目链接：https://nanti.jisuanke.com/t/39615
题解：
就是找 ")(" 和 合法的"()"
1#include<bits/stdc++.h> 2using namespace std; 3const int maxx = 1e6+10; 4char a[maxx],b[maxx]; 5stack<char>q; 6int main() 7{ 8 scanf("%s",a); 9 int s=strlen(a); 10 strcpy(b,a); 11 int flag=0; 12 for(int i=s-1;i>=1;i--) 13 { 14 if(b[i]=='('&&b[i-1]==')')//找")(" 15 { 16 b[i]=')';b[i-1]='('; 17 int t=0; 18 for(int j=i+1;j<s;j++) 19 { 20 if(b[j]=='(')q.push(b[j]); 21 else 22 { 23 if(b[j]==')'&&!q.empty())q.pop(); 24 else if(b[j]==')'&&q.empty())t++; 25 } 26 } 27 for(int j=i+1;j<i+1+t;j++) 28 b[j]=')'; 29 for(int j=i+1+t;j<s-1;j+=2) 30 b[j]='(',b[j+1]=')'; 31 flag=1;break; 32 } 33 } 34 if(flag)printf("%s\n",b); 35 else 36 { 37 for(int i=0;i<s-2;i+=2) 38 printf("()"); 39 printf("\n"); 40 } 41 strcpy(b,a); 42 flag=0; 43 for(int i=s-1;i>=1;i--) 44 { 45 if(b[i]==')'&&b[i-1]=='(')//找交换后合法的"()" 46 { 47 while(!q.empty())q.pop(); 48 b[i]='(';b[i-1]=')'; 49 int j; 50 for(j=0;j<s;j++) 51 { 52 if(b[j]=='(')q.push(b[j]); 53 else 54 { 55 if(b[j]==')'&&!q.empty())q.pop(); 56 else break; 57 } 58 } 59 if(j<s||!q.empty())b[i]=')',b[i-1]='('; 60 else 61 { 62 int t=0; 63 for(int k=i+1;k<s;k++) 64 if(b[k]=='(')t++; 65 for(int k=i+1;k<i+1+t;k++)b[k]='('; 66 for(int k=i+1+t;k<s;k++)b[k]=')'; 67 flag=1;break; 68 } 69 } 70 } 71 if(flag==1)printf("%s",b); 72 else 73 { 74 s=s+2; 75 for(int i=1;i<=s/2;i++) 76 printf("("); 77 for(int i=s/2+1;i<=s;i++) 78 printf(")"); 79 } 80 return 0; 81} 82/*((((()))))()()()()(()) 83((()())())*/
View Code