回来了一个星期有余，一切都挺顺利的（特别是逃掉了寒假作业），只不过周末发了个烧，现在喉咙还是很痛。这些都算是小插曲，没什么大不了的。
在经历了几周的 OI 训练之后回到学校，感觉文化课在变得越来越简单了。除了毒瘤数学上的速度跟开飞机一样、这一段时间的作业有点跟不上之外，其他的科目都算是小清新，物理补完的天数已经可以预估出来了，化学再巩固巩固，必修二的时候，必修一的综合练习也做做。生物这种平常写题周末抱抱佛脚 80 就稳了的科目目前还不需要担心。语文比较毒瘤，随它去吧。
班上最近出了点事情，反正没触及到我的事情我基本上懒得理。触及到了估计也是些鸡毛蒜皮的小事情，反正他就喜欢管这种玩意，也管不好这种玩意。我就佛系的学习就行了。
其实刚开始我心态是很崩的，简章发布的那天我又是发烧，所以心情直接爆炸。这个分数不是傻逼都考得到吗？
即使明年政策会更加缩紧，我也会继续全力学。管他狼来不来，我特么就是要杀出一条血路，即使凉了我就把这套放在文化课上。我就不信一堆死老头老太太能掌握我的人生。
先这样吧，上晚自习了。
春季集训的最后一天了，果然比赛也崩了。
这道题怎么这么神仙啊。
我们先来考虑一行内的方案数。我们可以设出状态：\(f[i][j]\)代表前\(i\)个元素中有\(j\)种颜色，式子很好推：
\[ f[i][j] = f[i-1][j-1]*(p-(j-1))+f[i-1][j]*j \]
因为列数是固定的，所以我们只要保留当\(i=m\)的值即可，所以我们设\(g[i]=f[m][i]\)，也就是单行有\(i\)种颜色的方案。之后我们考虑设计一个状态来求我们的答案：我们可以固定一行，然后讨论两行放在一起的情况。所以，\(dp[i][k]\)的意义是前\(i\)行的方案，其中最后一行包括了\(k\)种颜色。
\[ dp[i][k] = dp[i-1][j]+\frac{g[k]}{{ p \choose k }}*\sum_{ x = max\{ j,k,q \} }^{ min\{ p,j+k \} } { { j \choose j+k-x }*{ p-j \choose x-j } } \]
我知道这个式子很复杂，我们来解释一下。首先，状态\(dp[i][k]\)代表到了第\(i\)行，第\(i\)行有\(k\)种颜色，枚举上一行有\(j\)种颜色，所以从\(dp[i-1][j]\)转移过来。因为我们这里单独枚举颜色类型对答案的贡献，所以我们要消去\(g[i]\)中答案种类对\(g[i]\)的影响，避免算重。之后再枚举两行一共有\(x\)种颜色，因为\(j\)和\(k\)可能会有重复，所以我们需要单独枚举，这个\(x\)的上下界为：\( [max\{ j,k,q \},min\{ p, j+k \}] \)。之后就是喜闻乐见的两部分的单独枚举：\( { j \choose j+k-x } \)代表枚举两行共有的部分，\( { p-j \choose x-j } \)则是代表两行不共有的部分。所以，这样就可以把答案统计出来了。
然后这道题的\(f[i]\)可以用矩阵快速幂来搞，复杂度进一步降低。
自从去年学长们去纪中培训后，我就已经听闻这所学校的优美环境了。这所学校的建筑非常吸引我，色调和复古的设计都非常符合我的口味。
不得不承认，在如此优美的环境下学习和生活，是何等的美事啊！我有幸在这个地方停留了三个星期，呆在机房里和全国的神仙们一起学习，无论是学习气氛还是说校园环境，我觉得都是非常让人满意的，这也可能就是为什么这个学校神仙这么多的原因吧，神仙都待在神仙之所。
这边的训练还是非常高强度的，每天早上 7:30 的比赛一直打到 11:30 ，中间屁股都不挪一下。晚自习要等到 22:00 才放，中途没有任何休息，全都是连贯的，又加上题目神仙，经常会感到疲惫。机房的外景些许可以缓解一下视觉的压力。
纪中有三个巨大的食堂：连在一起的一、二食堂，还有在西边的、靠近男生宿舍的三食堂。每一个食堂至少都有两层，其中二食堂还设有茶餐厅，体验非常出众，排队的同学挺多的。
一二食堂的壹加壹离我们宿舍比较近，所以一般我都会在晚自习结束后，趁着壹加壹还没关门就赶紧去买泡面或者是其他的可以用作夜宵的食物。
作为一个在南方生活了16年的小朋友，自从来了中山，我才知道什么才叫“南方风情”：老鼠、飞蛾、蚊子和蟑螂随时在宿舍迎接你；屋内过重的“地气”非常的难闻，被子里有动物尿液味道，而且晚上睡觉时非常的湿，有种粘稠的感觉；变换无常的天气随时会让你的袜子处在一个“明天才能干”的状态。总之，推荐短期集训的 OIer 尽量选择酒店。不过附近的酒店也好奇怪，空调有越吹越热的毛病，可能是个例吧。
我不放图了，免得大家呕吐。
这道题应该算是点分治的一道经典题目。点分治的精髓就在于找到重心、对子树进行计算并且合并答案，之后删除中心变成子树内的小问题，分治思想非常的巧妙。
我们首先写好找根函数：
// root finding functions;
void dfs1(int u, int fa, int siz)
{
son[u] = 1;
int res = 0;
for (int i = head[u]; i != -1; i = edges[i].nxt)
{
if (edges[i].to == fa || done[edges[i].to])
continue;
dfs1(edges[i].to, u, siz);
son[u] += son[edges[i].to];
res = max(res, son[edges[i].to] - 1);
}
res = max(res, siz - son[u]);
if (res < rootKey)
root = u, rootKey = res;
}
void findRoot(int src, int siz)
{
root = src, rootKey = siz;
dfs1(src, 0, siz);
}
遍历子树：我们设定一个\(dist[]\)数组，算出距离的答案，并且无视曾经被当作根的节点，并向cnt[from[u]]进行自增操作，维护子树的大小，并把本身编号加入vec供之后进行排序用途。
// the calc one;
void dfs(int u, int fa)
{
vec.push_back(u);
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa && !done[edges[i].to])
{
cnt[from[u]]++;
dist[edges[i].to] = dist[u] + edges[i].weight;
from[edges[i].to] = from[u];
dfs(edges[i].to, u);
}
}
点分治：我们在计算完子树答案之后，合并的方法是主要的问题。我们可以考虑将vec进行排序，然后通过递增的性质设置首尾指针，并且去除掉当前子树内的错误答案（因为子树内部的路径不经过根，所以要去掉，之后的分治子问题中会处理这些内部路径）。
void pdq(int curt, int siz)
{
memset(son, 0, sizeof(son));
memset(cnt, 0, sizeof(cnt));
findRoot(curt, siz);
dist[root] = 0, done[root] = true;
vec.clear(), vec.push_back(root), from[root] = root;
cnt[root]++;
for (int i = head[root]; i != -1; i = edges[i].nxt)
if (!done[edges[i].to])
{
from[edges[i].to] = edges[i].to, cnt[edges[i].to]++;
dist[edges[i].to] = edges[i].weight;
dfs(edges[i].to, root);
}
sort(vec.begin(), vec.end(), compare);
cnt[from[vec[0]]]--;
int l = 0, r = vec.size() - 1;
while (l < r)
{
while (dist[vec[l]] + dist[vec[r]] > k)
cnt[from[vec[r--]]]--;
answer += r - l - cnt[from[vec[l]]];
cnt[from[vec[++l]]]--;
}
int pos = root;
for (int i = head[pos]; i != -1; i = edges[i].nxt)
if (!done[edges[i].to])
pdq(edges[i].to, son[edges[i].to]);
}
嗯，写完了。具体代码如下：
// POJ1741.cpp
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 10100, INF = 0x3f3f3f3f;
int head[MAX_N], current, k, n, tmpx, tmpy, tmpz, root, rootKey, son[MAX_N];
int from[MAX_N], dist[MAX_N], cnt[MAX_N];
bool done[MAX_N];
long long answer = 0;
vector<int> vec;
struct edge
{
int to, nxt, weight;
} edges[MAX_N << 1];
bool compare(int a, int b) { return dist[a] < dist[b]; }
void addpath(int src, int dst, int weight)
{
edges[current].to = dst, edges[current].nxt = head[src];
edges[current].weight = weight, head[src] = current++;
}
// root finding functions;
void dfs1(int u, int fa, int siz)
{
son[u] = 1;
int res = 0;
for (int i = head[u]; i != -1; i = edges[i].nxt)
{
if (edges[i].to == fa || done[edges[i].to])
continue;
dfs1(edges[i].to, u, siz);
son[u] += son[edges[i].to];
res = max(res, son[edges[i].to] - 1);
}
res = max(res, siz - son[u]);
if (res < rootKey)
root = u, rootKey = res;
}
void findRoot(int src, int siz)
{
root = src, rootKey = siz;
dfs1(src, 0, siz);
}
// the calc one;
void dfs(int u, int fa)
{
vec.push_back(u);
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa && !done[edges[i].to])
{
cnt[from[u]]++;
dist[edges[i].to] = dist[u] + edges[i].weight;
from[edges[i].to] = from[u];
dfs(edges[i].to, u);
}
}
void pdq(int curt, int siz)
{
memset(son, 0, sizeof(son));
memset(cnt, 0, sizeof(cnt));
findRoot(curt, siz);
dist[root] = 0, done[root] = true;
vec.clear(), vec.push_back(root), from[root] = root;
cnt[root]++;
for (int i = head[root]; i != -1; i = edges[i].nxt)
if (!done[edges[i].to])
{
from[edges[i].to] = edges[i].to, cnt[edges[i].to]++;
dist[edges[i].to] = edges[i].weight;
dfs(edges[i].to, root);
}
sort(vec.begin(), vec.end(), compare);
cnt[from[vec[0]]]--;
int l = 0, r = vec.size() - 1;
while (l < r)
{
while (dist[vec[l]] + dist[vec[r]] > k)
cnt[from[vec[r--]]]--;
answer += r - l - cnt[from[vec[l]]];
cnt[from[vec[++l]]]--;
}
int pos = root;
for (int i = head[pos]; i != -1; i = edges[i].nxt)
if (!done[edges[i].to])
pdq(edges[i].to, son[edges[i].to]);
}
int main()
{
while (scanf("%d%d", &n, &k) && n != 0)
{
answer = 0;
memset(head, -1, sizeof(head)), current = 0;
for (int i = 1; i <= n - 1; i++)
scanf("%d%d%d", &tmpx, &tmpy, &tmpz), addpath(tmpx, tmpy, tmpz), addpath(tmpy, tmpx, tmpz);
memset(done, false, sizeof(done));
pdq(1, n);
printf("%lld\n", answer);
}
return 0;
}
裸的二分图匹配，匹配数除以二即可。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100;
int head[MAX_N], n, current, matching[MAX_N], dfn[MAX_N], arr[MAX_N];
bool isPrime[2020];
struct edge
{
int to, nxt;
} edges[(MAX_N * (MAX_N - 1)) >> 1];
void addpath(int src, int dst)
{
edges[current].to = dst, edges[current].nxt = head[src];
head[src] = current++;
}
bool dfs(int u, int org)
{
for (int i = head[u]; i != -1; i = edges[i].nxt)
{
int to = edges[i].to;
if (dfn[to] != org)
{
dfn[to] = org;
if ((!matching[to]) || dfs(matching[to], org))
{
matching[to] = u;
return true;
}
}
}
return false;
}
int main()
{
freopen("prime.in", "r", stdin);
freopen("prime.out", "w", stdout);
memset(head, -1, sizeof(head)), memset(isPrime, true, sizeof(isPrime));
int ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &arr[i]);
for (int i = 2; i < 2020; i++)
if (isPrime[i])
for (int j = 2; i * j < 2020; j++)
isPrime[j * i] = false;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (isPrime[arr[i] + arr[j]])
addpath(i, j);
for (int i = 1; i <= n; i++)
if (dfs(i, i))
ans++;
printf("%d", ans / 2);
return 0;
}
这道题我在考场上 A 掉了，方法跟题解不太一样（欢迎来 Hack），当然复杂度可能会高一点。
我们考虑魔改 DFS 序，在进入节点之前先进行排序，排序之后 DFS 完了之后再进行标记。可以发现，这就是我们在不删除节点的情况下的最优放法：
如上图所示，这就是我们在不搞删除的情况下放置的最佳顺序：4、7、3、2、6、5、1。我们定义这种顺序叫做乱搞序。我们来讨论使用一种乱搞的线段树（以上面那种顺序做关键字）来搞定这两个操作。
\(OPT = 1\)的情况下：我们先考虑之前没有删除操作的情况，其实很简单，直接往最后一个乱搞序最小的槽位设置为一即可；如果之前有过删除操作的话，那么已有的乱搞序上肯定不是连续的1：一定有个0表示被删除，我们可以考虑在 UPDATE 操作里面判断左右儿子是否有不满足连续的情况（也就是和等于区间长度），如果有那么就从加数里取出一些，如果加数有剩余，那么左儿子直接打标记，然后递归右儿子：因为我们设置 UPDATE 操作的返回值为最后一个乱搞值，之后通过 anti 数组重新转换为节点编号。
int update(int l, int r, int p, int c)
{
if (c == 0)
return -1;
if (l == r)
{
tree[p] += c;
return l;
}
int lft = (mid - l + 1) - tree[lson], rig = c - lft;
int ans = 0;
if (rig > 0)
{
tree[lson] = mid - l + 1, lazy[lson] = 1;
ans = update(mid + 1, r, rson, rig);
}
else
ans = update(l, mid, lson, c);
tree[p] = tree[lson] + tree[rson];
return ans;
}
\(OPT=2\)的情况下也比较简单，我们只要找出该节点到根节点链上的已用节点个数并减去一即可，进行单点修改。
建议详读代码，理解我的乱搞思想。
// B.cpp
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define lowbit(x) (x & -x)
using namespace std;
const int MAX_N = 1e5 + 2000;
int n, t, dfn[MAX_N], st[20][MAX_N], tmpx, tmpy, tree[MAX_N << 2], lazy[MAX_N << 2], dtot, anti[MAX_N];
vector<int> G[MAX_N];
void addpath(int src, int dst) { G[src].push_back(dst); }
void pushdown(int p, int l, int r)
{
if (lazy[p] && l != r)
{
tree[lson] = mid - l + 1, tree[rson] = r - mid;
lazy[lson] = 1, lazy[rson] = 1;
}
lazy[p] = 0;
}
int update(int l, int r, int p, int c)
{
if (c == 0)
return -1;
if (l == r)
{
tree[p] += c;
return l;
}
int lft = (mid - l + 1) - tree[lson], rig = c - lft;
int ans = 0;
if (rig > 0)
{
tree[lson] = mid - l + 1, lazy[lson] = 1;
ans = update(mid + 1, r, rson, rig);
}
else
ans = update(l, mid, lson, c);
tree[p] = tree[lson] + tree[rson];
return ans;
}
void remove(int qx, int l, int r, int p)
{
if (l == r && l == qx)
{
tree[p] = 0, lazy[p] = 0;
return;
}
pushdown(p, l, r);
if (qx <= mid)
remove(qx, l, mid, lson);
else
remove(qx, mid + 1, r, rson);
tree[p] = tree[lson] + tree[rson];
}
bool query(int qx, int l, int r, int p)
{
if (l == r && l == qx)
return tree[p];
pushdown(p, l, r);
if (qx <= mid)
return query(qx, l, mid, lson);
else
return query(qx, mid + 1, r, rson);
}
void dfs(int u)
{
sort(G[u].begin(), G[u].end());
int siz = G[u].size();
for (int i = 0; i < siz; i++)
{
int to = G[u][i];
if (st[0][u] != to)
st[0][to] = u, dfs(to);
}
dfn[u] = ++dtot, anti[dfn[u]] = u;
}
int main()
{
scanf("%d%d", &n, &t);
for (int i = 1; i <= n - 1; i++)
scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy), addpath(tmpy, tmpx);
dfs(1);
for (int i = 1; i < 20; i++)
for (int j = 1; j <= n; j++)
st[i][j] = st[i - 1][st[i - 1][j]];
while (t--)
{
int opt, x;
scanf("%d%d", &opt, &x);
if (opt == 1)
printf("%d\n", anti[update(1, n, 1, x)]);
else
{
int u = x, ans = 0;
for (int i = 19; i >= 0; i--)
if (st[i][u] != 0 && query(dfn[st[i][u]], 1, n, 1) == true)
u = st[i][u], ans += 1 << i;
printf("%d\n", ans);
remove(dfn[u], 1, n, 1);
}
}
return 0;
}
我考场上以为是费用流，然后打凉掉了。
可以考虑先对序列进行排序（按第一、二和三关键字），然后再进行分段：二分出两个位置\(mid,mid1\)，然后分成三段：\( [1,mid],[mid+1,mid1],[mid1+1,n] \)
之后统计即可。
// C.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e5 + 1000;
struct cas
{
ll x, y, z;
bool operator<(const cas &cs) const { return x < cs.x || (cs.x == x && y < cs.y) || (y == cs.y && x == cs.x && z < cs.z); }
} cases[MAX_N];
ll n, ans1, ans2, ans3, ans;
int main()
{
freopen("psy.in", "r", stdin);
freopen("psy.out", "w", stdout);
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
{
scanf("%lld%lld%lld", &cases[i].x, &cases[i].y, &cases[i].z);
ans1 = max(ans1, cases[i].x), ans2 = max(ans2, cases[i].y), ans3 = max(ans3, cases[i].z);
}
ans = min(ans1, min(ans2, ans3));
sort(cases + 1, cases + 1 + n);
ll l = 0, r = n, l1 = 0, r1 = n;
while (l < r)
{
ll mid = (l + r) >> 1;
l1 = 0, r1 = n;
bool flag = true;
while (l1 < r1)
{
ll mid1 = (l1 + r1) >> 1;
if (mid1 == mid)
if (mid1 + 1 <= r)
mid1++;
else if (mid1 - 1 >= l)
mid1--;
else
{
flag = false;
break;
}
ll k = 0;
for (int i = 1; i <= n; i++)
{
if (cases[i].x <= cases[mid].x)
continue;
if (cases[i].y <= cases[mid1].y)
continue;
if (cases[i].z > k)
k = cases[i].z;
}
ans1 = cases[mid].x + cases[mid1].y + k;
if (ans1 < ans)
ans = ans1, flag = true, r1 = mid1;
else
l1 = mid1 + 1;
}
if (flag)
r = mid;
else
l = mid + 1;
}
ll k = 0;
for (int i = 1; i <= n; i++)
{
if (cases[i].x <= cases[l].x)
continue;
if (cases[i].y <= cases[l1].y)
continue;
if (cases[i].z > k)
k = cases[i].z;
}
ans = min(ans, cases[l].x + cases[l1].y + k);
printf("%lld", ans);
return 0;
}
这道题很好，很有趣。
如果您是神仙的话呢，可以考虑直接线段是卡掉本题（有人试过了），但是我这个菜鸡不行，所以写了题解的\(O(1)\)询问解法。
首先，树形 DP 的方程为：
\[ dp[u] = \frac{1}{2} * (dp[lson]+dp[rson]) \]
我们观察叶子节点对答案的贡献，发现为该条链上的权值和除掉\(2^{dep-1}\)，也就是与深度有关。那么，为了简化答案，我们可以把这个写作：
\[ \frac{1}{2^{dep-1}} = 2^{1-dep} = \frac { 2^{maxDep – dep} }{ 2^{maxDep-1} } \]
就变成了乘法形式。我们在讨论询问的问题。在区间\([l,r]\)之间加上\(x\)，链对答案的贡献是：
\[ x · \sum_{i = 1}^{dep} \frac{1}{2^{i-1}} \]
所以，维护一个前缀和，往答案上面加上前缀和段和这个贡献的积即可获得答案。（记得用 gcd 约分）
// P3924.cpp
#include <bits/stdc++.h>
#define ll long long
#define mid ((l + r) >> 1)
#define lson (p << 1)
#define rson ((p << 1) | 1)
using namespace std;
const int MAX_N = 1e6 + 2000;
ll n, m, qwq, sum[MAX_N << 2], depth[MAX_N << 2], arr[MAX_N], s[MAX_N], max_dep;
inline ll read()
{
ll s = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
s = s * 10 + ch - '0', ch = getchar();
return s * w;
}
void build(ll l, ll r, ll dp, ll p)
{
if (l == r)
{
sum[p] = arr[l], depth[l] = dp, max_dep = max(max_dep, dp);
return;
}
build(l, mid, dp + 1, lson), build(mid + 1, r, dp + 1, rson);
sum[p] = sum[lson] + sum[rson];
}
ll query(ll l, ll r, ll p, ll dep, ll prefix)
{
if (l == r)
return (1 << dep) * (prefix + sum[p]);
return query(l, mid, lson, dep - 1, prefix + sum[p]) + query(mid + 1, r, rson, dep - 1, prefix + sum[p]);
}
ll gcd(ll a, ll b) { return (b == 0) ? a : gcd(b, a % b); }
int main()
{
n = read(), m = read(), qwq = read();
for (int i = 1; i <= n; i++)
arr[i] = read();
build(1, n, 1, 1);
ll ans = query(1, n, 1, max_dep - 1, 0), dominator = 1 << (max_dep - 1);
ll fact = gcd(dominator, qwq);
dominator /= fact, qwq /= fact;
for (int i = 1; i <= n; i++)
s[i] = s[i - 1] + (((1 << depth[i]) - 1) << (max_dep - depth[i]));
while (m--)
{
ll l = read(), r = read(), w = read();
ans += (s[r] - s[l - 1]) * w;
printf("%lld\n", ans / dominator * qwq);
}
return 0;
}