[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;
}
[SPOJ]LCS
震惊！SAM与AC自动机间的神秘关系，竟然是为了……
考虑到是子串嘛，我们建立\(A\)的后缀自动机，考虑把\(B\)放在上面进行匹配。然后考虑当前节点下面再加一个字符，如果有这个字符的转移那么直接走过去即可。如果没有呢？
观察到SAM上的父亲其实就是一个被儿子包含了的子串，所以这一步走不下去，可以考虑去找父亲解决。所以找到最低的有该转移的祖先，转移过去即可。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
const int maxn = 250005;
const int maxsiz = 30000005;
char buf[maxsiz];
char *cur = buf;
void *alloc(size_t size) {
if(cur - buf + size > maxsiz) {
return malloc(size);
} else {
void *ret = (void*)cur;
cur += size;
return ret;
}
}
int idx(char c) {
return c - 'a';
}
struct Node {
Node *fa;
int len;
Node *ch[26];
};
Node *alloc_node(int len = 0, Node *fa = NULL) {
Node *ret = (Node*)alloc(sizeof(Node));
ret -> len = len; ret -> fa = fa;
memset(ret -> ch, 0, sizeof(ret -> ch));
return ret;
}
Node *rt, *last;
void init_sam() {
rt = alloc_node();
last = rt;
}
void extend(char c) {
int i = idx(c);
Node *np = alloc_node(last -> len + 1);
Node *p = last;
while(p != NULL && p -> ch[i] == NULL) {
p -> ch[i] = np;
p = p -> fa;
}
if(p == NULL) {
np -> fa = rt;
} else {
Node *q = p -> ch[i];
if(q -> len == p -> len + 1) {
np -> fa = q;
} else {
Node *nq = alloc_node(p -> len + 1, q -> fa);
memcpy(nq -> ch, q -> ch, sizeof(q -> ch));
np -> fa = q -> fa = nq;
while(p != NULL && p -> ch[i] == q) {
p -> ch[i] = nq;
p = p -> fa;
}
}
}
last = np;
}
char A[maxn], B[maxn];
int search() {
int n = strlen(B);
Node *u = rt;
int ans = 0, len = 0;
for(int i = 0; i < n; i ++) {
int c = idx(B[i]);
if(u -> ch[c]) {
u = u -> ch[c];
len ++;
} else {
while(u != NULL && u -> ch[c] == NULL) u = u -> fa;
if(u == NULL) {
u = rt; len = 0;
} else {
len = u -> len + 1;
u = u -> ch[c];
}
}
ans = std::max(ans, len);
}
return ans;
}
int main() {
scanf("%s%s", A, B);
int n = strlen(A);
init_sam();
for(int i = 0; i < n; i ++) {
extend(A[i]);
}
printf("%d\n", search());
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;
}
[SPOJ]NSUBSTR
第一次做了一道有一定难度的SAM题……
考虑每个SAM上的结点\(x\)，他的子串表示范围一定是一个区间\([Min(x), Max(x)]\)，然后他的\(Right(x)\)的大小就是该点所代表的每个子串的出现次数。
那么考虑怎么搞出这个\(|Right(x)|\)。我们把每个“实点”（就是在SAM每一次插入后成为\(last\)的结点）的点权钦定为1，其他搞成0。然后每个点的\(|Right(x)|\)就是\(x\)在Right树上的子树的点权和。
然后接下来看上去可以直接做……但是区间chkmax这种黑暗操作，是不是要涉及毒瘤数据结构？
答案是否定的。任何短的子串都是某一个长子串的子串，所以说我们只需要在\(Max(x)\)那个地方chkmax，然后搞个后缀最大值即可。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
const int maxn = 250005;
const int sigma_siz = 26;
struct Node {
int maxl, rs;
Node *fa;
Node *ch[sigma_siz];
};
Node pool[maxn << 1]; Node *tot = pool;
Node *rt = tot, *last = tot;
void extend(int c) {
Node *np = ++ tot;
np -> maxl = last -> maxl + 1; np -> rs = 1;
Node *p = last;
while(p != NULL && p -> ch[c] == NULL) {
p -> ch[c] = np;
p = p -> fa;
}
if(p == NULL) {
np -> fa = rt;
} else {
Node *q = p -> ch[c];
if(q -> maxl == p -> maxl + 1) {
np -> fa = q;
} else {
Node *nq = ++ tot;
nq -> maxl = p -> maxl + 1; nq -> fa = q -> fa;
memcpy(nq -> ch, q -> ch, sizeof(q -> ch));
q -> fa = np -> fa = nq;
while(p != NULL && p -> ch[c] == q) {
p -> ch[c] = nq;
p = p -> fa;
}
}
}
last = np;
}
int first[maxn << 1];
int next[maxn << 2], to[maxn << 2];
int gcnt = 0;
void add_edge(int u, int v) {
gcnt ++;
next[gcnt] = first[u];
first[u] = gcnt;
to[gcnt] = v;
}
int len[maxn << 1], siz[maxn << 1];
int F[maxn];
void dfs(int x) {
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
dfs(v);
siz[x] += siz[v];
}
F[len[x]] = std::max(F[len[x]], siz[x]);
}
int main() {
static char S[maxn];
scanf("%s", S);
int n = strlen(S);
for(int i = 0; i < n; i ++) {
extend(S[i] - 'a');
}
for(int i = 0; i <= (tot - pool); i ++) {
Node *p = pool + i;
len[i] = p -> maxl;
siz[i] = p -> rs;
if(p -> fa) {
int fa = (p -> fa) - pool;
add_edge(fa, i);
}
}
dfs(0);
for(int i = n - 1; i >= 0; i --) {
F[i] = std::max(F[i], F[i + 1]);
}
for(int i = 1; i <= n; i ++) {
printf("%d\n", F[i]);
}
return 0;
}
[BZOJ 3158]千钧一发
好有意思的题呢qwq
首先观察到一点，我们可以把所有装置按照\(a_i\)的奇偶性进行分类（也可以说是黑白染色？）。容易发现任意偶数的最大公约数都至少是2，所以任意偶数间不会互相冲突。然后任意两个奇数的平方和一定不是完全平方数，可以这么证一下（感谢金爷！）：
那两个奇数可以分别设成\(2x + 1\)和\(2y + 1\)，然后他们的平方和就是\(4(x^2 + y^2 + x + y) + 2\)。然后思考一点，就是一个奇数的平方一定是奇数，所以说那个平方和是一个偶数。但是，如果一个完全平方数是偶数，那么它的算术平方根一定是偶数。然而，一个偶数的平方一定是4的倍数。但我们求出的平方和膜4得2，所以不行。
所以说冲突只存在于奇偶性不同的数中。然后用无限大的边来表示冲突关系，最小割高一波即可。
代码（常数卡卡卡……只能用pb_ds的蛤希表了）：
/**************************************************************
Problem: 3158
User: danihao123
Language: C++
Result: Accepted
Time:9676 ms
Memory:130460 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
typedef long long ll;
ll gcd(ll a, ll b) {
if(!b) {
return a;
} else {
return gcd(b, a % b);
}
}
__gnu_pbds::gp_hash_table<ll, bool> S2;
void process_S2() {
for(ll i = 1LL; i * i <= 2000000000000LL; i ++) {
S2[i * i] = true;
}
}
const int maxno = 1050;
const int maxm = 2000500;
int first[maxno];
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 n;
int s, t;
int d[maxno];
bool bfs() {
static bool vis[maxno];
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;
Q.push(v);
}
}
}
return vis[t];
}
int cur[maxno];
int dfs(int u, int a) {
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;
}
const int maxn = 1005;
ll A[maxn]; int B[maxn];
int main() {
process_S2();
scanf("%d", &n); tot = n + 1;
s = 0, t = tot;
std::vector<int> odd, even;
for(int i = 1; i <= n; i ++) {
scanf("%lld", &A[i]);
if(1LL & A[i]) {
odd.push_back(i);
} else {
even.push_back(i);
}
}
int ans = 0;
for(int i = 1; i <= n; i ++) {
scanf("%d", &B[i]); ans += B[i];
if(1LL & A[i]) {
ins_edge(i, t, B[i]);
} else {
ins_edge(s, i, B[i]);
}
}
for(int i = 0; i < even.size(); i ++) {
int p1 = even[i];
for(int j = 0; j < odd.size(); j ++) {
int p2 = odd[j];
if(gcd(A[p1], A[p2]) == 1LL && S2.find(A[p1] * A[p1] + A[p2] * A[p2]) != S2.end()) {
ins_edge(p1, p2, 0x7f7f7f7f);
}
}
}
ans -= dinic();
printf("%d\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;
}
[CF 19E]Fairy
啊啊啊我只会做水题了……
这题就是要求你只删除一条边拆爆所有的奇环，同时不能产生新的gay环，求所有可能的选择方案。
如果说只有一个奇环，那么上面的树边和非树边都是可以拆爆的。但如果有好几个奇环，那么只能选择树边了。奇环的树边部分肯定是若干链，我们只要树上差分标记一下就能求出这些链的交了。
但考虑一件事，如果一个偶环和一个奇环的树边部分相交了，那么删掉其中一边会导致新的奇环出现（证明的话考虑将环异或一下）。所以说在偶环的树边并上的边也不能取。
注意这题图可能不连通……所以要对每个连通块都DFS。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
using ll = long long;
const int maxn = 10005;
const int maxm = 20005;
struct Edge {
int u, v;
int id;
};
std::vector<Edge> G[maxn];
int n, m;
inline void ins_edge(int u, int v, int id) {
G[u].push_back((Edge){u, v, id});
G[v].push_back((Edge){v, u, id});
}
int dep[maxn], anc[maxn][15];
bool vis[maxn];
void dfs_1(int x, int fa = -1) {
vis[x] = true;
anc[x][0] = fa;
for(auto &e : G[x]) {
int v = e.v;
if(!vis[v]) {
dep[v] = dep[x] + 1;
dfs_1(v, x);
}
}
}
int lca(int u, int v) {
if(dep[u] < dep[v]) std::swap(u, v);
for(int j = 14; j >= 0; j --) {
int a = anc[u][j];
if(a != -1 && dep[a] >= dep[v]) u = a;
}
if(u == v) return u;
for(int j = 14; j >= 0; j --) {
int a1 = anc[u][j];
int a2 = anc[v][j];
if(a1 != -1 && a2 != -1 && a1 != a2) {
u = a1, v = a2;
}
}
return anc[u][0];
}
bool used[maxm];
int d1[maxn], d2[maxn];
int o_cnt = 0, o_id;
void dfs_2(int x) {
vis[x] = true;
for(auto &e : G[x]) {
if(used[e.id]) continue;
used[e.id] = true;
int v = e.v;
if(vis[v]) {
int l = lca(x, v);
int dis = dep[x] + dep[v] - 2 * dep[l];
int *d;
if(dis & 1) {
d = d2;
} else {
d = d1;
o_cnt ++;
if(o_cnt == 1) o_id = e.id;
}
d[x] ++; d[v] ++; d[l] -= 2;
} else {
dfs_2(v);
}
}
}
void dfs_3(int x) {
vis[x] = true;
for(auto &e : G[x]) {
int v = e.v;
if(!vis[v]) {
dfs_3(v);
d1[x] += d1[v];
d2[x] += d2[v];
}
}
}
bool allow[maxm], expc[maxm];
void dfs_4(int x) {
vis[x] = true;
for(auto &e : G[x]) {
int v = e.v, id = e.id;
if(!vis[v]) {
if(d1[v] == o_cnt) {
allow[id] = true;
}
if(d2[v] > 0) {
expc[id] = true;
}
dfs_4(v);
}
}
}
std::vector<int> ret;
void solve() {
memset(anc, -1, sizeof(anc));
for(int i = 1; i <= n; i ++) {
if(!vis[i]) dfs_1(i);
}
for(int j = 1; (1 << j) < n; j ++) {
for(int i = 1; i <= n; i ++) {
int a = anc[i][j - 1];
if(a != -1) {
anc[i][j] = anc[a][j - 1];
}
}
}
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i ++) {
if(!vis[i]) dfs_2(i);
}
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i ++) {
if(!vis[i]) dfs_3(i);
}
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i ++) {
if(!vis[i]) dfs_4(i);
}
if(o_cnt == 0) {
for(int i = 1; i <= m; i ++) ret.push_back(i);
} else {
for(int i = 1; i <= m; i ++) {
if(allow[i] && (!expc[i])) {
ret.push_back(i);
} else if(o_cnt == 1 && o_id == i) {
ret.push_back(i);
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++) {
int u, v; scanf("%d%d", &u, &v);
ins_edge(u, v, i);
}
solve();
printf("%d\n", ret.size());
bool flag = false;
for(auto i : ret) {
if(flag) putchar(' ');
flag = true;
printf("%d", i);
}
puts("");
return 0;
}
[BZOJ 1061][NOI2008]志愿者招募
膜了一发BYVoid的题解……竟然搞懂了
这首先是个非常简单的线性规划，就是有若干限制（每天要求的志愿者），形如：
\[P_i = X_a + X_b +\ldots + X_c\geq A_i\]
（这里用\(X_i\)表示第\(i\)类志愿者雇佣了多少个，\(P_i\)表示第\(i\)天的志愿者总数，\(A_i\)同原题面）
且最小化总费用。
既然我们我知道\(P_i\geq A_i\)，那么说明\(P_i\)一定可以表示为\(A_i + Y_i\)（\(Y_i\geq 0\)）。然后这样限制就变成了：
\[P_i = X_a + X_b +\ldots + X_c + Y_i = A_i\]
这个长得很像可以流量平衡的样子，但是流量的变动是表示不了的……
然后假设\(P_0 = 0\)且\(P_{n + 1} = 0\)，这样就可以对限制差分一下，我们就有了\(n + 1\)个限制，然后这个式子就可以流量平衡做了（因为不考虑常数项的话，同一变量只可能在两个限制中出现，并且一正一负，这样就可以通过一个限制送给另一个限制流量来表示了。至于常数项，通过源或者汇连边即可表达）。
然后由于志愿者无限，所以这个东西也一定有解……
我局的我这么渣各位看官看懂的可能性基本上是零……还是推荐BYVoid神犇的题解，比我透彻多了。
代码：
/**************************************************************
Problem: 1061
User: danihao123
Language: C++
Result: Accepted
Time:3164 ms
Memory:6824 kb
****************************************************************/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <utility>
#include <algorithm>
#include <queue>
#include <cassert>
typedef long long ll;
int m, n;
const int maxno = 100005;
const int maxe = 100005;
int first[maxno];
int next[maxe], from[maxe], to[maxe]; ll flow[maxe], cap[maxe];
ll cost[maxe];
int gcnt = 0;
void add_edge(int u, int v, ll f, ll c) {
gcnt ++;
next[gcnt] = first[u];
first[u] = gcnt;
from[gcnt] = u; to[gcnt] = v;
cap[gcnt] = f; flow[gcnt] = 0;
cost[gcnt] = c;
}
int rev(int i) {
return ((i - 1) ^ 1) + 1;
}
int ins_edge(int u, int v, ll f, ll c = 0LL) {
#ifdef LOCAL
printf("Inserting Edge (%d, %d, %lld, %lld)\n", u, v, f, c);
#endif
add_edge(u, v, f, c);
add_edge(v, u, 0, -c);
return gcnt - 1;
}
const ll LINF = 0x7f7f7f7f7f7f7f7fLL;
int tot;
bool spfa(int s, int t, ll &f, ll &c) {
static ll d[maxno];
static bool inq[maxno];
static ll a[maxno]; static int p[maxno];
std::fill(d, d + tot + 1, LINF);
std::fill(inq, inq + tot + 1, false);
std::fill(a, a + tot + 1, 0LL);
std::fill(p, p + tot + 1, 0);
d[s] = 0;
std::queue<int> Q; Q.push(s); inq[s] = true;
a[s] = LINF;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for(int i = first[u]; i; i = next[i]) {
if(cap[i] > flow[i]) {
int v = to[i];
if(d[v] > d[u] + cost[i]) {
d[v] = d[u] + cost[i];
a[v] = std::min(a[u], cap[i] - flow[i]); p[v] = i;
if(!inq[v]) {
Q.push(v); inq[v] = true;
}
}
}
}
}
if(a[t] == 0LL) return false;
f += a[t];
c += a[t] * d[t];
for(int e = p[t]; e; e = p[from[e]]) {
flow[e] += a[t];
flow[rev(e)] -= a[t];
}
return true;
}
void mcmf(int s, int t, ll &f, ll &c) {
while(spfa(s, t, f, c));
}
const int maxn = 1005, maxm = 10005;
int E[maxn];
int A[maxn], D[maxn];
int main() {
scanf("%d%d", &n, &m);
int s = 0, t = n + 2; tot = n + 2;
for(int i = 1; i <= n; i ++) scanf("%d", &A[i]);
for(int i = 1; i <= n + 1; i ++) {
D[i] = A[i] - A[i - 1];
if(D[i] >= 0) {
E[i] = ins_edge(s, i, D[i]);
} else {
E[i] = ins_edge(i, t, -D[i]);
}
}
for(int i = 1; i <= n; i ++) {
ins_edge(i + 1, i, LINF);
}
while(m --) {
int S, T, C; scanf("%d%d%d", &S, &T, &C);
ins_edge(S, T + 1, LINF, C);
}
ll f = 0, c = 0; mcmf(s, t, f, c);
printf("%lld\n", c);
return 0;
}
[BZOJ 3171][TJOI2013]循环格
流量平衡入门中……
我竟然想民白了……
这个题就是要求每个点在且仅在一个环中，这样每个点的入、出度都是1。出度肯定是1，接下来我们想想怎么保证入度为1。
我们建两排点（也可以说是拆点？），一排表示流出，一排表示接受。然后流出点向相邻的接收点连边，费用的话考虑是否和原来这一格的方向不一样就行了。
这个不需要判断是否满流啥的……因为一定有解（比如说每个行构成一个环啥的）。
代码：
/**************************************************************
Problem: 3171
User: danihao123
Language: C++
Result: Accepted
Time:28 ms
Memory:13844 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
const int maxn = 20;
typedef long long ll;
char S[maxn][maxn];
int tot = 0; int num[maxn][maxn][2];
int R, C;
char D[4] = {'L', 'R', 'U', 'D'};
int tow(int i, int j, char dir, int flag) {
int dx = 0, dy = 0;
if(dir == 'L') {
dx = -1;
} else if(dir == 'R') {
dx = 1;
} else if(dir == 'U') {
dy = -1;
} else if(dir == 'D') {
dy = 1;
}
int nx = (i + dy + R) % R;
int ny = (j + dx + C) % C;
return num[nx][ny][flag];
}
const int maxno = 100005;
const int maxe = 400005;
int first[maxno];
int next[maxe], from[maxe], to[maxe], flow[maxe], cap[maxe];
ll cost[maxe];
int gcnt = 0;
void add_edge(int u, int v, int f, ll c) {
gcnt ++;
next[gcnt] = first[u];
first[u] = gcnt;
from[gcnt] = u; to[gcnt] = v;
cap[gcnt] = f; flow[gcnt] = 0;
cost[gcnt] = c;
}
int rev(int i) {
return ((i - 1) ^ 1) + 1;
}
void ins_edge(int u, int v, int f, ll c = 0LL) {
#ifdef LOCAL
printf("Inserting Edge (%d, %d, %d, %lld)\n", u, v, f, c);
#endif
add_edge(u, v, f, c);
add_edge(v, u, 0, -c);
}
const ll LINF = 0x7f7f7f7f7f7f7f7fLL;
bool spfa(int s, int t, int &f, ll &c) {
static ll d[maxno];
static bool inq[maxno];
static int a[maxno], p[maxno];
std::fill(d, d + tot + 1, LINF);
std::fill(inq, inq + tot + 1, false);
std::fill(a, a + tot + 1, 0);
std::fill(p, p + tot + 1, 0);
d[s] = 0;
std::queue<int> Q; Q.push(s); inq[s] = true;
a[s] = 0x7fffffff;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for(int i = first[u]; i; i = next[i]) {
if(cap[i] > flow[i]) {
int v = to[i];
if(d[v] > d[u] + cost[i]) {
d[v] = d[u] + cost[i];
a[v] = std::min(a[u], cap[i] - flow[i]); p[v] = i;
if(!inq[v]) {
Q.push(v); inq[v] = true;
}
}
}
}
}
if(a[t] == 0) return false;
f += a[t];
c += (ll(a[t])) * d[t];
for(int e = p[t]; e; e = p[from[e]]) {
flow[e] += a[t];
flow[rev(e)] -= a[t];
}
return true;
}
void mcmf(int s, int t, int &f, ll &c) {
while(spfa(s, t, f, c));
}
int main() {
tot = 1; int s = 0, t = 1;
scanf("%d%d", &R, &C);
for(int i = 0; i < R; i ++) {
scanf("%s", S[i]);
for(int j = 0; j < C; j ++) {
num[i][j][0] = ++ tot;
num[i][j][1] = ++ tot;
}
}
for(int i = 0; i < R; i ++) {
for(int j = 0; j < C; j ++) {
ins_edge(s, num[i][j][0], 1);
ins_edge(num[i][j][1], t, 1);
for(int it = 0; it < 4; it ++) {
int u = num[i][j][0];
int v = tow(i, j, D[it], 1);
ins_edge(u, v, 1, (D[it] == S[i][j]) ? 0LL : 1LL);
}
}
}
int f = 0; ll c = 0;
mcmf(s, t, f, c);
printf("%lld\n", c);
return 0;
}
[UOJ 110][APIO2015]Bali Sculptures
第一次做subtask题= =其实这题也没啥难度吧
其实就是两个subtask……
对于第一个subtask，就是满足\(1\leq n\leq 100\)且\(1\leq a\leq b\leq n\)。我们应该优先满足高位为\(0\)，于是乎可以贪心，从高位枚举到低位，看是否能在满足之前几位的限制条件的同时满足这一位答案为\(0\)。这个判定过程的话，可以设计状态\(d[i][k]\)表示前\(i\)位割成\(k\)段是否满足约束条件，枚举断点\(O(n)\)转移。
第二个subtask，虽然有\(n\leq 2000\)但是满足\(a = 1\)。这意味着分段数想怎么小就怎么小，所以我们可以直接去求这个序列要满足限制条件的话最少可以割成几段，这样的话第二维就可以省掉了。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const int maxn = 2005;
ll Y[maxn], S[maxn];
int n, a, b;
const int maxb = 41;
ll st = 0;
namespace Task1 {
bool d[105][105];
bool dp(int bi) {
memset(d, 0, sizeof(d));
d[0][0] = true;
for(int i = 1; i <= n; i ++) {
for(int k = 1; k <= b; k ++) {
for(int j = 0; j < i; j ++) {
ll sum = S[i] - S[j];
if((sum & (st | (1LL << bi))) == 0LL) {
d[i][k] = (d[i][k] || d[j][k - 1]);
}
}
}
}
for(int k = a; k <= b; k ++) {
if(d[n][k]) return true;
}
return false;
}
};
namespace Task2 {
int d[maxn];
bool dp(int bi) {
d[0] = 0;
for(int i = 1; i <= n; i ++) {
d[i] = 0x3f3f3f3f;
for(int j = 0; j < i; j ++) {
ll sum = S[i] - S[j];
if(!(sum & (st | (1LL << bi)))) {
d[i] = std::min(d[i], d[j] + 1);
}
}
}
return (d[n] <= b);
}
};
ll solve() {
ll ans = 0;
for(int i = maxb; i >= 0; i --) {
bool flag = n <= 100 ? Task1::dp(i) : Task2::dp(i);
if(flag) {
st |= (1LL << i);
} else {
ans |= (1LL << i);
}
}
return ans;
}
int main() {
scanf("%d%d%d", &n, &a, &b);
for(int i = 1; i <= n; i ++) {
scanf("%lld", &Y[i]);
S[i] = S[i - 1] + Y[i];
}
printf("%lld\n", solve());
return 0;
}
