ARC154
A
似乎是均值反着用,直接最大乘最小即可
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
int n;
string A,B;
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
cin>>A;
cin>>B;
int Mul=1;
int Res=0;
for(int i=n-1;i>=0;i--)
{
if(A[i]>B[i])
{
swap(A[i],B[i]);
}
}
int Ma=0,Mb=0;
for(int i=0;i<n;i++)
{
Ma=((long long)Ma*10+(A[i]-'0'))%MOD;
Mb=((long long)Mb*10+(B[i]-'0'))%MOD;
}
Res=((long long)Ma*Mb)%MOD;
printf("%d\n",Res);
return 0;
}
B
似乎很明显的二分,也明显有单调性
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n;
char A[MAXN];
char B[MAXN];
int C[27];
int check(int x)
{
for(int i=0;i<26;i++)
{
C[i]=0;
}
for(int i=1;i<=x;i++)
{
C[A[i]-'a']++;
}
int Pi=x+1;
for(int i=1;i<=n;i++)
{
if(Pi<=n&&A[Pi]==B[i])
{
++Pi;
}
else if(C[B[i]-'a'])
{
C[B[i]-'a']--;
}
else
{
return 0;
}
}
return 1;
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
scanf("%s",A+1);
scanf("%s",B+1);
int l=0;
int r=n;
int Key=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
{
r=mid-1;
Key=mid;
}
else
{
l=mid+1;
}
}
printf("%d",Key);
return 0;
}
C
成纸张了/kk
感觉像是什么建图然后钦定跑个基环树
结果实际上,如果把\(A\)相邻值相同的缩成一个块,可以发现操作实际上就是块之间的相互侵蚀
但不管怎么弄,相对顺序是不会变的,因此可以直接判断\(B\)缩块后是否是\(A\)的子序列
注意特判一下\(A\)弄不出来的情况
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
int T;
int n;
int A[MAXN];
int B[MAXN];
int Ta[MAXN];
int Tb[MAXN];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&T);
for(int id=1;id<=T;id++)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&A[i]);
}
int Cnx=0;
Ta[++Cnx]=A[1];
int Last=A[1];
for(int i=2;i<=n;i++)
{
if(A[i]==Last)
{
}
else
{
Ta[++Cnx]=A[i];
Last=A[i];
}
}
if(Ta[Cnx]==Ta[1]&&Cnx!=1)
{
Cnx--;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&B[i]);
}
int Ca=Cnx;
Cnx=0;
Tb[++Cnx]=B[1];
Last=B[1];
for(int i=2;i<=n;i++)
{
if(B[i]==Last)
{
}
else
{
Tb[++Cnx]=B[i];
Last=B[i];
}
}
if(Tb[Cnx]==Tb[1]&&Cnx!=1)
{
Cnx--;
}
int Cb=Cnx;
if(Ca==Cb&&Ca==n)
{
bool fp=1;
for(int i=1;i<=Ca;i++)
{
if(Ta[i]!=Tb[i])
{
fp=0;
}
}
if(fp)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
continue;
}
bool f=0;
for(int i=1;i<=Ca;i++)
{
int Pi=1;
for(int j=i;j<=Ca;j++)
{
if(Pi<=Cb&&Ta[j]==Tb[Pi])
{
++Pi;
}
}
for(int j=1;j<i;j++)
{
if(Pi<=Cb&&Ta[j]==Tb[Pi])
{
++Pi;
}
}
if(Pi==Cb+1)
{
f=1;
}
}
if(f)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
return 0;
}
D
先找\(1\),只要\(2P_i>P_j\)返回\(No\)说明\(i\)可能成为\(1\),直接顺着做即可,会用\(N\)次操作
找到\(1\)后，\(P_i+1>P_j\)返回\(No\)直接说明\(P_i<P_j\),因此我们可以比较两数大小
直接归并即可
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2005;
int n;
int P[MAXN];
int Tmp[MAXN];
string S;
int P1=1;
bool cmp(int x,int y)
{
cout<<'?'<<' '<<x<<' '<<P1<<' '<<y<<endl;
cin>>S;
if(S[0]=='N')
{
return 0;
}
return 1;
}
void solve(int l,int r)
{
if(l>r)
{
return;
}
if(l==r)
{
return;
}//3 1 2 4
int mid=(l+r)>>1;
solve(l,mid);
solve(mid+1,r);
int pi=l;
int pj=mid+1;
int pt=l;
while(pi<=mid&&pj<=r)
{
if(!cmp(P[pi],P[pj]))
{
Tmp[pt++]=P[pi++];
}
else
{
Tmp[pt++]=P[pj++];
}
}
while(pi<=mid)
{
Tmp[pt++]=P[pi++];
}
while(pj<=r)
{
Tmp[pt++]=P[pj++];
}
for(int i=l;i<=r;i++)
{
P[i]=Tmp[i];
}
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
cin>>n;
for(int i=2;i<=n;i++)
{
cout<<'?'<<' '<<i<<' '<<i<<' '<<P1<<endl;
cin>>S;
if(S[0]=='N')
{
P1=i;
}
}
for(int i=1;i<=n;i++)
{
P[i]=i;
}
solve(1,n);
for(int i=1;i<=n;i++)
{
Tmp[P[i]]=i;
}
cout<<'!';
for(int i=1;i<=n;i++)
{
cout<<' '<<Tmp[i];
}
cout<<endl;
return 0;
}
E
神仙题
首先考虑\(f(P)\)是什么
考虑拆开每个\(i\)的贡献\(f(P)=\sum\limits_{i=1}i(\sum\limits_{j<i}[P_i<P_j]-\sum\limits_{j>i}[P_j<P_i])\)
注意到
\(\sum\limits_{j<i}[P_i<P_j]+\sum\limits_{j<i}[P_i>P_j]=i-1\)
\(\sum\limits_{j<i}[P_i>P_j]+\sum\limits_{j>i}[P_i>P_j]=P_i-1\)
两式相减就是上面括号里面的式子
即\(\sum\limits_{i=1}i(i-P_i)\)
有\(m\)次操作这玩意直接求并不好做,我们考虑求个期望
问题在于求\(E(\sum\limits iP_i)\)
也即\(\sum\limits E(i)P_i\)
然后你会发现,如果有操作作用到\(i\)上,考虑走到\(j\)
其满足的方案数为\(min(i,n-i+1,j,n-j+1)\),那其实走到\(n-j+1\)的概率和走到\(j\)的概率是一样的,那\(j,n-j+1\)对期望的贡献就是\(P(j)\dfrac{n+1}{2}\)
因此\(E(i)\)决定于\(i\)是否会被操作,这个直接算就行了
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
const int MAXN=2e5+5;
int Pow(int a,int b,int p)
{
int res=1;
int base=a;
while(b)
{
if(b&1)
{
res=((long long)res*base)%p;
}
base=((long long)base*base)%p;
b>>=1;
}
return res;
}
int inv(int a,int p)
{
return Pow(a,p-2,p);
}
int n,m;
int P[MAXN];
int inv2;
int C(int n)
{
return ((((long long)n*(n+1))%MOD)*inv2)%MOD;
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d",&n,&m);
inv2=MOD-MOD/2;
int Res=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&P[i]);
Res=((long long)Res+((long long)i*i)%MOD)%MOD;
}
for(int i=1;i<=n;i++)
{
int p=((((long long)C(i-1)+C(n-i))%MOD)*(inv(C(n),MOD)))%MOD;
int Rp=((long long)Pow(p,m,MOD)*i)%MOD;
int Rq=(((long long)(1ll-Pow(p,m,MOD)+MOD)%MOD)*((((long long)n+1)*inv2)%MOD))%MOD;
Rp=((long long)Rp+Rq)%MOD;
//printf("%d %d %d???\n",p,i,Rp);
Rp=((long long)Rp*P[i])%MOD;
Res=((long long)Res-Rp+MOD)%MOD;
}
Res=((long long)Res*Pow(C(n),m,MOD))%MOD;
printf("%d",Res);
return 0;
}