很 Easy 一场，共计用时 \(34\) min
A
const int N=1000100;
signed main(){
string s;cin>>s;
int cnt=0;
int n=s.size();
if(s[n-1]=='0'&&s[n-2]=='0'&&s[n-3]=='0'){
s.pop_back();
s.pop_back();
s.pop_back();
s.pop_back();
}else{
while(s.back()=='0')
s.pop_back();
}
cout<<s<<'\n';
}
B
signed main(){
string s;cin>>s;
int cnt=0;
int n=s.size();
if(s[n-1]=='0'&&s[n-2]=='0'&&s[n-3]=='0'){
s.pop_back();
s.pop_back();
s.pop_back();
s.pop_back();
}else{
while(s.back()=='0')
s.pop_back();
}
cout<<s<<'\n';
}
C
发现数的范围很小，所以直接 dfs 然后判断是否合法即可。
const int N=1000100;
int a[N],b[N],n,k;
void dfs(int dep){
if(dep==n+1){
int s=0;
F(i,1,n)s+=b[i];
if(s%k==0){
F(i,1,n)cout<<b[i]<<' ';
cout<<'\n';
}
return;
}
F(i,1,a[dep]){
b[dep]=i;
dfs(dep+1);
}
}
signed main(){
cin>>n>>k;
F(i,1,n)cin>>a[i];
dfs(1);
}
D
考虑经典套路破换成链，然后双指针扫描合法区间，即求在合法区间内和在模 \(M\) 意义下同余 \(0\) 的方案数。记录每一个前缀和出现次数即可。时间复杂度为 \(O(n)\) 但是我写丑了所以是 \(O(n\log n)\) 的。
const int N=1000100;
int a[N],s[N];
signed main(){
int n,m;cin>>n>>m;
F(i,1,n)cin>>a[i];
F(i,1,n-1)a[i+n]=a[i];
F(i,1,n+n-1)s[i]=(s[i-1]+a[i])%m;
map<int,int>mp;
int cnt=0;
F(i,1,n+n-1){
if(i>n)--mp[s[i-n]];
cnt+=(mp[s[i]]);
if(i<=n)++mp[s[i]];
// cout<<i<<": "<<s[i]<<' '<<mp[s[i]]-1<<'\n';
}
cout<<cnt<<'\n';
}
E
经典套路，将每一个点分开考虑。设 \(f_{i,x}\) 表示 \(x\) 点连续执行 \(2^i\) 次操作之后到达的点，因此 \(O(\log n)\) 时间复杂度内暴力跳得每一个点的答案即可。时间复杂度为 \(O(n\log n)\)。注意数组不要开小要不然会像我一样调 15min。
const int N=200100;
int x[N],a[N],f[63][N],b[N];
int get(int x,int y){
int t=x;
F(i,0,62)
if(y>>i&1)
x=f[i][x];
return x;
}
signed main(){
int n,k;cin>>n>>k;
F(i,1,n)cin>>x[i];
F(i,1,n)cin>>a[i];
if(k==0){
F(i,1,n)cout<<a[i]<<' ';
cout<<'\n';
return 0;
}
F(i,1,n)f[0][i]=x[i];
F(i,1,62)
F(j,1,n)f[i][j]=f[i-1][f[i-1][j]];
F(i,1,n)
cout<<a[get(i,k)]<<' ';
cout<<'\n';
}
F
参见原神数学测试本上第 \(35\) 页的 DS 第 \(11\) 题
考虑给两个序列都做一个和位置无关的哈希，然后建两棵线段树，计算其哈希值是否全都一样即可。时间复杂度为 \(O(n\log n)\)。
因为这一类哈希的冲突概率极大，因此考虑多写几个哈希，或者给每一个值随机赋权即可。
const int N=1000100;
int a[N],b[N];
namespace _1{
using ull=unsigned long long;
const int m1=998244353,m2=1e9+7;
struct qwq{
int l,r,sum,xr,s4m1,s4m2;
ull s2,s3;
void init(int p){
l=r=p;
sum=xr=a[p];
s2=a[p]*a[p];
s3=a[p]*a[p]*a[p];
s4m1=a[p]*a[p]%m1*a[p]%m1*a[p]%m1;
s4m2=a[p]*a[p]%m2*a[p]%m2*a[p]%m2;
}
}z[N<<2];
qwq operator+(const qwq&l,const qwq &r){
return {l.l,r.r,l.sum+r.sum,l.xr^r.xr,(l.s4m1+r.s4m1)%m1,(l.s4m2+r.s4m2)%m2,l.s2+r.s2,l.s3+r.s3};
}
void build(int l,int r,int rt){
if(l==r)return z[rt].init(l);
int mid=l+r>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
z[rt]=z[rt<<1]+z[rt<<1|1];
}
qwq qu(int l,int r,int rt,int ll,int rr){
if(ll<=l&&r<=rr)return z[rt];
int mid=l+r>>1;
if(ll<=mid&&mid<rr)return qu(l,mid,rt<<1,ll,rr)+qu(mid+1,r,rt<<1|1,ll,rr);
if(ll<=mid)return qu(l,mid,rt<<1,ll,rr);
return qu(mid+1,r,rt<<1|1,ll,rr);
}
}
namespace _2{
using ull=unsigned long long;
const int m1=998244353,m2=1e9+7;
struct qwq{
int l,r,sum,xr,s4m1,s4m2;
ull s2,s3;
void init(int p){
l=r=p;
sum=xr=b[p];
s2=b[p]*b[p];
s3=b[p]*b[p]*b[p];
s4m1=b[p]*b[p]%m1*b[p]%m1*b[p]%m1;
s4m2=b[p]*b[p]%m2*b[p]%m2*b[p]%m2;
}
}z[N<<2];
qwq operator+(const qwq&l,const qwq &r){
return {l.l,r.r,l.sum+r.sum,l.xr^r.xr,(l.s4m1+r.s4m1)%m1,(l.s4m2+r.s4m2)%m2,l.s2+r.s2,l.s3+r.s3};
}
void build(int l,int r,int rt){
if(l==r)return z[rt].init(l);
int mid=l+r>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
z[rt]=z[rt<<1]+z[rt<<1|1];
}
qwq qu(int l,int r,int rt,int ll,int rr){
if(ll<=l&&r<=rr)return z[rt];
int mid=l+r>>1;
if(ll<=mid&&mid<rr)return qu(l,mid,rt<<1,ll,rr)+qu(mid+1,r,rt<<1|1,ll,rr);
if(ll<=mid)return qu(l,mid,rt<<1,ll,rr);
return qu(mid+1,r,rt<<1|1,ll,rr);
}
}
signed main(){
int n,q;cin>>n>>q;
F(i,1,n)cin>>a[i];
F(i,1,n)cin>>b[i];
_1::build(1,n,1);
_2::build(1,n,1);
while(q--){
int l,r,ll,rr;
cin>>l>>r>>ll>>rr;
if(r-l+1==rr-ll+1){
auto f1=_1::qu(1,n,1,l,r);
auto f2=_2::qu(1,n,1,ll,rr);
if(f1.sum==f2.sum&&f1.xr==f2.xr&&f1.s2==f2.s2&&f1.s3==f2.s3&&f1.s4m1==f2.s4m1&&f1.s4m2==f2.s4m2)cout<<"Yes\n";
else cout<<"No\n";
}else cout<<"No\n";
}
}