「Summary」2022-06-25 做题记录

updated…

2022-06-25

$\mathbb{CF}\mathbb{1301}\mathbb{F}$

link

中转！扩展！

看到具有相同性质之间的块可以有联系 $\to$ 缩点 / 整体处理。
对于要求答案可以进行拆分，找中转点，小扩大。

$\mathbb{CF}\mathbb{1209}\mathbb{F}$

link

十进制可以拆成一位一位的处理

$bfs$ 贪心时注意更新方式。在有距离相等的点的时候，应该将它们打包，同时对他们的权值为 $1\dots 9$ 的边进行更新。 所以 $bfs$ 应该这样写

vector<vector<int> > que1, que2;
void bfs() {

	vector<int> tmp;
	tmp.push_back(1), vis[1] = 1;
	que1.push_back(tmp);

	while (1) {

		if (que1.empty()) break;
		for (auto fr : que1) {

			for (int len = 0; len < 10; len++) {

				tmp.clear();

				for (auto u : fr) {
					for (auto v : G[u][len]) if (!vis[v])
						vis[v] = 1, dis[v] = (dis[u] * 10 + len) % Mod, tmp.push_back(v);
				}

				if (!tmp.empty()) que2.push_back(tmp);

			}

		}

		que1 = que2, que2.clear();

	}

}

$\mathbb{CF}\mathbb{698}\mathbb{D}$

link

等价的两个数据范围差距大时注意利用小的，改变枚举顺序;

这题有依明显的依赖关系的问题可以递归。
若可以抽象成图，可以建 $DAG$ 解决，该题可以递归判断解的可行性。