Educational Codeforces Round 127 (Rated for Div. 2)
A
显然，长度 \(2\) 和 \(3\) 能拼出任意长度字符串，所以无解情况考虑有没有单独的长度为 \(1\) 的即可。
/*
by L1rs1ngzN1sLyr
*/
#include<bits/stdc++.h>
const int AI=1e3+9;
const int KI=1e6+2;
const int CI=1e7+3;
int read(){int x=0,w=1;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*w;}
int main()
{
int T=read();
while(T--)
{
std::string a;
std::cin>>a;
int cnta=0,cntb=0;
int flag=1;
for(int i=0;i<a.size();i++)
{
if(a[i]=='a')
{
cnta++;
if(cntb==1)
{
flag=0;
break;
}
else cntb=0;
}
else if(a[i]=='b')
{
cntb++;
if(cnta==1)
{
flag=0;
break;
}
else cnta=0;
}
}
if(!flag || cnta==1 || cntb==1) std::cout<<"No\n";
else std::cout<<"Yes\n";
}
}
B
要变成连续的排列，那么情况就好讨论了。
给出的序列严格递增，所以从左往右扫一遍。
两个相邻的数可以，当且仅当它们差不超过三，差等于三的时候整个序列不能有差为二的且不能有多个差等于三的，差等于二时整个序列不能有两个超过二的。
/*
by L1rs1ngzN1sLyr
*/
#include<bits/stdc++.h>
const int AI=1e3+9;
const int KI=1e6+2;
const int CI=1e7+3;
int read(){int x=0,w=1;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*w;}
int a[KI];
int main()
{
int T=read();
while(T--)
{
int n=read(),cnta=0,cntb=0,flag=1;
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<n;i++)
{
if(a[i+1]-a[i]>3) flag=0;
else if(a[i+1]-a[i]==3) cntb++;
else if(a[i+1]-a[i]==2) cnta++;
}
if(cnta && cntb) std::cout<<"NO\n";
else if(!flag) std::cout<<"NO\n";
else if(cnta>2) std::cout<<"NO\n";
else if(cntb>1) std::cout<<"NO\n";
else std::cout<<"YES"<<'\n';
}
}
C
用前缀和可以做到常数复杂度查询前几个的总价值，所以排序后边枚举买前 \(i\) 个边二分天数判断能买多少即可。
/*
by L1rs1ngzN1sLyr
*/
#include<bits/stdc++.h>
#define int long long
const int AI=1e3+9;
const int KI=1e6+2;
const int CI=1e7+3;
int read(){int x=0,w=1;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*w;}
int a[KI],s[KI];
signed main()
{
int T=read();
while(T--)
{
int n=read(),x=read();
memset(s,0,sizeof s);
for(int i=1;i<=n;i++) a[i]=read();
std::sort(a+1,a+n+1);
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
int ans=0;
for(int i=1;i<=n;i++)
{
int l=-1,r=x+1;
while(l<r-1)
{
int mid=(l+r)>>1;
if(s[i]+mid*i>x) r=mid;
else l=mid;
}
ans+=l+1;
}
std::cout<<ans<<'\n';
}
}
D
Unsovled.
E
两个子树对答案有贡献，当且仅当他们构成的先序串不同，每个能交换产生贡献的子树对答案贡献显然是 \(2\)，统计不同的先序串左右子树即可，答案即为 \(2^{这个数量}\)。
/*
by L1rs1ngzN1sLyr
*/
#include<bits/stdc++.h>
#define int long long
const int AI=1e3+9;
const int KI=1e6+2;
const int CI=1e7+3;
const int mod=0x3b800001;
int read(){int x=0,w=1;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*w;}
char a[KI];
std::string b[KI];
int p;
int qsm(int x,int y)
{
int res=1;
while(y)
{
if(y&1) res=res*x%mod;
x=x*x%mod,y>>=1;
}
return res;
}
void dfs(int u,int m)
{
if(u*2+1>m)//leaf
{
b[u]=a[u];
return ;
}
dfs(u*2,m);
dfs(u*2+1,m);
if(b[u*2]!=b[u*2+1]) p++;
if(b[u*2+1]>b[u*2]) b[u]=a[u]+b[u*2+1]+b[u*2];
else b[u]=a[u]+b[u*2]+b[u*2+1];
}
signed main()
{
int n=read();
std::string s;
std::cin>>s;
for(int i=0;i<s.size();i++) a[i+1]=s[i];
dfs(1,s.size());
std::cout<<qsm(2,p)%mod;
}