ABC264.

A. "atcoder".substr()

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
signed main() {
	string s="atcoder";
	int l=read()-1, r=read()-1;
	for(;l<=r;++l) printf("%c",s[l]);
	puts("");
}

B. Nice Grid

不会结论，写了大暴力。把行折半之后大力判断。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
signed main() {
	int r=read(), c=read();
	if(r>=8) r=16-r;
	if(r==1) puts("black");
	else if(r==8) if(c&1) puts("black"); else puts("white");
	else {
		if(r&1) {
			if(r==3) if(c!=2&&c!=14) puts("black"); else puts("white"); 
			else if(r==5) if(c!=2&&c!=14&&c!=4&&c!=12) puts("black"); else puts("white"); 
			else if(r==7) if(c!=2&&c!=14&&c!=4&&c!=12&&c!=6&&c!=10) puts("black"); else puts("white"); 
		} else {
			if(r==2) if(c!=1&&c!=15) puts("white"); else puts("black");
			else if(r==4) if(c!=1&&c!=15&&c!=3&&c!=13) puts("white"); else puts("black");
			else if(r==6) if(c!=1&&c!=15&&c!=3&&c!=13&&c!=5&&c!=11) puts("white"); else puts("black");
		}
	}
}

C. Matrix Reducing

显然对于任意 \(i\)，\(B_i\) 中每一个元素都要在 \(A\) 中某一行 \(j\) 全部出现，且若 \(i' > i\)，则 \(j' > j\)。否则无解。

然后如同

6 7 8 9 10
16 17 18 19 20
    
6 8 9
16 18 19

\(B\) 中每一行的元素在 \(A\) 中对应行的位置，必须完全相同。样例中都是1 3 4。

就这么点东西，实现的时候有亿点细节。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
int n1, m1, n2, m2, a[15][15], b[15][15], c[15][15];
int lst;
multiset<int> st[15];
signed main() {
	n1=read(), m1=read();
	for(int i=1;i<=n1;++i) for(int j=1;j<=m1;++j) {
		a[i][j]=read();
		st[i].insert(a[i][j]);
        // multiset维护每一行出现的数字
	}
	n2=read(), m2=read();
	for(int i=1;i<=n2;++i) for(int j=1;j<=m2;++j) b[i][j]=read();
	for(int i=1;i<=n2;++i) {
		int fg=0;
		for(int j=lst+1;j<=n1;++j) if(st[j].count(b[i][1])) {
			st[j].erase(st[j].find(b[i][1]));
            // 存在第一个元素的话就尝试找所有元素
            // 记得找完之后删除，因为可能有重复的
			bool ok=1;
			for(int k=2;k<=m2;++k)
				if(!st[j].count(b[i][k])) { ok=0; break; }
                // 有一个数字不存在，直接放弃这行
				else st[j].erase(st[j].find(b[i][k]));
			if(ok) { fg=j; break; }
		}
		if(!fg) { puts("No"); return 0; }
		else {
			for(int j=1;j<=m2;++j) for(int k=1;k<=m1;++k) {
				if(b[i][j]==a[fg][k]) c[i][j]=k;
                // 记录位置
			}
			lst=fg;
            // 下一行要从fg+1开始找
		}
	}
    // 下面这两块都是判断c[i][j]是否完全相同。
	for(int i=1;i<=n2;++i) {
		int pre=0;
		for(int j=1;j<=m2;++j) {
			if(pre>c[i][j]) { puts("No"); return 0; }
			else pre=max(pre,c[i][j]);
		}
        // 看有没有逆序对，有逆序对也是无解
	}
    // 看看对应位置，所有行是否相同
	for(int j=1;j<=m2;++j) {
		int fg=c[1][j];
		for(int i=2;i<=n2;++i) if(c[i][j]!=fg) { puts("No"); return 0; }
	}
	puts("Yes");
}

D. "redocta".swap(i,i+1)

求逆序对个数。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
int trans(char c) {
	if(c=='a') return 1;
	else if(c=='t') return 2;
	else if(c=='c') return 3;
	else if(c=='o') return 4;
	else if(c=='d') return 5;
	else if(c=='e') return 6;
	else if(c=='r') return 7;
	return 114514;
}
int a[10];
signed main() {
	string s; cin>>s;
	s=" "+s;
	for(int i=1;i<=7;++i) a[i]=trans(s[i]);
	int ans=0;
	for(int i=1;i<=7;++i) for(int j=i+1;j<=7;++j) {
		if(a[i]>a[j]) ++ans;
	}
	printf("%lld\n",ans);
}

E. Blackout 2

经典套路，删边转化为倒序加边，于是乎问题变为维护连通性和连通块信息。

设 \(sz_i\) 为连通块 \(i\) 的大小，\(d_i\) 为连通块 \(i\) 包含的 power plants 的数量。

考虑合并两个连通块 \(i\) 和 \(j\)，如果 \(d_i > 0\) 并且 \(d_j > 0\)，那么合并之后不会产生任何贡献，因为在合并之前，\(i\) 和 \(j\) 之中的城市就已经连接到各自的 power plants 了。

否则，如果 \(d_i =0\) 且 \(d_j = 0\)，那么合并之后也没有贡献。

当 \(d_i = 0\) 且 \(d_j > 0\) 时，贡献为 \(sz_i\)，否则为 \(sz_j\)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=1e6+5;
int n, m, e, Q, dlt, u[N], v[N], q[N], d[N], fa[N], sz[N], ans[N];
bool vv[N];
int get(int x) { return x==fa[x]? x:fa[x]=get(fa[x]); }
void merge(int x,int y) {
	x=get(x), y=get(y);
	if(x!=y) {
		if(!d[x]&&d[y]) dlt+=sz[x];
		else if(!d[y]&&d[x]) dlt+=sz[y];
		fa[x]=y, sz[y]+=sz[x], d[y]+=d[x];
	}
}
signed main() {
	n=read(), m=read(), e=read();
	for(int i=1;i<=m;++i) d[n+i]=1;
	for(int i=1;i<=n+m;++i) fa[i]=i, sz[i]=1;
	for(int i=1;i<=e;++i) {
		u[i]=read(), v[i]=read();
	}
	Q=read(); 
	for(int i=1;i<=Q;++i) q[i]=read(), vv[q[i]]=1;
	for(int i=1;i<=e;++i) if(!vv[i]) merge(u[i],v[i]);
    // 合并没有被删的边
	ans[Q]=dlt;
    // ans[i]表示第i次删除之后的信息，所以只需要加边[q[2],q[Q]]即可
	for(int i=Q;i>1;--i) {
		merge(u[q[i]],v[q[i]]);
		ans[i-1]=dlt;
	}
	for(int i=1;i<=Q;++i) printf("%lld\n",ans[i]);
}

F. Monochromatic Path

分析

显然，对于一行或者一列，修改次数只有 \(0\) 和 \(1\)。

设 \(f(i,j,p=0/1,q=0/1)\) 表示，从 \((1,1)\) 到达 \((i,j)\)，且第 \(i\) 行的修改次数为 \(p\)，第 \(j\) 列的修改次数为 \(q\)，所需的最小代价。

通过状态记录的信息就能得出，此时 \((i,j)\) 的数字为 \(c1 = a_{i,j} \oplus p \oplus q\)。顺便说一句这是因为异或是异或的逆运算，异或两次等于没异或。

同时也就得到了 \((i+1,j)\) 和 \((i,j+1)\) 的颜色 \(c2\)，分别为 \(a_{i+1,j} \oplus q\)，\(a_{i,j+1} \oplus p\)。

这样就能够转移了。若颜色相同则代价不变，否则加上修改那一行/列的代价。 $$ \[\begin{cases} f(i,j,p,q) \rightarrow f(i+1,j,0,q) & c1 = c2 \\ f(i,j,p,q) + r_{i+1} \rightarrow f(i+1,j,1,q) & c1 \neq c2 \end{cases}\]

$$

\[ \begin{cases} f(i,j,p,q) \rightarrow f(i,j+1,p,0) & c1=c2 \\ f(i,j,p,q) \rightarrow f(i,j+1,p,q) & c1 \neq c2 \end{cases} \]

最终答案 \[ \min_{i=0}^1 \min_{j=0}^1 \{ f(n,m,i,j) \} \]

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=2005;
int n, m, a[N][N], r[N], c[N];
int f[N][N][2][2];
#define rep(i,j,k) for(int i=j;i<=k;++i)
signed main() {
	n=read(), m=read();
	rep(i,1,n) r[i]=read();
	rep(i,1,m) c[i]=read();
	rep(i,1,n) rep(j,1,m) scanf("%1d",&a[i][j]);
	memset(f,0x3f,sizeof(f));
	f[1][1][0][0]=0, f[1][1][1][0]=r[1], f[1][1][0][1]=c[1];
	f[1][1][1][1]=r[1]+c[1];
    // 初始值
	rep(i,1,n) rep(j,1,m) rep(p,0,1) rep(q,0,1) {
		if(i+1<=n) {
			int c1=a[i][j]^p^q, c2=a[i+1][j]^q;
			if(c1==c2) f[i+1][j][0][q]=min(f[i+1][j][0][q],f[i][j][p][q]);
			else f[i+1][j][1][q]=min(f[i+1][j][1][q],f[i][j][p][q]+r[i+1]);
		}
		if(j+1<=m) {
			int c1=a[i][j]^p^q, c2=a[i][j+1]^p;
			if(c1==c2) f[i][j+1][p][0]=min(f[i][j+1][p][0],f[i][j][p][q]);
			else f[i][j+1][p][1]=min(f[i][j+1][p][1],f[i][j][p][q]+c[j+1]);
		}
	}
	int ans=1e15;
	rep(i,0,1) rep(j,0,1) ans=min(ans,f[n][m][i][j]);
	printf("%lld\n",ans);
}