Robert 的火车旅行
线段树合并
对于不在环上的直接线段树合并统计，对于环上的，第一圈边线段树合并边统计，第二圈统计上上一圈没统计的就行
Code
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 5e5+10;
int n, k, cnt, top, tot;
int p[maxn], head[maxn], dep[maxn];
int rt[maxn], sta[maxn], a[maxn], cc[maxn], ans[maxn];
bool cir[maxn], vis[maxn];
struct Edge {
int to, nxt;
}e[maxn<<1];
struct Node {
int ls, rs, siz;
}t[maxn*25];
int read(int x = 0, bool f = 0, char ch = getchar()) {
for(;ch < '0' || ch > '9';ch = getchar()) f = ch=='-';
for(;ch >= '0' && ch <= '9';ch = getchar()) x = (x<<3)+(x<<1)+(ch&15);
return f ? -x : x;
}
void add(int x, int y) {
e[++cnt] = (Edge){y, head[x]}, head[x] = cnt;
}
void Insert(int &rt, int l, int r, int v) {
if(!rt) rt = ++tot;
++t[rt].siz;
if(l == r) return;
int mid = (l+r)/2;
if(v <= mid) Insert(t[rt].ls, l, mid, v);
else Insert(t[rt].rs, mid+1, r, v);
}
int Query(int rt, int l, int r, int x, int y) {
if(x <= l && r <= y) return t[rt].siz;
int mid = (l+r)/2, ret = 0;
if(x <= mid) ret += Query(t[rt].ls, l, mid, x, y);
if(y > mid) ret += Query(t[rt].rs, mid+1, r, x, y);
return ret;
}
int merge(int rt1, int rt2) {
if(!rt1 || !rt2) return rt1|rt2;
t[rt1].siz += t[rt2].siz;
t[rt1].ls = merge(t[rt1].ls, t[rt2].ls);
t[rt1].rs = merge(t[rt1].rs, t[rt2].rs);
return rt1;
}
void dfs(int x) {
vis[x] = 1;
for(int i = head[x];i;i = e[i].nxt) {
int y = e[i].to;
if(cir[y]) continue;
dep[y] = dep[x]+1;
dfs(y);
rt[x] = merge(rt[x], rt[y]);
}
Insert(rt[x], 1, n, dep[x]);
ans[x] = Query(rt[x], 1, n, dep[x], dep[x]+k);
}
int main() {
freopen("robert.in","r",stdin);
freopen("robert.out","w",stdout);
n = read(), k = read();
for(int i = 1;i <= n; ++i) add(p[i]=read(), i);
for(int i = 1;i <= n; ++i) {
if(vis[i]) continue;
int x = i;
sta[++top] = x, vis[x] = 1;
while(!vis[p[x]]) sta[++top] = x = p[x], vis[x] = 1;
int st = p[x], c = 0;
do {
x = sta[top--];
cir[x] = 1, dep[x] = ++c, a[c] = x;
} while(x != st);
int now = 0;
for(int j = c;j >= 1; --j) {
dfs(x=a[j]);
now = merge(rt[x], now);
ans[x] = Query(now, 1, n, dep[x], dep[x]+k);
if(k >= c) ans[x] -= Query(now, 1, n, dep[x], dep[x]+k-c);
}
for(int j = c;j >= 1; --j) {
x = a[j];
if(k >= (c-j+1)) ans[x] += Query(now, 1, n, 1, 1+k-(c-j+1));
}
}
for(int i = 1;i <= n; ++i) printf("%d
", ans[i]);
return 0;
}
钻石教练老姚的神仙LIS
网络流
-
第一问 n^2 dp
-
第二问对每个数，拆出、入点，出点向入点连1流量边，根据dp值的转移，出点连向入点，然后s连向所有dp为1的点的入点有1流量边，所有dp为len的点的出点连向t有1流量的边，直接最大流
-
第三问对于s向1，1向1+n，n向n+n，n+n向t的边流量改为inf即可
注意特判只有一个数的的情况，ans=1，这一个数不要和s,t都有inf边
Code
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2e3+10;
const int maxm = 3e6+10;
const int inf = 1e9;
int s, t, n, cnt, len, a[maxn], head[maxn], f[maxn];
int cur[maxn], dep[maxn];
struct Edge {
int to, nxt, flow;
}e[maxm];
void add(int x, int y, int flow) {
e[++cnt] = (Edge){y, head[x], flow}, head[x] = cnt;
e[++cnt] = (Edge){x, head[y], 0}, head[y] = cnt;
}
bool bfs() {
queue <int> q;
memset(cur, 0, sizeof cur);
memset(dep, 0, sizeof dep);
dep[s] = 1, cur[s] = head[s], q.push(s);
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x];i;i = e[i].nxt) {
int y = e[i].to;
if(e[i].flow && !dep[y]) {
dep[y] = dep[x]+1;
cur[y] = head[y];
if(y == t) return 1;
q.push(y);
}
}
}
return 0;
}
int dinic(int x, int flow) {
if(x == t) return flow;
int rest = flow;
for(int i = cur[x];i && rest;i = e[i].nxt) {
cur[x] = i;
int y = e[i].to;
if(e[i].flow && dep[y] == dep[x]+1) {
int tmp = dinic(y, min(rest, e[i].flow));
rest -= tmp;
e[i].flow -= tmp;
e[i^1].flow += tmp;
}
}
return flow-rest;
}
void Q1() {
for(int i = 1;i <= n; ++i) {
f[i] = 1;
for(int j = 1;j < i; ++j) {
if(a[j] <= a[i]) f[i] = max(f[i], f[j]+1);
}
len = max(len, f[i]);
}
printf("%d
", len);
}
void Add() {
memset(head, 0, sizeof head), cnt = 1;
for(int i = 1;i <= n; ++i) {
add(i, n+i, 1);
if(f[i] == 1) add(s, i, 1);
if(f[i] == len) add(i+n, t, 1);
}
for(int i = 1;i <= n; ++i) {
for(int j = 1;j < i; ++j) {
if(a[j] <= a[i] && f[i] == f[j]+1) add(j+n, i, 1);
}
}
}
void Q2() {
Add();
int ans = 0;
while(bfs()) ans += dinic(s, inf);
printf("%d
", ans);
}
void Q3() {
Add();
add(1, 1+n, inf);
add(n, n+n, inf);
if(f[1] == 1) add(s, 1, inf);
if(f[n] == len && n > 1) add(n+n, t, inf);
int ans = 0;
while(bfs()) ans += dinic(s, inf);
printf("%d
", ans);
}
int main() {
scanf("%d", &n), s = n*2+1, t = n*2+2;
for(int i = 1;i <= n; ++i) scanf("%d", &a[i]);
Q1(), Q2(), Q3();
return 0;
}
组合空间
子集反演，高维前缀和
f[s]表示只有状态s表示的位置未被覆盖
g[s]表示至少状态s表示的位置未被覆盖
那么ans=f[0]
子集反演 (f[S]=sum_{Ssubseteq T}(-1)^{left | T ight|-left | S ight|}g[T])
高维前缀和求出num[s]表示s表示的位置为0的集合个数
(g[s]=2^{num[s]}-1)，其他的都不选，这num[s]个选不选都行，但除去都不选的。
Code
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1<<22|10;
const int mod = 1e9+7;
int n, m, maxs, ans, pw[(int)1e6+10], c[maxn];
int read(int x = 0, bool f = 0, char ch = getchar()) {
for(;ch < '0' || ch > '9';ch = getchar()) f = ch == '-';
for(;ch >= '0' && ch <= '9';ch = getchar()) x = (x<<3)+(x<<1)+(ch&15);
return f ? -x : x;
}
int main() {
freopen("longdie.in","r",stdin);
freopen("longdie.out","w",stdout);
n = read(), m = read(), maxs = (1<<n)-1;
pw[0] = 1;
for(int i = 1;i <= m; ++i) pw[i] = pw[i-1]*2%mod;
for(int i = 1;i <= m; ++i) {
int k = read(), S = maxs;
for(int j = 1;j <= k; ++j) S ^= (1<<(read()-1));
++c[S];
}
for(int i = 1;i <= n; ++i) {
for(int j = 0;j <= maxs; ++j) {
if(j&(1<<(i-1))) c[j^(1<<(i-1))] += c[j];
}
}
for(int i = 0;i <= maxs; ++i) {
int g = pw[c[i]]-1;
int cc = 0, x = i;
for(;x;x -= (x&-x)) ++cc;
(ans += (cc&1) ? mod-g : g) %= mod;
}
printf("%d
", ans);
return 0;
}