2021.7.16模拟赛

比赛概括：

\(\mathrm{sum}=10+30+0+100\)

唉，我果然只是暴力选手。

T1 【BZOJ 4131】并行博弈：

题目大意：

在一个 \(n\times m\) 的棋盘上，选择一个黑点可使得矩阵 \((1,1,x,y)\) 翻转。无法操作的人败。问 \(k\) 组棋盘一起下，是否先手必胜。

思路：

先手最优一定是选一直选棋盘的左上角，所以统计左上角是 \(1\) 的个数，询问是否是奇数。证明不会，看来得增加博弈论的知识储备。

代码：

inline ll Read()
{
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}


int k, n, m;

int main()
{
	for (int T = Read(); T--; )
	{
		k = Read();
		int ans = 0; 
		for (int t = 1; t <= k; t++)
		{
			n = Read(), m = Read();
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= m; j++)
				{
					int x = Read();
					if (i == 1 && j == 1) 
						ans ^= x;
				}
		}
		puts(!ans? "ld win": "lyp win");
	}
	return 0;
}

T2 图书馆：

题目大意：

在一个 DAG 找到一条长度不到 \(20\) 的 \(s\rightarrow t\) 的路径，使得路径方差最小。

思路：

先化方差：

\[\begin{aligned} \sigma^2&=\frac{1}{n}\sum_{i=1}^n(a_i-\bar{a})^2\\ &=\frac{1}{n}\sum_{i=1}^n(a_i^2-2a_i\bar{a}+\bar{a}^2)\\ &=\frac{1}{n}\sum_{i=1}^n(a_i^2-2a_i\bar{a})+\bar{a}^2\\ &=\frac{1}{n}\sum_{i=1}^na_i^2-\frac{1}{n}\sum_{i=1}^n2a_i\bar{a}+\bar{a}^2\\ &=\frac{1}{n}\sum_{i=1}^na_i^2-2\bar{a}^2+\bar{a}^2\\ &=\frac{1}{n}\sum_{i=1}^na_i^2-\bar{a}^2\\ \end{aligned} \]

然后设 \(f_{i,j,k}\) 表示当前在 \(i\) 楼梯，已经走了 \(j\) 个楼梯，且消耗了 \(k\) 体力的最小体力平方和。则有：

\[f_{u,j,k}=\min_{v\to u,\mathrm{val}}\{f_{v,j-1,k-\mathrm{val}}+\mathrm{val}^2\} \]

统计答案时把 \(f_{i,j,k}\) 代回去就行了。

代码：

const int N = 60, M = 310, V = 1010;

inline ll Read()
{
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

int n, m;
int f[N][M][V];

struct edge
{
	int to, val, nxt;
}e[M];
int head[N], tot;
void add(int u, int v, int w)
{
	e[++tot] = (edge) {v, w, head[u]}, head[u] = tot;
}

int main()
{
	freopen("library.in", "r", stdin);
	freopen("library.out", "w", stdout);
	memset (f, 127 / 3, sizeof f);
	n = Read(), m = Read();
	for (int i = 1; i <= m; i++)
	{
		int u = Read(), v = Read(), w = Read();
		add(u, v, w);
	}
	f[1][0][0] = 0;
	
	for (int len = 0; len < 19; len++)
		for (int u = 1; u < n; u++)
			for (int i = head[u]; i; i = e[i].nxt)
			{
				int v = e[i].to;
					for (int sum = 0; sum <= 1000; sum++)
						f[v][len + 1][sum + e[i].val] = 
						    min(f[v][len + 1][sum + e[i].val], f[u][len][sum] + e[i].val * e[i].val);
			}
		
	double ans = 1e9;
	for (int j = 1; j <= 20; j++)
		for (int k = 0; k <= 1000; k++)
			if (f[n][j][k] < f[0][0][0])
				ans = min(ans, f[n][j][k] * 1.0 / j - (k * k * 1.0 / j / j));
	printf ("%.4f", ans);
	return 0;
}

T3 [GDOI2017]小学生语文题：

题目大意：

将字符串 \(t\) 中的一些字符往前移动若干位得到 \(s\)，求次数及方案。

正文：

设 \(f_{i,j}\) 表示 \(s\) 串中 \([i,n]\) 与 \(t\) 串 \([j,n]\) 匹配（有可能有剩余的）的最小次数。

则分三部分：

1. \(s_i=t_j\)，直接往前跳，\(f_{i,j}=f_{i+1,j+1}\)。
2. \(s_i\ne t_j\) 但是 \(t\) 串 \([j,n]\) 中的字符 \(s_i\) 的数量大于 \(s\) 串 \([i,n]\)，则说明 \(t\) 中可以移动一个字符 \(s_i\)，\(f_{i,j}=f_{i+1,j}\)。
3. \(t\) 串中不够，\(f_{i,j}=f_{i+1,j+1}+1\)。

顺便维护 \(g_{i,j,[0,1]}\) 表示 \(f_{i,j}\) 从哪两个点转移过来的。

然后从 \(1,1\) 往后跳，把不定点排除，枚举剩下的点即可。

代码：

const int N = 2010;

inline ll Read()
{
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

int T, n;
char s[N], t[N];
int a[30][N], b[30][N];
int f[N][N], g[N][N][2];

bool NoMoveA[N], NoMoveB[N];

int main()
{
	freopen("chinese.in", "r", stdin);
	freopen("chinese.out", "w", stdout);
	for (T = Read(); T--;)
	{
		scanf ("%s%s", s + 1, t + 1);
		memset (a, 0, sizeof a);
		memset (b, 0, sizeof b);
		memset (NoMoveA, 0, sizeof NoMoveA);
		memset (NoMoveB, 0, sizeof NoMoveB);
		n = strlen(s + 1);
		for (int i = n; i; i--)
		{
			a[s[i] - 'a'][i] = 1, b[t[i] - 'a'][i] = 1;
			for (int j = 0; j < 26; j++) a[j][i] += a[j][i + 1], b[j][i] += b[j][i + 1];
		}
		memset (f, 127 / 3, sizeof f);
		f[n + 1][n + 1] = 0;
		for (int j = n; j; j--) f[n + 1][j] = f[n + 1][j + 1] + 1;
		for (int i = n; i; i--)
		{
			for (int j = n; j; j--)
			{
				if (f[i][j] > f[i + 1][j] && a[s[i] - 'a'][i + 1] < b[s[i] - 'a'][j])
					f[i][j] = f[i + 1][j], g[i][j][0] = i + 1, g[i][j][1] = j;
				
				if (f[i][j] > f[i + 1][j + 1] && s[i] == t[j])
					f[i][j] = f[i + 1][j + 1], g[i][j][0] = i + 1, g[i][j][1] = j + 1;
				
				if (f[i][j] > f[i][j + 1] + 1)
					f[i][j] = f[i][j + 1] + 1, g[i][j][0] = i, g[i][j][1] = j + 1;
			}
		}
		printf ("%d\n", f[1][1]);
		
		int x = 1, y = 1;
		while (x <= n && y <= n)
		{
			int nxtx = g[x][y][0], nxty = g[x][y][1];
			if (nxtx == x + 1 && nxty == y + 1)
				NoMoveA[x] = 1, NoMoveB[y] = 1;
			x = nxtx, y = nxty;
		}
		
		for (int i = 1; i <= n; i++)
		{
			if (NoMoveA[i]) continue;
			for (int j = i; j <= n; j++)
			{
				if (NoMoveB[j] || s[i] != t[j]) continue;
				bool tmp = NoMoveB[j];
				for (int k = j; k >= i + 1; k--)
					t[k] = t[k - 1], NoMoveB[k] = NoMoveB[k - 1];
				NoMoveB[i] = tmp;
				t[i] = s[i];
				printf ("%d %d\n", j, i);
				break;
			}
		}
	}
	return 0;
}

T4 矩形：

题目大意：

给你 \(n\) 条线段（他们要么平行要么垂直），求那些线段可以围成矩阵。

正文：

每行用 bitset 存一个与每列是否有交点的状态，然后枚举两行求同时拥有两列的数量。时间复杂度 \(\mathcal{O}(n^3\omega^{-1})\)，其中 \(\omega=32\)，勉强卡过。

代码：

const int N = 2010;

inline ll Read()
{
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

int n; 
int cnt1, cnt2;
struct Segment
{
	int x1, y1, x2, y2;
}a[N], b[N];

bool isInt (int u, int v)
{
	return b[v].y1 <= a[u].y1 && a[u].y1 <= b[v].y2 && a[u].x1 <= b[v].x1 && b[v].x1 <= a[u].x2;
}

bitset<N> con[N], tmp;
ll ans;

int main()
{
	n = Read();
	for (int i = 1; i <= n; i++)
	{
		int x1 = Read(), y1 = Read(), x2 = Read(), y2 = Read();
		if (x1 != x2) 
		{
			if (x1 > x2) x1 ^= x2 ^= x1 ^= x2, y1 ^= y2 ^= y1 ^= y2;
			a[++cnt1] = (Segment){x1, y1, x2, y2};
		}
		else 
		{
			if (y1 > y2) x1 ^= x2 ^= x1 ^= x2, y1 ^= y2 ^= y1 ^= y2;
			b[++cnt2] = (Segment){x1, y1, x2, y2};
		}
	}
	for (int i = 1; i <= cnt1; i++)
		for (int j = 1; j <= cnt2; j++)
			if (isInt(i, j))
				con[i].set(j, 1);
	for (int i = 2; i <= cnt1; i++)
		for (int j = 1; j < i; j++)
		{
			tmp = con[i] & con[j];
			ll cnt = tmp.count();
			ans += cnt * (cnt - 1) / 2;
		}
	printf ("%lld\n", ans);
	return 0;
}