本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-09 18:15:31

思路：

先考虑连续偶数的和：

$ \begin{matrix} \sum_{i=1}^{n} 2i \ =2\sum_{i=1}^{n}i \ =2\frac{n(n+1)}{2}\ =n(n+1) \end{matrix} $。

然后是奇数的和：

$\begin{matrix} \sum_{i=0}^{n} 2i+1 \ =(2\sum_{i=0}^{n-1}i)+n \ =2\frac{n(n-1)}{2}+n\ =n(n-1)+n\ =n^2 \end{matrix}$

于是可以求出进行 $k$ 轮的和。

那么对于一个 $n$ 求第 $1,2 \dots n$ 所有数的和可以考虑先求出最大的 $k$ 使得 $2^k-1 \le n$。

那么对于进行了 $k$ 轮后没算的数字可以考虑 $k$ 的奇偶，然后算出要添加的种类的数的总个数，用总个数的贡献减去已有的贡献即可。

然后对于 $[l,r]$ 这段区间可以拆分成 $[1,r] - [1,l-1]$，然后按照上面说的做即可。

由于中途怕爆 long long，所以用了 __int128。

Code：

#include <bits\/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

ll l, r;
array<ll, 3> s[70];

ll power(ll a, ll b) {
	ll res = 1;

	for (; b; b >>= 1, a = a * a % mod)
		if (b & 1) res = res * a % mod;

	return res;
}

ll solve(ll n) {
	if (!n) return 0;

	ll k = 1;
	while ((1ll << (k + 1)) - 1 <= n)
		++k;

	\/\/ cout << n << ' ' << k << endl;
	ll ans = s[k][0];
	if (k & 1) {
		ll even = s[k][2], cnt = n - s[k][1];
		ans = (__int128)ans + (__int128)cnt * (cnt + 1) % mod - (__int128)even * (even + 1) % mod;
		ans = (ans + mod) % mod;
	} else {
		ll odd = s[k][1], cnt = n - s[k][2];
		\/\/ cout << odd << ' ' << cnt <<  ' ' << n << endl;
		ans = ((__int128)ans + (__int128)cnt * (cnt - 1) % mod - (__int128)odd * (odd - 1) % mod + cnt - odd) % mod;
		ans = (ans + mod) % mod;
	}

	return ans;
}

int main() {
	ll odd = 0, even = 0;
	for (ll i = 1; i <= 60; ++i) {
		if (i & 1) odd += (1ll << (i - 1ll));
		else even += (1ll << (i - 1ll));

		s[i] = {((__int128)even * ((__int128)even + 1) % mod + (__int128)odd * ((__int128)odd - 1) % mod + (__int128)odd % mod) % mod, odd, even};
\/\/		cout << s[i][0] << ' ' << i << endl;
	}

	scanf("%lld%lld", &l, &r);

	\/\/ cout << solve(r) << ' ' << solve(l - 1) << endl;

	printf("%lld\n", (solve(r) - solve(l - 1) + mod) % mod);

	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-09 19:44:30

思路：

可以依次从小到大考虑归位。

对于第 $i$ 大，若它原本的位置和它要在的位置满足题目中给出的关系那么直接交换即可。

若它原本的位置和它要在的位置相等直接跳过即可。

否则在这个数的后面或前边一定有一部分中数的个数是 $\ge \frac n 2$。

• 若这个数的后边数的个数 $\ge \frac n 2$，那么可以考虑直接跳到 $n$，然后再跳到它应在的位置。
• 若这个数的前边数的个数 $\ge \frac n 2$，那么可以考虑先于第一个数交换，然后若于它应在的位置距离满足条件就直接跳，否则就先跳到 $n$，再跳到应该在的位置，然后再将第一个数换回去。

然后最多的交换次数就是这个数前面的数的个数 $\ge \frac n 2$ 且跳到 $1$ 之后要再跳到 $n$，再跳回应在的位置，所以最多的交换次数为 $4n$，低于上界可行。

#include <bits\/stdc++.h>

using namespace std;

int n;
int a[300010];
pair<int, int> b[300010];
int di[300010];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		b[i] = {a[i], i};
	}

	sort(b + 1, b + 1 + n);
	for (int i = 1; i <= n; ++i) {
		di[i] = b[i].second;
	}

	vector<pair<int, int>> opt;

	for (int i = 1; i <= n; ++i) {
		\/\/ cout << i << ' ' << a[1] << "---\n";
		\/\/ printf("QAQWQ\n");
		\/\/ for (int j = 1; j <= n; ++j) printf("%d ", a[j]);
		\/\/ puts("");
		if (di[i] == i) continue;
		else if (2 * abs(di[i] - i) >= n) {
			opt.push_back({i, di[i]});
			swap(di[a[i]], di[i]);
			swap(a[i], a[di[a[i]]]);
		} else {
			if (n - di[i] >= n \/ 2) {
				opt.push_back({di[i], n});
				swap(di[i], di[a[n]]);
				swap(a[di[a[n]]], a[n]);
				opt.push_back({i, n});
				swap(di[a[n]], di[a[i]]);
				swap(a[i], a[n]);
			} else {
				opt.push_back({1, di[i]});
				swap(di[a[1]], di[i]);
				swap(a[1], a[di[a[1]]]);
				\/\/ cout << a[1] << endl;
				if (i - 1 >= n \/ 2) {
					opt.push_back({1, i});
					swap(di[a[1]], di[a[i]]);
					swap(a[1], a[di[a[1]]]);
					opt.push_back({1, di[1]});
					swap(di[a[1]], di[1]);
					swap(a[1], a[di[a[1]]]);
				} else {
					opt.push_back({1, n});
					swap(di[a[1]], di[a[n]]);
					swap(a[1], a[n]);
					\/\/ cout << a[1] << "---\n";
					opt.push_back({i, n});
					swap(di[a[i]], di[a[n]]);
					swap(a[i], a[n]);
					\/\/ cout << a[1] << "---\n";
					opt.push_back({di[1], 1});
					\/\/ cout << di[1] << ' ' << a[1] << ' ' << di[a[1]] << a[di[a[1]]] << endl;
					swap(di[1], di[a[1]]);
					swap(a[1], a[di[a[1]]]);
				}
			}
		}
	}

	printf("%d\n", opt.size());
	for (auto v : opt) {
		printf("%d %d\n", v.first, v.second);
	}

	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-10 19:14:10

思路：

可以先考虑将不经过一号点的连通分量找出来。

然后若连通分量个数 $>D$ 则无解（因为无法通过选 $D$ 条边而使其联通）。

否则对于 $1$ 连接每个连通分量的边任选一条，然后剩余的边随便选即可。

最后对于每个和 $1$ 相连的点，从他 dfs 一遍，当然不经过 $1$ 节点，对于每个点若当前位于它联通就将这条边加上并继续 dfs，否则跳过。

Code：

代码写的有点丑（

#include <bits\/stdc++.h>

using namespace std;

int n, m, D;
int idx, st[200010];
vector<int> e[200010];
int vis[200010], stt[200010];
map<pair<int, int>, int> ma1;

void dfs(int u) {
	st[u] = idx;
	for (auto v : e[u]) {
		if (v != 1 && !st[v]) {
			dfs(v);
		}
	}
}

void dfs1(int u) {
	vis[u] = 1;
	for (auto v : e[u]) {
		if (v != 1 && !vis[v]) {
			\/\/ cout << u << ' ' << v << "---\n";
			ma1[{u, v}] = 1;
			dfs1(v);
		}
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &D);
	for (int i = 1; i <= m; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		if (u > v) swap(u, v);
		e[u].push_back(v);
		e[v].push_back(u);
	}

	if (e[1].size() < D) {
		puts("NO");
		\/\/ cout << 1 << endl;
		return 0;
	}

	for (auto v : e[1])
		if (!st[v]) {
			++idx;
			dfs(v);	
		}

	for (auto v : e[1]) {
		if (stt[st[v]]) continue;
		stt[st[v]] = true;
		--D;
		if (D < 0) {
			puts("NO");
			return 0;
		}
		vis[v] = true;
		ma1[{1, v}] = 1;
	}

	for (auto v : e[1]) {
		if (D) {
			if (!vis[v]) {
				vis[v] = true;
				--D;
				ma1[{1, v}] = true;
			}
		}
	}

	puts("YES");

	for (auto v : e[1]){
		if (ma1.count({1, v})) {
			\/\/ cout << v << endl;
			dfs1(v);
		}
	}

	for (auto [u, v] : ma1) printf("%d %d\n", u.first, u.second);
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-12 19:56:05

思路：

考虑贪心，对于一个深度为偶数的点，那么显然将它取到它子树中每个数的权值最小。

比如这组数据：

5
1 2 2 3
1 -1 2 3 -1

考虑在 $2$ 处设 $a_2 = 1$，这样可以使得 $a_3$ 和 $a_4$ 同时减一。

Code：

#include <bits\/stdc++.h>

using namespace std;

#define int long long

int n;
int s[100010];
vector<int> e[100010];
int sum;

void dfs(int u, int sfa, int fa = -1) {
	if (s[u] != -1) {
		if (s[u] < sfa) {
			puts("-1");
			exit(0);
		}
		sum += s[u] - sfa;
		for (auto v : e[u]) {
			if (v != fa)
				dfs(v, s[u], u);
		}
	} else {
		int minn = 1 << 30;
		for (auto v : e[u]) {
			if (v != fa)
				minn = min(minn, s[v] - sfa);
		}
		if (minn < 0) {
			puts("-1");
			exit(0);
		}
		if (minn != 1 << 30)
			sum += minn;
		for (auto v : e[u])
			if (v != fa)
				dfs(v, sfa + minn, u);
	}
}

signed main() {
	scanf("%lld", &n);
	for (int i = 2; i <= n; ++i) {
		int fa;
		scanf("%lld", &fa);
		e[fa].push_back(i);
		e[i].push_back(fa);
	}
	for (int i = 1; i <= n; ++i) scanf("%lld", &s[i]);

	dfs(1, 0);

	printf("%lld\n", sum);

	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-13 08:30:29

打表题。

看题一眼发现好像 $n$ 不会很大，打个表，发现当 $n=2 \times 10^6$ 的时候回文数的个数 $\times 42$ 已经 $<$ 素数的个数了。

所以考虑直接预处理 $2 \times 10^6$ 以内的素数个数以及回文数的个数，然后判断即可。

这里由于是 $\pi(n) \le A \cdot rub(n)$，由 $A=\frac{p}{q}$，那么就可以转化成 $\pi(n) \cdot q \le p \cdot rub(n)$ 来避免除法。

#include <bits\/stdc++.h>

using namespace std;

int T;
int cnt[2000010], cnt1[2000010];

bool is(int u) {
	string s = to_string(u), t = s;

	reverse(t.begin(), t.end());

	return s == t;
}
void init() {
	for (int i = 1; i <= 2000000; ++i) cnt[i] = 1;
	cnt[0] = cnt[1] = 0;
	for (int i = 2; i <= 2000000; ++i) {
		if (cnt[i]) {
			for (int j = 2; i * j <= 2000000; ++j)
				cnt[i * j] = 0;
		}
	}

	for (int i = 1; i <= 2000000; ++i) cnt[i] += cnt[i - 1], cnt1[i] += cnt1[i - 1] + is(i);
}

int main() {
	init();
	int p, q; scanf("%d%d", &p, &q);

	for (int n = 2000000; n >= 0; --n) {
		if (cnt1[n] * p >= cnt[n] * q) {
			printf("%d\n", n);
			return 0;
		}
	}

	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-16 06:00:04

先找性质。

由于 $1,2,3$ 无论怎么 $\oplus$ 都凑不出来 $4$，所以要合法，必须让 $4$ 的个数为偶数。

然后又 $1 \oplus 2 = 3$，所以一个 $1$ 和一个 $2$ 可以和一个 $3$ 抵消，所以 $1,2,3$ 的个数奇偶性相同。

然后考虑预处理，由于 $1,2,3$ 的次数贡献跟 $4$ 无关，所以预处理的时候不用考虑 $4$。

那么设 $f_{i,j,k}$ 表示 $i$ 个 $1$，$j$ 个 $2$，$k$ 个 $3$ 的最大赢得次数，并且 $i, j, k$ 奇偶性相同，那么我们要么选出两个相同的数，然后异或抵消，要么选择 $1,2,3$ 并抵消，即 $f_{i,j,k} = \min\{ f_{i-2,j,k},f_{i,j-2,k}, f_{i,j,k-2},f_{i-1,j-1,k-1} \} + 1$。

然后询问的时候分别将 $a,b,c$ 变为同奇或同偶然后取最大即可。

#include <bits\/stdc++.h>
 
using namespace std;
 
int T;
int f[210][210][210];
 
int main() {
	f[1][1][1] = 1;
	for (int i = 0; i <= 200; ++i) {
		for (int j = (i & 1); j <= 200; j += 2) {
			for(int k = (j & 1); k <= 200; k += 2) {
				if (i == 1 && j == 1 && k == 1) continue;
				if (i == 0 && j == 0 && k == 0) continue;
				if (i >= 2) f[i][j][k] = max(f[i][j][k], f[i - 2][j][k] + 1);
				if (j >= 2) f[i][j][k] = max(f[i][j][k], f[i][j - 2][k] + 1);
				if (k >= 2) f[i][j][k] = max(f[i][j][k], f[i][j][k - 2] + 1);
				if (i >= 1 && j >= 1 && k >= 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k - 1] + 1);
			}
		}
	}
 
	scanf("%d", &T);
	while (T--) {
		int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d);
 
		int ans = 0;
		if (a - (a & 1) >= 0 && b - (b & 1) >= 0 && c - (c & 1) >= 0) ans = f[a - (a & 1)][b - (b & 1)][c - (c & 1)];
		if (a - (!(a & 1)) >= 0 && b - (!(b & 1)) >= 0 && (c - (!(c & 1))) >= 0) ans = max(ans, f[a - (!(a & 1))][b - (!(b & 1))][(c - (!(c & 1)))]);
 
		printf("%d\n", d \/ 2 + ans);
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-16 06:03:35

显然的，遇到一个 $0$ 就一定要从当前开始翻转，若不够无法翻转，那么无解。

然后对于翻转，实际上就是将区间 $+1$ 并 $\bmod 2$，那么 $+1$ 直接差分，然后边做边记录前缀和即可，然后用到当前值时再 $\bmod 2$。

然后枚举 $k$ 按照刚才的思路翻转即可。

#include <bits\/stdc++.h>

using namespace std;

typedef long long ll;

int T;
int n;
char s[5010];
int sum[5010];

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		scanf("%s", s + 1);

		for (int k = n; k >= 1; --k) {
			for (int i = 0; i <= n; ++i) sum[i] = 0;
			for (int i = 1; i <= n - k + 1; ++i) {
				int t = s[i] - '0';
				sum[i] += sum[i - 1];
				if (!((t + sum[i]) & 1)) {
					++sum[i];
					--sum[i + k];
				}
			}

			for (int i = n - k + 2; i <= n; ++i) sum[i] += sum[i - 1];

			bool ok = true;

			for (int i = 1; i <= n; ++i) {
				int t = s[i] - '0';

				if (!((t + sum[i]) & 1)) {
					ok = false;
					break;
				}
			}

			if (ok) {
				printf("%d\n", k);
				break;
			}
		}
	}

	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-09 11:56:32

显然的，答案至多为 $2$，所以可以考虑分类讨论。

当差有 $x,y$ 时直接输出 $0$。

若只有 $x,y$ 中的一个，那么最优就是在没有这个点的地方标记一下，次数为 $1$。

否则 $x,y$ 都没有，那么只需要考虑此时只需要标记一次的情况。若要标记两次，那么直接在 $x,y$ 对应位置标记即可。

考虑是否有间隔长度为 $x+y$ 的区间，若有此时只需要在中间标记一下。

否则就是类似这种（红色为原有点，蓝色为新加的点）：

此时就是判断有没有长度为 $x-y$ 的区间，然后看在区间的左/右放一个点是否越界，若越界则不行，否则可以。

#include <bits\/stdc++.h>

using namespace std;

int n, l, x, y;
int a[100010];
map<int, int> ma;

int main() {
	scanf("%d%d%d%d", &n, &l, &x, &y);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), ma[a[i]] = 1;
	int cntx = 0, cnty = 0;
	for (int i = 1; i <= n; ++i) {
		if (ma[a[i] + x]) ++cntx;
		if (ma[a[i] + y]) ++cnty;
	}

	cntx = min(cntx, 1);
	cnty = min(cnty, 1);

	if (cntx + cnty == 2) puts("0");
	else if (cntx + cnty == 1) {
		if (cntx == 1) {
			puts("1");
			printf("%d\n", y);
		} else {
			puts("1");
			printf("%d\n", x);
		}
	}
	else {
		for (int i = 1; i <= n; ++i) if (ma[a[i] + x + y]) {
			puts("1");
			printf("%d\n", a[i] + x);
			return 0;
		} else if (ma[a[i] + y - x] && a[i] + y <= l) {
			puts("1");
			printf("%d\n", a[i] + y);
			return 0;
		} else if (ma[a[i] + y - x] && a[i] - x >= 0) {
			puts("1");
			printf("%d\n", a[i] - x);
			return 0;
		}

		puts("2");
		printf("%d %d\n", x, y);
	}

	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-06 20:25:41

晚宴筵题解：

Subtask 0

由于 $w_i \ge i$，所以没有负权边。

可以直接模拟题意建边，然后跑一遍 dijkstra。

Subtask 1

由于没有边权限制，可以用 $dp$。

设 $f_{i,j}$ 表示 $(1,1) \sim(i,j)$ 的最短路。

然后转移就显然是 $f_{i,j}=\min_{l1_i \le k \le r1_i,l2_j\le p \le r2_j}\{f_{k, p}+w_i+w_j+w_k+w_p-i-j-k-p\}$，然后暴力转移即可。

Subtask 2

可以直接 $(1,1)$ 到，而且没有其他的边了，那么就直接输出 $w_i+w_j+w_1+w_1-i-j-2$ 即可。

当然，第一行第一列除 $(1,1)$ 外都为 inf。

Subtask 3

考虑如何优化 DP。

我们可以把关于 $i,j$ 的放到外面去，也就是 $f_{i,j}=\min_{l1_i \le k \le r1_i,l2_j\le p \le r2_j}\{f_{k, p}+w_k+w_p-k-p\}+w_i+w_j-i-j$。

然后我们可以发现，对于 $\min$ 中的值，可以用树套树求区间最大值，然后按照 Subtask 1 中的转移方程转移。

然后再把 $f_{i,j}+w_i+w_j-i-j$ 插入树中即可。

#include <bits\/stdc++.h>
using namespace std;
\/*
省略百行快读
*\/

#define min(a,b) (a<b?a:b)

typedef int ll;

const int INF = 0x3f3f3f3f;
const int N = 2010;

ll minV, tr[N << 2][N << 2];
ll a[N << 2][N << 2];
int n;
ll l1[N], r1[N], l2[N], r2[N], w[N];
ll f[N][N];
#define pushupX(deep,rt) tr[deep][rt] = min(tr[deep << 1][rt], tr[deep << 1 | 1][rt])
#define pushupY(deep,rt) tr[deep][rt] = min(tr[deep][rt << 1], tr[deep][rt << 1 | 1])
void buildY(int ly, int ry, int deep, int rt, int flag) {
    if (ly == ry){
        if (flag!=-1)
            tr[deep][rt] = INF;
        else
            pushupX(deep, rt);
        return;
    }
    int m = (ly + ry) >> 1;
    buildY(ly, m, deep, rt << 1, flag);
    buildY(m + 1, ry, deep, rt << 1 | 1, flag);
    pushupY(deep, rt);
}
void buildX(int lx, int rx, int deep) {
    if (lx == rx){
        buildY(1, n + 1, deep, 1, lx);
        return;
    }
    int m = (lx + rx) >> 1;
    buildX(lx, m, deep << 1);
    buildX(m + 1, rx, deep << 1 | 1);
    buildY(1, n + 1, deep, 1, -1);
}
void modifyY(int Y, int val, int ly, int ry, int deep, int rt, int flag) {
    if (ly == ry) {
        if (flag) 
            tr[deep][rt] = val;
        else pushupX(deep, rt);
        return;
    }
    int m = (ly + ry) >> 1;
    if (Y <= m)
        modifyY(Y, val, ly, m, deep, rt << 1, flag);
    else
        modifyY(Y, val, m + 1, ry, deep, rt << 1 | 1, flag);
    pushupY(deep, rt);
}
void modifyX(int X, int Y, int val, int lx, int rx, int deep) {
    if (lx == rx) {
        modifyY(Y, val, 1, n + 1, deep, 1, 1);
        return;
    }
    int m = (lx + rx) >> 1;
    if (X <= m)
        modifyX(X, Y, val, lx, m, deep << 1);
    else
        modifyX(X, Y, val, m + 1, rx, deep << 1 | 1);
    modifyY(Y, val, 1, n + 1, deep, 1, 0);
}
void queryY(int Yl, int Yr, int ly, int ry, int deep, int rt) { 
    if (Yl <= ly && ry <= Yr) {
        minV = min(tr[deep][rt], minV);
        return;
    }
    int m = (ly + ry) >> 1;
    if (Yl <= m)
        queryY(Yl, Yr, ly, m, deep, rt << 1);
    if (m < Yr)
        queryY(Yl, Yr, m + 1, ry, deep, rt << 1 | 1);
}
void queryX(int Xl, int Xr, int Yl, int Yr, int lx, int rx, int rt) {
    if (Xl <= lx && rx <= Xr){
        queryY(Yl, Yr, 1, n + 1, rt, 1);
        return;
    }
    int m = (lx + rx) >> 1;
    if (Xl <= m)
        queryX(Xl, Xr, Yl, Yr, lx, m, rt << 1);
    if (m < Xr)
        queryX(Xl, Xr, Yl, Yr, m + 1, rx, rt << 1 | 1);
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> l1[i];
    for (int i = 1; i <= n; ++i) cin >> r1[i];
    for (int i = 1; i <= n; ++i) cin >> l2[i];
    for (int i = 1; i <= n; ++i) cin >> r2[i];
    for (int i = 1; i <= n; ++i) cin >> w[i];

    buildX(1, n + 1, 1);

    for (int i = 0; i <= n + 1; ++i)
        for (int j = 0; j <= n + 1; ++j)
            f[i][j] = 0x3f3f3f3f;
    f[1][1] = 0;
    modifyX(2, 2, w[1] + w[1] - 1 - 1, 1, n + 1, 1);

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            if (i == 1 && j == 1) continue;
            minV = INF;
            queryX(l1[i] + 1, r1[i] + 1, l2[j] + 1, r2[j] + 1, 1, n + 1, 1);
            if (minV != INF) {
                f[i][j] = minV + w[i] + w[j] - i - j;
                modifyX(i + 1, j + 1, f[i][j] + w[i] + w[j] - i - j, 1, n + 1, 1);
            }
        }
        
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (f[i][j] == 0x3f3f3f3f) cout << "inf ";
            else cout << f[i][j] << " ";
        }
        cout << "\n";
    }
        
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-16 19:37:30

路虽远题解

题意：

给你一个 $n$ 个点 $m$ 条边的图，从一个节点出发到另一个节点时可能要等红绿灯，可以闯黄灯 $g$ 次，要在 $k$ 条边上添加限速，限速会使小 $X$ 经过这条边的时间变长，求小 $X$ 从第一个节点到第 $n$ 个节点的最短时间。

Subtask0

可以直接爆搜，让后每次就记录当前时间，当前节点，以及还剩多少条边需要限速，以及还可以闯多少次黄灯，因为可以通过每个灯的时间算出来当前是哪个灯，然后判断要不要闯黄灯，以及需要等多长时间。

得分：$20pts$。

Subtask1

因为只有绿灯，而且无法闯红灯，没有限速，那么就直接对原图跑最短路就可以了。

加上前面的 Subtask 可以拿 $25$ 分。

Subtask2

没有黄灯，也就是无法闯黄灯。

那么考虑如何做限速。

因为相当于修改 $k$ 条边的边权，那么可以考虑分层图。

那么可以考虑都限速，然后建 $m - k$ 层，每层由不限速的边连起来，这样到达最后一层中相当于第一层的的 $n$ 个点（后面统称为终点），就相当于一定有 $k$ 条边是限速的（因为最多走 $m - k$ 条不限速的边）。

然后再把每一层的终点向最后一层的终点连一条边权为 $0$ 的边连起来，这样能保证走不足 $m - k$ 条不限速的边可以直接到达。

最后就输出到达终点的最短距离即可，因为 spfa 会被卡，所以要用堆优化的 dijkstra。

加上前面的 Subtask 可以拿 $50$。

Subtask3

其实可以使用三维的 dijkstra，每一维分别表示当前是那个点，当前还剩多少条边可以不限速，当前还可以闯多少黄灯。

设当前时刻为 $t$。

• 1.若还可以不限速：

• 2.若不可以不限速：

同上，只不过把通过的时间改为限速的权值即可。

则有两种情况：

• 1.不闯黄灯，则判断当前时刻当前路口是否为绿灯，若是则可以直接冲过去，权值为不限速的权值，否则就加上等红绿灯的时间，也就是灯亮的总时间减去当前时刻 $t$，也就是总时间减去已经过去的时间。
• 2.闯黄灯，那么当前是绿灯或者黄灯时间，那么可以直接冲过去，否则再加上等红绿灯的时间即可。

按照权值跑 dijkstra 即可。

#include <bits\/stdc++.h>

using namespace std;

#define int long long

const int N = 110, M = N << 1;
const int INF = 1ll << 60;

int n, m, k, g;
int a[N], b[N], c[N], dist[N][N][N];
int h[N], e[M], ne[M], p[M], q[M], idx;

struct Node {
    int x, y, z, w;
    const bool operator<(const Node &x) const{
        return w > x.w;
    }
};
priority_queue<Node> q1;

void add(int a, int b, int n, int m) {
    e[idx] = b, p[idx] = n, q[idx] = m, ne[idx] = h[a], h[a] = idx++;
}

void update(int x, int y, int z, int w) {
    if (dist[x][y][z] > w) {
        dist[x][y][z] = w;
        q1.push({x, y, z, w});
    }
}

void dijkstra() {
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= k; ++j)
            for (int k = 0; k <= g; ++k)
                dist[i][j][k] = INF;

    dist[1][0][0] = 0;
    q1.push({1, 0, 0, 0});

    while (!q1.empty()) {
        auto u = q1.top();
        q1.pop();
        int x = u.x, y = u.y, z = u.z, w = u.w, now = w % (a[x] + b[x] + c[x]);
        if (dist[x][y][z] < w) continue;
        for (int i = h[x]; ~i; i = ne[i]) {
            int v = e[i];
            if (y < k) {
                if (now < a[x]) update(v, y + 1, z, w + p[i]);
                else update(v, y + 1, z, w + a[x] + b[x] + c[x] - now + p[i]);
                if (z < g) {
                    if (now < (a[x] + b[x])) update(v, y + 1, z + 1, w + p[i]);
                    else update(v, y + 1, z + 1, w + a[x] + b[x] + c[x] - now + p[i]);
                }
            }
            if (now < a[x]) update(v, y, z, w + q[i]);
            else update(v, y, z, w + a[x] + b[x] + c[x] - now + q[i]);
            if (z < g) {
                if (now < (a[x] + b[x])) update(v, y, z + 1, w + q[i]);
                else update(v, y, z + 1, w + a[x] + b[x] + c[x] - now + q[i]);
            }
        }
    }
}

signed main() {
    memset(h, -1, sizeof(h));
    scanf("%lld%lld%lld%lld", &n, &m, &k, &g);
    k = m - k;

    for (int i = 1; i <= n; ++i) scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);

    for (int i = 1; i <= m; ++i) {
        int u, v, p, q;
        scanf("%lld%lld%lld%lld", &u, &v, &p, &q);
        add(u, v, p, q);
        add(v, u, p, q);
    }

    dijkstra();
    int ans = INF;

    for (int i = 0; i <= k; ++i)
        for (int j = 0; j <= g; ++j)
            ans = min(ans, dist[n][i][j]);

    if (ans == INF) puts("-1");
    else printf("%lld\n", ans);

    return 0;
}