ARC155
ARC155
A
模拟一下你会发现这个长度为\(k\)子串\(T\)会在左右依次填\(S,S^{rev}\)
这个我们可以直接让\(k\bmod 2n\)(最开始\(\bmod n\)了\kk)
然后你会发现填到最后就是\(T\)前\(n\)个\(S^{rev}\),后面\(S\)
直接\(check\)一下即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T;
long long k;
int n;
string s;
signed main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%lld",&T);
while(T--)
{
scanf("%lld %lld",&n,&k);
k%=2*n;
cin>>s;
string t;
t.resize(k,'.');
for(int i=0;i<k;i++)
{
if(!(i/n))
{
t[i]=s[n-(i%n)-1];
}
else
{
t[i]=s[i%n];
}
}
//cout<<t<<endl;
string A=s+t;
string B=t+s;
int C=A.size();
bool f=1;
for(int i=0;i<A.size();i++)
{
int To=C-i-1;
if(A[i]!=A[To])
{
f=0;
}
if(B[i]!=B[To])
{
f=0;
}
}
if(f)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
}
B
注意到\(||a-x|-b|=min(|x-(a+b)|,|x-(a-b)|)\)
然后就把它拆成\((a+b),(a-b)\)用\(set\)维护即可
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int Q;
int A,B;
int t,a,b;
set<int>s;
signed main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d %d",&Q,&A,&B);
s.insert(A+B);
s.insert(A-B);
//printf("%d %d\n",A+B,A-B);
while(Q--)
{
scanf("%d %d %d",&t,&a,&b);
if(t==1)
{
s.insert(a-b);
s.insert(a+b);
// printf("%d %d\n",a-b,a+b);
}
else
{
int Res=0x3f3f3f3f;
auto it=s.lower_bound(a);
if((it!=s.end()))
{
if((*it)<=b)
{
Res=0;
}
else
{
Res=min(Res,(*it)-a);
}
}
it=s.upper_bound(a);
if(it!=s.begin())
{
--it;
Res=min(Res,a-(*it));
}
it=s.upper_bound(b);
if(it!=s.begin())
{
--it;
if((*it)>=a)
{
Res=0;
}
else
{
Res=min(Res,b-(*it));
}
}
it=s.lower_bound(b);
if(it!=s.end())
{
Res=min(Res,(*it)-b);
}
printf("%d\n",Res);
}
}
}
C
操作一定是三个偶数或者是两奇一偶
如果存在两奇一偶说明所有奇数可以自由滑动
事实上这种情况只要满足偶数个数\(\ge 2\)就能任意排序
考虑一次性把奇数全部提到最前面,然后在取一个奇数出来
如果不能自由滑动,说明可以用奇数划分,每个块内自由排序
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n;
int A[MAXN];
int B[MAXN];
int Ap[MAXN];
int Bp[MAXN];
int main()
{
scanf("%d",&n);
vector<int>odd;
vector<int>even;
for(int i=1;i<=n;i++)
{
scanf("%d",&A[i]);
Ap[i]=A[i];
if(A[i]&1)
{
odd.push_back(i);
}
else
{
even.push_back(i);
}//////
}
vector<int>Even;
vector<int>Odd;
for(int i=1;i<=n;i++)
{
scanf("%d",&B[i]);
Bp[i]=B[i];
if(B[i]&1)
{
Odd.push_back(i);
}
else
{
Even.push_back(i);
}
}
sort(Ap+1,Ap+1+n);
sort(Bp+1,Bp+1+n);
bool fou=1;
for(int i=1;i<=n;i++)
{
if(Ap[i]!=Bp[i])
{
fou=0;
}
}
if(!fou)
{
printf("No");
return 0;
}
bool found=0;
for(int i=1;i<odd.size();i++)
{
if((odd[i]==odd[i-1]+1)||(odd[i]==odd[i-1]+2))
{
found=1;
}
}
bool Found=0;
for(int i=1;i<odd.size();i++)
{
if((Odd[i]==Odd[i-1]+1)||(Odd[i]==Odd[i-1]+2))
{
Found=1;
}
}
if(!Even.size())
{
found=0;
Found=0;
}
if(found&&Found)
{
if(Even.size()>2)
{
printf("Yes");
}
else
{
int f=1;
for(int i=0;i<even.size();i++)
{
if(A[even[i]]!=B[Even[i]])
{
f=0;
}
}
if(f)
{
printf("Yes");
}
else
{
printf("No");
}
}
}
else if((!Found)&&(!found))
{
bool f=1;
for(int i=0;i<Odd.size();i++)
{
if(B[Odd[i]]!=A[odd[i]])
{
f=0;
}
if(Odd[i]!=odd[i])
{
f=0;
}
}
if(!f)
{
printf("No");
}
else
{
for(int i=0;i<Odd.size();i++)
{
if(i==0)
{
int l=1;
int r=Odd[i]-1;
if(r-l+1>2)
{
}
else
{
for(int j=l;j<=r;j++)
{
if(A[j]!=B[j])
{//
f=0;
}
}
}
}
else
{
int l=Odd[i-1]+1;
int r=Odd[i]-1;
if(r-l+1>2)
{
}
else
{
for(int j=l;j<=r;j++)
{
if(A[j]!=B[j])
{
f=0;
}
}
}
}
if(i==Odd.size()-1)
{
int l=Odd[i]+1;
int r=n;
if(r-l+1>2)
{
}
else
{
for(int j=l;j<=r;j++)
{
if(A[j]!=B[j])
{
f=0;
}
}
}
}
}
if(f)
{
printf("Yes");
}
else
{
printf("No");
}
}
}
else
{
printf("No");
}
}
D
nknb!!!!(话说nk一眼秒)
考虑前面选的数一定是当前\(G\)的倍数
下一步决策要么\(G\rightarrow G',(G'|G),\exist x,gcd(k,G)=G'\)
要么\(G\rightarrow G\)
这里的\(G\rightarrow G\)如果没有的话似乎就可以直接\(dp\)了,我们只需要找到是否存在这样的\(k\),因为这里用了一个\(k\)并不会对后续选择产生影响,这里可以容斥计算个数,对于\(G\)我们从大到小枚举\(G'\)并在后面减去\(G'\)的贡献
如果有呢?
实际上只需要在状态中加入当前是\(G\)的倍数的还有奇数/偶数个
// LUOGU_RID: 118979939
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n;
int A[MAXN];
int C[MAXN];
vector<int>V[MAXN];
int D[MAXN];
int dp[MAXN][2];
signed main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&A[i]);
C[A[i]]++;
}
for(int i=1;i<=MAXN-5;i++)
{
for(int j=2*i;j<=MAXN-5;j+=i)
{
V[j].push_back(i);
C[i]+=C[j];
}
}
for(int i=1;i<=MAXN-5;i++)
{
reverse(V[i].begin(),V[i].end());
}
for(int i=1;i<=MAXN-5;i++)
{
if(i==1)
{
dp[i][0]=1;
dp[i][1]=1;
continue;
}
for(int j=0;j<V[i].size();j++)
{
D[V[i][j]]=C[V[i][j]]-C[i];
}
for(int j=0;j<V[i].size();j++)
{
if(D[V[i][j]]>0)
{
//printf("%d %d %d??\n",i,V[i][j],dp[V[i][j]][0]);
if(!dp[V[i][j]][0])
{
dp[i][(C[i]&1)^(C[V[i][j]]&1)^1]=1;
}
if(!dp[V[i][j]][1])
{
dp[i][(C[i]&1)^(C[V[i][j]]&1)]=1;
}
}
for(int k=0;k<V[V[i][j]].size();k++)
{
D[V[V[i][j]][k]]-=D[V[i][j]];
}
}
if((!dp[i][0]))
{
dp[i][1]=1;
}
}
for(int i=1;i<=n;i++)
{
if(!dp[A[i]][(C[A[i]]-1)&1])
{
printf("Takahashi\n");
}
else
{
printf("Aoki\n");
}
}
}