1201考试总结
T1
题目链接
我tm直接双指针, 水题不硕了.
#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 = 1e6 + 5;
int n, k, cnt, now, ans;
int in[65];
struct node { int p, c; } a[N];
int cmp(node a, node b) {
return a.p < b.p;
}
int main() {
n = read(); k = read();
for(register int i = 1, x;i <= k; i++) {
x = read();
for(register int j = 1;j <= x; j++) a[++ cnt].p = read(), a[cnt].c = i;
}
sort(a + 1, a + n + 1, cmp);
int l = 1; ans = 1e9;
for(register int i = 1;i <= n; i++) {
while(a[l].c == a[i].c && l < i) {
if(now == k) ans = min(ans, a[i - 1].p - a[l].p);
in[a[l].c] --; if(!in[a[l].c]) now --; l ++;
}
if(!in[a[i].c]) now ++; in[a[i].c] ++;
if(now == k) ans = min(ans, a[i].p - a[l].p);
while(in[a[l].c] > 1) {
if(now == k) ans = min(ans, a[i].p - a[l].p);
in[a[l].c] --; l ++;
}
if(now == k) ans = min(ans, a[i].p - a[l].p);
}
printf("%d", ans);
return 0;
}
T2
题目链接
容斥 + 缩索 + 剪枝
首先我们可以预处理出只含有"6, 8"这两个数字的数, 我们把这些数存在\(num\)数组里, 然后容斥求区间\([l,r]\)内这些数的倍数.
直接容斥肯定会T, 考虑剪枝.
如果说\(num_i \% num_j == 0\), 也就是存在倍数关系, 那么\(num_i\)是没用的.
对于\(num_i >= r / 2\)的那些数也是不用容斥的, 直接给答案加上\(r / num_i - (l - 1) / num_i\)就好, 因为这种数字不可能与其他数字的\(lcm\)小于\(r\).
对\(num_i\)数组从大到小排序, 使\(lcm\)更快大于\(r\).
复杂度玄学, 但是跑的飞快.
#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 = 1e6 + 5;
long long a, b, ans, num[N];
int cnt, vis[N];
int cmp(int a, int b) { return a > b; }
void make_num(int now, long long sum) {
if(sum > b) return ;
if(sum != 0) num[++ cnt] = sum;
if(now > 10) return ;
make_num(now + 1, sum * 10 + 6); make_num(now + 1, sum * 10 + 8);
}
void cut() {
int t = 0;
for(register int i = 1;i <= cnt; i++)
if(!vis[i]) {
if(num[i] <= b / 2) num[++ t] = num[i];
else ans += b / num[i] - a / num[i];
for(register int j = i + 1;j <= cnt; j++)
if(!(num[j] % num[i])) vis[j] = 1;
}
cnt = t;
}
void dfs(int now, long long s, int t) {
if(s > b) return ;
if(now == cnt + 1) {
if(s != 1) ans += (b / s - a / s) * ((t & 1) ? 1 : -1);
return ;
}
dfs(now + 1, s, t);
long long tmp = num[now] / __gcd(num[now], s);
if(tmp * s <= b) dfs(now + 1, tmp * s, t + 1);
}
int main() {
a = read(); b = read(); a --;
make_num(1, 0); sort(num + 1, num + cnt + 1); cut();
sort(num + 1, num + cnt + 1, cmp);
dfs(1, 1, 0); printf("%lld", ans);
return 0;
}
T3
题目链接
cdq分治.
话说第一次做cdq分治竟然是在考试. 另一种解法是\(KD-Tree\)但我不会233.
先介绍一下cdq分治, 它的全称应该是基于时间的分治算法, 主要流程是这样的.
把修改操作和查询操作放一起, 按某个标准排序, 然后进行分治:
1.递归计算\(solve(l,mid)\);
2.递归计算\(solve(mid+1, r)\);
3.计算\([l, mid]\)中的修改操作对\([mid + 1, r]\)中查询操作的影响.
那么这道题怎么做呢?
假设只有操作二, 也就是没有修改操作, 我们对于每一个询问\((x, y)\)要求的是 : \(\sum_{i = 1}^n min(\mid x - x_i\mid, \mid y - y_i\mid)\) ;
考虑把绝对值去掉, 那么这个平面上的点可以被\((x,y)\)分成左下, 左上, 右上, 右下四部分.对于左下部分的, 要求的是 : \(min(x - x_i, y - y_i)\) = \(x + y - max(x_i+ y_i)\).
然后我们将这些节点按\(x\)为第一关键字, \(y\)为第二关键字排序, 保证\(x_i <= x\), 然后用树状数组取找那些\(y_i<=y\)的点, 树状数组维护的是\(x_i + y_i\)的最大值.
对于左上, 右上, 右下也是一样的.
然后把修改操作考虑上, 这时候就要用到cdq分治了. 我们把所有的修改和询问和初始节点按\(x\)为第一关键字, \(y\)为第二关键字排序, 然后进行cdq分治, 每次计算\([l, mid]\)中的修改操作对\([mid + 1, r]\)中查询操作的影响的时候, 像上面一样考虑四个部分就好了.
注意每次修改完树状数组后有撤销这些操作, 不然会对后面造成影响, 并且不能够开一个新的树状数组.
#include <bits/stdc++.h>
#define lowbit(x) x & -x
#define mid ((l + r) >> 1)
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, inf = 0x3f3f3f3f;
int n, m;
int t[N], ans[N];
struct node { int x, y, z; } a[N], b[N];
int cmp(node a, node b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
void change(int x, int y) { for(; x < N; x += lowbit(x)) t[x] = max(t[x], y); return ; }
void change_inf(int x) { for(; x < N; x += lowbit(x)) t[x] = -inf; return ; }
int query(int x) { int res = -inf; for(; x ; x -= lowbit(x)) res = max(res, t[x]); return res; }
void calc(int s, int tt, int dx, int dy, int f) {
for(int i = s;i != tt; i += f) {
int y = dy == -1 ? N - b[i].y : b[i].y; // 当dy为-1时, 要查询的下标变成了-yi, 加上1e6转正(其实我也不透彻, 也不知道这么解释对不对)
int tmp = b[i].x * dx + b[i].y * dy;
if(a[b[i].z].z == 1) change(y, tmp);
else ans[b[i].z] = min(ans[b[i].z], abs(tmp - query(y))); //这里要加绝对值是因为query相当于是对称节点, 画个图就明白了
}
for(int i = s;i != tt; i += f) {
int y = dy == -1 ? N - b[i].y : b[i].y;
if(a[b[i].z].z == 1) change_inf(y);
}
}
void cdq(int l, int r) {
if(l < mid) cdq(l, mid); if(mid + 1 < r) cdq(mid + 1, r);
int t = 0;
for(int i = l;i <= r; i++) if(i <= mid && a[i].z == 1 || i > mid && a[i].z == 2) b[++ t] = a[i], b[t].z = i;
sort(b + 1, b + t + 1, cmp);
calc(1, t + 1, 1, 1, 1); calc(1, t + 1, 1, -1, 1);
calc(t, 0, -1, -1, -1); calc(t, 0, -1, 1, -1);
}
int main() {
n = read(); m = read();
for(int i = 1;i <= n; i++) a[i].x = read(), a[i].y = read() + 1, a[i].z = 1;
for(int i = 1;i <= m; i++) a[i + n].z = read(), a[i + n].x = read(), a[i + n].y = read() + 1;
n += m; memset(ans, 0x3f, sizeof(ans)); memset(t, 0xcf, sizeof(t));
cdq(1, n);
for(int i = 1;i <= n; i++) if(a[i].z == 2) printf("%d\n", ans[i]);
return 0;
}
T4
题目链接
树形DP找直径 + 单调队列优化 + 基环树.
这个题可把我恶心坏了, 口区
首先转化题意 : 给定一张基环树森林, 让你求出所有基环树的直经之和. 为啥转化成这样了呢? 首先\(n\)个点\(n\)条边, 并且每一个点都会有一条出边, 所以它是一张基环树森林.
看题目中这句话 : "渡船：你可以选择这种方法，仅当没有任何桥和以前使用过的渡船的组合可以由 S 走到 D (当检查是否可到达时，你应该考虑所有的路径，包括经过你曾游览过的那些岛)。"这话啥意思呢?这句话的意思就是, 你从一个联通块里出来, 就不可以在回去了, 这是因为从\(S\)渡船到\(D\), 这条路本来就是通过一些桥和渡船, 所以从D到S走这条路也可以. 也就是说你要在每个联通块内找一条最长的路径, 那肯定就是直径了.
如何找一颗基环树的直径呢?我们可以把那个环提出来, 然后枚举环上的每个点, 这个直径可能是每个节点的子树内的直径, 也可能是\(dis(i,j) + d_i + d_j\).\(dis(i,j)\)是环上两点距离, \(d_x\)是\(x\)这棵子树内的最长链.
对于第一种情况, 直接树形DP求最长链和直径就好了.对于第二种情况, 我们需要断环成链, 变成原来环的2倍.但是不可直接枚举\(i, j\) , 可以尝试用单调队列优化, 上面式子可以用前缀和表示为 : \(s_i - s_j + d_i + d_j = d_i + s_i + (d_j - s_j)\), 然后我们用单调队列维护一个\(d-s\)的最大值就好了.
#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 = 1e6 + 5;
int n, st, cnt;
long long ans, ans1, ans2, s[N], dep[N], Dep[N];
int v[N], q[N], id[N], head[N];
bool vis[N];
struct edge { int to, nxt, val; } e[N << 1];
void add(int x, int y, int z) {
e[++ cnt].nxt = head[x];
head[x] = cnt;
e[cnt].to = y;
e[cnt].val = z;
}
int dfs(int x, int fa) {
if(v[x]) {
v[x] = 2; id[++ cnt] = x; vis[x] = 1; return 1;
}
v[x] = 1;
for(int i = head[x]; i ; i = e[i].nxt) {
int y = e[i].to; if(i == ((fa - 1) ^ 1) + 1) continue ;
if(dfs(y, i)) {
if(v[x] == 2) { s[st - 1] = s[st] - e[i].val; return 0; }
if(v[x] == 1) { ++ cnt; s[cnt] = s[cnt - 1] + e[i].val; vis[x] = 1; id[cnt] = x; }
return 1;
}
}
return 0;
}
void get_dep(int x) {
vis[x] = 1;
for(int i = head[x]; i ; i = e[i].nxt) {
int y = e[i].to; if(vis[y]) continue ;
get_dep(y);
ans1 = max(ans1, dep[x] + e[i].val + dep[y]);
dep[x] = max(dep[x], dep[y] + e[i].val);
}
}
long long work(int u) {
st = cnt + 1; ans1 = ans2 = 0;
dfs(u, 0);
for(register int i = st;i <= cnt; i++) {
get_dep(id[i]);
Dep[i] = Dep[cnt + i - st + 1] = dep[id[i]];
s[cnt + i - st + 1] = s[cnt + i - st] + s[i] - s[i - 1];
}
int l = 1, r = 0;
for(register int i = st;i <= 2 * cnt - st + 1; i++) {
while(l <= r && q[l] <= i - cnt + st - 1) l ++;
if(l <= r) ans2 = max(ans2, Dep[i] + s[i] + Dep[q[l]] - s[q[l]]);
while(l <= r && Dep[q[r]] - s[q[r]] <= Dep[i] - s[i]) r --;
q[++ r] = i;
}
return max(ans1, ans2);
}
int main() {
n = read();
for(register int i = 1, y, z;i <= n; i++) {
y = read(), z = read(), add(i, y, z), add(y, i, z);
}
cnt = 0;
for(register int i = 1;i <= n; i++) if(!vis[i]) ans += work(i);
printf("%lld\n", ans);
return 0;
}