返回 C 组做题，然后发现自己挂分了。
T1 寻找道路
反向建边，跑 dfs 算出能到达终点的点，然后跑 dij 就可以了。
/**
* @file 寻找道路.cpp
* @tag: #GMOJ#最短路
* @author: ZnPdCo
* @date: 2023-12-30 14:26:11
* @problem: https://gmoj.net/senior/#main/show/3934
**/
#include <cstdio>
#include <queue>
#define ll long long
#define N 10010
#define M 200010
using namespace std;
ll n, m, st, ed;
bool flag[N], go[N];
ll head[N];
ll nxt[2*M];
bool type[2*M];
ll to[2*M], cnt;
void addEdge(ll u, ll v, ll t) {
cnt++;
to[cnt] = v;
nxt[cnt] = head[u];
type[cnt] = t;
head[u] = cnt;
}
void dfs(ll u) {
flag[u] = 1;
for(ll i = head[u]; i; i = nxt[i]) if(type[i] == 1) {
ll v = to[i];
if(!flag[v]) dfs(v);
}
}
priority_queue<pair<ll, ll> > q;
ll dis[N];
bool vis[N];
void dij() {
for(ll i = 1; i <= n; i++) dis[i] = 1e15;
dis[st] = 0;
q.push(make_pair(0, st));
while(!q.empty()) {
ll u = q.top().second;
q.pop();
if(vis[u]) continue;
vis[u] = 1;
for(ll i = head[u]; i; i = nxt[i]) if(type[i] == 0) {
ll v = to[i];
if(!go[v]) continue;
if(!vis[v]) {
if(dis[v] > dis[u] + 1) {
dis[v] = dis[u] + 1;
q.push(make_pair(-dis[v], v));
}
}
}
}
}
int main() {
scanf("%lld %lld", &n, &m);
for(ll i = 1; i <= m; i++) {
ll u, v;
scanf("%lld %lld", &u, &v);
addEdge(u, v, 0);
addEdge(v, u, 1);
}
scanf("%lld %lld", &st, &ed);
dfs(ed);
for(ll u = 1; u <= n; u++) {
go[u] = true;
for(ll i = head[u]; i; i = nxt[i]) {
ll v = to[i];
if(flag[v] == 0) go[u] = false;
}
}
dij();
if(dis[ed] == 1e15) printf("-1");
else printf("%lld", dis[ed]);
}
/*
3 3
1 2
2 3
3 1
1 2
*/
T2 联合权值
样例太水了，脑子也抽了，忘记还有兄弟距离了。
题目说得很明白，就是一棵树。对于树上的每一个节点与其相连的两个不同节点距离为 2。
然后就是数学题了。
/**
* @file 联合权值.cpp
* @tag: #GMOJ#树
* @author: ZnPdCo
* @date: 2023-12-30 14:26:53
* @problem: https://gmoj.net/senior/#main/show/3931
**/
#include <cstdio>
#include <algorithm>
#define ll long long
#define N 200010
#define P 10007
using namespace std;
ll n, w[N], ans1, ans2;
ll fa[N];
ll dep[N];
ll f[N], mx[N];
ll head[N];
ll nxt[2*N];
ll to[2*N], cnt;
void addEdge(ll u, ll v) {
cnt++;
to[cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
}
int main() {
scanf("%lld", &n);
for(ll i = 1; i < n; i++) {
ll u, v;
scanf("%lld %lld", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
for(ll i = 1; i <= n; i++) {
scanf("%lld", &w[i]);
}
for(ll u = 1; u <= n; u++) {
ll sum1 = 0, sum2 = 0, mx1 = 0, mx2 = 0;
for(ll j = head[u]; j; j = nxt[j]) {
ll v = to[j];
(sum1 += w[v]) %= P;
(sum2 += w[v]*w[v]) %= P;
if(w[v] > mx1) mx1 = w[v];
else if(w[v] > mx2) mx2 = w[v];
}
ans1 = max(ans1, mx1*mx2);
(ans2 += sum1 * sum1 - sum2) %= P;
}
printf("%lld %lld", ans1, ans2);
}
T3 飞扬的小鸟
赛时不知道为什么，直接上线段树，常数炸了。
其实可以直接用背包思想。原题就是一个可重复取的背包。
/**
* @file 飞扬的小鸟.cpp
* @tag: #GMOJ#dp
* @author: ZnPdCo
* @date: 2023-12-30 14:27:53
* @problem: https://gmoj.net/senior/#main/show/3932
**/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define N 10010
using namespace std;
ll n, m, k, ans2;
ll x[N], y[N];
ll f[2][N];
struct node {
ll p, h, l;
} a[N];
ll pos = 1;
bool cmp(node x, node y) {
return x.p < y.p;
}
int main() {
scanf("%lld %lld %lld", &n, &m, &k);
for(ll i = 1; i <= n; i++) {
scanf("%lld %lld", &x[i], &y[i]);
}
for(ll i = 1; i <= k; i++) {
scanf("%lld %lld %lld", &a[i].p, &a[i].l, &a[i].h);
}
sort(a+1, a+1+k, cmp);
for(ll i = 1; i <= n; i++) {
for(ll j = 0; j <= m; j++) f[i%2][j] = 1e15;
for(ll j = x[i]+1; j < m; j++) {
f[i%2][j] = min(f[i%2][j], min(f[(i-1)%2][j-x[i]], f[i%2][j-x[i]]) + 1);
}
for(ll j = m - x[i]; j <= m; j++) {
f[i%2][m] = min(f[i%2][m], min(f[(i-1)%2][j], f[i%2][j]) + 1);
}
for(ll j = 0; j <= m - y[i]; j++) {
f[i%2][j] = min(f[i%2][j], f[(i-1)%2][j+y[i]]);
}
// for(ll j = 0; j <= m; j++) printf("f[%lld][%lld]=%lld\n", i, j, f[i%2][j]);
if(pos <= k && a[pos].p == i) {
for(ll j = 0; j <= a[pos].l; j++) f[i%2][j] = 1e15;
for(ll j = a[pos].h; j <= m; j++) f[i%2][j] = 1e15;
for(ll j = 0; j <= m; j++) {
if(f[i%2][j] != 1e15) {
ans2 = max(ans2, pos);
}
}
pos++;
}
}
ll ans = 1e15;
for(ll i = 1; i <= m; i++) {
ans = min(ans, f[n%2][i]);
}
if(ans != 1e15) {
printf("1\n");
printf("%lld", ans);
} else {
printf("0\n");
printf("%lld", ans2);
}
}
T4 解方程
赛时一眼 \(O(nm)\) 正解，然后不知道为什么我竟然每次都求一次 \(x^i\)，常数送到 30pts。
因为 \(0\bmod p = 0\)，我们可以利用模数的性质，把 \(a_i\) 都取模，然后就是正常暴力。
但是对于 \(p\) 的倍数怎么办呢？没关系，两个模数撞的概率比较小，就可以过了。
我只用了 \(998244353\)。
不要每次都求一次 \(x^i\)。
然后可以边输入边取模。
/**
* @file 联合权值.cpp
* @tag: #GMOJ#玄学
* @author: ZnPdCo
* @date: 2023-12-30 14:27:22
* @problem: https://gmoj.net/senior/#main/show/3935
**/
#include <cstdio>
#include <random>
#include <ctime>
#include <algorithm>
using namespace std;
#define ll long long
#define N 110
#define P 998244353
mt19937 rnd(time(0));
ll n, m;
ll a[N];
bool ismx;
ll ans[N], cnt;
ll read() {
ll x=0, flag = 0;
char c = '.';
while((c < '0' || c > '9') && c != '-') c = getchar();
if(c == '-') flag = 1, c = getchar();
while(c >= '0' && c <= '9') {
x = ((x<<1)%P + (x<<3)%P + (c^'0')) % P;
c = getchar();
}
if(flag) x = (-x % P + P) % P;
return x;
}
void output() {
printf("%lld\n", cnt);
for(ll i = 1; i <= cnt; i++) {
printf("%lld\n", ans[i]);
}
}
int main() {
n = read(), m = read();
for(ll i = 0; i <= n; i++) {
a[i] = read();
}
for(ll i = 1; i <= m; i++) {
ll sum = 0, xc = 1;
for(ll j = 0; j <= n; j++) {
(sum += a[j] * xc % P) %= P;
(xc *= i) %= P;
}
if(sum == 0) ans[++cnt] = i;
}
output();
}
比赛赛时发挥不好，很多点都没有想到，特别是 T3，完全没有把背包联系起来（最后其实想到了，但不知道为什么自己丢掉了）