1124考试总结
T1
题目大意 :
n 点 m 边无向图，每点度数至多为 3，边容量为 1，求任意两点间最大流之和。\(n <= 3000, m <= 4500\)
Tarjan求边双 + 并查集 + 哈希.
首先可以想到是不可以任选两个点然后跑一边网络流的, 那么我们发现每个点的度数很小, 我们可以考虑从度数入手.
我们知道最大流等于最小割, 因为一个点的度数最多为3, 那么任意两点之间的最大流肯定是小于等于3的.
当两个点的最大流是1时 : 两个点联通就行了.
当两个点的最大流是2时 : 两个点一定在一个边双联通分量里, 也就是两点之间不能有割边.
当两个点的最大流是3时 : 任意删除一条边, 这两个点都在一个边双联通分量里.
我们对这三种情况分开算就好啦, 维护联通性可以用并查集, 求边双直接用nb的Tarjan. 这里要注意一点 : 判断任意删除一条边之后两个点是否都在一个边双连通分量里可以用哈希优化, 从\(O(m)\)优化到\(O(1)\).
枚举任意两点是\(O(n^2)\)的, 任意删除一条边, 每次都跑一边Tarjan是\(O(m(n + m))\)的, 所以总复杂度是\(O(n ^ 2 + m(n + m))\).还有这题要卡卡常.
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 3005, M = 4505;
int n, m, d, cnt, tot, top, css, ban;
long long ans;
int fa[N], id[M << 1], siz[N], sta[N], col[N], deg[N], dfn[N], low[N], head[N], ha[N][3], base[3] = {1000000007, 998244353, 233333};
struct edge { int to, nxt; } e[M << 2];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
inline void merge(int x, int y) {
int fx = find(x), fy = find(y);
if(fx == fy) return ;
if(siz[fx] > siz[fy]) swap(fx, fy);
fa[fx] = fy; siz[fy] += siz[fx];
}
inline void add(int x, int y, int i) { e[++ cnt].nxt = head[x]; head[x] = cnt; e[cnt].to = y; id[cnt] = i; }
inline void clear() {
for(int i = 1;i <= n; i++) col[i] = dfn[i] = 0; tot = css = 0;
}
void Tarjan(int x, int Fa) {
dfn[x] = low[x] = ++ tot; sta[++ top] = x;
for(register int i = head[x]; i ; i = e[i].nxt) {
if(id[i] == ban || id[i ^ 1] == ban) continue;
int y = e[i].to;
if(!dfn[y]) Tarjan(y, x), low[x] = min(low[x], low[y]);
else if(y != Fa) low[x] = min(low[x], dfn[y]);
}
if(low[x] == dfn[x]) {
int p; css ++;
do {
p = sta[top --]; col[p] = css;
} while(p != x);
}
}
int main() {
n = read(); m = read(); d = read(); cnt = 1;
for(register int i = 1;i <= n; i++) fa[i] = i, siz[i] = 1;
for(register int i = 1, x, y;i <= m; i++) {
x = read(), y = read(); add(x, y, i << 1); add(y, x, i << 1); merge(x, y);
}
for(register int i = 1;i <= n; i++) if(fa[i] == i) ans += 1ll * siz[i] * (siz[i] - 1) / 2;
for(register int i = 1;i <= n; i++) if(!dfn[i]) Tarjan(i, 0);
for(register int i = 1;i <= n; i++)
for(register int j = i + 1;j <= n; j++) if(col[i] == col[j]) ans ++;
for(register int i = 1;i <= m; i++) {
ban = i << 1; clear();
for(register int j = 1;j <= n; j++) if(!dfn[j]) Tarjan(j, 0);
for(register int j = 1;j <= n; j++)
for(register int k = 0;k < 2; k++) (ha[j][k] *= base[k]) += col[j];
}
for(register int i = 1;i <= n; i++)
for(register int j = i + 1;j <= n; j++)
if(ha[i][0] == ha[j][0] && ha[i][1] == ha[j][1]) ans ++;
printf("%lld", ans);
fclose(stdin); fclose(stdout);
return 0;
}
T2
题目大意:
EndSaH 有 n 个数 \(a_1\)...n ，他打算选出这些数中的两个数进行拼接。一次拼数操作指的是将 x,y 两个正整数视作数字串，x 在前 y 在后拼接成一个新数字串，该新数字串所表示的正整数即这次拼数操作的结果。例如将 1234 与 56 拼数，将得到结果 123456。注意拼数操作是有顺序的，如拼接 56 与 1234 会得到561234。
但不知道为什么，EndSaH 一点也不喜欢 k 的倍数。他很好奇一个问题：有多少数对 (i,j)(1 ≤ i,j ≤ n,i ̸= j) 满足对 a i 与 a j 进行拼数操作后，结果不是 k 的倍数？
\(n <= 1e5, k, a_i <= 1e9\)
挺简单的一道题, 考场上竟然没有想出来mdzz.
利用单步容斥的思想, 用总的方案数减去是\(k\)的倍数的方案数.
我们将\(x, y\)两个数拼起可以得到 \(x * 10^{log \ y} + y\), 设\(mod = x * 10^{log \ y} \% k\), 要使拼起来的数字是\(k\)的倍数, 那么\(y\)应该满足的条件是:
当\(mod = 0\)时, \(y \% k = 0\);
当\(mod != 0\)时, \(y\%k = k - mod\).
然后我们用map存一个数组\(mp\), \(mp[i][j]\)表示\(log \ y\)为\(i\), \(mod\)为\(j\)的方案数, 在输入的时候就可以统计了.再然后枚举\(y\)就好了.
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 1e5 + 5;
int n, k, l;
long long ans;
int a[N], len[N];
map <int, int> mp[11];
inline calc_l(int x) {
int res = 0;
while(x) { res ++; x /= 10; }
return res;
}
int main() {
n = read(); k = read();
for(int i = 1;i <= n; i++) a[i] = read(), l = max(l, len[i] = calc_l(a[i]));
for(register int i = 1;i <= n; i++) {
int tmp = a[i];
for(register int j = 1;j <= l; j++) {
tmp = 1ll * tmp * 10 % k; mp[j][tmp] ++;
}
}
for(register int i = 1;i <= n; i++) {
int tmp = a[i];
for(int j = 1;j <= len[i]; j++) tmp = 1ll * tmp * 10 % k;
mp[len[i]][tmp] --; //注意要除去自己
if(a[i] % k) ans += mp[len[i]][k - a[i] % k];
else ans += mp[len[i]][0];
mp[len[i]][tmp] ++;
}
printf("%lld", 1ll * n * (n - 1) - ans);
return 0;
}
T3
题目大意:
细雨迷蒙中，Tea 在路上散步。忽而，一棵参天大树出现在眼前。细数一下，可以数出这棵树上有 n 个节点。便于描述，我们给每个节点编号，其中 1 号节点为根节点。Tea 突然想施展自己多年没有释放过的低阶法术——火花术，并想尝试着烧掉这棵树。若是正常情况，火势会迅速蔓延，将整棵树化作焦炭。但现在，他发现了两件有趣的事情：
- 刚下了雨，树枝有些湿润。Tea 定义了每根树枝的湿润度 w，是因为他发现如果他这次用于火花术的法力值小于 w，那么火花就无法点燃这根树枝；否则，火就从当前节点可以蔓延到这根树枝所指向的那个节点上，并烧掉这根树枝。
- 无论走到哪里，强者总会散发出气场。由于 Tea 现在站在树下，强大的气场风让火无法向根而只能向上蔓延。
若是燃烧掉了一条树枝，Tea 将会获得与其湿润度相等的成就感。现在，Tea 想问你，若是他用 k 的法力值对节点 u 释放火花术，他得到的成就感是多少。
\(n, q <= 1e5\), 强制在线.
dfs序 + 主席树.
主席树就是可持久化线段树. 我们发现对于每次询问, 我们需要找到\(w <= k\)的那些边. 于是我们可以想到把所有的\(w <= k\)的那些边建成一颗线段树, 然后利用dfs序可以把求一颗子树内的东西转化成区间问题. 对于\(w <= k + 1\)的那些边也是建一颗线段树, 我们会发现这就是可持久化线段树呀.
具体的实现过程看代码把.
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define int long long
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 3e5 + 5, mod = 1048576;
int n, m, T, ID, cnt;
int fa[N], siz[N], dfn[N], head[N], root[N], father[N]; // root[i]代表w <= i的那些边所构成的线段树
long long las, sum[N];
struct edge {
int to, nxt, val, from;
edge() {} edge(int z) { val = z; }
friend int operator < (const edge &a, const edge &b) { return a.val < b.val; }
} b[N], e[N];
struct tree { int ls, rs; long long sum; } t[N * 30];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void add(int x, int y) {
e[++ cnt].nxt = head[x]; head[x] = cnt; e[cnt].to = y;
}
void get_tree(int x) { //搞出dfs序和子树大小, 这样可以转化成区间问题
dfn[x] = ++ cnt; siz[x] = 1;
for(int i = head[x]; i ; i = e[i].nxt) {
int y = e[i].to; get_tree(y); siz[x] += siz[y];
}
}
void change(int &k, int p, int l, int r, int x, int val) { //主席树区间求和
k = ++ cnt;
t[k] = t[p]; t[k].sum += val;
if(l == r) return ;
if(x <= mid) change(t[k].ls, t[p].ls, l, mid, x, val);
if(x > mid) change(t[k].rs, t[p].rs, mid + 1, r, x, val);
}
long long query(int k, int l, int r, int x, int y) {
if(x <= l && y >= r) return t[k].sum;
long long res = 0;
if(x <= mid) res += query(t[k].ls, l, mid, x, y);
if(y > mid) res += query(t[k].rs, mid + 1, r, x, y);
return res;
}
int main() {
ID = read(); n = read(); T = read();
for(int i = 1;i <= n; i++) fa[i] = i;
for(int i = 2;i <= n; i++) {
father[i] = read();
b[i - 1].from = father[i]; b[i - 1].to = i; b[i - 1].val = read();
add(father[i], i);
}
cnt = 0; get_tree(1);
sort(b + 1, b + n); cnt = 0;
for(int i = 1, x, y, fx, fy;i < n; i++) {
x = b[i].from, y = b[i].to;
fx = find(x), fy = find(y); sum[fy] += b[i].val; //每次加入一条新边(x,y), sum表示这个联通块内的w值的总和
change(root[i], root[i - 1], 1, n, dfn[x], sum[fy]);
if(fx != 1) change(root[i], root[i], 1, n, dfn[father[fx]], -sum[fy]);
// 差分一下, 当前不完全的树上能追溯到的最早祖先的子树和全部加上当前 y 的子树和。(题解原话)
sum[fx] += sum[fy]; fa[fy] = fx;
}
m = read();
for(int i = 1, u, k, t;i <= m; i++) {
u = read(); k = read();
if(T) (u ^= las) %= mod, (k ^= las) %= mod;
t = upper_bound(b + 1, b + n, edge{k}) - b - 1; //找到需要回溯到的位置, 也就是找到w <= k的那些边的线段树
las = query(root[t], 1, n, dfn[u], dfn[u] + siz[u] - 1);
printf("%lld\n", las); las %= mod;
}
return 0;
}
T4
题目大意 :
给定一段长度为\(n\)的序列, 求最长不下降子序列的长度. \(n <= 1e12\).
给出序列的生成方式: \((A × a_{n−1}^2 + B × a_{n−1} + C) mod D, n >= 2\), \(a_1, A, B, C, D\)会给出.\(1 <= D <= 150\)
乱搞.
一看这数据范围, woc毒瘤啊, 输入都输入不完, 肯定是乱搞.
打表发现, 会出现循环节.
或者用抽屉原理解释, \(a_i\)最大就是149(因为D的限制), 那么当第150个数出现时, 一定会更前面的某个数重复, 然后就会出现循环节了.
设循环节长度为\(len\), 开始循环的位置是\(wei\).
我们可以暴力处理出\(wei + 100 * len\)的部分, 然后对于中间的那些循环节, 每个循环节的贡献是1, 然后在暴力处理剩下的那一部分就好了.暴力处理指的是求最长不下降子序列, 可以用树状数组优化一下,
那么为什么要处理\(wei + 100 * len\)这些部分呢?因为在一开始的那些循环节里, 每个循环节的贡献可能不是1, 到后面才会是1, 举个例子:
比如循环节为23, 10, 11, 8, 9, 30, 按照上面的方法, 第一个循环节会找到30, 然后后面每个循环节都是1.但是正确的方法应该是直接选9, 然后后面选10, 11, 再后面一直选11, 最后一个循环节还能多选个30, 后者明显更优.
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 1e6 + 5;
int n, A, B, C, D, ans, wei, len;
int a[N], t[N], f[N], vis[N], last[N];
int lowbit(int x) { return x & -x; }
int query(int x) {
int res = 0; for( ; x ; x -= lowbit(x)) res = max(res, t[x]); return res;
}
void change(int x, int y) {
for(; x < N; x += lowbit(x)) t[x] = max(y, t[x]);
}
signed main() {
n = read(); a[1] = read(); A = read(); B = read(); C = read(); D = read();
vis[a[1]] = 1; last[a[1]] = 1; wei = n;
for(int i = 2;i <= n; i++) {
a[i] = (1ll * A * a[i - 1] % D * a[i - 1] % D + 1ll * B * a[i - 1] % D + C) % D;
if(vis[a[i]]) { wei = i; break; }
vis[a[i]] = 1; last[a[i]] = i;
}
if(wei == n) {
for(int i = 1;i <= n; i++) f[i] = query(a[i] + 1) + 1, change(a[i] + 1, f[i]), ans = max(ans, f[i]);
}
else {
len = wei - last[a[wei]]; wei -= len;
int S = wei - 1 + len * 100;
for(int i = 1;i <= min(S, n); i++) {
if(i > wei) a[i] = (1ll * A * a[i - 1] % D * a[i - 1] % D + 1ll * B * a[i - 1] % D + C) % D;
f[i] = query(a[i] + 1) + 1, change(a[i] + 1, f[i]), ans = max(ans, f[i]);
}
if(S < n) {
int k = n - S; int div = k / len, mod = 0;
if(div != 0) div --, mod = len; mod += k % len;
for(int i = wei + len * 99;i <= S; i++) f[i] += div, change(a[i] + 1, f[i]), ans = max(ans, f[i]);
for(int i = S + 1;i <= S + mod; i++) {
a[i] = (1ll * A * a[i - 1] % D * a[i - 1] % D + 1ll * B * a[i - 1] % D + C) % D;
f[i] = query(a[i] + 1) + 1, change(a[i] + 1, f[i]), ans = max(ans, f[i]);
}
}
}
printf("%lld", ans);
return 0;
}