A.Marin and PhotoshootB.Marin and Anti-coprime PermutationC.Shinju and the Lost PermutationD1.388535 (Easy Version)D2.388535 (Hard Version)E.Gojou and Matrix GameF.Juju and Binary String
A.Marin and Photoshoot题意：有一串01串，0代表男生，1代表女生，你可以进行添加男生操作，使得对于任意一段
[
l
,
r
]
[l,r]
[l,r](r>=l+1)中男生的数量不超过女生。问最少操作几次。
题解：首先对于男生来说，两边都必须为女生，对于长度为3的时候，女生数量必须大于等于2。也就是说两个男生之间必须要有至少两个女生。
void solve(){
int n;
cin>>n;
string s;
cin>>s;
int a=0,b=0;
vectorv;
for(int i=0;i>t;
// t=1;
while(t--){
solve();
}
return 0;
}
B.Marin and Anti-coprime Permutation
题意：
p
1
,
p
2
,
p
3
.
.
.
p
n
p_1,p_2,p_3...p_n
p1,p2,p3...pn为
[
1
,
n
]
[1,n]
[1,n]的排列，问满足
g
c
d
(
1
∗
p
1
,
2
∗
p
2
,
.
.
.
n
∗
p
n
)
>
1
gcd(1*p_1,2*p_2,...n*p_n)>1
gcd(1∗p1,2∗p2,...n∗pn)>1的方案数。
题解：
对于相邻的两个数，一奇一偶
g
c
d
gcd
gcd为
1
1
1,为了使得
g
c
d
>
1
gcd>1
gcd>1，我们必须把奇数安排在偶数位置，因此当n为奇数时，有一个奇数没有偶数位置安排，答案为0，n为偶数时，奇偶数分开全排列，
a
n
s
=
(
n
2
!
n
2
!
)
ans=(frac{n}{2}!frac{n}{2}!)
ans=(2n!2n!)
ll fac[maxn];
void solve(){
ll n;
cin>>n;
if(n%2)cout<<"0n";
else cout<>t;
// t=1;
fac[0]=1;
for(ll i=1;i
C.Shinju and the Lost Permutation
题意：现在有一个
[
1
,
n
]
[1,n]
[1,n]的数组P，但是顺序忘记了，只知道它的C数组，问这个C数组是否合法。
定义B数组为
b
i
=
m
a
x
(
p
1
,
p
2
,
.
.
.
p
i
)
b_i=max(p_1,p_2,...p_i)
bi=max(p1,p2,...pi)
定义C数组为
c
i
=
p
循
环
右
移
(
i
−
1
)
位
得
到
的
b
数
组
去
重
后
的
个
数
c_i=p循环右移(i-1)位得到的b数组去重后的个数
ci=p循环右移(i−1)位得到的b数组去重后的个数
首先B数组一定是递增的。
当最大值
n
n
n在第一个时，
B
=
n
,
n
,
.
.
n
,
c
i
=
1
B={n,n,..n},c_i=1
B=n,n,..n,ci=1。当c等于1时说明当前位置最大值在第一个位置。
那么我们对c数组移动使得1在第一个位置，这样当我们循环右移时最大值后面的状态都不用考虑，因为取max都为
n
n
n。当当前最后一个数移动到第一位时，然后小于后面的数，他就会使得c+1，所以相邻的两项最多只会差1，并且后面的c都不可能为1.
int a[maxn];
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
vectorv;
int index=-1;
for(int i=1;i<=n;i++){
if(a[i]==1){
index=i;
break;
}
}
if(index==-1){
cout<<"NOn";
return;
}
for(int i=index;i<=n;i++)v.push_back(a[i]);
for(int i=1;ii+1||v[i]==1||v[i]>v[i-1]+1){
cout<<"NOn";
return;
}
}
cout<<"YESn";
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin>>t;
// t=1;
while(t--){
solve();
}
return 0;
}
D1.388535 (Easy Version)
题意：
[
l
,
r
]
区
间
中
的
所
有
数
异
或
上
x
得
到
a
数
组
[l,r]区间中的所有数异或上x得到a数组
[l,r]区间中的所有数异或上x得到a数组，问
x
x
x的值。
（
l
=
=
0
）
（l==0）
（l==0）
题解：
对
[
l
,
r
]
[l,r]
[l,r]中的数进行二进制拆分,对
[
a
1
,
a
r
−
l
+
1
]
[a_1,a_{r-l+1}]
[a1,ar−l+1]也进行拆分，若拆分后第
i
i
i位的个数不相同，说明这一位进行了异或操作，使得个数翻转了，将这一位计入答案。
int num[30],num2[30];
void solve(){
int l,r;
cin>>l>>r;
for(int i=0;i<=17;i++)num[i]=0;
for(int i=0;i<=17;i++)num2[i]=0;
for(int i=1,x;i<=r-l+1;i++){
cin>>x;
for(int j=0;j<=17;j++){
if((x>>j)&1){
num[j]++;
}
}
}
for(int i=l;i<=r;i++){
for(int j=0;j<=17;j++){
if((i>>j)&1){
num2[j]++;
}
}
}
int ans=0;
for(int i=0;i<=17;i++){
if(num[i]==num2[i])continue;
else ans+=(1<>t;
// t=1;
while(t--){
solve();
}
return 0;
}
D2.388535 (Hard Version)
题意：同D1，但是
(
l
>
=
0
)
(l>=0)
(l>=0)
题解：当
l
!
=
0
l!=0
l!=0时，上面的构造方法就存在问题。
首先我们得知道
[
l
,
r
]
[l,r]
[l,r]中得值，两两异或都不为0，因为任意两个值都不相等。那么所有值都异或上
x
x
x后，所有值也都不相等，因为异或后得两个值异或等价于
(
i
⨁
x
)
⨁
(
j
⨁
x
)
=
(
i
⨁
j
)
(i bigoplus x) bigoplus (j bigoplus x)=(i bigoplus j)
(i⨁x)⨁(j⨁x)=(i⨁j),所以异或后的任意两个值也不相等，那么我们枚举
x
x
x的时候，只需要计算a数组异或上
x
x
x的最小值为
l
l
l,最大值为
r
r
r就可以确定这个数组异或上
x
x
x得到的为
[
l
,
r
]
[l,r]
[l,r]
异或最大最小值用01字典树可以log的算出，枚举x的时间为n，总时间为nlog
int tol; //节点个数
ll val[32*maxn]; //点的值
int ch[32*maxn][2]; //边的值
void init()
{ //初始化
for(int i=0;i<=tol;i++)ch[i][0]=ch[i][1]=0;
tol=1;
}
void insert(ll x)
{ //往 01字典树中插入 x
int u=0;
for(int i=16;i>=0;i--)
{
int v=(x>>i)&1;
if(!ch[u][v])
{ //如果节点未被访问过
ch[tol][0]=ch[tol][1]=0; //将当前节点的边值初始化
val[tol]=0; //节点值为0，表示到此不是一个数
ch[u][v]=tol++; //边指向的节点编号
}
u=ch[u][v]; //下一节点
}
val[u]=x; //节点值为 x，即到此是一个数
}
ll query(ll x)
{ //查询所有数中和 x异或结果最大的数
int res=0;
int u=0;
for(int i=16;i>=0;i--)
{
int v=(x>>i)&1;
//利用贪心策略，优先寻找和当前位不同的数
if(ch[u][v^1]) u=ch[u][v^1],res|=(1<=0;i--)
{
int v=(x>>i)&1;
//利用贪心策略，优先寻找和当前位不同的数
if(ch[u][v]) u=ch[u][v];
else u=ch[u][v^1],res|=(1<>l>>r;
init();
for(int i=l;i<=r;i++){
cin>>x;
insert(x);
}
for(int i=l;i<=r;i++){
int ans=x^i;
int mx=query(ans);
int mn=query_min(ans);
if(mn==l&&mx==r){
cout<>t;
while(t--){
solve();
}
return 0;
}
E.Gojou and Matrix Game
题意：两个人博弈，有一个n*n的棋盘，每个点都有不同的值，两个下的棋子之间的曼哈顿距离不得小于等于k，问对于每个点，若先手下这个点，谁获胜。，每人下
1
0
100
次
10^{100}次
10100次
题解：对于后手下的人，若在先手的k距离外，没有比k距离内的值大，就输了，因为先手的一直都比你大，你又进不去k的范围内。反之后手就赢了。
按点值从大到小枚举，最大的点值先手下必胜，再进行转移，对于所有的必胜点都得在目前点的k范围内，只有这样目前点才能为必胜点。
判断是否覆盖所有必胜点只需要维护上下左右四个端点值。
int u,d,l,r,k,n;
bool check(int i,int j){
return (abs(i-u)<=k&&abs(i-d)<=k&&abs(j-l)<=k&&abs(j-r)<=k);
}
int dp[2222][2222];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>k;
vector>v;
for(int i=1;i<=n;i++){
for(int j=1,x;j<=n;j++){
cin>>x;
v.push_back({x,i,j,i+j,j-i});
}
}
sort(v.begin(),v.end(),greater>());
u=v[0][3];d=v[0][3];l=v[0][4];r=v[0][4];
for(auto &it:v){
if(check(it[3],it[4])){
dp[it[1]][it[2]]=1;
u=min(u,it[3]);
d=max(d,it[3]);
l=min(l,it[4]);
r=max(r,it[4]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dp[i][j])cout<<"M";
else cout<<"G";
}
cout<<"n";
}
return 0;
}
F.Juju and Binary String
题意：有一串01串，该S串的值定义为
n
u
m
1
n
frac{num1}{n}
nnum1,你需要找k个连续字串拼成长度为
m
m
m的串，使得它们的值相同。
题解：
首先T字符串的1的值设为
x
x
x,
x
m
=
n
u
m
1
n
frac{x}{m}=frac{num1}{n}
mx=nnum1
若
n
u
m
1
∗
m
%
n
!
=
0
num1*m%n!=0
num1∗m%n!=0无解。
否则
x
=
n
u
m
1
∗
m
/
n
x=num1*m/n
x=num1∗m/n转化为找k个字串使得子串的长度为
m
m
m，1的数量为
x
x
x
存在一个结论k一定<=2;分类讨论。
我们现在还假设这个字符串是圆形的。考虑这个圆形字符串中任何长度为m的子数组，包括环绕的子数组。如果我们能找到一个恰好有
x
x
x个
1
1
1的子数，那么我们需要的最小零件数是
1
1
1或
2
2
2，这取决于它是否环绕。而这两者都可以用滑动窗口/前缀和来检查。
事实证明，这样的子阵列总是存在的。如果
i
≤
n
−
m
+
1
i≤n-m+1
i≤n−m+1，让
c
i
c_i
ci为
s
[
i
.
.
.
i
+
m
−
1
]
s[i...i+m-1]
s[i...i+m−1]中的
1
1
1的数量，否则为
s
[
1...
m
−
(
n
−
i
+
1
)
]
+
s
[
i
.
.
.
n
]
s[1...m-(n-i+1)]+s[i...n]
s[1...m−(n−i+1)]+s[i...n]（即，环绕的子阵列与不环绕的子阵列）。请注意，对于所有
1
≤
i
<
n
1≤i
假设
m
a
x
(
c
i
)
≥
x
max(c_i)≥x
max(ci)≥x和
m
i
n
(
c
i
)
≤
x
min(c_i)≤x
min(ci)≤x，意味着某些
c
i
=
x
c_i=x
ci=x。假设
m
a
x
(
c
i
)
<
x
max(c_i)
m
⋅
n
u
m
1
x*n>m⋅num1
x∗n>m⋅num1，这与
x
x
x的定义是矛盾的。
∑
i
=
1
n
c
i
=
m
⋅
n
u
m
1
>
n
⋅
x
sum_{i=1}^nci=m⋅num1>n⋅x
∑i=1nci=m⋅num1>n⋅x，或者
x
∗
n
<
m
⋅
n
u
m
1
x*n
int num[maxn];
void solve(){
int n,m;
cin>>n>>m;
string s;
cin>>s;
num[0]=0;
for(int i=0;i>t;
while(t--){
solve();
}
return 0;
}
