近期训练题目一句话总结

然后 “-”+“空格”可以得到无序列表

• HDU 2026 春季联赛 10 D - 歪歪爱追剧：筛掉不含明星时刻的区间后做带权区间选择；坑点是没有前驱时也要允许当前区间单独成为答案。

• CF 1100 E - Deconstruction Tree ：固定终点看前驱区间，非根转移是 need[y] < x < y；根转移只看第二大的根分支最大值。 题解

• CF Round 1101 Div2 C2 - Seating Arrangement：两个洞见串起来看：一是桌子从空到非空是单向状态变化，所以拆成开桌者 / 跟随者；二是 A 不能待定式分配，因为其具有中间过程价值，因为它只有先作为跟随者进入结构，才会拥有“以后改成开桌者时吐回旧槽位”的中间过程价值。

• 金马 5 校 - 奇点蜂测序：区间异或约束先转成前缀点关系 $s_l \oplus s_{r+1}=x$，再用带权并查集维护连通块内相对异或；查询时同块输出差值，不同块输出 -1。

• CF Edu 170 D - Attribute Checks：INT 当 dp 下标、STR 靠「已得点数 − INT」反推，把两维属性压成一维；每条检定本质是给一段连续区间 +1，用差分做到 O(1)，只有遇到加点才把差分 partial_sum 摊开、做一次背包式分裂转移再压回；m=5000 这个小界就是在暗示 O(n+m²)。

• CF Edu 170 E - Card Game：单花色按点数从大到小变成括号前缀余额，用 Catalan / ballot 数压出 dp1；再让花色 1 的多余资源做一维 DP，刚好补完所有非王牌缺口。

• ABC-470-D - Inverse and Swap 把排列看成位置和值之间的对应关系。

• ABC-470-C - Inc, Dec, Xor 增减异或（注意题目条件限制：初始时 $A$ 的所有元素均为 $0$，以及操作的摊还分析） 其实是一个比较简单的摊还分析，那么比较需要注意的就是题目中的初始时A的所有元素均为0，然后操作 1 只能给一个元素加1，然后操作 2 是对所有值减1，而且是减到0以后就不减了，注意到，其实这样子的话，数组中的正数元素是非常少的，直接暴力维护即可啊。

• ABC-468-F - Chmax 我们不难注意到，观察到每步操作我们都必须要做啊，然后就可以发现，有些数字，我们是必须会被迫选到的**，这个前缀最大值数组中出现的值，我们必须要选**啊，而且不仅仅是必须要选，我们的有一个 X / Y 的上升序列一定就是长这个样！否则就不是很优秀啊。

• Voronezh State University - Sitronics contest II——J. Just a map editor（连通块拼图）
  先用 bfs 黑白染色，每一行贡献这个 m 个联通块啊。
  然后可以用这个操作补上零头啊。
  

• 2026牛客暑期多校 8——B-Deep Finesse（深算） 一个东西，整体比。。。小，可以化为前缀+1，-1 模型啊，进而转化为这个走格子模型啊，使用 dp 进行计数求解啊。

2026牛客暑期多校 8——B-Deep Finesse（深算）

2026 杭电暑期多校 8——1007 用传送门来让网格连通吧

https://acm.hdu.edu.cn/contest/problem?cid=1236&pid=1007

注意到这个 k 很小，虽然传送门是单向的这个（不方便直接使用并查集），但是我们直接在这个上面搞就好了，直接在并查集祖宗有向图上跑 bfs 即可啊。

没有这个 is_run 啊，会一不小心跑了 N*M 次啊。

vector<char> is_run(N * M + M + 10);
ll tim = 0;
for (int x = 1; x <= N; ++x) {
	for (int y = 1; y <= M; ++y) {
		if (!checkXY(x, y)) {
			continue;
		}
		++tim;
		int src = getIdx(x, y);
		src = dsu.find(src);
		if (is_run[src]) {
			continue;
		}
		is_run[src] = true;
		queue<int> q;
		q.push(src);
		vis[src] = tim;
		while (!q.empty()) {
			ll u = q.front();
			q.pop();
			for (auto to: g[u]) {
				if (vis[to] >= tim) continue;
				vis[to] = tim;
				connect[src].insert(to);
				q.push(to);
			}
		}
	}
}

整体全部 AC 代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1236&rid=3138

// teamname: Gospel_rock
/**
 * Problem: 用传送门来让网格连通吧
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1236&pid=1007
 * Created: 2026-08-13 12:39:11
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define fsp(x) fixed << setprecision(x)
#define debug(x) cerr << "[" << #x << "]" << ": " << x << "\n"
#define cend cerr << "\n---------------------------------------------------\n"
#define cEnd cerr << "\n***************************************************\n"

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
// 不用 M_PI: 后者是 POSIX 扩展, glibc <cmath> 严格模式会 undef
const long double PI = acosl(-1.0);

ll lT, testcase;

/*
 *
 */

ll N, M, K, Q;


/**   并查集（DSU）+ DSU on next
 *    find(x) 表示 x 之后第一个没有被标记的数字。
 *    构造函数传入的 n 必须不多不少，否则 countFa 会出错。
 *    base = 0 / 1 切换 0-based 与 1-based，合法下标范围分别是 [0, n) 与 [1, n]，默认 1-based。
 */
struct DSU {
	vector<int> fa;
	ll n;
	int base = 1; // 0 或 1，决定合法下标的起点

	DSU() {
	}

	DSU(ll n, int base = 1) : n(n), base(base) { init(n); }

	void init(ll n) {
		fa.resize(n + base + 5);
		for (int i = 0; i < SZ(fa); ++i) fa[i] = i;
	}

	ll find(ll x) {
		ll root = x;
		while (root != fa[root]) {
			root = fa[root];
		}
		while (x != root) {
			tie(x, fa[x]) = make_tuple(fa[x], root);
		}
		return x;
	}

	bool same(ll x, ll y) { return find(x) == find(y); }

	bool merge(ll x, ll y) {
		// 注意方向：fa[x] = y，配合 dsu on next
		x = find(x);
		y = find(y);
		if (x == y) return false;
		fa[x] = y;
		return true;
	}

	// 把 [l, r] 这段区间整段标记，标记后这段区间内任意点 find 都会越过去
	void taglr(ll l, ll r) {
		l = max((ll)base, l);
		r = min((ll)SZ(fa) - 2, r);
		l = find(l);
		while (l <= r) {
			merge(l, l + 1);
			l = find(l + 1);
		}
	}

	ll countFa() {
		// 当前还有多少个独立的根
		ll res = 0;
		for (ll i = base; i < base + n; ++i) if (fa[i] == i) ++res;
		return res;
	}
};

/* -> (Right, Down, Left, Up)
  |  |
   <-
*/


// 来自wida github仓库 https://github.com/hh2048/XCPC/tree/main 加了一些新功能
//46 ms https://acm.hdu.edu.cn/contest/view-code?cid=1179&rid=14912 读入字符getc(a) 的AC记录
// AC https://vjudge.net/solution/63197697 一道测试读写的codechef题目
namespace QuickRead {
	// 快读
	char buf[1 << 21], *p1 = buf, *p2 = buf;

	inline int getc() {
		return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
	}

	template<typename T>
	void Cin(T &a) {
		T ans = 0;
		bool f = 0;
		char c = getc();
		for (; c < '0' || c > '9'; c = getc()) {
			if (c == '-') f = 1;
		}
		for (; c >= '0' && c <= '9'; c = getc()) {
			ans = ans * 10 + c - '0';
		}
		a = f ? -ans : ans;
	}

	void getc(char &a) {
		char c = getc();
		while (isspace(c)) {
			c = getc();
		}
		a = c;
	}

	template<typename T, typename... Args>
	void Cin(T &a, Args &... args) {
		Cin(a), Cin(args...);
	}

	// ===== 输出 =====
	static constexpr size_t OUT_CAP = 1 << 21; // 大概是2MB
	char obuf[OUT_CAP];
	size_t op = 0;

	inline void flush() {
		if (op) {
			fwrite(obuf, 1, op, stdout);
			op = 0;
		}
	}

	inline void putc(char c) {
		if (op == OUT_CAP) flush();
		obuf[op++] = c;
	}

	template<typename T>
	void write(T x) {
		// 注意，这里输出不带换行
		if (x < 0) putc('-'), x = -x;
		if (x > 9) write(x / 10);
		putc(x % 10 + '0');
	}

	struct Flusher {
		// 析构时自动刷新
		~Flusher() { flush(); }
	} flusher;
} // namespace QuickRead
using namespace QuickRead;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};


ll getIdx(ll x, ll y) {
	return x * M + y;
}

void Solve() {
	// cin >> N >> M >> K >> Q;
	Cin(N, M, K, Q);
	vector<vector<char> > maze(N + 2, vector<char>(M + 2));
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= M; ++j) {
			// cin >> maze[i][j];
			getc(maze[i][j]);
		}
	}
	DSU dsu(N * M + M + 10);
	auto checkXY = [&](ll x, ll y) {
		if (x < 1 || x > N) return false;
		if (y < 1 || y > M) return false;
		if (maze[x][y] == '#') {
			return false;
		}
		return true;
	};
	for (int x = 1; x <= N; ++x) {
		for (int y = 1; y <= M; ++y) {
			if (!checkXY(x, y)) {
				continue;
			}
			for (int i = 0; i < 4; ++i) {
				auto [tox,toy] = make_tuple(x + dx[i], y + dy[i]);
				if (checkXY(tox, toy)) {
					dsu.merge(getIdx(tox, toy), getIdx(x, y));
				}
			}
		}
	}
	vector<vector<int> > g(N * M + M + 10);
	for (int i = 1; i <= K; ++i) {
		ll x1, y1, x2, y2;
		Cin(x1, y1, x2, y2);
		if (dsu.same(getIdx(x1, y1), getIdx(x2, y2))) {
			continue;
		}
		ll fa1 = dsu.find(getIdx(x1, y1)), fa2 = dsu.find(getIdx(x2, y2));
		g[fa1].push_back(fa2);
	}
	vector<int> vis(N * M + M + 10);
	vector<set<int> > connect(N * M + M + 10);
	vector<char> is_run(N * M + M + 10);
	ll tim = 0;
	for (int x = 1; x <= N; ++x) {
		for (int y = 1; y <= M; ++y) {
			if (!checkXY(x, y)) {
				continue;
			}
			++tim;
			int src = getIdx(x, y);
			src = dsu.find(src);
			if (is_run[src]) {
				continue;
			}
			is_run[src] = true;
			queue<int> q;
			q.push(src);
			vis[src] = tim;
			while (!q.empty()) {
				ll u = q.front();
				q.pop();
				for (auto to: g[u]) {
					if (vis[to] >= tim) continue;
					vis[to] = tim;
					connect[src].insert(to);
					q.push(to);
				}
			}
		}
	}
	for (int i = 1; i <= Q; ++i) {
		ll x1, y1, x2, y2;
		// cin >> x1 >> y1 >> x2 >> y2;
		Cin(x1, y1, x2, y2);
		if (dsu.same(getIdx(x1, y1), getIdx(x2, y2))) {
			putc('1');
			putc('\n');
			continue;
		}
		ll fa1 = dsu.find(getIdx(x1, y1)), fa2 = dsu.find(getIdx(x2, y2));
		if (connect[fa1].contains(fa2)) {
			putc('1');
			putc('\n');
		} else {
			putc('0');
			putc('\n');
		}
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef LOCAL
	cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

	Cin(lT);
	for (testcase = 1; testcase <= lT; ++testcase)
		Solve();
	return 0;
}

/*

TLE
https://acm.hdu.edu.cn/contest/view-code?cid=1236&rid=2789

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1236&rid=3138

*/

2026 杭电暑期多校 8-1009-价值总是越大越好

首选排除我们管不了的，我们管的了的东西，两两配对，绝对值之差要最大，显然是划分为两个集合，大的集合中的数字减去小的集合中的数字。这种较为简单，而且限制一看就比较宽松的计数题目，一般都和这个阶乘，集合划分后乱排有关系。然后两两配对计数的话，一开始可以不用关心这个两两是谁在前，谁在后，先关注哪两个数被分配到了同一集合，或者说是这个分配的顺序。

2026 杭电暑期多校 8-1002-会自动求和的序列

那么，如果我们发现一个操作每一轮都会做，或者操作的时间非常有规律，即便这个操作有一些不规律的增量啊，那么往往来说，其肯定是有办法通过基底值加上这个一个我们维护的增量值得到答案的。

2026 杭电暑期多校 8-1008-分数越小还是越大越好

这种让你构造这个最大最小的，可以先手玩一下样例，自己画一画，看看最大最小的构造策略是什么。

Mex 的题目，我们肯定要利用好 Mex 的性质。Mex 要求在 $<mex$ 的全部一一出现啊，一个都不能落下啊。

可以利用 mex 要求的这个连续属性，定义 dp 状态。设 $DP(u, v)$ 表示：将标签 $0, 1, \dots, \operatorname{dist}(u, v)$ 分配给路径 $u \dots v$ 上的所有节点，所能获得的最大累计贡献分数。（比如这道题目，他就利用了这个性质）

你也可以反过来这么想，如果说你的DP状态定义要比较的暴力的话，那么其实你将会需要考虑每一个点它到底要放什么值，这个其实我们完全不能够去考虑的，因为你每个点都要考虑的话，你这个DP就是一个N维的DP，完全没有任何效率可言，反正基本上就和暴力差不多。