[LibreOJ 2035][SDOI2016]征途
又做了一道适合我这种沙茶做的题qwq
考虑方差，它满足这个式子：
\[Var(X) = E[X^2] - (E[X])^2\]
对于这个题展开，发现后半部分是一个常量（\((\frac{s_n}{m})^2\)）。最小化的就是前半部分，前半部分相当于要求你求一个序列划分，使得各部分平方和的平均值最小。这个值乘上\(m^2\)之后就变成了各部分平方和乘上\(m\)。
然后就很简单了……DP方程化简之后是这样的：
\[f_{t, i} = ms_i^2 + max(f_{t - 1, j} + ms_j^2 - 2ms_i s_j)\]
求截距式形式，得：
\[2ms_i s_j + d_i = f_j + ms_j^2\]
然后用类似于上上题的方法搞就行。还有我想想啥时候补一下斜率优化的tutorial……
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <deque>
#include <cmath>
#include <climits>
typedef long long ll;
typedef ll T;
struct Point {
T x, y;
Point(T qx = 0LL, T qy = 0LL) {
x = qx; y = qy;
}
};
typedef Point Vector;
Vector operator +(const Vector &a, const Vector &b) {
return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
return Vector(a.x - b.x, a.y - b.y);
}
Vector operator *(const Vector &a, T lam) {
return Vector(a.x * lam, a.y * lam);
}
Vector operator *(T lam, const Vector &a) {
return Vector(a.x * lam, a.y * lam);
}
inline T dot(const Vector &a, const Vector &b) {
return (a.x * b.x + a.y * b.y);
}
inline T times(const Vector &a, const Vector &b) {
return (a.x * b.y - a.y * b.x);
}
const int maxn = 3005;
T f[maxn][maxn];
T S[maxn];
int n; T m;
void dp() {
for(int t = 1; t <= m; t ++) {
std::deque<Point> Q;
Q.push_back(Point(0LL, 0LL));
for(int i = 1; i <= n; i ++) {
ll k = 2 * m * S[i];
Vector st(1LL, k);
while(Q.size() > 1 && times(Q[1] - Q[0], st) > 0LL) {
Q.pop_front();
}
f[t][i] = m * S[i] * S[i];
f[t][i] += Q.front().y - Q.front().x * k;
#ifdef LOCAL
printf("f[%d][%d] : %lld\n", t, i, f[t][i]);
#endif
if(t == 1) continue;
Vector ins(S[i], f[t - 1][i] + m * S[i] * S[i]);
while(Q.size() > 1 && times(ins - Q.back(), Q.back() - Q[Q.size() - 2]) > 0LL) {
Q.pop_back();
}
Q.push_back(ins);
}
}
}
int main() {
scanf("%d%lld", &n, &m);
for(int i = 1; i <= n; i ++) {
scanf("%lld", &S[i]);
}
for(int i = 1; i <= n; i ++) {
S[i] += S[i - 1];
}
dp();
printf("%lld\n", f[m][n] - S[n] * S[n]);
return 0;
}
[LibreOJ 2197][SDOI2014]向量集
xjb写了写……我评测时候心脏跳得贼快（逃
考虑如果知道了那一段区间的凸包那么怎么做。首先如果向量是往上指的话，一定在上凸壳上找点比较好，反之则在下凸壳上找点比较好（放到坐标系里脑补一下？）。然后我们观察一点，在上凸壳上的最优解往两边的点会越来越劣，所以这玩意是个上凸函数，可以三分答案（我才学的整数三分啊）。
但区间凸包求起来复杂度很爆炸啊……考虑用线段树搞？观察到一点，我们区间查询所使用的线段树节点一定是只包含了已经加进来的点。所以说，一个线段树节点的凸包需要被求的情况只有一种，那就是这个节点完全已加入点被覆盖了。那每次修改之后看是否一个节点完全被已加入点覆盖，如果被完全覆盖的话才去求它的凸包。
这样一来，线段树上每个节点之多会被求一次凸包。线段树有\(\log n\)层，每一层所有节点的大小加起来是\(n\)，所以求凸包耗费的总复杂度是\(n\log^2 n\)级别的。
其实这就是用线段树模拟二进制分组？
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <climits>
#include <cassert>
using ll = long long;
using T = ll;
struct Point {
T x, y;
Point(T qx = 0LL, T qy = 0LL) {
x = qx; y = qy;
}
};
using Vector = Point;
Vector operator +(const Vector &a, const Vector &b) {
return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
return Vector(a.x - b.x, a.y - b.y);
}
Vector operator *(const Vector &a, T lam) {
return Vector(a.x * lam, a.y * lam);
}
Vector operator *(T lam, const Vector &a) {
return Vector(a.x * lam, a.y * lam);
}
inline T dot(const Vector &a, const Vector &b) {
return (a.x * b.x + a.y * b.y);
}
inline T times(const Vector &a, const Vector &b) {
return (a.x * b.y - a.y * b.x);
}
inline bool cmp(const Point &a, const Point &b) {
if((a.x - b.x) == 0LL) {
return a.y < b.y;
} else {
return a.x < b.x;
}
}
inline void andrew(Point *P, int L, std::vector<Point> &bot, std::vector<Point> &top) {
std::sort(P + 1, P + 1 + L, cmp);
for(int i = 1; i <= L; i ++) {
if(i != 1 && (P[i].x - P[i - 1].x) == 0LL) continue;
while(bot.size() > 1 && (times(P[i] - bot.back(), bot.back() - bot[bot.size() - 2])) >= 0LL) {
bot.pop_back();
}
bot.push_back(P[i]);
}
for(int i = L; i >= 1; i --) {
if(i != L && (P[i].x - P[i + 1].x) == 0LL) continue;
while(top.size() > 1 && (times(P[i] - top.back(), top.back() - top[top.size() - 2])) >= 0LL) {
top.pop_back();
}
top.push_back(P[i]);
}
std::reverse(top.begin(), top.end());
}
const int maxn = 400005;
const int maxno = maxn << 2;
const int N = 400000;
bool zen[maxno];
std::vector<Point> bot[maxno], top[maxno];
Point P[maxn];
inline void maintain(int o, int L, int R) {
static Point tmp[maxn];
const int lc = o << 1, rc = o << 1 | 1;
const bool used = zen[o];
zen[o] = (zen[lc] && zen[rc]);
if(zen[o] != used) {
std::copy(P + L, P + R + 1, tmp + 1);
int len = R - L + 1;
andrew(tmp, len, bot[o], top[o]);
}
}
void modify(int o, int L, int R, const int &p, const Point &v) {
if(L == R) {
zen[o] = true;
P[L] = v;
bot[o].push_back(v); top[o].push_back(v);
} else {
const int M = (L + R) / 2;
if(p <= M) {
modify(o << 1, L, M, p, v);
} else {
modify(o << 1 | 1, M + 1, R, p, v);
}
maintain(o, L, R);
}
}
inline T search(const std::vector<Point> &vec, const Point &p) {
int l = 0, r = vec.size() - 1;
while(r - l > 2) {
int lm = (l * 2 + r) / 3, rm = (2 * r + l) / 3;
if(dot(p, vec[lm]) > dot(p, vec[rm])) {
r = rm;
} else {
l = lm;
}
}
T ans = LLONG_MIN;
for(int i = l; i <= r; i ++) {
ans = std::max(ans, dot(p, vec[i]));
}
return ans;
}
T query(int o, int L, int R, const int &ql, const int &qr, const Point &p) {
if(ql <= L && R <= qr) {
if(p.y > 0LL) {
return search(top[o], p);
} else {
return search(bot[o], p);
}
} else {
int M = (L + R) / 2;
T ans = LLONG_MIN;
if(ql <= M) {
ans = std::max(ans, query(o << 1, L, M, ql, qr, p));
}
if(qr > M) {
ans = std::max(ans, query(o << 1 | 1, M + 1, R, ql, qr, p));
}
return ans;
}
}
inline int decode(int x, long long lastans) {
return x ^ (lastans & 0x7fffffff);
}
int main() {
int q; char buf[4]; scanf("%d%s", &q, buf);
bool typ_E = (buf[0] == 'E' && buf[1] == char(0));
T las = 0LL;
int tot = 0;
while(q --) {
char op[4]; scanf("%s", op);
if(op[0] == 'A') {
T x, y; scanf("%lld%lld", &x, &y);
if(!typ_E) {
x = decode(x, las); y = decode(y, las);
}
tot ++;
modify(1, 1, N, tot, Point(x, y));
} else {
T x, y, l, r; scanf("%lld%lld%lld%lld", &x, &y, &l, &r);
if(!typ_E) {
x = decode(x, las); y = decode(y, las);
l = decode(l, las); r = decode(r, las);
}
las = query(1, 1, N, l, r, Point(x, y));
printf("%lld\n", las);
}
}
return 0;
}
[LibreOJ 2102][TJOI2015]弦论
xjbYY了一下竟然就艹过去了……
如果说是我们知道了每个点出发能得到的串有多少个，我们就能用类似树上求\(k\)大的求法来搞了。问题来了，怎么知道这个？
我先说一下不重复的情况吧，首先到达这个点就有一种串了，然后我们加上他的出边（注意是转移边！）指向的点的值就行了。重复的情况我们考虑一下\(|Right(x)|\)就能搞出来了
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <utility>
#include <queue>
#include <algorithm>
#include <set>
const int maxn = 500005;
const int maxno = maxn * 4;
const int bufsiz = 50 * 1024 * 1024;
typedef long long ll;
int fa[maxno], ch[maxno][26];
int len[maxno];
ll ans[maxno][2], val[maxno];
int rt, last;
int cur;
inline void init_sam() {
rt = last = 1;
cur = 1;
ans[1][0] = ans[1][1] = -1LL;
}
inline int alloc_node(int l = 0, int f = 0) {
int ret = ++ cur;
len[ret] = l; fa[ret] = f;
ans[ret][0] = ans[ret][1] = -1LL;
return ret;
}
inline int idx(char c) {
return c - 'a';
}
inline void extend(char cx) {
int c = idx(cx);
int np = alloc_node(len[last] + 1);
val[np] = 1LL;
int p = last;
while(p && !(ch[p][c])) ch[p][c] = np, p = fa[p];
if(!p) {
fa[np] = rt;
} else {
int q = ch[p][c];
if(len[q] == len[p] + 1) {
fa[np] = q;
} else {
int nq = alloc_node(len[p] + 1, fa[q]);
memcpy(ch[nq], ch[q], sizeof(ch[q]));
fa[q] = fa[np] = nq;
while(p && ch[p][c] == q) ch[p][c] = nq, p = fa[p];
}
}
last = np;
}
int lc[maxno], rb[maxno];
inline void add_edge(int c, int f) {
rb[c] = lc[f];
lc[f] = c;
}
void dfs_1(int x) {
for(int i = lc[x]; i; i = rb[i]) {
dfs_1(i);
val[x] += val[i];
}
}
void dfs_2(int x) {
if(ans[x][0] != -1LL) return;
ans[x][0] = 1LL; ans[x][1] = val[x];
for(int c = 0; c < 26; c ++) {
int v = ch[x][c];
if(v) {
dfs_2(v);
ans[x][0] += ans[v][0];
ans[x][1] += ans[v][1];
}
}
}
inline void process() {
for(int i = 2; i <= cur; i ++) {
add_edge(i, fa[i]);
}
dfs_1(1); dfs_2(1);
#ifdef LOCAL
for(int i = 1; i <= cur; i ++) {
printf("ans[%d] : (%lld, %lld)\n", i, ans[i][0], ans[i][1]);
}
#endif
}
char ret[maxno];
void search(ll k, int typ) {
static ll val_0[maxno];
for(int i = 1; i <= cur; i ++) {
val_0[i] = 1;
}
ll *self[2] = {val_0, val};
k += self[typ][1];
if(k > ans[1][typ]) {
ret[0] = '-', ret[1] = '1';
return;
}
int cnt = 0;
int u = 1;
while(k > self[typ][u]) {
int used = 0;
k -= self[typ][u];
for(int c = 0; c < 26; c ++) {
int v = ch[u][c];
if(!v) continue;
used ++;
if(k > ans[v][typ]) {
k -= ans[v][typ];
} else {
ret[cnt ++] = c + 'a';
#ifdef LOCAL
printf("Towardsing %d with %c\n", v, c + 'a');
printf("k : %lld\n", k);
#endif
u = v; break;
}
}
// if(used == 0) break;
}
}
int main() {
static char S[maxn];
scanf("%s", S); int n = strlen(S);
int typ; ll k; scanf("%d%lld", &typ, &k);
init_sam();
for(int i = 0; i < n; i ++) {
extend(S[i]);
}
process();
search(k, typ);
puts(ret);
return 0;
}
[LibreOJ 2033][SDOI2016]生成魔咒
辣鸡爆炸OJ又被卡了说好的修bug呢说好的新OJ呢哼我去loj交了
本题的正解是SA，但很显然可以用SAM搞过去（逃
首先字符集过大？我们可以考虑开map解决转移的问题。
然后思考一个点加入后对答案会有什么影响。一个点的对答案的贡献，就是他自己的最大表示范围减去他父亲的。因为更小的长度在之前都已经被表示过了。即使之后这个点被拆成了两个，那这两个点对答案的总贡献是不会变的。所以每次加完点，把贡献加到答案里即可。
代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
typedef long long ll;
#define REP(i, l, r) for(int i = (l); i <= (r); i ++)
struct Node {
Node *fa;
std::map<int, Node*> *ch;
int len;
Node() {
fa = NULL;
ch = new std::map<int, Node*>();
}
Node(int l) {
fa = NULL;
ch = new std::map<int, Node*>();
len = l;
}
~Node() {
delete ch;
}
};
Node *rt, *last;
void init() {
rt = new Node(0);
// rt -> tl = 1;
last = rt;
}
ll ans = 0;
void insert(int c) {
static int clk = 1;
Node *np = new Node();
np -> len = last -> len + 1;
Node *p = last;
while(p != NULL && p -> ch -> count(c) == 0) {
p -> ch -> insert(std::make_pair(c, np));
p = p -> fa;
}
if(p == NULL) {
np -> fa = rt;
} else {
Node *q = (*(p -> ch -> find(c))).second;
if(q -> len == p -> len + 1) {
np -> fa = q;
} else {
Node *nq = new Node(p -> len + 1);
nq -> fa = q -> fa;
nq -> ch -> insert(q -> ch -> begin(), q -> ch -> end());
// nq -> ch -> insert(std::make_pair(c, np));
np -> fa = q -> fa = nq;
while(p != NULL && ((*(p -> ch -> find(c))).second) == q) {
p -> ch -> erase(p -> ch -> find(c));
p -> ch -> insert(std::make_pair(c, nq));
p = p -> fa;
}
}
}
last = np;
ans += np -> len - np -> fa -> len;
}
int main() {
int n; scanf("%d", &n);
init();
REP(i, 1, n) {
int c; scanf("%d", &c);
insert(c);
printf("%lld\n", ans);
}
return 0;
}
[LibreOJ 2174][FJOI2016]神秘数 & [CC]FRBSUM
震惊！省选惊现CodeChef原题……竟然是为了……出原题难道不是普遍现象吗
这个题的思想肥肠喵啊（我膜了很长时间题解才看懂）……我争取给各位读者讲懂。
首先对于最后的答案\(x + 1\)，一定说明\([1, x]\)都会被凑出来。那么我们可以考虑去维护这个前缀区间。
考虑把数从小到大加入。假设当前我们的可凑出来的前缀区间是\([1, r]\)，那么加入一个数\(x\)，如果说\(x > r + 1\)，那么把之前所有可能的子集和都加上这个\(x\)，一定凑不出来\(r + 1\)。并且这之后加入的数会越来越大，那个\(r\)不会再变大了，所以那个\(r\)就是答案了。
如果说\(x\leq r + 1\)呢？那么把前缀区间的每个数加上\(x\)都是可凑成数。所以前缀区间会变成\([1, r + x]\)。
然后观察出来这种性质之后，我们发现我们要考虑区间中不同的数，可以考虑主席树。我们建立一排主席树，对于查询\([L, R]\)，不妨假设当前的前缀区间是\([1, r]\)，然后考虑将其扩大。首先再加上大于\(r + 1\)的数是对扩大\(r\)没有意义的，所以我们就考虑在\([L, R]\)中找到所有权值处于\([1, r + 1]\)的数字的和（主席树可以派上用场），这样就是一个新的答案了。如果发现转移过去之后答案没有变大，那么以后也不会变大了，跳出来即可。
考虑分析一波复杂度。对于每一个\(r\)，转移到更大的\(r\)会让他至少加上\(r + 1\)，所以转移的次数是\(\log_2 s\)（这里假设\(s\)是所有数的和），然后每次一次转移的复杂度是\(\log_2 n\)，所以单次查询复杂度可以大致认为是\(\log^2 n\)。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const int maxn = 100005;
const int maxsiz = maxn * 40;
ll sumv[maxsiz]; int tot = 0;
int lc[maxsiz], rc[maxsiz];
int build_tree(int L, int R) {
int ret = ++ tot;
if(L < R) {
int M = (L + R) / 2;
lc[ret] = build_tree(L, M);
rc[ret] = build_tree(M + 1, R);
}
return ret;
}
int update(int o, int L, int R, int p, int v) {
int ret = ++ tot;
sumv[ret] = sumv[o] + (ll(v));
lc[ret] = lc[o], rc[ret] = rc[o];
if(L < R) {
int M = (L + R) / 2;
if(p <= M) {
lc[ret] = update(lc[ret], L, M, p, v);
} else {
rc[ret] = update(rc[ret], M + 1, R, p, v);
}
}
return ret;
}
ll query(int o, int L, int R, int ql, int qr) {
if(ql <= L && R <= qr) {
return sumv[o];
} else {
int M = (L + R) / 2;
ll ans = 0;
if(ql <= M) ans += query(lc[o], L, M, ql, qr);
if(qr > M) ans += query(rc[o], M + 1, R, ql, qr);
return ans;
}
}
int n;
ll A[maxn], A2[maxn];
int cnt;
void discretiz() {
std::sort(A2 + 1, A2 + n + 1);
cnt = std::unique(A2 + 1, A2 + 1 + n) - A2 - 1;
}
int get_p(ll v) {
int ret = (std::lower_bound(A2 + 1, A2 + 1 + cnt, v) - A2);
if(A2[ret] > v) ret --;
return ret;
}
int T[maxn];
void init_tree() {
T[0] = build_tree(1, cnt);
for(int i = 1; i <= n; i ++) {
T[i] = update(T[i - 1], 1, cnt, get_p(A[i]), A[i]);
}
}
const ll INF = 1000000000LL;
ll calc_sum(int l, int r, int typ) {
if(typ == 0) return 0LL;
return query(T[r], 1, cnt, 1, typ) - query(T[l - 1], 1, cnt, 1, typ);
}
ll calc(int l, int r) {
ll maxv = 0LL, R = 1LL;
maxv = calc_sum(l, r, get_p(R));
while(maxv >= R && R < INF) {
R = std::min(maxv + 1LL, INF);
maxv = calc_sum(l, r, get_p(R));
}
return maxv + 1LL;
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
scanf("%lld", &A[i]); A2[i] = A[i];
}
discretiz(); init_tree();
int q; scanf("%d", &q);
while(q --) {
int l, r; scanf("%d%d", &l, &r);
printf("%lld\n", calc(l, r));
}
return 0;
}
[LibreOJ 2146][SHOI2017]寿司餐厅
建了半天图……搞出来了几个神奇的最小割……
然后发现这TM不就是最简单的最大权闭合子图吗……
首先和正负点权普通的最大权闭合子图一样，然后任意\(d_{i, i}\)去依赖点\(i\)。对于一个\(d_{i, j}(i < j)\)，我们要保证那一天\([i, j]\)全部被吃了，所以说它需要依赖\(d_{i + 1, j}\)和\(d_{i, j - 1}\)。
每种寿司的费用也不难处理，我们把\(mx^2\)和\(cx\)分开考虑。\(mx^2\)单独建点，很显然代号为所有\(x\)都要依赖它。对于\(cx\)，可以视为所有点有一个\(x\)的费用。
然后van了……
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
const int maxn = 5000005;
const int maxm = 5000005;
int first[maxn];
int next[maxm], to[maxm], cap[maxm], flow[maxm];
int gcnt = 0;
void add_edge(int u, int v, int f) {
gcnt ++;
next[gcnt] = first[u];
first[u] = gcnt;
to[gcnt] = v;
cap[gcnt] = f;
flow[gcnt] = 0;
}
int rev(int i) {
if(1 & i) {
return i + 1;
} else {
return i - 1;
}
}
void ins_edge(int u, int v, int f) {
add_edge(u, v, f); add_edge(v, u, 0);
}
int s, t;
int d[maxn];
bool bfs() {
#ifdef LOCAL
// puts("A new round :");
#endif
static bool vis[maxn];
memset(vis, 0, sizeof(vis));
d[s] = 1; vis[s] = true;
std::queue<int> Q; Q.push(s);
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for(int i = first[u]; i; i = next[i]) {
int v = to[i];
if(cap[i] > flow[i] && !vis[v]) {
d[v] = d[u] + 1; vis[v] = true;
#ifdef LOCAL
// printf("d[%d] : %d\n", v, d[v]);
#endif
Q.push(v);
}
}
}
return vis[t];
}
int cur[maxn];
int dfs(int u, int a) {
#ifdef LOCAL
// printf("State (%d, %d)\n", u, a);
#endif
if(a == 0 || u == t) return a;
int fl = 0;
for(int &i = cur[u]; i; i = next[i]) {
int v = to[i]; int f;
if(d[v] == d[u] + 1 && (f = dfs(v, std::min(cap[i] - flow[i], a))) > 0) {
fl += f; a -= f;
flow[i] += f; flow[rev(i)] -= f;
if(a == 0) break;
}
}
if(a > 0) d[u] = -1;
return fl;
}
int tot;
int dinic() {
int ans = 0;
while(bfs()) {
for(int i = 0; i <= tot; i ++) cur[i] = first[i];
ans += dfs(s, 0x7fffffff);
}
return ans;
}
int ma_p[105], ma_m[1005];
int ma_d[105][105];
int main() {
tot = 1;
int n, m; scanf("%d%d", &n, &m);
int ans = 0;
s = 0, t = 1;
for(int i = 1; i <= n; i ++) {
int a; scanf("%d", &a);
ma_p[i] = ++ tot;
#ifdef LOCAL
printf("p[%d] : %d\n", i, tot);
#endif
if(!ma_m[a]) {
ma_m[a] = ++ tot;
#ifdef LOCAL
printf("m[%d] : %d\n", a, tot);
#endif
ins_edge(tot, 1, m * a * a);
}
ins_edge(ma_p[i], 1, a);
ins_edge(ma_p[i], ma_m[a], 0x7fffffff);
}
for(int i = 1; i <= n; i ++) {
ma_d[i][i] = ++ tot;
for(int j = i + 1; j <= n; j ++) {
ma_d[i][j] = ++ tot;
#ifdef LOCAL
printf("ma_d[%d][%d] : %d\n", i, j, tot);
#endif
}
}
for(int i = 1; i <= n; i ++) {
int d_i; scanf("%d", &d_i);
if(d_i >= 0) {
ans += d_i;
ins_edge(0, ma_d[i][i], d_i);
} else {
ins_edge(ma_d[i][i], 1, -d_i);
}
ins_edge(ma_d[i][i], ma_p[i], 0x7fffffff);
for(int j = i + 1; j <= n; j ++) {
scanf("%d", &d_i);
int np = ma_d[i][j];
if(d_i >= 0) {
ans += d_i;
ins_edge(0, np, d_i);
ins_edge(np, ma_d[i][j - 1], 0x7fffffff);
ins_edge(np, ma_d[i + 1][j], 0x7fffffff);
} else {
ins_edge(np, 1, -d_i);
ins_edge(np, ma_d[i][j - 1], 0x7fffffff);
ins_edge(np, ma_d[i + 1][j], 0x7fffffff);
}
}
}
ans -= dinic();
#ifdef LOCAL
for(int i = 0; i <= tot; i ++) {
for(int j = first[i]; j; j = next[j]) {
if(!(j & 1)) continue;
int v = to[j];
if(cap[j] == flow[j]) {
printf("Edge (%d, %d, %d) deleted.\n", i, v, cap[j]);
}
}
}
#endif
printf("%d\n", ans);
return 0;
}
[LibreOJ 2142][SHOI2017]相逢是问候
f**********ck我终于肝掉这道题了……在这种辣鸡题上浪费了大量时间
首先一堆\(c\)套起来的幂让我们想到了上帝与集合的正确用法那道题（这题题解我屯到现在没写，还是算了吧就写这题得了）……那让我们试试欧拉降幂公式？
观察欧拉降幂公式
\[a^x\equiv a^{x\mod \varphi(m) + \varphi(m)}\pmod{m}(a\geq m)\]
在多次降幂之后，最后肯定存在一个膜数为1，最后在对这一个地方进行操作的话，虽然\(A[i]\)的位置会被移到更高的次幂上，但是开始出现膜数1的地方一定只能取到1了，所以再对这些地方操作是不合理的。
每次取\(\varphi(x)\)都会使数至少下降一半，所以一个数最多被操作\(\log_2 p\)次。
然后我就跪了（虽然在BZOJ上水过去了），后来手肝gprof发现瓶颈在快速幂（逃
然后这TM怎么优化……膜了一发题解发现正解非常的KBS……
对于一个幂，他的指数肯定可以表示为\(2^{16} a + b\)且\(a\)最大的形式……然后我们可能用到的膜数是很少的，对于每种膜数大力预处理可能的\(b\)的答案和\(a\)的答案，然后求一次幂就\(O(1)\)了……
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <utility>
#include <climits>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
const int maxn = 50005;
const int maxno = maxn << 2;
const int siz = 65536;
typedef long long ll;
inline ll phi(ll x) {
ll bd = sqrt(x + 0.5);
ll ans = x;
for(ll i = 2; i <= bd; i ++) {
if(x % i == 0LL) {
ans = ans / i * (i - 1LL);
while(x % i == 0LL) {
x /= i;
}
}
}
if(x > 1LL) ans = ans / x * (x - 1LL);
return ans;
}
int n, m;
ll p, c;
ll f[100]; int fn, bd;
ll pow1[70][siz], pow2[70][siz];
inline void process() {
f[0] = p; fn = 1LL;
for(int i = 1; ; i ++) {
f[i] = phi(f[i - 1]);
if(f[i] == 1LL) {
fn = i;
break;
}
}
ll tmp = 1LL; bd = 0;
if(c != 1LL) {
while(tmp * c < p) {
bd ++; tmp *= c;
}
} else {
bd = 0x7fffffff;
}
f[69] = LLONG_MAX;
for(int i = 0; i <= fn; i ++) {
ll c1 = c % f[i]; ll c2 = c1;
int t = 16; while(t --) c2 = (c2 * c2) % f[i];
pow1[i][0] = 1LL; if(i == fn) pow1[i][0] = 0;
for(int j = 1; j < siz; j ++) pow1[i][j] = (pow1[i][j - 1] * c1) % f[i];
pow2[i][0] = 1LL; if(i == fn) pow2[i][0] = 0;
for(int j = 1; j < siz; j ++) pow2[i][j] = (pow2[i][j - 1] * c2) % f[i];
}
int i = 69;
for(int g = 0; g <= 0; g ++) {
ll c1 = c % f[i]; ll c2 = c1;
int t = 16; while(t --) c2 = (c2 * c2) % f[i];
pow1[i][0] = 1LL;
for(int j = 1; j < siz; j ++) pow1[i][j] = (pow1[i][j - 1] * c1) % f[i];
pow2[i][0] = 1LL;
for(int j = 1; j < siz; j ++) pow2[i][j] = (pow2[i][j - 1] * c2) % f[i];
}
}
inline ll pow_mod(ll a, ll b, ll p) {
return (pow1[p][b & (siz - 1)] * pow2[p][b >> 16]) % f[p];
}
ll A[maxn];
int be_done[maxn]; ll sumv[maxno];
bool break_down[maxno];
inline void maintain(int o) {
int lc = o << 1, rc = o << 1 | 1;
sumv[o] = (sumv[lc] + sumv[rc]);
if(sumv[o] >= p) sumv[o] -= p;
break_down[o] = (break_down[lc] && break_down[rc]);
}
inline ll get_ans(int i) {
register ll up;
for(int j = be_done[i]; j >= 0; j --) {
if(j == be_done[i]) {
up = A[i];
} else {
if(up > bd) {
up = pow_mod(c % f[j], up, j) + f[j];
} else {
up = pow_mod(c, up, 69);
}
}
}
return up;
}
void build_tree(int o, int L, int R) {
if(L == R) {
be_done[L] = 0;
break_down[o] = 0;
sumv[o] = A[L];
} else {
int M = (L + R) / 2;
build_tree(o << 1, L, M);
build_tree(o << 1 | 1, M + 1, R);
maintain(o);
}
}
int ql, qr;
void modify(int o, int L, int R) {
if(L == R) {
be_done[L] ++;
if(c == 1LL) {
sumv[o] = 1LL;
break_down[o] = true;
} else {
sumv[o] = get_ans(L) % p;
if((A[L] != 0LL && be_done[L] == fn) || (A[L] == 0LL && be_done[L] == fn + 1)) break_down[o] = true;
}
} else {
int M = (L + R) / 2;
if(ql <= M && !break_down[o << 1]) {
modify(o << 1, L, M);
}
if(qr > M && !break_down[o << 1 | 1]) {
modify(o << 1 | 1, M + 1, R);
}
maintain(o);
}
}
ll query(int o, int L, int R) {
if(ql <= L && R <= qr) {
return sumv[o];
} else {
int M = (L + R) / 2;
ll ans = 0;
if(ql <= M) {
ans = (ans + query(o << 1, L, M));
if(ans >= p) ans -= p;
}
if(qr > M) {
ans = (ans + query(o << 1 | 1, M + 1, R));
if(ans >= p) ans -= p;
}
return ans;
}
}
int main() {
// freopen("17.in", "r", stdin);
// freopen("dummy", "w", stdout);
scanf("%d%d%lld%lld", &n, &m, &p, &c);
process();
for(int i = 1; i <= n; i ++) scanf("%lld", &A[i]);
build_tree(1, 1, n);
while(m --) {
int op; scanf("%d%d%d", &op, &ql, &qr);
if(op == 0) {
modify(1, 1, n);
} else {
printf("%lld\n", query(1, 1, n));
// fflush(stdout);
}
}
return 0;
}
[LibreOJ 114]k大异或和
最近学了一点线性基……所以也就做了一些线性基的题目
这题还算挺简单的吧……先转成求第$s - k + 1$（这里用$s$表示异或和有多少种）大。求出线性基，然后从高位向低位枚举，然后乱搞就行……
唯一的坑就是子集要求非空。这样有可能会出现选不出$0$的情况，但是稍微思索一下可以发现如果$|B| < n$（这里用$B$表示线性基）那么一定可以用$B$里的东西凑出来一个数，然后再和不在线性基里的一个数异或一下，这样就能搞出来$0$了。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
using ll = long long int;
const int maxb = 51;
ll T[maxb];
void insert(ll x) {
for(int i = 50; i >= 0; i --) {
if(!x) break;
if((x & (1LL << i)) == 0) continue;
if(T[i]) {
x ^= T[i];
} else {
for(int j = i - 1; j >= 0; j --) {
if(x & (1LL << j)) {
x ^= T[j];
}
}
for(int j = i + 1; j < maxb; j ++) {
if(T[j] & (1LL << i)) {
T[j] ^= x;
}
}
T[i] = x; break;
}
}
}
#ifdef LOCAL
#define LO "%I64d"
#else
#define LO "%lld"
#endif
int main() {
int sz = 0;
ll tot = 0;
int n; scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
ll x; scanf(LO, &x);
insert(x);
}
for(int i = 0; i < maxb; i ++) if(T[i]) sz ++;
tot = (1LL << sz) - 1LL;
if(sz < n) tot ++;
int m; scanf("%d", &m);
while(m --) {
ll k; scanf(LO, &k);
if(k <= 0LL || k > tot) {
puts("-1");
} else if(sz < n && k == 1LL) {
puts("0");
} else {
k = tot - k + 1LL;
int rest = sz; ll ret = 0;
for(int i = 50; i >= 0; i --) {
if(!T[i]) continue;
rest --;
if(k <= (1LL << rest)) {
ret ^= T[i];
} else {
k -= (1LL << rest);
}
}
printf(LO, ret); puts("");
}
}
return 0;
}
[LibreOJ 2135][ZJOI2015]幻想乡战略游戏
竟然1A了蛤蛤蛤蛤蛤
这题用人话说就是给你一个不会动的树，让你求带权重心。
先解决一个问题：如果要求动态修改点权，并且要求多次询问求某点\(x\)的\(\sum_{i = 1}^n d_i\cdot dist(i, x)\)，怎么做？
很显然对于一个点\(x\)，对它造成贡献的点，可能是在以\(x\)为根的点分子树里的，也可能在\(x\)之外。但是一个不在该点分子树内的点要对\(x\)产生贡献，必须要经过\(x\)在分治树上的祖先。
所以我们可以考虑对每个重心，记录下它这个点分子树中所有点对该重心的贡献、对点分树上的父亲的贡献以及该点分子树的点权和。每次求答案时\(x\)所在的分治子树的贡献很好考虑，那考虑一下其分治树上祖先对\(x\)的贡献就行了。
那带权重心怎么求呢？如果我们把树的根变成带权重心，那么我们会发现越远离根则答案越劣。所以我们如果只往使得答案更小的地方走，那么最后一定会走到带权重心上。
我们考虑把这个过程放点分树上。从整棵树的重心开始往下走，每次如果发现有一条出边指向的点答案更好，那就往这个子结构（不是指向的点而是那个联通块的重心，否则时间复杂度不对）里走。最后走不动了，走到的点就是带权重心了。
求LCA我用的是\(O(logn)\)的树剖而不是\(O(1)\)搞法，但是跑的贼快（可能和树剖常数小有关？）。
吐槽一点，原题提到了每个点的度数不超过20，但是网上几乎所有OJ上该题的题面都没提到这一点……
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <set>
#include <vector>
#include <queue>
#include <stack>
typedef long long ll;
const int maxn = 100005;
const int maxe = maxn << 1;
int first[maxn];
int next[maxe], to[maxe];
ll dist[maxe];
void add_edge(int u, int v, ll d) {
static int cnt = 0;
cnt ++;
next[cnt] = first[u];
first[u] = cnt;
to[cnt] = v;
dist[cnt] = d;
}
int n;
int size[maxn], hson[maxn], fa[maxn], dep[maxn];
ll dis[maxn];
void dfs_1(int x, int father = 0, int depth = 1, ll d = 0) {
size[x] = 1;
fa[x] = father;
dep[x] = depth;
dis[x] = d;
int max_siz = 0;
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(v != father) {
dfs_1(v, x, depth + 1, d + dist[i]);
size[x] += size[v];
if(size[v] > max_siz) {
max_siz = size[v];
hson[x] = v;
}
}
}
}
int dfn[maxn], top[maxn], tid[maxn];
void dfs_2(int x, int father = 0, int a = 1) {
static int dfn_clk = 0;
dfn[x] = ++ dfn_clk;
tid[dfn[x]] = x;
top[x] = a;
if(!hson[x]) {
return;
} else {
dfs_2(hson[x], x, a);
}
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(v != father && v != hson[x]) {
dfs_2(v, x, v);
}
}
}
int lca(int x, int y) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
x = fa[top[x]];
}
if(dep[x] > dep[y]) {
return y;
} else {
return x;
}
}
ll calc_dist(int x, int y) {
int l = lca(x, y);
return dis[x] + dis[y] - 2LL * dis[l];
}
bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int f = 0) {
siz[x] = 1;
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(!vis[v] && v != f) {
gen_siz(v, x);
siz[x] += siz[v];
}
}
}
int nrt, rt;
void gen_rt(int x, int f = 0) {
bool flag = (siz[x] * 2 >= siz[nrt]);
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(!vis[v] && v != f) {
flag = (flag && (siz[v] * 2 <= siz[nrt]));
gen_rt(v, x);
}
}
if(flag) rt = x;
}
ll w[maxn];
int crt, cfa[maxn];
ll pans[maxn], give[maxn], sumv[maxn];
int point2[maxe];
/*
void search_p(int x, std::stack<int> *V, int f = 0) {
V -> push(x);
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(!vis[v] && v != f) {
search_p(v, V, x);
}
}
}
*/
int divide(int x) {
nrt = rt = x;
gen_siz(x); gen_rt(x);
x = rt; vis[x] = true;
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(!vis[v]) {
int ch = divide(v);
point2[i] = ch;
cfa[ch] = x;
}
}
return x;
}
void update(int x, ll delta) {
int p = x;
while(p) {
pans[p] += delta * calc_dist(p, x);
if(p != crt) give[p] += delta * calc_dist(x, cfa[p]);
sumv[p] += delta;
p = cfa[p];
}
}
ll get_ans(int x) {
ll ans = pans[x];
int p = x;
while(p != crt) {
int f = cfa[p];
ans += pans[f] - give[p];
ans += calc_dist(x, f) * (sumv[f] - sumv[p]);
p = cfa[p];
}
return ans;
}
ll get_best() {
int p = crt;
std::stack<int> S;
ll now_ans;
while(true) {
S.push(p); vis[p] = true;
bool fix = true;
now_ans = get_ans(p);
for(int i = first[p]; i; i = next[i]) {
int v = to[i];
if(vis[v]) continue;
if(get_ans(v) < now_ans) {
fix = false;
p = point2[i];
break;
}
}
if(fix) break;
}
while(!S.empty()) {
int u = S.top(); S.pop();
vis[u] = false;
}
return now_ans;
}
int main() {
int q; scanf("%d%d", &n, &q);
for(int i = 0; i < n - 1; i ++) {
int u, v; ll d; scanf("%d%d%lld", &u, &v, &d);
add_edge(u, v, d); add_edge(v, u, d);
}
dfs_1(1); dfs_2(1);
crt = divide(1); memset(vis, 0, sizeof(vis));
while(q --) {
int u, e; scanf("%d%d", &u, &e);
update(u, e);
printf("%lld\n", get_best());
}
return 0;
}
[LibreOJ 6238][Baltic2015]Network
LibreOJ真是好用（以后尽可能少用BZOJ）
这题我觉得真是个意识流神题。
考虑所有度数为1的点（姑且称为叶子），这些点是一定要向外连边的（只要有一个度数为1的树边不在一个环中，肯定就出桥了）。
那是否可以只在这种叶子之间连边？答案是肯定的。假设叶子上形成了足够多的环，那么上面的边可以随便上。
那是否叶子配对连边就行了（这说明答案是\(\lceil \frac{l}{2}\rceil\)，其中\(l\)是叶子的数目）？答案也是肯定的。但这种方案里显然两个结点间有新边则两点不可能在根的同一棵子树里。
然后就有一种乱搞做法：找到一个根使得每个子树的叶子数都不超过总数的一半（这种点很显然存在），然后从这个根开始DFS，把所有叶子按照DFS序排序一遍，前一半向后一半依次连边。如果叶子数目是奇数，那么最后一个可以随便连。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cctype>
#include <utility>
#include <queue>
#include <set>
#include <vector>
using std::vector;
const int maxn = 500005;
vector<int> G[maxn];
int n;
int leaves[maxn];
vector<int> L;
int leavenum = 0;
void calc_leave(int x, int fa = 0) {
if(int(G[x].size()) == 1) {
leaves[x] = 1; L.push_back(x);
leavenum ++;
}
for(auto v : G[x]) {
if(v != fa) {
calc_leave(v, x);
leaves[x] += leaves[v];
}
}
}
int gen_rt(int x, int fa = 0) {
for(auto v : G[x]) {
if(v != fa && leaves[v] * 2 >= leavenum) {
return gen_rt(v, x);
}
}
return x;
}
int dfn[maxn];
void calc_dfn(int x, int fa = 0) {
static int cnt = 0;
dfn[x] = ++ cnt;
for(auto v : G[x]) {
if(v != fa) {
calc_dfn(v, x);
}
}
}
bool cmp(const int &x, const int &y) {
return dfn[x] < dfn[y];
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n - 1; i ++) {
int u, v; scanf("%d%d", &u, &v);
G[u].push_back(v); G[v].push_back(u);
}
calc_leave(1);
int rt = gen_rt(1);
calc_dfn(rt);
sort(L.begin(), L.end(), cmp);
printf("%d\n", (leavenum + 1) / 2);
int half = leavenum / 2;
for(int i = 0; i < half; i ++) {
printf("%d %d\n", L[i], L[i + half]);
}
if(1 & leavenum) {
printf("%d %d\n", L[half - 1], L[leavenum - 1]);
}
return 0;
}
