周一打了牛客
发现自己不知不觉连肝了16天了
最近几天有感觉到有点疲惫了
好好休息一下
周五
回家休息了几天，恢复了很多
今天补补训练赛的题目
Gig Combinatorics（手推公式）
手推一下公式即可
可以发现，每次多一个2，就相当于乘2并加上1的个数
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int mod = 1e9 + 7;
const int N = 1e6 + 10;
int a[N], n, cnt, cur, ans;int add(int a, int b) { return (a + b) % mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }int main()
{scanf("%d", &n);_for(i, 1, n){int x; scanf("%d", &x);if(x == 1) cnt++;if(x == 2) cur = add(mul(cur, 2), cnt);if(x == 3) ans = add(ans, cur);}printf("%d\n", ans);return 0;
}
Coin Stacks（贪心）
这道题就是一个贪心的思想
想想什么时候不行，一定是最后剩下一堆，其他都空了
为了尽可能避免这种情况，就要尽可能平均
所以就每次选最大的两堆来取，实现尽可能平均
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
struct node
{int val, id;
}a[N];
int n, sum, mx;bool cmp(node a, node b)
{return a.val > b.val;
}int main()
{scanf("%d", &n);_for(i, 1, n){int x; scanf("%d", &x);a[i] = node{x, i};sum += x;mx = max(mx, x);}if(sum % 2 == 1 || sum - mx < mx){puts("no");return 0;}puts("yes");_for(i, 1, sum / 2){sort(a + 1, a + n + 1, cmp);printf("%d %d\n", a[1].id, a[2].id);a[1].val--;a[2].val--;}return 0;
}
Defend Your Country（tarjan求割点）
这道题首先要推出一个结论，就是如果是奇数的话那就删掉一个点就好了
可以删的点包括非割点，或者是割点而剩下每个联通分量的点数均是偶数的
所以就是用tarjan来写
要在模板上改一改，这就要求能回忆起tarjan的原理了
在能确定是割点的时候意味着删掉此点会多出一个联通分量，这个时候统计。否则这个联通分量就是和上面的连在一起
tarjan就是维护一个low数组，然后根据low[v] >= dfn[u]来判断割点
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 1e6 + 10;
int dfn[N], low[N], siz[N], a[N];
int n, m, cnt, mi, root;
vector<int> g[N];
ll ans;void dfs(int u, int fa)
{dfn[u] = low[u] = ++cnt;siz[u] = 1;int son = 0, cut = 0, tag = 0;for(int v: g[u]){if(v == fa) continue;if(!dfn[v]){dfs(v, u);siz[u] += siz[v];low[u] = min(low[u], low[v]);if(u == root && ++son > 1 || u != root && low[v] >= dfn[u]){cut = 1;if(siz[v] & 1) tag = 1;}}else low[u] = min(low[u], dfn[v]);}if(!cut || !tag) mi = min(mi, a[u]);
}int main()
{int T; scanf("%d", &T);while(T--){ans = cnt = 0;scanf("%d%d", &n, &m);_for(i, 1, n){scanf("%d", &a[i]);ans += a[i];g[i].clear();dfn[i] = low[i] = 0;}while(m--){int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}if(n % 2 == 0) printf("%lld\n", ans);else{mi = 1e9;dfs(root = 1, 0);printf("%lld\n", ans - 2 * mi);}}return 0;
}
P5490 【模板】扫描线
有一道题有关扫描线的
我忘了好多了，复习一下
注意这里的线段树就是维护区间覆盖的长度
而cnt数组是不传递的，传的是sum数组
注意线段树里面一个节点维护的是一段区间
#include<bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 1e5 + 10;
struct node
{ll x1, x2, y, c;bool operator < (const node& rhs) const{return y < rhs.y;}
};
vector<node> line;
int X[N << 1], cnt[N << 3], n, m;
ll t[N << 3];void up(int k, int l, int r)
{if(cnt[k]) t[k] = X[r + 1] - X[l];else{if(l == r) t[k] = 0;else t[k] = t[l(k)] + t[r(k)];}
}void add(int k, int l, int r, int L, int R, int c)
{if(L <= l && r <= R){cnt[k] += c;up(k, l, r);return;}int m = l + r >> 1;if(L <= m) add(l(k), l, m, L, R, c);if(R > m) add(r(k), m + 1, r, L, R, c);up(k, l, r);
}int main()
{scanf("%d", &n);_for(i, 1, n){ll x1, x2, y1, y2;scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);X[++m] = x1, X[++m] = x2;line.push_back(node{x1, x2, y1, 1});line.push_back(node{x1, x2, y2, -1});}sort(line.begin(), line.end());sort(X + 1, X + m + 1);m = unique(X + 1, X + m + 1) - X - 1;ll ans = 0;rep(i, 0, line.size() - 1){int x1 = lower_bound(X + 1, X + m + 1, line[i].x1) - X;int x2 = lower_bound(X + 1, X + m + 1, line[i].x2) - X;add(1, 1, m - 1, x1, x2 - 1, line[i].c); //注意这里是x2 - 1ans += t[1] * (line[i + 1].y - line[i].y);}printf("%lld\n", ans);return 0;
}
Delete Edges（论文题）
答案就是输出所有(i + j + k) % n = 0
好几页ppt的证明……
传说中的论文题……
有少部分队AC了，我尝试理解它们的思路
难点在于如何避免删除同一条边
如果删除同一条边，就会是
a b c
a b d
构造一种方式来避免这种情况
如果三个点中任意两个点确定了，就可以确定第三个点，那么就可以避免这种情况
那么(a + b + c) mod n = 0就很巧妙地实现了
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;struct node{ int x, y, z; };
vector<node> ans;
int n;int main()
{scanf("%d", &n);_for(i, 1, n)_for(j, i + 1, n){int k = n - (i + j) % n;if(k == 0) k = n;if(k > j) ans.push_back(node{i, j, k});}printf("%d\n", ans.size());rep(i, 0, ans.size()) printf("%d %d %d\n", ans[i].x, ans[i].y, ans[i].z);return 0;
}
周六
Hopping Rabbit（扫描线）
全部平移到一个矩形里面
然后用扫描线来看是否有空的位置
这里不同的是要转化为格子，而不是线
所以要做一些加1减1的处理
输入的矩形右上角要减一
添加扫描线的时候，上面的线要加1，因为上面的线相当于这个矩形结束的线
然后有一个小技巧，就是把线要排序的那个元素直接开个vector的数组
这样就直接排好序了
当然这样的前提是这个元素很密集
#include<bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e5 + 10;
struct node { int l, r, c; };
vector<node> line[N];
int cnt[N << 3], t[N << 3], n, d;void add(int x1, int y1, int x2, int y2)
{line[y1].push_back(node{x1, x2, 1});line[y2 + 1].push_back(node{x1, x2, -1});
}void up(int k, int l, int r)
{if(cnt[k]) t[k] = r - l + 1;else{if(l == r) t[k] = 0;else t[k] = t[l(k)] + t[r(k)];}
}void modify(int k, int l, int r, int L, int R, int c)
{if(L <= l && r <= R){cnt[k] += c;up(k, l, r);return;}int m = l + r >> 1;if(L <= m) modify(l(k), l, m, L, R, c);if(R > m) modify(r(k), m + 1, r, L, R, c);up(k, l, r);
}int getx(int k, int l, int r)
{if(!t[k]) return l;int m = l + r >> 1;if(t[l(k)] < m - l + 1) return getx(l(k), l, m);else return getx(r(k), m + 1, r);
}int main()
{scanf("%d%d", &n, &d);_for(i, 1, n){int x1, y1, x2, y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);x2--; y2--;if(x2 - x1 + 1 >= d) { x1 = 0; x2 = d - 1; }if(y2 - y1 + 1 >= d) { y1 = 0; y2 = d - 1; }x1 = (x1 % d + d) % d; x2 = (x2 % d + d) % d;y1 = (y1 % d + d) % d; y2 = (y2 % d + d) % d;if(x1 <= x2 && y1 <= y2) add(x1, y1, x2, y2);if(x1 <= x2 && y1 > y2) add(x1, 0, x2, y2), add(x1, y1, x2, d - 1);if(x1 > x2 && y1 <= y2) add(0, y1, x2, y2), add(x1, y1, d - 1, y2);if(x1 > x2 && y1 > y2) add(0, 0, x2, y2), add(0, y1, x2, d - 1), add(x1, 0, d - 1, y2), add(x1, y1, d - 1, d - 1);}_for(i, 0, d - 1){for(auto cur: line[i]) modify(1, 0, d - 1, cur.l, cur.r, cur.c);if(t[1] < d){puts("YES");printf("%d %d\n", getx(1, 0, d - 1), i);return 0;}}puts("NO");return 0;
}
P4281 [AHOI2008]紧急集合 / 聚会（LCA）
这题一直在分类讨论，然后没有结果
然后休息了一下突然发现要跑到的点就是三个两两lca中，有两个相同，一个不同，就是要跑到不同的那个lca
我试了好几种情况都符合
然后就开写了，用树上倍增，然后T了
加了速度才卡过去
然后用树剖写，果然常数小，过了
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 5e5 + 10;
int d[N], fa[N], siz[N], son[N], top[N], n, m;
vector<int> g[N];void dfs1(int u, int father)
{d[u] = d[father] + 1;fa[u] = father;siz[u] = 1;for(int v: g[u]){if(v == father) continue;dfs1(v, u);siz[u] += siz[v];if(siz[son[u]] < siz[v]) son[u] = v;}
}void dfs2(int u, int t)
{top[u] = t;if(siz[u] == 1) return;dfs2(son[u], t);for(int v: g[u]){if(v == fa[u] || v == son[u]) continue;dfs2(v, v);}
}int lca(int u, int v)
{while(top[u] != top[v]){if(d[top[u]] < d[top[v]]) swap(u, v);u = fa[top[u]];}return d[u] > d[v] ? v : u;
}int dis(int u, int v)
{return d[u] + d[v] - 2 * d[lca(u, v)];
}int main()
{scanf("%d%d", &n, &m);_for(i, 1, n - 1){int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}dfs1(1, 0);dfs2(1, 1);while(m--){int a, b, c, lc;scanf("%d%d%d", &a, &b, &c);int t1 = lca(a, b), t2 = lca(b, c), t3 = lca(a, c);if(t1 == t2) lc = t3;else if(t1 == t3) lc = t2;else lc = t1;printf("%d %d\n", lc, dis(a, lc) + dis(b, lc) + dis(c, lc));}return 0;
}树的直径
第二种写法
把当前节点作为路径的中间节点
维护当前点到子树节点的最长路和次长路
两者加起来就是这颗子树内部的直径
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e5 + 10;
int d1[N], d2[N], ans, n;
vector<int> g[N];void dfs(int u, int fa)
{for(int v: g[u]){if(v == fa) continue;dfs(v, u);int t = d1[v] + 1;if(t > d1[u]) d2[u] = d1[u], d1[u] = t;else if(t > d2[u]) d2[u] = t;ans = max(ans, d1[u] + d2[u]);}
}int main()
{scanf("%d", &n);_for(i, 1, n - 1){int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}dfs(1, 0);printf("%d\n", ans);return 0;
}
xay loves count（枚举顺序）
这道题的关键在于不是枚举每一个数，而是枚举具体的值
在比较密集的时候可以这么写，也就是ai的值范围比较小的时候
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 1e6 + 10;
int cnt[N], n;int main()
{scanf("%d", &n);_for(i, 1, n){int x; scanf("%d", &x);cnt[x]++;}ll ans = 0;_for(i, 1, 1e6)for(int j = 1; i * j <= 1e6; j++)ans += 1LL * cnt[i] * cnt[j] * cnt[i * j];printf("%lld\n", ans);return 0;
}
周日
xay loves trees（dfs序 + 主席树区间修改）
这题搞了很久，也收获很多
首先是一个转化，把第二颗树的祖先儿子的关系转化为dfs序的区间
这个区间有一个特点
如果有祖孙的关系的话两个区间是包含的，也就是说有交集的
否则就没有交集
那么看第一棵树，对于一个节点，它与它的祖孙最多有多少个不为祖孙的节点
其实就是看从这个节点往上最多有多少个没有交集的区间
也就是找到与当前这个区间第一个有交集的区间
第一个意味着最近，可以转化为深度最深，因此可以把区间都赋值为深度
所以就是找当前区间的深度最大值，就是第一个有交集的区间
那么这只是对于当前这个点而言，如果一条链要作为答案的话，任意两点都不能为祖孙关系
那么处理出每一个点的最近相交的点，设为hu
那么以u为深度最深的点的答案就是可以扩展到u到根节点的hu的最大值
那么要实现维护区间最大值，这里用到了可以区间修改的主席树
我还是第一次写可以区间修改的主席树，之前都是单点修改的
其实不写错的关键还是理解本质，理解主席树无非就是每次一个新版本的树，就新建一个节点，然后复制前一个树的节点的信息，然后拓展新的信息
细节写在注释里面
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 3e5 + 10;
int ls[N << 6], rs[N << 6], t[N << 6], lazy[N << 6], root[N]; //以后写主席树一定左移6
int L[N], R[N], n, ans, cnt;
vector<int> g1[N], g2[N];void up(int k) { t[k] = max(t[ls[k]], t[rs[k]]); }void update(int& k, int x)
{if(!k) { k = ++cnt; ls[k] = rs[k] = 0; } //down的时候可能是已经存在的节点，可能是新节点，小心t[k] = lazy[k] = max(t[k], x);
}void down(int k)
{if(lazy[k]){update(ls[k], lazy[k]);update(rs[k], lazy[k]);lazy[k] = 0;}
}void add(int& k, int pre, int l, int r, int L, int R, int x)
{k = ++cnt; //add的时候不要写!k 其复制了前一个的值 直接++cntt[k] = t[pre]; ls[k] = ls[pre]; rs[k] = rs[pre]; lazy[k] = lazy[pre]; //先创造新节点，然后复制值if(L <= l && r <= R){t[k] = lazy[k] = max(t[k], x);ls[k] = rs[k] = 0; //非常重要。这时不要再左右儿子连到上一课树了。不加会错return;}down(pre); //向下搜的时候,pre要downint m = l + r >> 1;if(L <= m) add(ls[k], ls[pre], l, m, L, R, x);if(R > m) add(rs[k], rs[pre], m + 1, r, L, R, x);up(k);
}int query(int k, int l, int r, int L, int R)
{if(!k) return 0; //可能有空节点，小心if(L <= l && r <= R) return t[k];down(k); //询问的时候要downint m = l + r >> 1, res = 0;if(L <= m) res = max(res, query(ls[k], l, m, L, R));if(R > m) res = max(res, query(rs[k], m + 1, r, L, R));return res;
}void dfs(int u, int fa, int mx, int dep)
{mx = max(mx, query(root[fa], 1, n, L[u], R[u]));ans = max(ans, dep - mx);add(root[u], root[fa], 1, n, L[u], R[u], dep);for(int v: g1[u]){if(v == fa) continue;dfs(v, u, mx, dep + 1);}
}void dfs2(int u, int fa)
{L[u] = ++cnt;for(int v: g2[u]){if(v == fa) continue;dfs2(v, u);}R[u] = cnt;
}int main()
{int T; scanf("%d", &T);while(T--){scanf("%d", &n);_for(i, 1, n) g1[i].clear(), g2[i].clear(), root[i] = 0;_for(i, 1, n - 1){int u, v;scanf("%d%d", &u, &v);g1[u].push_back(v);g1[v].push_back(u);}_for(i, 1, n - 1){int u, v;scanf("%d%d", &u, &v);g2[u].push_back(v);g2[v].push_back(u);}cnt = 0;dfs2(1, 0);cnt = ans = 0;dfs(1, 0, 0, 1);printf("%d\n", ans);_for(i, 1, cnt) ls[i] = rs[i] = t[i] = lazy[i] = 0; //结尾的时候清空}return 0;
}
P3293 [SCOI2016]美味（异或 + 主席树）
首先看到异或，可以考虑一位一位处理
求异或最大值，那就高位往低位贪心
对于b ^ (ai + x)
当前b的第i位如果是1，那么ai + x这一位是0
那么我们可以倒推出ai的范围
ai + x 应该为 00000……到01111……
满足第i位为0
也就是0到（1 << i） - 1
倒推出ai的范围为[-x, -x + (1 << i) - 1]
那么其实就判断这个范围内有没有数就行了，可以用主席树来维护
但是这还有一个问题，就是接下来怎么处理
我们要维护一个ans，表示最优的ai + x
按照贪心把一位一位确定以后，每一次应当是
ai + x - ans 属于某个范围
因为前面的位已经确定了，就要先减去
这里有点绕，也是这道题的难点
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 2e5 + 10;
int t[N << 6], ls[N << 6], rs[N << 6], root[N];
int n, m, cnt;void add(int& k, int pre, int l, int r, int x)
{k = ++cnt;ls[k] = ls[pre]; rs[k] = rs[pre]; t[k] = t[pre] + 1;if(l == r) return;int m = l + r >> 1;if(x <= m) add(ls[k], ls[pre], l, m, x);else add(rs[k], rs[pre], m + 1, r, x);
}int query(int k, int pre, int l, int r, int L, int R)
{if(t[k] == t[pre]) return 0; //注意空节点就return if(L <= l && r <= R) return t[k] - t[pre];int m = l + r >> 1, res = 0;if(L <= m) res += query(ls[k], ls[pre], l, m, L, R);if(R > m) res += query(rs[k], rs[pre], m + 1, r, L, R);return res;
}int main()
{scanf("%d%d", &n, &m);_for(i, 1, n){int x; scanf("%d", &x);add(root[i], root[i - 1], 0, 1e5, x);}while(m--){int b, x, l, r, ans = 0;scanf("%d%d%d%d", &b, &x, &l, &r);for(int i = 17; i >= 0; i--){if(b & (1 << i) && !query(root[r], root[l - 1], 0, 1e5, ans - x, ans - x + (1 << i) - 1)) ans |= 1 << i;if(!(b & (1 << i)) && query(root[r], root[l - 1], 0, 1e5, ans - x + (1 << i), ans - x + (1 << i + 1) - 1)) ans |= 1 << i;}printf("%d\n", b ^ ans);}return 0;
}