Home Archives Tags Friends About
杂题
2023-11-13

NOIP S & 计数杂题。

A. 卡门

https://www.luogu.com.cn/problem/P6370

https://www.becoder.com.cn/contest/4434/problem/1

我们惊讶地发现全场没多少人会做绿题。

就是说呢，我们把它「滚动到相邻行然后落下」的过程直接变成「往左下 / 右下滚」。那么球掉下去的过程呢，就可以理解为它是一直一次往下掉一格的，然后每一次掉落呢，会根据实际情况往左 / 往右 / 直着掉。

所以我们可以直接用 \(m\) 个长度为 \(n\) 的序列，记录从每 \(1\sim m\) 列扔下去的情况。然后我们很容易可以知道，如果任意两个序列发生了交汇，那么从交汇点开始至序列结束呢，这两个序列的内容都是完全一样的。因为之前序列长什么样子，完全不会对之后产生影响。所以一旦有任意一个状态是一样的，后面都会是一样的。

所以呢，一旦我们跟着计划好的路线走，却发现走不动了，那就说明从走不动的位置开始，到原定路线结束，这些位置都会被封掉。所以这个时候我们直接重新计算路线就好了。

对于这 \(m\) 列，就算每一列预定路线上的每个位置都被占了一次，也只会被更改 \(n\times m\) 次；总体时间复杂度只有 \(\mathcal O(nm^2)\)。然后又由于不可能跑满，其实是完全没有问题，甚至跑得出溜快的。

namespace XSC062 {
using namespace fastIO;
const int maxm = 35;
const int maxn = 3e4 + 5;
char a[maxn][maxm];
int n, m, q, u, x, y;
std::vector<int> p[maxm]; 
int main() {
#ifdef ONLINE_JUDGE
	freopen("kamen.in", "r", stdin);
	freopen("kamen.out", "w", stdout);
#endif
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i)
		scanf("%s", a[i] + 1);
	for (int i = 1; i <= m; ++i) {
		x = 1, y = i;
		for (;;) {
			p[i].push_back(y); 
			if (a[x + 1][y] == '.') ++x;
			else {
				if (a[x + 1][y] == 'X') break;
				if (a[x][y - 1] == '.' && a[x + 1][y - 1] == '.')
					++x, --y;
				else if (a[x][y + 1] == '.' && a[x + 1][y + 1] == '.')
					++x, ++y;
				else break;
			}
		}
	}
	scanf("%d", &q);
	while (q--) {
		scanf("%d", &u);
		while (a[p[u].size()][p[u].back()] != '.')
			p[u].pop_back();
		x = p[u].size(), y = p[u].back();
		for (;;) {
			p[u].push_back(y); 
			if (a[x + 1][y] == '.') ++x;
			else {
				if (a[x + 1][y] == 'X') break;
				if (a[x][y - 1] == '.' && a[x + 1][y - 1] == '.')
					++x, --y;
				else if (a[x][y + 1] == '.' && a[x + 1][y + 1] == '.')
					++x, ++y;
				else break;
			}
		}
		a[x][y] = 'O';
	}
	for (int i = 1; i <= n; ++i) puts(a[i] + 1);
	return 0;
}
} // namespace XSC062

B. 商人

https://www.becoder.com.cn/contest/4434/problem/2

首先忽略图中的环带来的问题，假设 \(f_u\) 表示从 \(u\) 点出发的答案，不难想到 DP 式 \(f_u = \min\{\max(f_v-p_{(u,v)}, r_{(u,v)})\}\)。

那么问题来了，图中是会有环的，不能简单地去更新 DP 值。我们首先考虑「根源」，每一个 \(f_u\) 一定都是由另一个 \(f_v\) 转移得到的，那么一定会存在一个已知的 \(f_u\)，不由其他任何 \(f_v\) 得到。

考虑一个环中 \(r\) 最大的一条边 \((u,v)\)。假设图中只有这一个环，那么 \(f_u\) 的值一定为 \(r\)，因为 \(p\) 只能为非负。这样「根源」就被我们找到了。接下来进一步考虑转移方法。

一个点 \(u\) 只能被其相连的点 \(v\) 更新，那么当且仅当所有 \(f_v\) 都是确定的，\(f_u\) 才能被确定，进而去更新 \(u\) 的前驱。这让我们想到了拓扑排序。如果我们将所有边反向，那么上面的过程几乎就是拓扑排序。

为了保证任意一个环上的「根源」都能最先被确定，我们按照按 \(r\) 从大到小遍历每一条边的方式处理问题。对于每一条边 \((u,v)\)，我们都假设它是「根源」并用 \(r_{(u,v)}\) 更新 \(f_u\)。我们其实并不关心 \(u\) 是否是我们刚刚定义的形式上的「根源」，毕竟，只要 \(f_u\) 能被 \(r_{(u,v)}\) 更新，它就能算作广义上的，当前时刻的「根源」。

我们在一开始将出度为 \(0\)（反图上就是入度为 \(0\)）的点全部加入队列，在每次加边的时候进行拓扑排序。每次一条边以任意形式被「使用」后，都要打标记删除并不能再访问，以保证转移的正确性和高效。如果一条边被「使用」，分两种情况：

  1. 更新「根源」：

    这个时候这条边已经发挥了它的所有作用了，作为 当前时刻的「根源」，这条边的源点在未来至少不会再经由这一条边被更新。故可以删除。

  2. 拓扑排序中转移：

    一个点被加入队列，说明它的 DP 值是确定的，那么就不用拿一个已经确定的值多次更新另一个 DP 值。故可以删除。

所以正确性是可以保证的。类拓扑排序的结构也保证了算法复杂度 \(\mathcal O(n+m)\)。

#define int long long
namespace XSC062 {
using namespace fastIO;
const int inf = 1e18;
const int maxn = 2e5 + 5;
const int maxm = 2e5 + 5;
struct _ {
	int v, r, p, i;
	_() {}
	_(int v1, int r1, int p1, int i1) {
		v = v1, r = r1, p = p1, i = i1;
	}
};
struct __ {
	int x, y, r, p;
	bool operator< (const __ &q) const {
		return r > q.r;
	}
};
__ a[maxm];
bool del[maxn];
std::queue<int> q;
int n, m, x, y, r, p;
std::vector<_> g[maxn];
int f[maxn], deg[maxn];
int max(int x, int y) { return x > y ? x : y; }
int min(int x, int y) { return x < y ? x : y; }
void add(int x, int y, int r, int p, int i) {
	g[x].emplace_back(y, r, p, i);
	return;
}
int main() {
#ifdef ONLINE_JUDGE
	freopen("merchant.in", "r", stdin);
	freopen("merchant.out", "w", stdout);
#endif
	read(n), read(m);
	std::fill(f + 1, f + n + 1, inf);
	for (int i = 1; i <= m; ++i) {
		read(a[i].x), read(a[i].y);
		read(a[i].r), read(a[i].p);
		++deg[a[i].x];
	}
	std::sort(a + 1, a + m + 1);
	for (int i = 1; i <= n; ++i)
		if (!deg[i]) q.push(i);
	for (int i = 1; i <= m; ++i)
		add(a[i].y, a[i].x, a[i].r, a[i].p, i);
	for (int i = 1; i <= m; ++i) {
		while (!q.empty()) {
			int t = q.front(); q.pop();
			for (auto j : g[t]) {
				if (del[j.i]) continue;
				del[j.i] = 1;
				if (f[t] != inf)
					f[j.v] = min(f[j.v], max(f[t] - j.p, j.r));
				if (!--deg[j.v]) q.push(j.v);
			}
		}
		if (!del[i]) {
			del[i] = 1, f[a[i].x] = min(f[a[i].x], a[i].r);
			if (!--deg[a[i].x]) q.push(a[i].x);
		}
	}
	for (int i = 1; i <= n; ++i)
		print(f[i] == inf ? -1 : f[i], ' ');
	putchar('\n');
	return 0;
}
} // namespace XSC062
#undef int

A - Gerald and Giant Chess

https://vjudge.net/contest/594162#problem/A

这个呢，一道简单的数数题，但是因为我忘了 DP 容斥怎么打了所以自行思考了很久很久很久，还差最后一点点想出来的时候放弃了去抄题解 /cf

就是，这种「限制通行」的 DP 容斥（名字是我现场起的）类型的数数题有一种通法，就是首先我们只计算非法方案然后减掉。

那么非法方案怎么算呢？令 \(f_i\) 表示一个非法点都不经过，到达 \(i\) 这个非法点的方案数，那么有 \(f_i=calc(s,i)-\sum f_j\times calc(j,i)\)，其中 \(s\) 是起点，\(calc(j,i)\) 是从 \(j\to i\) 的方案数。这样就能不重不漏地枚举完所有情况了。

我们把 \((n,m)\) 也视作一个非法点然后代入 DP 即可得到答案。

#define int long long
namespace XSC062 {
using namespace fastIO;
const int lim = 3e5;
const int mod = 1e9 + 7;
const int maxk = 2e3 + 5;
const int maxn = 3e5 + 5;
struct _ {
	int x, y;
	bool operator< (const _ &q) const {
		return x == q.x ? y < q.y : x < q.x;
	}
};
_ a[maxk];
int n, m, k, res; 
int f[maxk], fac[maxn];
int qkp(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1) (res *= x) %= mod;
		(x *= x) %= mod, y >>= 1;
	}
	return res;
}
int inv(int x) { return qkp(x, mod - 2); }
int A(int n, int m) {
	return fac[n] * inv(fac[n - m]) % mod;
}
int C(int n, int m) {
	return A(n, m) * inv(fac[m]) % mod;
}
int calc(int i, int j) {
	int x = a[j].x - a[i].x + 1,
		y = a[j].y - a[i].y + 1;
	return C(x + y - 2, y - 1);
}
int main() {
	fac[0] = 1;
	for (int i = 1; i <= lim; ++i)
		fac[i] = fac[i - 1] * i % mod;
	bool flag = 0;
	read(n), read(m), read(k);
	for (int i = 1; i <= k; ++i) {
		read(a[i].x), read(a[i].y);
		flag |= (a[i].x == 1 && a[i].y == 1);
		flag |= (a[i].x == n && a[i].y == m);
	}
	a[0].x = a[0].y = 1;
	if (flag) { print(0, '\n'); return 0; }
	++k, a[k].x = n, a[k].y = m;
	std::sort(a + 1, a + k + 1);
	for (int i = 1; i <= k; ++i) {
		f[i] = calc(0, i);
		for (int j = 1; j < i; ++j) {
			if (a[j].x > a[i].x || a[j].y > a[i].y) continue;
			(f[i] -= f[j] * calc(j, i) % mod) %= mod;
		}
	}
	f[k] = (f[k] % mod + mod) % mod;
	print(f[k], '\n');
	return 0;
}
} // namespace XSC062
#undef int

一言 - Hitokoto