B.Electric Board
题目描述
给定长度为 \(n\) 两个字符串 \(S,T\)，要求通过最少的操作数把 \(S\) 变成 \(T\)，操作就是对于 \(s_l=0\and s_{l+1}=...=s_r=1\) 或者 \(s_l=1\and s_{l+1}=...=s_r=0\) 可以交换元素 \(s_l\) 和 \(s_r\)
\(2\leq n\leq 500000\)
解法1
我们可以把所有 \(0\) 换到应该的位置上，那么 \(1\) 也就确定了。
\(0\) 换过去的代价是路上 \(0\) 的数量，这就和 \(1\) 没关系了，那么我们把 \(S,T\) 的 \(0\) 都取出来，相邻的配对即可。
解法2
我们可以把所以 \(1\) 换到应该的位置上，那么 \(0\) 也就是确定了。
\(1\) 换过去的代价是路上 \(0\) 的数量，这和 \(0/1\) 都有关系，直接匹配是行不通的，\(\tt oneindark\) 给出的做法是从左往右扫，如果遇到 \(S\) 有 \(1\) 但是 \(T\) 没有就把他移动到右边第一个 \(0\)，如果 \(T\) 有 \(1\) 但是 \(S\) 没有也把他移动到右边第一个 \(0\)
这种做法的正确性有二：一是两个状态都往中间靠拢；二是我们永远在不得不操作的时候操作。
C.ARC Wrecker 2
题目描述
有 \(n\) 个楼房，第 \(i\) 个高为 \(a_i\)，相邻的楼房可以同时增加或同时减少，问能够推平（高度全部变成 \(0\)）的区间有多少个。
\(2\leq n\leq 300000,1\leq a_i\leq 10^9\)
解法
一定要有敏锐的观察能力，这道题的结论是：如果奇偶位置高度相同则可以推平。
证明不难，因为无论怎么操作奇偶的差都是不变的，而目标奇偶差值为 \(0\)，初始状态一定能到目标状态。
然后搞一个特殊的前缀和，奇数位置符号为正，偶数位置符号为负，找权值和为 \(0\) 的区间即可。
#include <cstdio>
#include <map>
using namespace std;
const int M = 300005;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,ans,a[M];map<int,int> mp;
signed main()
{
n=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
if(i>1) a[i]+=a[i-2];
}
mp[0]=mp[a[1]]=1;
for(int i=1;i<=n/2;i++)
{
int x=2*i;
ans+=mp[a[x-1]-a[x]];
if(x<n) ans+=mp[a[x+1]-a[x]];
mp[a[x-1]-a[x]]++;
mp[a[x+1]-a[x]]++;
}
printf("%lld\n",ans);
}
D.Grid Repainting 3
题目描述
解法
注意到一开始没有白色格子，所以设被染白的行数量为 \(a\)，列数量为 \(b\)，我们只需要最大化：
\[n\times m-(n-a)(m-b) \]然后就要开始观察了，不难发现一个红色格子操作后可能覆盖到其他格子，就不能让所有红色格子充分发挥作用。所以如果我们确定了某一个红色格子的状态，那么可以确定和他在同行同列格子的状态，以此类推，这像是一个牵一发而动全身的过程。
举个例子，比如我们要操作 \((x,y)\) 的行 \(x\)，那么和他同行的格子必须选择漂白列，和他同列的格子必须选择漂白行，因为不能影响 \((x,y)\)，所以我们把每个点和其同行同列的点连边，那么所形成的连通块就能解决所有它的行和列的染色，除了激发点，如果激发点漂白行那么就少了一列的漂白，如果激发点漂白列那么就少了一行的漂白。
继续发现激发点的选择是无关紧要的，我们可以通过枚举来确定有多少连通块的激发点要漂白行，有多少连通块的激发点要漂白列，输出方案递归即可。
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
const int M = 2505;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,a,b,cnt,ans,p,r[M],c[M];
char s[M][M];vector<int> v;
void dfs(int x,int y)
{
if(r[x] && c[y]) return ;
bool rx=r[x],cy=c[y];r[x]=c[y]=1;
if(!rx) for(int i=1;i<=m;i++)
if(s[x][i]=='R') dfs(x,i);
if(!cy) for(int i=1;i<=n;i++)
if(s[i][y]=='R') dfs(i,y);
}
void print(int x,int y)
{
if(r[x] && c[y]) return ;
bool rx=r[x],cy=c[y];r[x]=c[y]=1;
if(!rx) for(int i=1;i<=m;i++)
if(s[x][i]=='R') print(x,i);
if(!cy) for(int i=1;i<=n;i++)
if(s[i][y]=='R') print(i,y);
if(!rx && cy) printf("X %d %d\n",x,y);
if(rx && !cy) printf("Y %d %d\n",x,y);
}
signed main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(s[i][j]=='R' && !r[i] && !c[j])
{
dfs(i,j);cnt++;
v.push_back(i*m+j-1);
}
for(int i=1;i<=n;i++) a+=r[i];
for(int i=1;i<=m;i++) b+=c[i];
for(int i=0;i<=cnt;i++)
{
int x=n-a+i,y=m-b+(cnt-i);
if(n*m-x*y>ans) ans=n*m-x*y,p=i;
}
for(int i=1;i<=max(n,m);i++)
c[i]=r[i]=0;
printf("%d\n",a+b-cnt);
for(int i=0;i<p;i++)
{
print(v[i]/m,v[i]%m+1);
printf("Y %d %d\n",v[i]/m,v[i]%m+1);
}
for(int i=p;i<cnt;i++)
{
print(v[i]/m,v[i]%m+1);
printf("X %d %d\n",v[i]/m,v[i]%m+1);
}
}
E.Pancakes
题目描述
解法
翻转一段区间 \([l,r]\)，两边和中间相邻数字差都不会变，只有左右端点会变，会令答案加上：
\[|s_r-s_{l-1}|+|s_{l}-s_{r+1}|-(|s_l-s_{l-1}|+|s_r-s_{r+1}|) \]后面那一块我们先不管，我们来把前面的绝对值拆开：
- 如果 \(s_r\geq s_{l-1},s_l\geq s_{r+1}\)，拆开后是 \((s_r-s_{r+1})-(s_l-s_{l-1})\)
- 如果 \(s_r\geq s_{l-1},s_l\leq s_{r+1}\)，拆开后是 \((s_r+s_{r+1})-(s_l+s_{l-1})\)
这道题有一个十分关键的点就是不需要区分是 \(l\) 还是 \(r\)，比如说某一个情况我们算成 \(r\) 在前 \(l\) 在后，这对应着另一种 \(l\) 在前 \(r\) 在后的情况，所以我们只需要看成 \((s_x,s_{x-1})\) 这若干个二元组求偏序关系即可。
然后偏序关系还有两种，但是会被 \(\tt Case\space 1,2\) 给计算到所以不用管，时间复杂度 \(O(n\log n)\)