[POI2008]BLO
一眼可以了解到是一道割点题。对于不是割点的情况，那么被计算的点对一定包含此点本身，又因为有序，所以贡献就是\(2(n – 1)\)。如果是割点的话，就比较麻烦，分下面几个来算：
- 此点延伸出去的点对。
- 连通块之间的点对。
- 本身就无法互通的点对。
第一个很好算，是\(2(n – 1)\)。第二个，在 Tarjan 枚举搜索子树的时候计算子树大小和全图补集的乘积（注意，这里会多计算一遍与点\(u\)的点对，所以我们第一个改成算\(n – 1\)）；第三个，算「当前整颗搜索树与图的补集大小」与「搜索树的大小」的乘积。
综合起来就是，对于点\(u\)：
\[ ans_u = \sum_{k \in son(u)} (n – size(k)) \times size(k) + (n – 1) + (n – 1 – \sum_{k \in son(u)} size(k)) \times (1 + \sum_{k \in son(u)} size(k)) \]
// BZ1123.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 100010, MAX_M = 500010;
struct edge
{
int to, nxt;
} edges[MAX_M << 1];
int head[MAX_N], current, n, m, dfn[MAX_N], low[MAX_N], ptot, siz[MAX_N], root;
ll ans[MAX_N];
bool cut[MAX_N];
void addpath(int src, int dst)
{
edges[current].to = dst, edges[current].nxt = head[src];
head[src] = current++;
}
void tarjan(int u)
{
ll flag = 0, sum = 0;
dfn[u] = low[u] = ++ptot, siz[u] = 1;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (dfn[edges[i].to] == 0)
{
tarjan(edges[i].to), low[u] = min(low[edges[i].to], low[u]);
siz[u] += siz[edges[i].to];
if (low[edges[i].to] >= dfn[u])
{
flag++;
ans[u] += 1LL * (n - siz[edges[i].to]) * siz[edges[i].to];
// sum accumulated from cut;
sum += siz[edges[i].to];
if (u != 1 || flag > 1)
cut[u] = true;
}
}
else
low[u] = min(dfn[edges[i].to], low[u]);
if (!cut[u])
ans[u] = 2LL * (n - 1);
else
ans[u] += 1LL * (n - sum - 1) * (sum + 1) + (n - 1);
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
for (int i = 1, u, v; i <= m; i++)
scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
tarjan(1);
for (int i = 1; i <= n; i++)
printf("%lld\n", ans[i]);
return 0;
}
Codeforces Round #588 (Div. 2)
D – Marcin and Training Camp
考虑两种情况：
- 如果技能的 Code 相同，那么可以认为这两个合并了。这个用 map 维护就行。
- 如果技能的 Code 不同，那么在\(O(n^2)\)枚举的时候，找到一个\(S_i \subseteq S_j\)，进行标记即可。
// CF1230D.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 7070;
ll skills[MAX_N], val[MAX_N], n;
bool tag[MAX_N];
map<ll, int> cnt;
int main()
{
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
scanf("%lld", &skills[i]), cnt[skills[i]]++;
for (int i = 1; i <= n; i++)
scanf("%lld", &val[i]);
ll ans = 0;
for (int i = 1; i <= n; i++)
// set it as origin;
if (cnt[skills[i]] > 1)
for (int j = 1; j <= n; j++)
if ((skills[i] & skills[j]) == skills[j])
tag[j] = true;
for (int i = 1; i <= n; i++)
if (tag[i])
ans += val[i];
printf("%lld", ans);
return 0;
}
E – Kamil and Making a Stream
这道题太妙了！
考虑正常的暴力情况：\(O(n^2)\)条链，直接统计完事。但是，发现：一条链向下的\(gcd\)一定都是根部的一个因子，根据对\(\gcd\)复杂度的论证，可以知道最多只会存在\(\log\)级别的\(\gcd\)个数。知道这个性质之后，我们在 DFS 的时候可以把父亲的链的\(gcd\)拿出来进行合并，乘上出现次数就行了。这个做法真的太神仙了。
// CF1230E.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 100100, mod = 1e9 + 7;
int head[MAX_N], current;
ll val[MAX_N], ans, n;
map<ll, ll> mps[MAX_N];
struct edge
{
int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
edges[current].to = dst, edges[current].nxt = head[src];
head[src] = current++;
}
ll gcd(ll a, ll b)
{
if (a == 0 && b == 0)
return 0;
if (a == 0)
return b;
return b == 0 ? a : gcd(b, a % b);
}
void dfs(int u, int fa)
{
for (map<ll, ll>::iterator it = mps[fa].begin(); it != mps[fa].end(); it++)
mps[u][gcd(val[u], it->first)] += it->second;
mps[u][val[u]]++;
for (map<ll, ll>::iterator it = mps[u].begin(); it != mps[u].end(); it++)
ans = (1LL * ans + 1LL * it->second * it->first % mod) % mod;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa)
dfs(edges[i].to, u);
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
scanf("%lld", &val[i]);
for (int i = 1, u, v; i <= n - 1; i++)
scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
dfs(1, 0), printf("%lld", ans);
return 0;
}
F – Konrad and Company Evaluation
题意翻译过来就是动态维护长度为三的链的个数。当然，给你的询问肯定会简化一点：所有的边的方向都取决于边两点动态点权的大小关系。官方题解用了一种非常日狗的方式证明了，这样的边比较少，所以可以直接暴力。真的是日狗。
// CF1230F.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e5 + 200;
list<int> l2r[MAX_N];
list<int> r2l[MAX_N];
int n, indeg[MAX_N], outdeg[MAX_N], salaries[MAX_N], m, q;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1, u, v; i <= m; i++)
{
scanf("%d%d", &u, &v);
if (u < v)
swap(u, v);
r2l[u].push_back(v), l2r[v].push_back(u);
outdeg[v]++, indeg[u]++;
}
for (int i = 1; i <= n; i++)
salaries[i] = i;
ll ans = 0;
for (int i = 1; i <= n; i++)
for (list<int>::iterator it = r2l[i].begin(); it != r2l[i].end(); it++)
ans += indeg[*it];
printf("%lld\n", ans);
scanf("%d", &q);
int days = 0;
while (q--)
{
int u;
days++, scanf("%d", &u), salaries[u] = n + days;
ll flip_num = 0;
for (list<int>::iterator it = l2r[u].begin(); it != l2r[u].end();)
// if there is a edge needs flipping;
if (salaries[u] > salaries[*it])
{
int id = *it;
flip_num++;
indeg[id]--;
ans -= outdeg[id] - indeg[id];
outdeg[id]++;
list<int>::iterator backup = it;
backup++, l2r[u].erase(it), it = backup;
l2r[id].push_back(u);
}
else
it++;
ans += 1LL * (outdeg[u] - flip_num) * (indeg[u] + flip_num) - (1LL * indeg[u] * outdeg[u]);
indeg[u] += flip_num, outdeg[u] -= flip_num;
printf("%lld\n", ans);
}
return 0;
}
线性时间建二叉树
一种方式是建笛卡尔树，但是我不会。另一种方式是「双端队列」：从后往前进行加边，且这个二叉树的中序遍历一定，所以合并的时候也要把序号的进行合并。可以看这道题：P1377 [TJOI2011]树的序。
// P1377.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 200;
int seq[MAX_N], pos[MAX_N], lft[MAX_N], rig[MAX_N], n, lson[MAX_N], rson[MAX_N];
void dfs(int u)
{
if (u == 0)
return;
printf("%d ", u);
dfs(lson[u]), dfs(rson[u]);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &seq[i]), pos[seq[i]] = i;
lft[i] = i - 1, rig[i] = i + 1;
}
for (int i = n; i >= 2; i--)
{
// connect to the prev or back one;
int l = lft[seq[i]], r = rig[seq[i]];
if (pos[l] > pos[r])
rson[l] = seq[i];
else
lson[r] = seq[i];
lft[r] = l, rig[l] = r;
}
dfs(seq[1]);
return 0;
}
出行预算
这道题也算是贪心的好题了。首先做好预处理，处理好\(n\)段的距离之类的东西。之后，我们一段一段来走：首先，我们要维护一个可以始终提供便宜油的节点，然后也需要知道之前在油箱里放了多少可供现在使用的油；知道这些之后，我们就可以贪心取，然后用线段树来维护油箱即可。
// B.cpp
#include <bits/stdc++.h>
#define pr pair<double, int>
using namespace std;
const int MAX_N = 500100;
int n;
double D, C, d0, nodes[MAX_N << 2], tag[MAX_N << 2], di[MAX_N], pi[MAX_N], segs[MAX_N];
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)
void pushdown(int p)
{
if (tag[p] != 0)
{
nodes[lson] += tag[p], nodes[rson] += tag[p];
tag[lson] += tag[p], tag[rson] += tag[p];
tag[p] = 0;
}
}
void pushup(int p)
{
nodes[p] = nodes[lson] + nodes[rson];
}
void update(int ql, int qr, int l, int r, int p, double val)
{
if (ql <= l && r <= qr)
return (void)(nodes[p] += val, tag[p] += val);
pushdown(p);
if (ql <= mid)
update(ql, qr, l, mid, lson, val);
if (mid < qr)
update(ql, qr, mid + 1, r, rson, val);
pushup(p);
}
double query(int ql, int qr, int l, int r, int p)
{
if (ql <= l && r <= qr)
return nodes[p];
double ret = 0;
if (ql <= mid)
ret = max(ret, query(ql, qr, l, mid, lson));
if (mid < qr)
ret = max(ret, query(ql, qr, mid + 1, r, rson));
return ret;
}
#undef lson
#undef rson
#undef mid
int main()
{
scanf("%d%lf%lf%lf", &n, &D, &C, &d0);
for (int i = 1; i <= n; i++)
scanf("%lf%lf", &di[i], &pi[i]);
for (int i = 1; i <= n - 1; i++)
segs[i] = di[i + 1] - di[i];
segs[n] = D - di[n];
priority_queue<pr> pq;
int lastpos = 0;
double ans = 0;
for (int i = 1; i <= n; i++)
{
pq.push(make_pair(-pi[i], i));
double need = segs[i] / d0;
while (need > 0)
{
if (pq.empty())
puts("Poor Congcong"), exit(0);
int pos = pq.top().second;
if (pos <= lastpos)
{
pq.pop();
continue;
}
double lft = C - query(pos, i, 1, n, 1);
if (lft <= 0)
{
pq.pop();
break;
}
if (need - lft <= 0)
{
ans += need * pi[pos];
update(pos, i, 1, n, 1, need);
need = 0;
}
else
{
ans += lft * pi[pos];
need -= lft, update(pos, i, 1, n, 1, lft);
lastpos = max(lastpos, pos);
pq.pop();
}
}
}
printf("%.2lf", ans);
return 0;
}
收作业
考场上切掉了。首先，最短路一定是不降路径；其次，不需要考虑具体的转移方式，所以可以直接找域内的点进行转移。二位偏序搞掉（第一次在考场上写这种玩意）。
// homework.cpp
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
int X = 0, w = 0;
char ch = 0;
while (!isdigit(ch))
{
w |= ch == '-';
ch = getchar();
}
while (isdigit(ch))
X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
return w ? -X : X;
}
const int MAX_N = 2e5 + 200;
struct point
{
int x, y, val, id;
bool operator<(const point &pt) const { return x < pt.x || (x == pt.x && y < pt.y); }
} pts[MAX_N];
int n, m, k, dp[MAX_N], tree[MAX_N << 1], upper;
vector<int> mpx, mpy;
inline int lowbit(int x) { return x & -x; }
void update(int x, int d)
{
if (x == 0)
return;
for (; x <= upper; x += lowbit(x))
tree[x] = max(tree[x], d);
}
int query(int x)
{
int ans = 0;
for (; x > 0; x -= lowbit(x))
ans = max(tree[x], ans);
return ans;
}
int main()
{
freopen("homework.in", "r", stdin);
freopen("homework.out", "w", stdout);
n = read(), m = read(), k = read();
for (int i = 1; i <= k; i++)
{
pts[i].x = read(), pts[i].y = read(), pts[i].val = read(), pts[i].id = i;
mpx.push_back(pts[i].x), mpy.push_back(pts[i].y);
}
pts[k + 1] = point{n - 1, m - 1, 0, k + 1}, k++;
mpx.push_back(n - 1), mpy.push_back(m - 1);
sort(mpx.begin(), mpx.end()), sort(mpy.begin(), mpy.end());
mpx.erase(unique(mpx.begin(), mpx.end()), mpx.end());
mpy.erase(unique(mpy.begin(), mpy.end()), mpy.end());
upper = mpy.size();
for (int i = 1; i <= k; i++)
{
pts[i].x = lower_bound(mpx.begin(), mpx.end(), pts[i].x) - mpx.begin() + 1;
pts[i].y = lower_bound(mpy.begin(), mpy.end(), pts[i].y) - mpy.begin() + 1;
}
sort(pts + 1, pts + 1 + k);
for (int i = 1; i <= k; i++)
{
int ans = query(pts[i].y);
dp[pts[i].id] = ans + pts[i].val;
update(pts[i].y, dp[pts[i].id]);
}
printf("%d", dp[k]);
return 0;
}