2022gdcpc

和学弟vp了一下这场，本来抓的数学选手咕咕了，只有2个人，打下来的感觉就是套路题和码量太大了，太久没写码量题导致$I$调太久了，最后G没写完，K也没冲出来，感觉数学大爹在的话这K应该随便秒。

A.拼图

置换相关，数学爹不在不会

B.FFT

题解
考虑组合意义，其实就是输出n的排列

#include <bits/stdc++.h>
using namespace std;int n;int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;int fc = 1;for (int i = 1; i <= n; i++)fc = 1ll * fc * (i) % 998244353;cout << fc << endl;
}

C.魔法师

不会，待补

D.剪纸

不难发现答案就是斐波那契数列，这题cf上个月好像才出了个类似的。注意$n=2$特判

#include <bits/stdc++.h>
using namespace std;long long n, f[1000];int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;f[0] = f[1] = 1;for (int i = 2; i <= 100; i++) {f[i] = f[i - 1] + f[i - 2];}int j = 0;if (n == 2) {cout << "1 1\n";} else {while (f[j + 2] <= n) j++;cout << f[j] << " " << f[j + 1] << endl;}
}

E.黑白大陆

考虑一种特殊情况，即对黑白格子两两染色，我们发现这不仅是个二分图，还是个分层图，所以考虑将同色块缩点，相邻不同色块的点进行连边，也是个分层图，从分层图上某个颜色到相邻点的代价即等价于一次魔法的代价。所以枚举每个点，最小值即是以该点为起点的任意点为终点的最短路的最大值，注意到达某点的时候，
假如该点颜色为黑色，需要再用一次魔法

#include <bits/stdc++.h>
using namespace std;const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const int maxn = 2500 + 11;
int n, m, G[60][60], vis[60][60], sid[60][60], idcnt, col[maxn];
vector<unordered_set<int>> e;void bfs(int i, int j, int c) {queue<pair<int, int>> q;q.push({i, j}), vis[i][j] = 1, sid[i][j] = idcnt;while (q.size()) {auto [x, y] = q.front();q.pop();for (int d = 0; d < 4; d++) {int tx = dx[d] + x, ty = dy[d] + y;if (tx <= 0 || ty <= 0 || tx > n || ty > m || vis[tx][ty] ||G[tx][ty] != c)continue;q.push({tx, ty}), vis[tx][ty] = 1, sid[tx][ty] = idcnt;}}
}struct Node {int d, x;bool operator<(const Node& rhs) const { return d > rhs.d; }
};int dis[maxn];
int dijkstra(int s) {for (int i = 0; i <= idcnt; i++) dis[i] = 1e9;priority_queue<Node> q;q.push({dis[s] = 0, s});int mxdis = 0, mxcol = col[s];while (q.size()) {auto [dd, x] = q.top();q.pop();if (dd != dis[x]) continue;if (dis[x] > mxdis) {mxdis = dis[x], mxcol = col[x];}for (int v : e[x]) {if (dis[v] > dis[x] + 1) {dis[v] = dis[x] + 1;q.push({dis[v], v});}}}return mxdis + mxcol;
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) cin >> G[i][j];for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)if (!vis[i][j]) ++idcnt, col[idcnt] = G[i][j], bfs(i, j, G[i][j]);e.assign(idcnt + 11, {});for (int i = 2; i <= n; i++) {for (int j = 1; j <= m; j++) {if (sid[i][j] != sid[i - 1][j]) {e[sid[i - 1][j]].insert(sid[i][j]);e[sid[i][j]].insert(sid[i - 1][j]);}}}for (int i = 1; i <= n; i++) {for (int j = 2; j <= m; j++) {if (sid[i][j] != sid[i][j - 1]) {e[sid[i][j - 1]].insert(sid[i][j]);e[sid[i][j]].insert(sid[i][j - 1]);}}}int ans = 1e9;for (int i = 1; i <= idcnt; i++) ans = min(ans, dijkstra(i));cout << ans << endl; 
}

F.望舒客栈的每日委托

队友写的，用set模拟即可

#include <bits/stdc++.h>
using namespace std;const int maxn = 3e6 + 11;
int n, table_sz[maxn];
set<int> st[5];struct Event {int Time, table, x, a, d, t;bool operator<(const Event& rhs) const { return Time > rhs.Time; }
};int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;priority_queue<Event> q;for (int i = 1, x, a, d, t; i <= n; i++) {cin >> x >> a >> d >> t;q.push({a, -1, x, a, d, t});}int ans = 0;while (q.size()) {auto it = q.top();q.pop();if (it.table == -1) {int mnid = -1, sz = -1;if (it.t) {for (int i = it.x; i <= 4; i++) {if (st[i].size()) {if (mnid == -1 || mnid > *st[i].begin())mnid = *st[i].begin(), sz = i;}}} else {if (st[4].size()) mnid = *st[4].begin(), sz = 4;}if (mnid == -1) {mnid = ++ans, sz = 4;st[4].insert(ans);table_sz[ans] = 4;}st[sz].erase(mnid);st[sz - it.x].insert(mnid);table_sz[mnid] = sz - it.x;q.push({it.d, mnid, it.x, it.a, it.d, it.t});} else {int mnid = it.table;st[table_sz[mnid]].erase(mnid);table_sz[mnid] += it.x;st[table_sz[mnid]].insert(mnid);}}cout << ans << endl;
}

G.Rock&Frog

考虑一个简单的$dp$, $dp[i]=dp[j]+a[j]c[i{]}^2+b[j]c[i]$
考虑这是一个关于$c[i]$的二次函数，似乎无法维护，根据题目给出的条件对两个二次函数做差与韦达定理，得到$x_1+x2<0$, 又由于c[i] >= 0, 所以两个二次函数在$x>=0$有且只有一个交点，很多人对李超线段树存在误区，以为只能维护线段或直线，其实对于交点<= 1且只有两段单调性的函数，都可以用李超线段树来维护，这题就是类似维护直线分类讨论即可，注意标记永久化与动态开点，不得不吐槽的是，这题还要用__int128, 注意中间不要爆了。

#include<bits/stdc++.h>
#define lson lc[p], l, mid
#define rson rc[p], mid + 1, r
#define ls lc[p]
#define rs rc[p]
using namespace std;
using ll = __int128;
const int maxn = 1e5 + 5;
const ll inf = 1e18;
ll INF = (ll)inf * inf;
const int N = maxn * 18 * 4;
const int M = 1e9;
int a[maxn], b[maxn], c[maxn];
ll dp[maxn];
struct F {int a, b;ll c;ll cal(int x) {return (ll) a * x * x + (ll)b * x + c;}
} fx[maxn];void print(__int128 x) {if (x < 0) {putchar('-');x = -x;}if (x > 9)print(x / 10);putchar(x % 10 + '0');
}struct SegmentTree {int lc[N], rc[N], cnt;F ff[N];void update(int &p, int l, int r, int L, int R, F x) {if (!p) {p = ++cnt;ff[p] = x;ls = rs = 0;return;}if (L <= l && r <= R) {if (x.cal(l) < ff[p].cal(l) && x.cal(r) < ff[p].cal(r)) {ff[p] = x;} else if (x.cal(l) >= ff[p].cal(l) && x.cal(r) >= ff[p].cal(r)) {return;} else {int mid = l + r >> 1;if (x.cal(l) > ff[p].cal(l)) {if (ff[p].cal(mid) > x.cal(mid)) {update(lson, L, R, ff[p]);ff[p] = x;} else {update(rson, L, R, x);}} else {if (x.cal(mid) > ff[p].cal(mid)) {update(lson, L, R, x);} else {update(rson, L, R, ff[p]);ff[p] = x;}}}return;}int mid = l + r >> 1;if (L <= mid)update(lson, L, R, x);if (R > mid) update(rson, L, R, x);}ll query(int p, int l, int r, int x) {if (!p)return INF;if (l == r) {return ff[p].cal(x);}int mid = l + r >> 1;ll ans = ff[p].cal(x);if (x <= mid)return min(ans, query(lson, x));elsereturn min(ans, query(rson, x));}
}tr;int main() {int n;scanf("%d", &n);for (int i = 1; i <= n; ++i) {scanf("%d%d%d", &a[i], &b[i], &c[i]);fx[i].a = a[i], fx[i].b = b[i];}dp[1] = 0;fx[1].c = dp[1];int rt = 0;tr.update(rt, 0, M, 0, M, fx[1]);for (int i = 2; i <= n; ++i) {dp[i] = tr.query(rt, 0, M, c[i]);fx[i].c = dp[i];tr.update(rt, 0, M, 0, M, fx[i]);}print(dp[n]);return 0;
}

H.梅花易数

队友写的模拟

#include <bits/stdc++.h>
using namespace std;map<string, int> H;
map<int, int> T;void print(int S) {for (int i = 0; i < 6; i++) {int s = (S >> i) & 1;if (s) cout << "---" << endl;else cout << "- -" << endl;}
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);H["Zi"] = 1;H["Chou"] = 2;H["Yin"] = 3;H["Mao"] = 4;H["Chen"] = 5;H["Si"] = 6;H["Wu"] = 7;H["Wei"] = 8;H["Shen"] = 9;H["You"] = 10;H["Xu"] = 11;H["Hai"] = 12;T[1] = 7;T[2] = (0) | (1 << 1) | (1 << 2);T[3] = (1) | (0 << 1) | (1 << 2);T[4] = (0) | (0 << 1) | (1 << 2);T[5] = (1) | (1 << 1) | (0 << 2);T[6] = (0) | (1 << 1) | (0 << 2);T[7] = (1) | (0 << 1) | (0 << 2);T[0] = (0) | (0 << 1) | (0 << 2);string y, h;int m, d;cin >> y >> m >> d >> h;int t0 = (H[y] + m + d) % 8;int t1 = (H[y] + m + d + H[h]) % 8;int t2 = (H[y] + m + d + H[h]) % 6;if (t2 == 0) t2 = 5;else t2 -= 1;print(T[t0] | (T[t1] << 3));cout << endl;print((T[t0] | (T[t1] << 3)) ^ (1 << (5 - (t2))));
}

I.Rock&String

转化后等价于问任意某个字符串的任意两个之间的最小距离差值。
无聊的SAM套路题，SAM parents树上线段树合并即可，线段树维护距离左端点的endpos最小距离，距离右端点的endpos的最小距离，询问的时候倍增跳过去查，纯码农题，vp的时候调了1h, 吐了

#include<bits/stdc++.h>
#define lson lc[p], l, mid
#define rson rc[p], mid + 1, r
#define ls lc[p]
#define rs rc[p]
using namespace std;
const int INF = 2e9;
const int maxn = 4e5 + 5;
const int N = maxn * 18 * 4;
struct SAM {int len[maxn], link[maxn], ch[maxn][26], last, tot, rt[maxn], ld[N], rd[N], ans[N], lc[N], rc[N], cnt, lg[maxn];int strlen, f[maxn][22], d[maxn], pos[maxn];vector<int> G[maxn];SAM() {tot = last = 1;}void pushUp(int p, int l, int r) {int mid = l + r >> 1;if (!ls) {ld[p] = ld[rs] + (mid - l + 1);rd[p] = rd[rs];ans[p] = ans[rs];} else if(!rs) {rd[p] = rd[ls] + (r - mid);ld[p] = ld[ls];ans[p] = ans[ls];} else {ld[p] = ld[ls];rd[p] = rd[rs];ans[p] = min({ans[ls], ans[rs], rd[ls] + ld[rs] + 1});}}void update(int &p, int l, int r, int x, int val) {if (!p)p = ++cnt;if (l == r) {ld[p] = rd[p] = 0;ans[p] = INF;return;}int mid = l + r >> 1;if (x <= mid)update(lson, x, val);elseupdate(rson, x, val);pushUp(p, l, r);}int merge(int p, int q, int l, int r) {if (!p || !q)return p + q;int x = ++cnt;if (l == r) {ld[x] = min(ld[p], ld[q]);rd[x] = min(rd[p], rd[q]);ans[x] = min(ans[p], ans[q]);return x;}int mid = l + r >> 1;lc[x] = merge(ls, lc[q], l, mid);rc[x] = merge(rs, rc[q], mid + 1, r);pushUp(x, l, r);return x;}void dfs(int x, int fa) {d[x] = d[fa] + 1;f[x][0] = fa;for (int i = 1; i <= lg[d[x]]; ++i) f[x][i] = f[f[x][i - 1]][i - 1];for (auto &v : G[x]) {dfs(v, x);rt[x] = merge(rt[x], rt[v], 1, strlen);}}int extend(int c, int id) {int cur = ++tot, p = last; last = cur;len[cur] = len[p] + 1;update(rt[cur], 1, strlen, len[cur], 1);for (;p&&!ch[p][c]; p = link[p])ch[p][c] = cur;if (!p)link[cur] = 1;else {int q = ch[p][c];if (len[p] + 1 == len[q])link[cur] = q;else {int clone = ++tot;memcpy(ch[clone], ch[q], sizeof(ch[q]));len[clone] = len[p] + 1;link[clone] = link[q];link[q] = link[cur] = clone;for (; p && ch[p][c] == q; p = link[p]) {ch[p][c] = clone;}}}return cur;}void solve() {for (int i = 1; i <= tot; ++i) {lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);}for (int i = 2; i <= tot; ++i) {G[link[i]].emplace_back(i);}dfs(1, 0);int m;cin >> m;for (int i = 1; i <= m; ++i) {int l, r;cin >> l >> r;int ps = pos[r];for (int i = 19; i >= 0; --i) {if (len[f[ps][i]] >= r - l + 1) {ps = f[ps][i];}}if (ps == 1 || ans[rt[ps]] == INF) {cout << -1 << '\n';} else {cout << r - l + ans[rt[ps]] + 1 << '\n';}}}
} sam;int main() {ios::sync_with_stdio(false);cin.tie(0);string s;cin >> s;sam.strlen = s.length();for (int i = 0; i < s.length(); ++i) {sam.pos[i + 1] = sam.extend(s[i] - 'a', i + 1);}sam.solve();return 0;
}/*
abaabccababc
5
1 2
3 4
6 6
1 9
1 34
-1
2
-1
10*/

J.新英雄

可撤销贪心。
1的位置是敌方小兵就无解。
我们能拿法力就拿法力，遇到敌人直接走，假如遇到敌人不够法力的时候，在0 - 1复用得到2点法力，最后的时候累计的时间减去累计法力 / 2 向下取整即可，考虑这个可撤销贪心的正确性，因为你在友军拿法力值的时候，你撤销等价于先少一点法力，再走斩消耗一点法力，所以相当于撤销2点法力，所以最后一定是2点2点法力可以全部考虑到0 - 1, 相当于提前预支代价。

#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
const int maxn = 1e5 + 5;
struct Seg {int t, l, r;friend bool operator<(const Seg&x, const Seg&y) {return x.l < y.l;}
}seg[maxn], seg2[maxn];
int n, m, num;signed main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; ++i) {cin >> seg[i].t >> seg[i].l >> seg[i].r;}seg[0].t = 1;seg[0].l = seg[0].r = 0;seg2[0].t = 1;seg2[0].l = seg2[0].r = 0;sort(seg + 1, seg + 1 + m);for (int i = 1; i <= m; ++i) {if (seg[i].t == seg2[num].t) {seg2[num].r = max(seg2[num].r, seg[i].r);} else {seg2[++num].t = seg[i].t;seg2[num].l = seg[i].l;seg2[num].r = seg[i].r;}}if (!seg2[0].r) {cout << "0/21/0";return 0;}ll ans = 0, sum = 0;for (int i = 0; i <= num; ++i) {int len = seg2[i].r - seg2[i].l + 1 - (i == 0);if (seg2[i].t == 1) {sum += len;ans += 3 * len;} else {if (sum < len) {ll res = len - sum;if (res & 1) {res++;}sum += res;ans += 3 * res;}            ans += len;sum -= len;}}cout << ans - sum / 2 * 2; return 0;
}

K.斐波那契

不会，数学队友不在，另一个队友没rush出来

L.启航者

$O(n^2)$枚举点，套路的考虑换根dp，f[x]表示从根往子树方向走最大值的答案，$dp[i][0/1]$ 表示从$i$点出发下一个走最大值还是次大值的答案，先$dfs$一次求出f和$dp[1][\ast ]$，第二次从1进去$dfs$的时候, 对于$x$点，考虑走父亲还是儿子，同时考虑父亲是自己的最大还是次大，自己是父亲的最大还是次大，转移即可， 这里的值是无重复的，直接记录最大次大值转移即可。

#include<bits/stdc++.h>using namespace std;
using ll = long long;
const int maxn = 1e6 + 5;
vector<int> G[maxn];
ll dp[maxn][2], f[maxn];
int n, mx[maxn][2], a[maxn];void dfs1(int x, int fa) {int mx = -1, id = 0;for (auto &v : G[x]) {if (v == fa)continue;if (a[v] > mx) {mx = a[v];id = v;}}for (auto &v : G[x]) {if (v == fa)continue;dfs1(v, x);}f[x] = f[id] + a[x];
}void getMx(int x, int v) {if (a[v] > mx[x][0]) {mx[x][1] = mx[x][0];mx[x][0] = a[v];} else if (a[v] > mx[x][1]) {mx[x][1] = a[v];}
}void dfs2(int x, int fa) {for (auto &v : G[x]) {if (v == fa && x != 1) {if (a[v] == mx[x][0]) {if (mx[v][0] == a[x]) {dp[x][0] = dp[fa][1] + a[x];} else {dp[x][0] = dp[fa][0] + a[x];}} else if (a[v] == mx[x][1]) {if (a[x] == mx[v][0]) {dp[x][1] = dp[fa][1] + a[x];} else {dp[x][1] = dp[fa][0] + a[x];}}} else {if (a[v] == mx[x][0]) {dp[x][0] = a[x] + f[v];} else if(a[v] == mx[x][1]) {dp[x][1] = a[x] + f[v];}}}for (auto & v: G[x]) {if (v == fa) continue;dfs2(v, x);}
}int main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 2; i <= n; ++i) {int x;cin >> x;G[i].emplace_back(x);G[x].emplace_back(i);}for (int i = 1; i <= n; ++i) {cin >> a[i];}for (int i = 1; i <= n; ++i) {mx[i][0] = mx[i][1] = -1;dp[i][0] = dp[i][1] = a[i];}for (int i = 1; i <= n; ++i) {for (auto v : G[i]) {getMx(i, v);}}dfs1(1, 0);for (int i = 1; i <= n; ++i) {if (a[i] == mx[1][0]) {dp[1][0] = f[i] + a[1];} else if(a[i] == mx[1][1]) {dp[1][1] = f[i] + a[1];}}dfs2(1, 0);ll ans = 0;int id = 0;for (int i = 1; i <= n; ++i) {ans = max(ans, dp[i][0]);}for (int i = 1; i <= n; ++i) {if (dp[i][0] == ans) {id = i;break;}}cout << id << "\n" << ans;return 0;
}

M.拉格朗日插值

原题套皮，怎么大四还要推拉格朗日乘数法啊，队友正好在考研让他给了公式，然后自己推了一下，推完后最大值是$k^{(-k/2)}$， 考虑剩下的子问题就是个傻逼题，2020年澳门$A$题也出过, 构造生成函数$F(x)={\prod }_{i=1}^m(1+b_{i}x)$, 做分治$fft$即可，答案即是第$k$项的系数，最终答案是$k^{-k/2}F(x)[k]\ast inv(C(m,k))$

#include<bits/stdc++.h>using namespace std;
using ll = long long;
const int mod = 998244353, G = 3;
const int maxn = 1e5 + 5;int b[maxn];int mul(int x, int y) {return (ll) x * y % mod;
}int Add(int x, int y) {x += y;if (x >= mod)x -= mod;return x;
}int Sub(int x, int y) {x -= y;if (x < 0)x += mod;return x;
}int mypow(int a, int b) {int ans = 1;while (b) {if (b & 1)ans = mul(ans, a);a = mul(a, a);b >>= 1;}return ans;
}namespace Poly
{typedef vector<int> poly;poly roots, rev;void getRevRoot(int base) {int lim = 1 << base;if ((int)roots.size() == lim)return;roots.resize(lim);rev.resize(lim);for (int i = 1; i < lim; ++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (base - 1));for (int mid = 1; mid < lim; mid <<= 1) {int wn = mypow(G, (mod - 1) / (mid << 1));roots[mid] = 1;for (int i = 1; i < mid; ++i)roots[mid + i] = mul(roots[mid + i - 1], wn);}}void ntt(poly &a, int base) {int lim = 1 << base;for (int i = 0; i < lim; ++i) {if (i < rev[i])swap(a[i], a[rev[i]]);}for (int mid = 1; mid < lim; mid <<= 1) {for (int i = 0; i < lim; i += (mid << 1)) {for (int j = 0; j < mid; ++j) {int x = a[i + j], y = mul(a[i + j + mid], roots[j + mid]);a[i + j] = Add(x, y);a[i + j + mid] = Sub(x, y);}}}}poly operator*(poly a, poly b) {int lim = (int)a.size() + (int)b.size() - 1, base = 0;while ((1 << base) < lim)++base;a.resize(1 << base);b.resize(1 << base);getRevRoot(base);ntt(a, base);ntt(b, base);for (int i = 0; i < (1 << base); ++i)a[i] = mul(a[i], b[i]);ntt(a, base);reverse(a.begin() + 1, a.end());a.resize(lim);int inv = mypow(1 << base, mod - 2);for (int i = 0; i < lim; ++i)a[i] = mul(a[i], inv);return a;}poly solve(int l, int r) {if (l == r) {return {1, b[l]};}int mid = l + r >> 1;return solve(l, mid) * solve(mid + 1, r);}
} // namespace nameint fac[maxn], facinv[maxn];void init() {fac[1] = fac[0] = 1;for (int i = 2; i < maxn; ++i)fac[i] = (ll) fac[i - 1] * i % mod;facinv[maxn - 1] = mypow(fac[maxn - 1], mod - 2);for (int i = maxn - 2; i >= 0; --i)facinv[i] = (ll)facinv[i + 1] * (i + 1) % mod;
}   int C(int n, int m) {return (ll)fac[n] * facinv[n - m] % mod * facinv[m] % mod;
}int main() {init();int n, k;cin >> n >> k;for  (int i = 1; i <= n; ++i) {cin >> b[i];}auto it = Poly::solve(1, n);cout << (ll)(mypow(mypow(k, k / 2), mod - 2)) * it[k] % mod * mypow(C(n, k), mod - 2) % mod;return 0;
}

感觉GDCPC还是一贯的套路题巨多，机时还是很紧缺的。