A题:外教 Michale 变身大熊猫
题目链接:https://nanti.jisuanke.com/t/39611
题解:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxx = 5e5+10;
const int mod = 998244353;
struct node{LL len,num;}tree[maxx];
int a[maxx],s[maxx];
LL len1[maxx],len2[maxx],num1[maxx],num2[maxx];
LL dp[maxx];
int n;
LL inv(LL x)
{
LL b=mod-2,ans=1;
while(b)
{
if(b&1)ans=(ans*x)%mod;
x=(x*x)%mod;
b>>=1;
}
return ans;
}
void up(int x,node t)
{
for(int i=x;i<=n;i+=(i&(-i)))
{
if(tree[i].len<t.len)tree[i]=t;
else if(tree[i].len==t.len)tree[i].num+=t.num,tree[i].num%=mod;
//注意这里也要取一下模
}
}
node getmax(int x)
{
node res;
res.len=0;res.num=1;
for(int i=x;i>0;i-=(i&(-i)))
{
if(res.len<tree[i].len)res=tree[i];
else if(res.len==tree[i].len)res.num+=tree[i].num,res.num%=mod;
//注意这里也要取一下模
}
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
s[i]=a[i];
tree[i].len=tree[i].num=0;
}
sort(s+1,s+1+n);
int t=unique(s+1,s+1+n)-s;
node ans;
ans.len=ans.num=0;
int sum=0;
for(int i=1;i<=n;i++)
{
a[i]=lower_bound(s+1,s+t,a[i])-s;//离散化
node temp=getmax(a[i]-1);
temp.len++;
up(a[i],temp);
len1[i]=temp.len;num1[i]=temp.num;
//cout<<len1[i]<<' '<<num1[i]<<endl;
if(ans.len<temp.len)ans=temp;
else if(ans.len==temp.len)ans.num+=temp.num,ans.num%=mod;
sum=max(sum,a[i]);
}
for(int i=1;i<=n;i++)
tree[i].len=tree[i].num=0;
for(int i=n;i>=1;i--)
{
a[i]=a[i]*(-1)+sum+1;
//cout<<a[i]<<endl;
node temp=getmax(a[i]-1);
temp.len++;
up(a[i],temp);
len2[i]=temp.len;num2[i]=temp.num;
//cout<<len2[i]<<' '<<num2[i]<<endl;
}
LL q=inv(ans.num);
for(int i=1;i<=n;i++)
{
if(len1[i]+len2[i]==ans.len+1)printf("%lld ",num1[i]*num2[i]%mod*q%mod);
else printf("0 ");
}
return 0;
}
View Code
B题:个性化评测系统
题目链接:https://nanti.jisuanke.com/t/39612
直接暴力,枚举每一张牌判断可不可以胡,判断的时候要先枚举对子并删去再判断可不可行,有一种可行就说明这张牌可以胡
#include<bits/stdc++.h>
using namespace std;
int ff(int *a)
{
for(int i=1;i<=7;i++)
if(a[i]==1||a[i]==2)return 0;
return 1;
}
int f(int *a)
{
int s[20];
for(int i=1;i<=9;i++)
s[i]=a[i];
for(int j=1;j<=7;j++)
{
if(s[j]>=3)s[j]-=3;
if(s[j]==1)
{
if(s[j+1]&&s[j+2])
{
s[j+1]--;s[j+2]--;
}
else return 0;
}
if(s[j]==2)
{
if(s[j+1]>=2&&s[j+2]>=2)
{
s[j+1]-=2;s[j+2]-=2;
}
else return 0;
}
}
if(s[8]==1||s[8]==2||s[9]==1||s[9]==2)return 0;
return 1;
}
int see(int *a,int *b,int *c,int *d)
{
int s[20],p[20],m[20],z[20];
int flag;
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
{
s[j]=a[j];p[j]=b[j];m[j]=c[j];z[j]=d[j];
}
if(s[i]>=2)s[i]-=2;//枚举并删去对子
if(f(s)&&f(p)&&f(m)&&ff(z))return 1;
}
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
{
s[j]=a[j];p[j]=b[j];m[j]=c[j];z[j]=d[j];
}
if(p[i]>=2)p[i]-=2;
if(f(s)&&f(p)&&f(m)&&ff(z))return 1;
}
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
{
s[j]=a[j];p[j]=b[j];m[j]=c[j];z[j]=d[j];
}
if(m[i]>=2)m[i]-=2;
if(f(s)&&f(p)&&f(m)&ff(z))return 1;
}
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
{
s[j]=a[j];p[j]=b[j];m[j]=c[j];z[j]=d[j];
}
if(z[i]>=2)z[i]-=2;
if(f(s)&&f(p)&&f(m)&&ff(z))return 1;
}
return 0;
}
int main()
{
char ch[5];
while(cin>>ch)
{
int s[20]={0},p[20]={0},m[20]={0},z[20]={0};
if(ch[1]=='s')s[ch[0]-'0']++;
if(ch[1]=='p')p[ch[0]-'0']++;
if(ch[1]=='m')m[ch[0]-'0']++;
if(ch[1]=='z')z[ch[0]-'0']++;
for(int i=2;i<=13;i++)
{
cin>>ch;
if(ch[1]=='s')s[ch[0]-'0']++;
if(ch[1]=='p')p[ch[0]-'0']++;
if(ch[1]=='m')m[ch[0]-'0']++;
if(ch[1]=='z')z[ch[0]-'0']++;
}
for(int i=1;i<=9;i++)
{
if(m[i]>=4)continue;
m[i]++;
if(see(s,p,m,z))printf("%dm\n",i);
m[i]--;
}
for(int i=1;i<=9;i++)
{
if(s[i]>=4)continue;
s[i]++;
if(see(s,p,m,z))printf("%ds\n",i);
s[i]--;
}
for(int i=1;i<=9;i++)
{
if(p[i]>=4)continue;
p[i]++;
if(see(s,p,m,z))printf("%dp\n",i);
p[i]--;
}
for(int i=1;i<=7;i++)
{
if(z[i]>=4)continue;
z[i]++;
if(see(s,p,m,z))printf("%dz\n",i);
z[i]--;
}
}
return 0;
}
/*3m 3m 3m 4m 5m 6m 6m 6m 1z 1z 1z 2z 2z
1p 1p 1p 4p 5p 6p 9p 9p 9p 8p 8p 8p 8p
1s 1s 1s 1s 2s 2s 2s 2s 3p 3p 3p 5p 5p
1s 1s 2s 3s 5s 5s 6s 6s 7s 7s 7s 8s 9s
1s 1s 1s 2s 3s 4s 5s 6s 7s 8s 9s 9s 9s*/
View Code
D题:“星云系统”
题目链接:https://nanti.jisuanke.com/t/39614
第一种解法:用单调栈
#include<bits/stdc++.h>
using namespace std;
stack<char>q;
char a[5000010],b[5000010];
int main()
{
scanf("%s",a);
int s=strlen(a);
int k;
scanf("%d",&k);
q.push(a[0]);
for(int i=1;i<s;i++)
{
while(!q.empty())
{
char t=q.top();
if(t<=a[i])
{
//q.push(a[i]);
break;
}
else
{
if(s-i+q.size()>k)q.pop();
else break;
}
}
q.push(a[i]);
}
int t=0;
while(!q.empty())
{
b[++t]=q.top();q.pop();
}
for(int i=t;i>t-k;i--)
printf("%c",b[i]);
return 0;
}
View Code
第二种解法:用26个vector存字母位置然后暴力,好像叫序列自动机
#include<bits/stdc++.h>
using namespace std;
const int maxx = 5e6+10;
vector<int>q[30];
char a[maxx];
int pos[30],len;
int find(int i,int s)//pos[i]用来标记用过的位置
{
while(q[i][pos[i]]<s && pos[i]<q[i].size())
pos[i]++;
return q[i][pos[i]];
}
void dfs(int s,int k)//s为当前位置
{
if(!k)return;
for(int i=0;i<26;i++)
{
int t=find(i,s);
if(t>=s&&len-t+1>=k)
{
printf("%c",i+'a');
dfs(t+1,k-1);
return;
}
}
}
int main()
{
for(int i=0;i<26;i++)q[i].push_back(0);
scanf("%s",a+1);
len=strlen(a+1);
for(int i=1;i<=len;i++)
q[a[i]-'a'].push_back(i);
int k;
scanf("%d",&k);
dfs(1,k);
return 0;
}
View Code
E题:撑起信息安全“保护伞
题目链接:https://nanti.jisuanke.com/t/39615
题解:
就是找 ")(" 和 合法的"()"
#include<bits/stdc++.h>
using namespace std;
const int maxx = 1e6+10;
char a[maxx],b[maxx];
stack<char>q;
int main()
{
scanf("%s",a);
int s=strlen(a);
strcpy(b,a);
int flag=0;
for(int i=s-1;i>=1;i--)
{
if(b[i]=='('&&b[i-1]==')')//找")("
{
b[i]=')';b[i-1]='(';
int t=0;
for(int j=i+1;j<s;j++)
{
if(b[j]=='(')q.push(b[j]);
else
{
if(b[j]==')'&&!q.empty())q.pop();
else if(b[j]==')'&&q.empty())t++;
}
}
for(int j=i+1;j<i+1+t;j++)
b[j]=')';
for(int j=i+1+t;j<s-1;j+=2)
b[j]='(',b[j+1]=')';
flag=1;break;
}
}
if(flag)printf("%s\n",b);
else
{
for(int i=0;i<s-2;i+=2)
printf("()");
printf("\n");
}
strcpy(b,a);
flag=0;
for(int i=s-1;i>=1;i--)
{
if(b[i]==')'&&b[i-1]=='(')//找交换后合法的"()"
{
while(!q.empty())q.pop();
b[i]='(';b[i-1]=')';
int j;
for(j=0;j<s;j++)
{
if(b[j]=='(')q.push(b[j]);
else
{
if(b[j]==')'&&!q.empty())q.pop();
else break;
}
}
if(j<s||!q.empty())b[i]=')',b[i-1]='(';
else
{
int t=0;
for(int k=i+1;k<s;k++)
if(b[k]=='(')t++;
for(int k=i+1;k<i+1+t;k++)b[k]='(';
for(int k=i+1+t;k<s;k++)b[k]=')';
flag=1;break;
}
}
}
if(flag==1)printf("%s",b);
else
{
s=s+2;
for(int i=1;i<=s/2;i++)
printf("(");
for(int i=s/2+1;i<=s;i++)
printf(")");
}
return 0;
}
/*((((()))))()()()()(())
((()())())*/
View Code