2020杭电多校（第十场）

比赛链接

1003 Mine Sweeper

如果 $S\leqslant 24$，在一排被交替摆放即可。如果 $S>24$，类似如下摆放：

$$\begin{matrix} &\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\ &\cdot&\text{X}&\cdot&\text{X}&\cdot&\text{X}&\cdot&\text{X}&\cdot\\ &\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\ &\cdot&\text{X}&\cdot&\text{X}&\cdot&\cdot&\cdot&\cdot&\cdot\\ &\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\ &\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\ &\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\ &\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\text{X}&\text{X}&\text{X}\\ \end{matrix}$$

孤立的 $\text{X}$ 提供 $8$ 的贡献，右下角连续的 $\text{X}$ 提供 $3$ 的贡献（最右端是 $2$，最左端是 $4$，平均一下还是 $3$）。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int main(){
	int T; for(read(T); T; T--){
		int S; read(S);
		if(S <= 24){
			printf("%d %d\n", 1, S+1);
			for(int i = 1; i <= S + 1; i++)	putchar(".X"[i&1]);
			puts("");
			continue;
		}
		int a, b;
		for(b = 0; ; b++){
			if((S - 3 * b) % 8 == 0){
				a = (S - 3 * b) / 8;
				break;
			}
		}
		char g[30][30];
		for(int i = 1; i <= 25; i++)
			for(int j = 1; j <= 25; j++)
				g[i][j] = '.';
		int cnt = 0;
		for(int i = 2; i <= 25; i += 2){
			for(int j = 2; j <= 25; j += 2){
				g[i][j] = 'X', cnt++;
				if(cnt == a)	break;
			}
			if(cnt == a)	break;
		}
		for(int j = 1; j <= b; j++)	g[25][25-j+1] = 'X';
		printf("%d %d\n", 25, 25);
		for(int i = 1; i <= 25; i++){
			for(int j = 1; j <= 25; j++)
				putchar(g[i][j]);
			puts("");
		}
	}
	return 0;
}

---

1004 Permutation Counting

设 $dp[i][j]$ 表示填了前 $i$ 个数，第 $i$ 个数目前排名为 $j$ 的方案数。那么：

$$dp[i][j] = \begin{cases}\sum\limits_{k=1}^{j-1}dp[i-1][k]&b_i=0\\\sum\limits_{k=j}^{i-1}dp[i-1][k]&b_i=1\end{cases}$$

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int MOD = 1e9+7;

int dp[5005][5005];

int main(){
	int T; for(read(T); T; T--){
		int n; read(n);
		dp[1][1] = 1;
		for(int i = 2; i <= n; i++){
			int b, sum = 0; read(b);
			if(b == 0){
				for(int j = 1; j <= i; j++){
					dp[i][j] = sum;
					sum = (sum + dp[i-1][j]) % MOD;
				}
			}
			else{
				for(int j = i; j >= 1; j--){
					sum = (sum + dp[i-1][j]) % MOD;
					dp[i][j] = sum;
				}
			}
		}
		int ans = 0;
		for(int i = 1; i <= n; i++)	ans = (ans + dp[n][i]) % MOD;
		printf("%d\n", ans);
	}
	return 0;
}

---

1010 Tic-Tac-Toe-Nim

枚举第一轮拿走的两堆，现在还剩下 $7$ 堆。不妨假设拿走的是 $(1,1)$ 和 $(2,2)$，那么剩下的所有堆中，除了 $(3,3)$ 可以拿光，其他堆的策略是拿到 $1$，因为其他任何一堆拿光就输了，所以这就是 $7$ 个堆、其中 $6$ 堆石子个数等于原数减一的 $\textbf{Nim}$ 游戏，判断异或和是否等于 $0$ 即可。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int a[5][5];

int main(){
	int T; for(read(T); T; T--){
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 3; j++)
				read(a[i][j]);
		int ans = 0;
		for(int i = 0; i < 9; i++){
			int x1 = i / 3, y1 = i % 3;
			bool ok = true;
			for(int j = 0; j < 9; j++){
				int x2 = j / 3, y2 = j % 3, x, y;
				if(x1 == x2 || y1 == y2)	continue;
				for(x = 0; x == x1 || x == x2; x++);
				for(y = 0; y == y1 || y == y2; y++);
				int xorsum = 0;
				for(int k = 0; k < 9; k++){
					if(k == i || k == j)	continue;
					xorsum ^= a[k/3][k%3] - 1 + ((k / 3 == x) && (k % 3 == y));
				}
				if(!xorsum){ ok = false; break; }
			}
			ans += ok;
		}
		printf("%d\n", ans);
	}
	return 0;
}

---

1011 Task Scheduler

除了 $k=0$ 是 $12\cdots n$，其他情况按照 $t$ 从大到小排序。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

struct Node{
	int t, id;
	bool operator < (const Node &A) const{ return t == A.t ? id < A.id : t > A.t; }
}a[105];

int main(){
	int T; for(read(T); T; T--){
		int n, m, k; read(n, m, k);
		for(int i = 1; i <= n; i++)	read(a[i].t), a[i].id = i;
		if(k == 0){
			for(int i = 1; i <= n; i++)	printf("%d%c", i, " \n"[i==n]);
			continue;
		}
		sort(a+1, a+n+1);
		for(int i = 1; i <= n; i++)	printf("%d%c", a[i].id, " \n"[i==n]);
	}
	return 0;
}