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

晚宴筵题解：

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-23 10:37:00

假设当前粉丝为 $t$ 个，则可以提问 $\lfloor \frac{t}{5} \rfloor$ 个问题。

Q1 为什么叫这个名字 by p_Hydroxy

A1 这是我第一款了解的支持连字的字体，所以就以它来命名（

Q2 有npy吗 by p_Hydroxy

A2 你说的对 （没错就是狗子（右）和小怪兽（左））

Q3 文化课怎么样 by p_Hydroxy

A3 不好评价

Q4 玩元神吗 by p_Hydroxy

A4 不玩

Q5 上几年级 by p_Hydroxy

A5 新初一

Q6 您的真名 by p_Hydroxy

A6 dcy

Q7 能成为奇迹行者吗 by LHYwssbfw555

A7 不能

Q8 能展示一下代码风格吗 by liuhl_weifang

A8 总而言之就是加空格，大括号不换行，函数一行一般会缩成一行,随心加空行，排序直接在排序里加比较函数。

加一堆代码： 感觉第二个更能表示我的码风（毕竟是最近写的，第一个是之前写的，然后稍微改了改

https:\/\/www.luogu.com.cn\/paste\/voqngclo https:\/\/www.luogu.com.cn\/paste\/17g30v8a

Q9 你对我的看法 by p_Hydroxy

A9

突然又想到一个属性，BJ，而且跟小怪兽一样（

这个 p_Hydroxy 怎么这么能出现在luogu里啊。

她怎么又在水啊。

别她妈水了啊。

不是这怎么又在水啊。

别**水了啊。

Q10 你对kele7的看法 by p_Hydroxy

A10 一眼顶针，鉴定为SaidBee xxs（雾，不玩元神导致的

Q11 你的身高 by p_Hydroxy

A11 大概1.8米

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-11-26 13:09:40

思路：

由于只要求起点和终点的颜色相同，那么可以枚举颜色。

对于每种颜色，分别考虑。

设当前颜色为 $c$。

考虑两种暴力：

• 1.对于当前颜色，设 $f_{i,j}$ 表示起点的颜色是 $c$，终点为 $(i,j)$ 时的路径数，初始化就是对于所有颜色为 $c$ 的位置 $f_{i,j}=1$，然后转移就是 $f_{i,j} += f_{i - 1,j} + f_{i,j-1}$；时间复杂度 $\mathcal{O(n^2)}$。
• 2.由于只要求起点和终点颜色相同那么可以枚举起点和终点然后组合数求个路径数即可，时间复杂度为 $\mathcal{O(n^4)}$。

然后我们发现当当前颜色不超过 $n$ 个时，暴力 $2$ 的时间总复杂度仅为 $\mathcal{O(n^3)}$，而超过 $n$ 个时，由于最多有 $n$ 个颜色的点数 $\ge n$（要不然总点数就超过 $n^2$ 了），那么用暴力 $1$ 总时间复杂度也为 $\mathcal{O(n^3)}$，所以两个结合起来就可以过啦。

总时间复杂度为 $\mathcal{O(n^3)}$。

Code:

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

using namespace std;

typedef long long ll;

#define int ll

const int N = 1010, mod = 998244353;
int fac[N], inv[N];

int n;
int a[410][410];
int f[410][410];
vector<pair<int, int>> e[160010];

int C(int n, int m) {
	if (n < m) return 0;
	if (n < 0 || m < 0) return 0;
	return fac[n] * inv[m] % mod * inv[n - m] % mod;
}

int qmi(int a, int k, int p) {
    int res = 1;
    while (k){
        if (k & 1) res = (ll)res * a % p;
        a = (ll)a * a % p;
        k >>= 1;
    }
    return res;
}

signed main() {
    fac[0] = inv[0] = 1;
    for (int i = 1; i < N; ++i) {
        fac[i] = (ll)fac[i - 1] * i % mod;
        inv[i] = (ll)inv[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			scanf("%lld", &a[i][j]);
			e[a[i][j]].push_back({i, j});
		}
	}

	ll ans = 0;

	for (int i = 1; i <= n * n; ++i) {
		if (!e[i].size()) continue;
		if (e[i].size() <= n) {
			for (auto [X1, Y1] : e[i])
				for (auto [X2, Y2] : e[i]) {
					ans = (ans + C(X2 - X1 + Y2 - Y1, X2 - X1)) % mod;
				}
		} else {
			for (int j = 1; j <= n; ++j)
				for (int k = 1; k <= n; ++k) {
					f[j][k] = (a[j][k] == i);
					f[j][k] = (f[j][k] + f[j][k - 1]) % mod;
					f[j][k] = (f[j][k] + f[j - 1][k]) % mod;
					ans += f[j][k] * (a[j][k] == i);
					ans %= mod;
				}
		}
	}

	printf("%lld\n", ans);
	return 0;
}

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

思路：

发现是排列，于是考虑直接枚举 $a_i$ 的倍数对应 $b$ 序列中哪个数，显然的调和级数时间复杂度 $\mathcal{O(n \log n)}$。

于是对于每个数对 $(i,j)$，其实就是选出尽可能多的点使得 $i$ 和 $j$ 都严格单调递增，那么可以考虑将其中一维排序（满足一维的单调状态），然后对另一维再去用经典的贪心或权值树状数组做即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-01 20:55:27

思路：

首先看到序列长度是 $2^{60}$ 一眼不太可做的样子。

实际上我们仔细分析一下，假如前 $i$ 个数的异或和的最高位为 $k$。

那么因为要求 $a$ 递增，又因为是异或，所以之前的数中二进制的第 $k$ 位为最高位的至少有一个，所以当前若最高位是 $k$，那么也应该是 $1$，但这样一异或就抵消的第 $k$ 为的 $1$，不满足异或和严格单调递增，所以最高位只要要比之前的 $+1$，所以方案数不为 $0$ 的 $n$ 也就是 $\log m$ 级别的。

那么就可以考虑 DP，设 $dp_i$ 表示序列长为 $i$ 的方案数。

那么枚举 $2^i < m$ 的 $i$，对于 $j < i$，都可以加上这一位（因为若长度为 $i$ 那么最大的数的二进制至少要 $i$ 位）的贡献（就是取第 $i$ 位，那么异或和无论如何都比以前大，所以剩下的位乱取即可，别忘了最多取到 $m$ 的限制就行）。

Code：

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

using namespace std;

const int mod = 998244353;
typedef long long ll;

ll n, m;
ll dp[100] = {0, 1};

int main() {
	scanf("%lld%lld", &n, &m);

	int Log2 = 1;
	for (ll x = 1; x <= m; ++Log2, x *= 2) {
		ll t = (min(m, x * 2 - 1ll) - x + 1) % mod;
		for (int j = Log2; j; --j) dp[j] = (dp[j] + dp[j - 1] * t % mod) % mod;
	}

	if (n > Log2) puts("0");
	else printf("%lld\n", dp[n]); 

	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-11 21:41:59

思路:

考虑每次枚举交换哪一行或那一列，然后用 vector 来模拟，拿 map 来去重即可。

Code：

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

using namespace std;

int n, m;
vector<vector<int>> a, b;
map<vector<vector<int>>, int> ma;

void bfs() {
	queue<pair<vector<vector<int>>, int>> q;
	q.push({a, 0});
	while (q.size()) {
		auto t = q.front().first;
		auto d = q.front().second;
		q.pop();
		if (t == b) {
			printf("%d\n", d);
			exit(0);
		}
		for (int i = 0; i < n - 1; ++i) {
			swap(t[i], t[i + 1]);
			if (!ma.count(t)) {
				ma[t] = 1;
				q.push({t, d + 1});
			}
			swap(t[i], t[i + 1]);
		}
		for (int i = 0; i < m - 1; ++i) {
			for (int j = 0; j < n; ++j) {
				swap(t[j][i], t[j][i + 1]);
			}
			if (!ma.count(t)) {
				ma[t] = 1;
				q.push({t, d + 1});
			}
			for (int j = 0; j < n; ++j) {
				swap(t[j][i], t[j][i + 1]);
			}
 		}
	}
}

int main() {
	scanf("%d%d", &n, &m);
	a.resize(n);
	for (int i = 0; i < n; ++i) {
		a[i].resize(m);
		for (int j = 0; j < m; ++j) scanf("%d", &a[i][j]);
	}
	b.resize(n);
	for (int i = 0; i < n; ++i) {
		b[i].resize(m);
		for (int j = 0; j < m; ++j) scanf("%d", &b[i][j]);
	}

	bfs();

	puts("-1");
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-24 18:28:04

思路:

由于是按顺序来发礼物，那么显然可以考虑 DP。

那么设 $f_{i}$ 表示发了前 $i$ 个，并且当前在 $0$ 的最小的距离花费，$dist(i,j)$ 表示第 $i$ 个点和第 $j$ 个点的距离，第 $0$ 个点表示起点，$cost(i, j)$，表示 $i$ 按顺序走到 $j$ 点的距离和。

那么 $f_{i} = \min \{f_j + dist(0,j + 1) + cost(j + 1, i) + dist(i, 0)\}$。

然后因为 $cost$ 既有 $i$ 也有 $j$ 不太好维护，所以考虑拆成前缀和：

$f_{i} = \min \{f_j + dist(0,j + 1) + sum_i-sum_j + dist(i, 0)\}$。

然后把与 $i$ 有关的提出来：

$f_{i} = \min \{f_j + dist(0,j + 1)-sum_j\} + dist(i, 0) + sum_i$。

于是 $\min$ 中的直接用线段树做即可（其实也可以单调队列滑动窗口）。

Code：

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

using namespace std;

int n, k;
pair<double, double> a[200010];
double f[200010], s[200010];
double tr[800010];

void modify(int u, int l, int r, int x, double d) {
    if (l == r) {
        tr[u] = d;
        return;
    }

    int mid = (l + r) >> 1;

    if (x <= mid) modify(u << 1, l, mid, x, d);
    else modify(u << 1 | 1, mid + 1, r, x, d);

    tr[u] = min(tr[u << 1], tr[u << 1 | 1]);
}

double query(int u, int l, int r, int ql, int qr) {
    if (l >= ql && r <= qr) return tr[u];

    int mid = (l + r) >> 1;
    double res = 1e18;

    if (ql <= mid) res = min(res, query(u << 1, l, mid, ql, qr));
    if (qr > mid) res = min(res, query(u << 1 | 1, mid + 1, r, ql, qr));

    return res;
}

double dist(pair<double, double> a, pair<double, double> b) {
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i <= n; ++i) scanf("%lf%lf", &a[i].first, &a[i].second);

    for (int i = 0; i <= n; ++i) f[i] = 1e18;
    for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + dist(a[i - 1], a[i]);

    f[0] = 0;
    modify(1, 0, n, 0, f[0] + dist(a[0], a[1]) - s[1]);

    for (int i = 1; i <= n; ++i) {
        f[i] = query(1, 0, n, max(0, i - k), i - 1) + s[i] + dist(a[i], a[0]);
        if (i < n) modify(1, 0, n, i, f[i] - s[i + 1] + dist(a[i + 1], a[0]));
    }

    printf("%.15lf\n", f[n]);
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-25 18:21:46

思路:

首先假如数组开始全为 $0$ 怎么做。

那么显然是每进行一次操作 $1$，就立马进行操作 $2$。因为若再进行一次，那么相等的贡献最多不变，因为是对前缀加，第一次是 $1$ 满足，而第二次只有 $2$ 满足或者没有，后面同理。

然后看不全为 $0$ 怎么做。

我们发现 $n$ 比较小，考虑暴力做 $2n$ 轮，然后对于每一轮都计算贡献。也就是对于 $i(0 \le i \le 2n)$ 来说，我们就是求做 $i$ 的贡献加上剩余轮数按照刚才的策略的贡献。

而为什么做 $2n$ 轮？是因为当执行 $2n$ 轮时，你可以直接按照上述 $2$ 轮一个贡献，就可以到 $n$ 的贡献，而若一直执行的话，最多也就所有的数字都一样，最多也就是 $n$，所以没必要在往后枚举了。

当然做的轮数还要 $<d$。

时间复杂度 $\mathcal{O(Tn^2)}$。

Code:

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

using namespace std;

int T;
int n, k, d;
int a[2010], v[100010];
int cnt[4010];

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d%d", &n, &k, &d);
		cnt[0] = 0;
		for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), cnt[0] += a[i] == i;
		for (int i = 1; i <= k; ++i) scanf("%d", &v[i]);
		for (int i = 1; i <= 2 * n && i < d; ++i) {
			cnt[i] = 0;
			for (int j = 1; j <= v[(i - 1) % k + 1]; ++j) a[j]++;
			for (int j = 1; j <= n; ++j) cnt[i] += a[j] == j;
		}
		int ans = 0;
		for (int i = 0; i <= 2 * n && i < d; ++i) {
			\/\/ cout << cnt[i] << endl;
			ans = max(ans, cnt[i] + (d - i - 1) \/ 2);
		}
		printf("%d\n", ans);
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-25 18:27:44

思路：

找规律题。

考虑对于 $s1,s2,\dots,s6$ 的情况。

$$s1,s2,s3,s4,s5,s6$$ $$s1,s3,s4,s5,s6$$ $$s2,s3,s4,s5,s6$$ $$s1,s4,s5,s6$$ $$s2,s4,s5,s6$$ $$s3,s4,s5,s6$$ $$s1,s5,s6$$ $$s2,s5,s6$$ $$s3,s5,s6$$ $$s4,s5,s6$$ $$s1,s6$$ $$s2,s6$$ $$s3,s6$$ $$s4,s6$$ $$s5,s6$$ $$s1$$ $$s2$$ $$s3$$ $$s4$$ $$s5$$ $$s6$$

我们发现按长度排序，那么对于长度为 $i$ 的，那么前 $n - i + 1$ 个数是前缀，而后缀都相同，然后每次枚举就行了。

Code:

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

using namespace std;

int T;
int n;
string s;
bool st[200010][30][30];
bool st1[30];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	cin >> T;
	while (T--) {
		cin >> n >> s;
		int cnt = 0;
		long long ans = 0;
		for (int i = 0; i < n; ++i) {
			if (!st1[s[i] - 'a']) ++cnt;
			ans = 1ll * ans + 1ll * cnt;
			st1[s[i] - 'a'] = true;
		}
		printf("%lld\n", ans);
		memset(st1, false, sizeof(st1));
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-26 22:18:45

思路：

我们考虑一个性质：当他们出现进位时就一定不可以。

因为当出现进位，那么他们的和对下一位的贡献要比进位增加的贡献大，所以最后他们每个数位的和一定大于 $n$ 数位的和。

那么实际上每一位是独立的，考虑直接预处理出当数位和为 $k(0\le k\le9)$ 时有序三元组的方案数。

最后每一位乘起来即可。

Code

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

using namespace std;

int T;
int n;
int sum = 9;
array<int, 3> a;
int res = 0;
int f[10];

int main() {
	scanf("%d", &T);
	for (int i = 0; i <= 9; ++i) {
		for (int j = 0; j <= 9; ++j)
			for (int k = 0; k <= 9; ++k)
				for (int p = 0; p <= 9; ++p) {
					if (j + k + p == i) ++f[i];
				}
	}
	while (T--) {
		scanf("%d", &n);
		vector<int> a;
		while (n) {
			a.push_back(n % 10);
			n \/= 10;
		}
		long long ans = 1;
		for (int i = 0; i < (int)a.size(); ++i) ans = 1ll * ans * f[a[i]];
		printf("%lld\n", ans);
	}
	return 0;
}