Xor-MST
来源：CF888G
考虑如何用 $\mathrm{kruskal}$ 求最小生成树：
将所有边权从小到大排序然后依次加入，能加则加，不加拉倒.
这道题是异或，不妨对所有点权建立一个 $\mathrm{trie}$, 这样 $\mathrm{trie}$ 的叶子就代表点.
然后显然两个点的 $\mathrm{lca}$ 深度越大说明这两个点的异或和越小.
考虑如何求 $\mathrm{trie}$ 中以 $\mathrm{x}$ 为根的 $\mathrm{MST}$.
显然 $\mathrm{lca}$ 为 $\mathrm{x}$ 的边会是子树中边权最大的，所以要后加.
递归处理左右子树后显然左右子树无任何交集，需要加入 $\mathrm{lca}$ 为 $x$ 保证联通.
而 $x$ 为 $\mathrm{lca}$ 的边权又是最大的，不过只加入一次，所以正确性是保证的.
这个边权的就用启发式合并然后在 $\mathrm{trie}$ 树中的另一个子树中查询就能求出来了.
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#define N 200009
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
ll fin ;
const int inf = 1200000000;
int idx;
int ch[N * 30][2],bin[40], a[N], si[N * 30 ], n , tot, L[N * 30 ], R[N * 30 ];
void init() {
for(int i=0;i<=29;++i) {
bin[i] = 1 << i;
}
}
void insert(int x, int dep, int v) {
++ si[x];
if(!L[x]) L[x] = idx;
R[x] = idx;
if(dep < 0) return ;
if(v & bin[dep]) {
if(!ch[x][1]) ch[x][1] = ++ tot;
insert(ch[x][1], dep - 1, v);
}
else {
if(!ch[x][0]) ch[x][0] = ++ tot;
insert(ch[x][0], dep - 1, v);
}
}
int query(int x, int dep, int v) {
if(dep < 0) return 0;
int l = (v & bin[dep]) > 0;
if(ch[x][l]) return query(ch[x][l], dep - 1, v);
else return query(ch[x][l ^ 1], dep - 1, v) + bin[dep];
}
void dfs(int x,int dep) {
if(dep < 0) return ;
if(!ch[x][0] && !ch[x][1]) return ;
if(ch[x][0] && ch[x][1]) {
dfs(ch[x][0], dep - 1);
dfs(ch[x][1], dep - 1);
// current edge is 2 ^ dep.
int lsize = si[ch[x][0]];
int rsize = si[ch[x][1]];
int ans = inf;
if(lsize > rsize) {
for(int i = L[ch[x][1]]; i <= R[ch[x][1]]; ++ i) {
ans = min(ans, query(ch[x][0], dep - 1, a[i]) + bin[dep]);
}
}
else {
for(int i = L[ch[x][0]]; i <= R[ch[x][0]]; ++ i) {
ans = min(ans, query(ch[x][1], dep - 1, a[i]) + bin[dep]);
}
}
fin += ans;
}
else if(ch[x][0]) {
dfs(ch[x][0], dep - 1);
}
else {
dfs(ch[x][1], dep - 1);
}
}
int main() {
// setIO("input");
init();
scanf("%d",&n);
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
}
sort(a+1,a+1+n);
// 编号连续.
for(int i=1;i<=n;++i) {
idx = i;
insert(0, 29, a[i]);
}
dfs(0, 29);
printf("%lld\n", fin);
return 0;
}
Frequency Problem (Easy Version)
来源：CF1446D1
需要用到一些结论的题.
当题目中出现众数，树上最长距离等字眼时很大可能答案会包含这些点.
结论：对于最优答案，一定包含序列众数.
如果答案没有包含序列众数，则一定可以不断加入序列众数来进行调整.
设这个数字为 $\mathrm{k}$, 然后每次枚举答案序列中和 $\mathrm{k}$ 等价的数字.
虽然每一次枚举 $\mathrm{i}$ 时算出的答案并不一定是正确的，但是最后一定能算出正确结果（类似悬线法 ？ ）
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 200009
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n , a[N], cn[N], val[N], neg[N], pos[N];
void solve(int c0, int mx) {
int ans = 0;
for(int i = 1; i <= 100 ; ++ i) {
for(int j = 1; j <= n; ++ j) {
int v;
if(a[j] == c0) v = -1;
else if(a[j] == i) v = 1;
else {
v = 0;
}
val[j] = v;
}
pos[0] = neg[0] = n + 1;
int sum = 0;
for(int j = n; j >= 1; -- j) {
sum += val[j];
if(sum >= 0) {
if(pos[sum]) ans = max(ans, pos[sum] - j);
if(!pos[sum]) {
pos[sum] = j;
}
}
else {
sum *= -1;
if(neg[sum]) ans = max(ans, neg[sum] - j);
if(!neg[sum]) {
neg[sum] = j;
}
sum *= -1;
}
}
for(int p = 0; p <= n + 1; ++ p) pos[p] = neg[p] = 0;
}
printf("%d\n", ans);
}
int main() {
// setIO("input");
scanf("%d",&n);
int mx = 0, c0 = 0;
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
cn[a[i]] ++ ;
mx = max(mx, cn[a[i]]);
}
for(int i = 1; i <= 100; ++ i) if(cn[i] == mx) {
if(c0) {
printf("%d\n", n);
return 0;
}
else {
c0 = i;
}
}
// printf("%d\n", c0);
// 出现次数最多的数字为 c0.
solve(c0, mx);
return 0;
}
Berland Beauty
来源：CF1296F
可以将最小值从小到大排序，然后按照权值大小依次加入.
显然，如果一条边会被后面权值大的边覆盖则不能覆盖当前权值.
否则，若一条边还没有被覆盖就用当前权值覆盖.
然后到最后检查一下是否合法即可.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 5109
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n ;
vector<int>G[N];
int fa[20][N], dep[N], mk[N], mx[N], fin[N], m;
struct data {
int x, y, val;
data(int x = 0, int y = 0, int val = 0):x(x),y(y),val(val){}
}a[N];
bool cmp(data i, data j) {
return i.val < j.val;
}
int A[N], B[N], top;
void dfs(int x, int ff) {
fa[0][x] = ff;
dep[x] = dep[ff] + 1;
for(int i=1;i<19;++i) {
fa[i][x]=fa[i-1][fa[i-1][x]];
}
for(int i = 0 ; i < G[x].size() ; ++ i) {
int v = G[x][i];
if(v == ff) continue;
dfs(v, x);
}
}
int get_lca(int x, int y) {
if(dep[x] > dep[y]) swap(x, y);
if(dep[x] != dep[y]) {
for(int i = 18; i >= 0 ; -- i) {
if(dep[fa[i][y]] >= dep[x]) y = fa[i][y];
}
}
if(x == y) return x;
for(int i = 18; i >= 0 ; -- i) {
if(fa[i][x] != fa[i][y]) {
x = fa[i][x];
y = fa[i][y];
}
}
return fa[0][x];
}
int main() {
// setIO("input");
scanf("%d",&n);
for(int i=1;i<n;++i) {
int x, y;
scanf("%d%d",&x,&y);
G[x].pb(y);
G[y].pb(x);
++top;
A[top] = x;
B[top] = y;
}
dfs(1, 0);
scanf("%d", &m);
for(int i = 1; i <= m ;++ i) {
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].val);
}
sort(a + 1, a + 1 + m, cmp);
for(int i = 1; i <= m ; ++ i) {
int lca = get_lca(a[i].x, a[i].y);
for(int j = a[i].x; j != lca; j = fa[0][j])
mx[j] = i;
for(int j = a[i].y; j != lca; j = fa[0][j])
mx[j] = i;
}
// 从最小的开始.
for(int i = 1, j = 1; i <= m ; i = j ) {
for(j = i; j <= m && a[j].val == a[i].val; ++ j);
// 每次搞这些.
// [i, j)
for(int k = 2; k <= n ; ++ k) {
if(mx[k] < j && !mk[k]) {
fin[k] = a[i].val;
mk[k] = 1;
}
}
}
for(int i = 2 ; i <= n ; ++ i) if(!fin[i]) fin[i] = 1;
for(int i = 1; i <= m ; ++ i) {
int lca = get_lca(a[i].x, a[i].y);
int m1 = 10000000;
for(int j = a[i].x; j != lca; j = fa[0][j])
m1 = min(m1, fin[j]);
for(int j = a[i].y; j != lca; j = fa[0][j])
m1 = min(m1, fin[j]);
if(m1 != a[i].val) {
printf("-1\n");
return 0;
}
}
for(int i = 1; i < n ; ++ i ) {
int x = A[i];
int y = B[i];
if(fa[0][x] == y) swap(x, y);
// y -> x.
printf("%d ", fin[y]);
}
return 0;
}
Earth Wind and Fire
来源：CF1148E
显然，原位置的数字的顺序可以不变，且不影响结果.
然后这道题就变成了一个匹配点唯一的问题了.
有一些点想向右配，一些点向左.
显然，从左到右扫一遍发现向左配的多于向右配的就不合法.
向左配的总量和向右配的总量不等也不行, 类似一个括号序列.
然后输出答案的话显然向右走的优先考虑位置靠前的向左的.
#include <cstdio>
#include <set>
#include <map>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 320008
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
set<int>se;
int n, a[N], b[N], pr[N], id[N];
vector<int>g;
struct data {
int x, y;
data(int x=0, int y=0):x(x),y(y){}
}pp[N];
bool cmp(data i, data j) {
return i.x < j.x;
}
int tot;
int A[N], B[N], C[N];
int main() {
// setIO("input");
scanf("%d", &n);
for(int i = 1; i <= n ; ++ i) {
scanf("%d",&a[i]), pp[i].x = a[i], pp[i].y = i;
}
for(int i = 1; i <= n ; ++ i) scanf("%d",&b[i]);
ll tmp = 0;
sort(pp + 1, pp + 1 + n, cmp);
sort(b + 1, b + 1 + n);
// sort(a + 1, a + 1 + n);
for(int i = 1; i <= n ; ++ i) {
tmp += (b[i] - pp[i].x);
if(tmp < 0) {
printf("NO\n");
return 0;
}
}
if(tmp == 0) {
printf("YES\n");
// 这种情况下才是合法的.
int cnt = 0;
for(int i = 1; i <= n ; ++ i) {
if(b[i] < pp[i].x) {
// 向左.
pr[i] = pp[i].x - b[i];
se.insert(i);
}
// if(b[i] > pp[i].x) ++ cnt;
}
// printf("%d\n", cnt);
for(int i = 1; i <= n ; ++ i) {
if(pp[i].x < b[i]) {
// 需要向右.
int cur = b[i] - pp[i].x;
for(set<int>::iterator it = se.begin(); it != se.end(); it ++ ) {
int p = (*it);
int det = min(cur, pr[p]);
pr[p] -= det;
cur -= det;
++ tot;
A[tot] = pp[i].y;
B[tot] = pp[p].y;
C[tot] = det;
/// printf("%d %d %d\n", pp[i].y, pp[p].y, det);
if(pr[p] > 0) {
break;
}
else {
g.pb(p);
if(cur == 0) break;
}
}
for(int j = 0 ; j < g.size() ; ++ j) se.erase(g[j]);
g.clear();
}
}
printf("%d\n", tot);
for(int j = 1; j <= tot; ++ j) {
printf("%d %d %d\n", A[j], B[j], C[j]);
}
}
else {
printf("NO\n");
}
return 0;
}
GCD of an Array
来源：CF1493D
$\mathrm{gcd}$ 取决于每种质因子在所有数中最小的次幂.
然后由于每一次加入的数字都小于等于 $2 \times 10^5$, 所以可以暴力拆解质因数.
然后用一个 $\mathrm{multiset}$ 维护一下每种质因子的次幂就行.
当 $\mathrm{multiset}$ 的集合大小达到 $\mathrm{n}$ 后贡献一下答案即可.
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#define N 200009
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const int mod=(int)1e9+7;
multiset<int>se[200009];
vector<int>G[N];
ll ans;
map<int,int>mp[N];
int n,Q,prime[N],tot,vis[N],a[N];
int qpow(int x, int y) {
int tmp=1;
for(;y;y>>=1,x=(ll)x*x%mod)
if(y&1) tmp=(ll)tmp*x%mod;
return tmp;
}
int get_inv(int x) {
return qpow(x, mod-2);
}
void init() {
for(int i=2;i<N;++i) {
if(!vis[i]) {
prime[++tot]=i;
G[i].pb(i);
for(int j=i+i;j<N;j+=i) vis[j] = 1, G[j].pb(i);
}
}
}
void mul(int x, int y) {
for(int i = 0; i < G[y].size(); ++ i) {
int o = 0, tmp = y;
while(tmp % G[y][i] == 0) tmp /= G[y][i], ++ o;
int p = mp[x][G[y][i]];
if(p == 0) {
se[G[y][i]].insert(o);
mp[x][G[y][i]] = o;
if(se[G[y][i]].size() == n) {
ans = (ll)ans * qpow(G[y][i], *se[G[y][i]].begin()) % mod;
}
}
else {
int p1 = *se[G[y][i]].begin();
se[G[y][i]].erase(se[G[y][i]].lower_bound(p));
se[G[y][i]].insert(p + o);
mp[x][G[y][i]] = o + p;
if(se[G[y][i]].size() == n) {
ans = (ll)ans * qpow(G[y][i], *se[G[y][i]].begin() - p1) % mod;
}
}
}
}
int main() {
// setIO("input");
init();
ans = 1;
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;++i) {
int v;
scanf("%d",&v);
mul(i, v);
}
for(int i=1;i<=Q;++i) {
int x, y;
scanf("%d%d",&x, &y);
if(y > 1)
mul(x, y);
printf("%lld\n", ans);
}
return 0;
}
New Roads
来源：CF746G
先判断是否有解：
每次肯定要在深度为 $\mathrm{i}$ 的点上连边，构成深度为 $\mathrm{i+1}$ 的点.
考虑新连点对当前叶子数量的影响：
1. 新增最多，那么就统一连到一个点上.
2. 新增最小，那么就尽量连到不同点上.
增量大小肯定是一个区间，且每个增量都能取到.
然后可以扫一遍求出叶子可能的取值区间.
若判断出来有解，则逆序还原每次选择的增量，最后输出结果即可.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 200009
#define pb push_back
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
vector<int>G[N],dep[N];
int n,t,K,a[N],num[N],tot,edges;
struct data {
int mn,mx,l,r;
}q[N];
struct Edge {
int x,y;
}e[N];
int main() {
// setIO("input");
scanf("%d%d%d",&n,&t,&K);
for(int i=1;i<=t;++i) {
scanf("%d",&a[i]);
}
a[0]=1;
int l=1,r=1;
for(int i=0;i<t;++i) {
int mn=a[i+1]-min(a[i+1],a[i]);
int mx=a[i+1]-1;
q[i].l=l;
q[i].r=r;
l+=mn;
r+=mx;
q[i].mn=mn;
q[i].mx=mx;
}
if(K>=l&&K<=r) {
int cur = K;
for(int i = t - 1; i >= 0 ; -- i) {
// 可知道操作 i 之前的东西.
if(cur >= q[i].l && cur <= q[i].r) {
num[i] = q[i].mn;
cur -= q[i].mn;
}
else {
num[i] = max(q[i].mn, (cur - q[i].r));
cur -= num[i];
}
//printf("%d %d %d %d %d\n",q[i].l,q[i].r,q[i].mn,q[i].mx,num[i]);
}
// return 0;
// 已知每一次操作的 num[i] 了.
tot = 1;
dep[0].pb(1);
for(int i=0;i<t;++i) {
// num[i] 为叶子的增量.
int det = q[i].mx - num[i];
// q[i].mx: 1 个点增加.
// det: (1 + det) 个点增加.
for(int j=1;j<=1+det;++j) {
int p = dep[i][j - 1];
++tot;
// G[p].pb( ++ tot);
dep[i + 1].pb(tot);
++edges;
e[edges].x = p;
e[edges].y = tot;
}
for(int j=2+det;j<=a[i + 1]; ++ j) {
int p = dep[i][0];
++tot;
// G[p].pb(++ tot);
dep[i + 1].pb(tot);
++edges;
e[edges].x = p;
e[edges].y = tot;
}
}
printf("%d\n", n);
for(int i=1;i<=edges;++i) {
printf("%d %d\n", e[i].x, e[i].y);
}
}
else {
printf("-1\n");
}
return 0;
}
Fixed Point Removal
来源：CF1404C
显然，若 $\mathrm{a[i]}>i$ 永远都删不掉.
否则需要 $\mathrm{i}$ 前面删掉 $\mathrm{i-a[i]}$ 个才行.
考虑最优策略怎么删：
每次扫一遍序列，找到最后一个能删的位置，这一定是最优的.
然后我们发现这个最优解的构成就是对于每一个位置只要可能删就都删了.
那么这个问题就从整体转化成单点了：只考虑 $\mathrm{i}$, 能否将 $\mathrm{i}$ 删掉.
然后不妨从后向前扫描左端点，并维护右端点答案.
用线段树来维护每个位置差多少个可以被删掉，然后如果加入的左端点可以直接被删掉就暴力更新后面.
由于每一个可能被删的位置只会被删除一次，所以时间复杂度为 $O(n \log n)$.
维护答案就用树状数组啥的就行了.
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#define N 300009
#define ll long long
#define pb push_back
#define ls (now << 1)
#define rs (now << 1) | 1
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const int inf = 100000000;
struct BIT {
int C[N];
int lowbit(int x) {
return x & (-x);
}
void upd(int x, int v){
while(x < N) {
C[x] += v;
x += lowbit(x);
}
}
int query(int x) {
int tmp = 0;
for(int i = x; i ; i -= lowbit(i))
tmp += C[i];
return tmp;
}
}T;
int n,Q, ans[N];
int det[N],a[N],lazy[N<<2],c0[N<<2], mn[N<<2];
struct node {
int r, id;
node(int r=0,int id=0):r(r),id(id){}
};
vector<node>G[N];
void pushup(int now) {
mn[now]=min(mn[ls], mn[rs]);
c0[now]=0;
if(mn[ls] == mn[now])
c0[now]+=c0[ls];
if(mn[rs] == mn[now])
c0[now]+=c0[rs];
}
void build(int l,int r,int now) {
mn[now]=inf;
lazy[now]=0;
if(l==r) {
c0[now]=1;
return ;
}
int mid=(l+r)>>1;
build(l,mid,ls);
build(mid+1,r,rs);
pushup(now);
}
void mark(int now, int v) {
lazy[now]+=v;
mn[now]+=v;
}
void pushdown(int now) {
if(lazy[now] != 0) {
mark(ls, lazy[now]);
mark(rs, lazy[now]);
lazy[now] = 0;
}
}
void modify(int l,int r,int now,int p,int v) {
if(l == r) {
mn[now] = v;
return ;
}
pushdown(now);
int mid=(l+r)>>1;
if(p<=mid) modify(l,mid,ls,p,v);
else modify(mid+1,r,rs,p,v);
pushup(now);
}
void update(int l,int r,int now,int L,int R,int v) {
if(l>=L&&r<=R) {
mark(now, v);
return ;
}
pushdown(now);
int mid=(l+r)>>1;
if(L<=mid) update(l,mid,ls,L,R,v);
if(R>mid) update(mid+1,r,rs,L,R,v);
pushup(now);
}
int get_nex(int l,int r,int now) {
if(mn[now] > 0) return n + 1;
if(l == r) {
return l ;
}
pushdown(now);
int mid=(l+r)>>1;
if(mn[ls] <= 0) return get_nex(l, mid, ls);
else return get_nex(mid + 1, r, rs);
}
int find(int pos) {
if(pos >= n || mn[1] > 0 ) return n + 1;
else {
return get_nex(1, n, 1);
}
}
int main() {
// setIO("input");
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
if(i >= a[i]) {
det[i] = i - a[i];
}
else {
det[i] = inf;
}
}
for(int i=1;i<=Q;++i) {
int x, y;
scanf("%d%d",&x, &y);
int l = x + 1;
int r = n - y;
G[l].pb(node(r, i));
}
build(1,n,1);
for(int i=n;i>=1;--i) {
if(det[i] == 0) {
for(int j = i; j <= n ; j = find(j)) {
T.upd(j, 1);
modify(1, n, 1, j, inf);
if(j < n) {
update(1, n, 1, j + 1, n, -1);
}
}
}
else {
modify(1, n, 1, i, det[i]);
}
for(int j = 0; j < G[i].size();++ j) {
node q = G[i][j];
ans[q.id] = T.query(q.r);
}
}
for(int i=1;i<=Q;++i) {
printf("%d\n", ans[i]);
}
return 0;
}
Ehab's Last Corollary
来源：CF1364D
分几种情况讨论：
1. 一棵树，直接黑白染色取数量多的颜色即可.
2. 有环.
对于有环的情况，直接提取环可能会出现被别的环嵌套的情况而不好处理.
不妨直接构建 DFS 树取出长度最小的环然后对这个环处理.
1. 长度小于等于 k, 则直接输出.
2. 长度大于 k 则直接黑白染色取出 k/2 个点即可.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 100009
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
vector<int>G[N],col[2];
int n,m,K,dfn[N],scc,fa[N],dep[N];
void dfs(int x, int ff, int co) {
col[co].pb(x);
for(int i=0;i<G[x].size();++i) {
int v=G[x][i];
if(v==ff) continue;
dfs(v, x, co ^ 1);
}
}
int UP(int x) {
return x / 2 + (x & 1);
}
void solve1() {
dfs(1, 0, 0);
int d = 0;
if(col[1].size() > col[0].size()) d = 1;
printf("1\n");
for(int i=1;i<=UP(K);++i)
printf("%d ", col[d][i - 1]);
}
vector<int>vec;
struct node {
int x, y, dis;
node(int x=0,int y=0,int dis=0):x(x),y(y),dis(dis){}
};
vector<node>pf;
bool cmp(node i, node j) {
return i.dis < j.dis;
}
void calc(int x, int v) {
for(int i=x;i!=v;i=fa[i]) {
vec.pb(i);
}
vec.pb(v);
if(vec.size() <= K) {
printf("2\n");
printf("%d\n", vec.size());
for(int i=0;i<vec.size();++i) {
printf("%d ", vec[i]);
}
}
else {
// length of cycle > K.
printf("1\n");
int cc = 0;
for(int i=0;i<vec.size()-1;i+=2) {
printf("%d ", vec[i]);
++ cc;
if(cc == UP(K)) break;
}
}
}
void dfs2(int x,int ff) {
dfn[x]=++scc;
fa[x]=ff,dep[x]=dep[ff]+1;
for(int i=0;i<G[x].size();++i) {
int v=G[x][i];
if(v==ff) continue;
if(!dfn[v]) {
// tree edge
dfs2(v, x);
}
else if(dfn[v] < dfn[x]) {
// find cycle.
// x -> fa[x] ->.....v ..
pf.pb(node(x, v, dep[x] - dep[v]));
// calc(x, v);
}
}
}
int main() {
// setIO("input");
scanf("%d%d%d",&n,&m,&K);
for(int i=1;i<=m;++i) {
int x, y;
scanf("%d%d",&x,&y);
G[x].pb(y);
G[y].pb(x);
}
if(m == n - 1) {
solve1();
}
else {
dfs2(1, 0);
sort(pf.begin(), pf.end(), cmp);
calc(pf[0].x, pf[0].y);
}
return 0;
}
Binary Subsequence Rotation
来源：CF1370E
显然，只需考虑数值不同的位置.
如果说选择的子序列长度为 $2$, 则相当于一次交换操作.
所以只要 $\mathrm{s}$ 与 $\mathrm{t}$ 0/1 的个数相同就有解.
我们希望出现 0/1 恰好错开的子序列，这些子序列只要一次操作就能换回去.
然后统计一下这样的子序列个数即可.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 1000009
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,c[3],d[3];
char s[N], t[N];
int main() {
// setIO("input");
scanf("%d",&n);
scanf("%s", s + 1);
scanf("%s", t + 1);
for(int i=1;i<=n;++i) {
if(s[i] == '0' && t[i] == '1') ++ c[0];
if(s[i] == '1' && t[i] == '0') ++ c[1];
}
if(c[0] != c[1]) printf("-1\n");
else {
for(int i=1;i<=n;++i) {
if(s[i] == t[i]) continue;
if(s[i] == '0' && t[i] == '1') {
// 0.
if(d[1]) {
-- d[1];
++ d[0];
}
else {
++ d[0];
}
}
else {
if(d[0]) {
--d[0];
++d[1];
}
else{
++d[1];
}
}
}
printf("%d\n", d[0] + d[1]);
}
return 0;
}
Array Destruction
来源：CF1474C
模拟赛的时候被这道题给降智了.
显然，最开始选的两个数一定包含最大值.
不妨枚举另一个数选的是什么，然后删除另选的数.
对于剩余的数，一定还会选剩余数的最大值.
然后这样的话每次就将问题规模缩小，且每次选择都是唯一的.
递归跑一下看看能不能走完，能走完就合法，否则就输出不合法.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
#define N 2009
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,len,a[N];
int bu[1000003], flag;
vector<int>g,v;
multiset<int>se;
void solve(int x) {
if(se.empty()) {
flag = 1;
return ;
}
int p = *se.rbegin();
se.erase(se.lower_bound(p));
int q = x - p;
if(q > p) {
flag = 0;
return ;
}
if(se.find(q) == se.end()) {
flag = 0;
return ;
}
se.erase(se.lower_bound(q));
g.pb(p);
v.pb(q);
solve(p);
}
void solve() {
scanf("%d",&n);
len = n << 1;
for(int i=1;i<=len;++i) {
scanf("%d",&a[i]);
}
sort(a+1,a+1+len);
for(int i=len-1;i>=1;--i) {
g.clear();
v.clear();
se.clear();
for(int j = 1; j <= len ; ++ j) {
se.insert(a[j]);
}
flag = 0;
g.pb(a[i]);
v.pb(a[len]);
se.erase(se.lower_bound(a[i]));
se.erase(se.lower_bound(a[len]));
solve(a[len]);
if(flag) {
break;
}
}
if(flag) {
printf("YES\n");
printf("%d\n", g[0] + v[0]);
for(int i=0;i<g.size();++i) {
printf("%d %d\n",g[i],v[i]);
}
}
else {
printf("NO\n");
}
}
int main() {
// setIO("input");
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
Painting the Array II
来源：CF1479B2
显然可以列出 DP 方程 $\mathrm{f[i][j]}$ 表示前 $\mathrm{i}$ 个数第一个集合划分到 $\mathrm{i}$, 另一个尾数为 $\mathrm{j}$.
然后这个方程在转移的时候形式是相似的，类似一个区间加，显然可以用线段树去维护.
虽然思路简单粗暴，但是由于过久没有敲线段树优化 DP, 竟然写了将近 30 分钟.
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define ls (now<<1)
#define rs (now<<1|1)
#define N 100009
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const int inf = 10000000;
int a[N], n, lazy[N<<2], mn[N<<2];
void build(int l,int r,int now) {
mn[now]=inf;
if(l==r) {
return ;
}
int mid=(l+r)>>1;
build(l,mid,ls);
build(mid+1,r,rs);
}
void mark(int now,int v) {
mn[now]+=v;
lazy[now]+=v;
}
void pushup(int now) {
mn[now]=min(mn[ls], mn[rs]);
}
void pushdown(int now) {
if(lazy[now]) {
mark(ls, lazy[now]);
mark(rs, lazy[now]);
lazy[now] = 0;
}
}
void modify(int l,int r,int now,int p,int v) {
if(l==r) {
mn[now]=min(mn[now], v);
return ;
}
pushdown(now);
int mid=(l+r)>>1;
if(p<=mid) modify(l,mid,ls,p,v);
else modify(mid+1,r,rs,p,v);
pushup(now);
}
void update(int l, int r, int now, int L, int R, int v) {
if(l>=L&&r<=R) {
mark(now, v);
return ;
}
pushdown(now);
int mid=(l+r)>>1;
if(L<=mid) update(l,mid,ls,L,R,v);
if(R>mid) update(mid+1,r,rs,L,R,v);
pushup(now);
}
int query(int l,int r,int now,int L,int R) {
if(l>=L&&r<=R) {
return mn[now];
}
pushdown(now);
int mid=(l+r)>>1, re = inf;
if(L<=mid) re = min(re, query(l,mid,ls,L,R));
if(R>mid) re = min(re, query(mid+1,r,rs,L,R));
return re;
}
int main() {
// setIO("input");
scanf("%d",&n);
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
}
// interval of segmentree: [0, n + 1]
build(0, n + 1, 1);
modify(0, n + 1, 1, 0, 0);
for(int i=0;i<n;++i) {
// update i + 1 from i.
// first -> dp[i + 1][a[i]] <- dp[i][j] + (j != a[i + 1])
int p = query(0, n + 1, 1, 0, a[i + 1] - 1);
int q = query(0, n + 1, 1, a[i + 1] + 1, n + 1);
int h = query(0, n + 1, 1, a[i + 1], a[i + 1]);
int mi = min(min(p, q) + 1, h);
if(a[i] != a[i + 1]) {
mark(1, 1);
}
modify(0, n + 1, 1, a[i], mi);
}
printf("%d\n", mn[1]);
return 0 ;
}
Decryption
来源：CF1419E
直接考虑去构造这个环.
显然，如果这个数字的所有质因子幂次为 1，且质因子数量大于 2 的话答案是 0.
然后出现质因子幂次大于 1 的情况，就将剩余的数字塞进 $\mathrm{p[i]}$ 与 $\mathrm{p[i] \times p[i+1]}$ 之间.
这样的话 $\mathrm{p[i]}$ 的倍数都不会产生互质，然后其他的数字同理.
答案为 $1$ 的情况当且仅当仅有两个质因数且幂次都为 $1$, 这个特判.
然后在构造答案的时候有一些细节需要注意一下.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 200009
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n, tot;
int cn[N], num[N];
void divide(int p) {
for(int i=2;i*i<=n;++i) {
if(p % i == 0) {
++ tot;
num[tot]=i;
while(p % i == 0) {
++cn[tot];
p /= i;
}
}
}
if(p > 1) {
++tot;
num[tot]=p;
cn[tot]=1;
}
}
vector<int>vec;
int st[N], top;
void solve() {
scanf("%d",&n);
divide(n);
if(tot==2&&cn[1]==1&&cn[2]==1) {
printf("%d %d %d\n", num[1], num[1]*num[2], num[2]);
printf("1\n");
}
else {
vec.clear();
for(int i=tot;i>=1;--i) {
top = 0;
for(int j=0;j<vec.size();++j) {
int cur = vec[j];
for(int t = 1,x = num[i]; t <= cn[i]; ++ t, x *= num[i]) {
st[++top] = cur * x;
}
}
int pos = vec.size() >= 1 ? vec.size() : 0;
for(int t = 1, x = num[i]; t <= cn[i] ; ++ t, x *= num[i]) {
vec.pb(x);
}
while(top >= 1) vec.pb(st[top]), -- top;
// 处理完毕 i ~ tot 的所有因数.
for(int j=pos;j<vec.size();++j) {
int cur = vec[j];
if((cur % num[i] == 0 && (cur / num[i] == num[i - 1] || cur / num[i] == num[i + 1])) || cur == n)
continue;
printf("%d ", cur);
}
if(i != 1) {
printf("%d ", num[i] * num[i - 1]);
}
}
printf("%d\n", n);
printf("0\n");
}
for(int i=0;i<=tot;++i) {
num[i]=cn[i]=0;
}
tot = 0;
}
int main() {
// setIO("input");
int T;
scanf("%d",&T);
while(T--) {
solve();
}
return 0;
}
New Game Plus!
来源：CF1415E
看数据范围，基本上就是一个 $O(n \log n)$ 的贪心算法了.
有 $\mathrm{k}$ 次清零机会，可以看作允许将序列分为 $\mathrm{k+1}$ 段，然后每段分别计算答案.
显然，在每段中，一定是按照从大到小排列.
然后根据贪心，不妨每次选取 $\mathrm{sum}$ 最大的那个.
对当前局面，这个对答案的贡献是最优的，且是当前最大的，似乎很有道理.
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 500009
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,k,c[N];
priority_queue<ll>q;
bool cmp(int i,int j) {
return i>j;
}
int main() {
// setIO("input");
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i) {
scanf("%d",&c[i]);
}
for(int i=1;i<=k+1;++i) q.push(0);
sort(c+1,c+1+n,cmp);
ll ans = 0;
for(int i=1;i<=n;++i) {
ll sum = q.top();
q.pop();
ans += sum;
sum += c[i];
q.push(sum);
}
printf("%lld\n",ans);
return 0;
}
Present
来源：CF1322B
显然拆位考虑，然后对于第 $\mathrm{i}$ 的计算，可以对 $\mathrm{2^{i+1}}$ 取模.
唯一的问题是对于合的取模，需要将每个元素分别取模后的和再取模.
但如果这样做的话时间复杂度还是降不下来.
但是仔细观察发现即使求和后不取模贡献可以写成两个区间的形式.
用排序 + 双指针处理这个东西就可以了.
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 400009
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,b[N],a[N],bin[90];
void init() {
for(int i=0;i<=28;++i) {
bin[i]=1<<i;
}
}
int calc(int L,int R) {
if(L>R) return 0;
ll ret = 0;
for(int l=n,r=n,i=1;i<=n;++i) {
while(l >= 1 && b[l] >= L - b[i]) -- l;
while(r >= 1 && b[r] > R - b[i]) -- r;
ret += r - l ;
if(i > l && i <= r) -- ret;
}
return (ret >> 1) & 1;
}
int solve(int k) {
for(int i=1;i<=n;++i) {
b[i] = a[i] % bin[k + 1];
}
sort(b+1,b+1+n);
int p = calc(bin[k], bin[k + 1] - 1) ^ calc(bin[k] + bin[k + 1], bin[k + 2] - 1);
//printf("%d\n", p);
return p;
}
int main() {
// setIO("input");
scanf("%d",&n);
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
}
init();
int ans = 0;
for(int i=0;i<=26;++i) {
ans += solve(i) << i;
}
printf("%d\n", ans);
return 0;
}
Multiples and Power Differences
来源：CF1485D
$\mathrm{a[i][j]}$ 小于等于 16, 而 1 到 16 所有数字的 $\mathrm{lcm}$ 也才刚等于 720720.
不妨对整个棋盘黑白染色，让黑格子等于 720720， 白格子等于 720720 - $\mathrm{a[i][j]^4}$.
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int gcd(int x, int y) {
return y ? gcd(y, x % y): x;
}
int lcm(int x, int y) {
return (ll) x * y / gcd(x, y);
}
int main() {
// setIO("input");
int p = 1;
for(int i = 1; i <= 16 ; ++ i) p = lcm(p, i);
int n , m ;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
int num;
scanf("%d",&num);
if((i + j) % 2 == 0) {
printf("%d ", p);
}
else {
printf("%d ", p - num * num * num * num);
}
}
printf("\n");
}
return 0;
}
作业
来源：bzoj3791
将原序列连续的 0 和 1 都进行压缩，形成一个新序列.
显然，如果进行 0/1 染色一定会是连续的 0 和 连续的 1 都染成同种颜色.
然后发现对于一个 $\mathrm{k}$, 最多可将序列分为 $\mathrm{2k-1}$ 段.
而任意一个 $\mathrm{2k-1}$ 段的染色序列都能对应到一个原序列.
用 DP 求解这个东西然后搞一搞就好了，注意边界.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 100009
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,K,f[N][102][2],b[N],col[N],tot,a[N];
int main() {
// setIO("input");
scanf("%d%d",&n,&K);
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
}
for(int i=1,j;i<=n;i=j) {
++tot;
col[tot]=a[i];
for(j=i;a[j]==a[i]&&j<=n;++j)
++b[tot];
}
memset(f, -0x3f, sizeof(f));
f[1][1][col[1]]=b[1];
f[1][1][col[1] ^ 1] = 0;
for(int i=1;i<tot;++i) {
for(int j=0;j<=2*K-1;++j) {
for(int o=0;o<2;++o) {
if(f[i][j][o] < 0) continue;
for(int nex=0;nex<2;++nex) {
if(nex == o) {
if(nex == col[i + 1]) {
// 匹配上了.
f[i+1][j][nex]=max(f[i+1][j][nex], f[i][j][o]+b[i+1]);
// printf("%d\n",f[i+1][j][nex]);
}
else{
f[i+1][j][nex]=f[i][j][o];
// printf("%d\n",f[i+1][j][nex]);
}
}
else {
if(nex == col[i + 1]) {
if(j+1<=2*K-1) f[i+1][j+1][nex]=max(f[i+1][j+1][nex], f[i][j][o]+b[i+1]);
// printf("%d\n",f[i+1][j+1][nex]);
}
else {
if(j+1<=2*K-1) f[i+1][j+1][nex]=max(f[i+1][j+1][nex], f[i][j][o]);
// printf("%d\n",f[i+1][j+1][nex]);
}
}
}
}
}
}
int ans = 0;
for(int i=0;i<=2*K-1;++i) {
ans=max(ans, max(f[tot][i][0], f[tot][i][1]));
}
printf("%d\n", ans);
return 0;
}
Two Different
来源：CF1408F
构造题.
考虑 $\mathrm{n=2^{k}}$ 的情况：
第一次将相邻两数合并，第二次将相邻 4 个数合并..... 第 $\mathrm{p}$ 次将 $\mathrm{2^p}$ 个数合并.
显然，将一段区间合并两次也不影响什么.
那么直接找到最大的 $2^k<n$ 然后前后分别覆盖一次就可以了.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 15009
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int lg[60],tot;
struct pai {
int x, y;
pai(int x=0,int y=0):x(x),y(y){}
}a[500009];
void solve(int l,int r) {
if(l==r) {
return ;
}
int mid=(l+r)>>1;
solve(l,mid);
solve(mid+1,r);
int len = mid - l + 1;
for(int i=l;i<=mid;++i) {
// [i, i + len];
a[++tot]=pai(i, i + len);
}
}
int main() {
// setIO("input");
int n;
scanf("%d",&n);
lg[0]=1;
for(int i=1;i<=25;++i) {
lg[i]=1<<i;
}
int p ;
for(p=0;;++p) {
if(lg[p] > n) break;
}
-- p;
solve(1, lg[p]);
solve(n - lg[p] + 1, n);
printf("%d\n", tot);
for(int i=1;i<=tot;++i) {
printf("%d %d\n",a[i].x,a[i].y);
}
return 0;
}
Multiples of Length
来源：CF1396A
构造题.
如果只有两次操作的话可以先将所有数变为 $\mathrm{n}$ 的倍数然后消除.
然后三次操作的话就将 $\mathrm{n}$ 位置的数特别处理一下.
要特判 $\mathrm{n=1}$ 的情况.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 1000009
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n;
ll a[N];
int main() {
// setIO("input");
scanf("%d",&n);
for(int i=1;i<=n;++i) {
scanf("%lld",&a[i]);
}
if(n == 1) {
printf("%d %d\n", 1, 1);
printf("%lld\n", -a[1]);
printf("%d %d\n", 1, 1);
printf("%d\n",0);
printf("%d %d\n", 1, 1);
printf("%d\n",0);
return 0;
}
printf("%d %d\n",1,n-1);
for(int i = 1; i < n ; ++ i) {
printf("%lld ", 1ll*(n - 1) * a[i]);
}
printf("\n");
printf("%d %d\n", n, n);
printf("%lld\n", 1ll*(n-1)*a[n]);
printf("%d %d\n", 1, n );
for(int i = 1; i <= n ; ++ i) {
printf("%lld ", - 1ll*(n) * a[i]);
}
return 0;
}
Nezzar and Binary String
来源：CF1477B
如果先修改，后询问则每次只要用线段树模拟一下就行.
而先询问后修改是不好处理的.
所以只需倒序处理将问题变成先修改后询问的就行了.
用线段树打打标记啥的就可以了.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 200009
#define ll long long
#define pb push_back
#define ls now<<1
#define rs now<<1|1
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
char st[N], ed[N];
int n,m,c0[N<<2],len[N<<2],lazy[N<<2],pl[N],pr[N];
void pushup(int now) {
c0[now]=c0[ls]+c0[rs];
}
void build(int l,int r,int now) {
len[now] = r - l + 1;
lazy[now] = -1;
if(l == r) {
c0[now] = (ed[l] == '0');
return ;
}
int mid=(l+r)>>1;
build(l , mid , ls);
build(mid + 1, r , rs);
pushup(now);
}
void mark(int now, int v) {
lazy[now] = v ;
if(v == 0) {
c0[now] = len[now];
}
else {
c0[now] = 0;
}
}
void pushdown(int now) {
if(lazy[now] != -1) {
mark(ls, lazy[now]);
mark(rs, lazy[now]);
lazy[now] = -1;
}
}
int query(int l,int r,int now,int L,int R) {
if(l >= L && r <= R) {
return c0[now];
}
pushdown(now);
int mid = (l + r) >> 1, re = 0;
if(L<=mid) re += query(l, mid, ls, L, R);
if(R>mid) re += query(mid+1, r, rs, L, R);
return re;
}
void update(int l,int r,int now,int L,int R,int v) {
if(l>=L&&r<=R) {
mark(now, v);
return ;
}
pushdown(now);
int mid=(l+r)>>1;
if(L<=mid) update(l,mid,ls,L,R,v);
if(R>mid) update(mid+1,r,rs,L,R,v);
pushup(now);
}
int FL;
void check(int l,int r,int now) {
if(l==r) {
int p = c0[now] ? 0 : 1;
if(p != st[l] - '0') FL = 1;
return ;
}
int mid=(l+r)>>1;
pushdown(now);
check(l,mid,ls);
check(mid+1,r,rs);
}
void solve() {
scanf("%d%d",&n,&m);
scanf("%s", st + 1);
scanf("%s", ed + 1);
build(1, n, 1);
for(int i = 1; i <= m ; ++ i) {
scanf("%d%d",&pl[i],&pr[i]);
}
int flag = 0;
for(int i = m ; i >= 1; -- i) {
int p0 = query(1, n, 1, pl[i], pr[i]);
int p1 = pr[i] - pl[i] + 1 - p0;
if(p0 == p1) {
printf("NO\n");
flag = 1;
break;
}
if(!p1 || !p0) continue;
if(p1 > p0) {
update(1, n, 1, pl[i], pr[i], 1);
}
else {
update(1, n, 1, pl[i], pr[i], 0);
}
}
if(!flag) {
check(1, n, 1);
if(FL) {
printf("NO\n");
}
else {
printf("YES\n");
}
}
FL = 0 ;
}
int main() {
// setIO("input");
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
数数
来源：[SDOI2014] 数数
数位DP+AC自动机，思路什么的就太显然了.
然后这道题的数位DP仍然是使用递归来处理的.
如果单纯用递推的话可能会很麻烦，但是递归却非常简单.
注意这道题中明确表示 $\mathrm{x}$ 是正整数.
所以不要把 $0$ 包含进去.
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define N 1509
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const int mod = (int)1e9 + 7;
char str[N];
queue<int>q;
int f[N][N][2][2];
int cnt,a[N],m,tot,ch[N][10], mark[N*10], fail[N*10];
void build() {
for(int i=0;i<10;++i) {
if(ch[0][i]) q.push(ch[0][i]);
}
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i=0;i<10;++i) {
int nex = ch[u][i];
if(!nex) {
ch[u][i] = ch[fail[u]][i];
continue;
}
q.push(nex);
fail[nex] = ch[fail[u]][i];
if(mark[fail[nex]]) {
mark[nex] = 1;
}
}
}
}
int dfs(int cur, int x, int d, int o) {
if(cur > cnt) {
return (o == 0);
}
if(f[cur][x][d][o] != -1) {
return f[cur][x][d][o];
}
int re = 0;
int lim = d ? a[cur] : 9;
for(int i = 0 ; i <= lim ; ++ i) {
int nex ;
if(o == 1 && i == 0) nex = 0;
else nex = ch[x][i];
if(mark[nex]) continue;
(re += dfs(cur + 1, nex, d && (i == lim), o && (i == 0))) %= mod;
}
return f[cur][x][d][o] = re;
}
int main() {
// setIO("input");
scanf("%s", str + 1);
cnt=strlen(str+1);
for(int i=1;i<=cnt;++i) a[i]=str[i]-'0';
scanf("%d",&m);
for(int i=1;i<=m;++i) {
scanf("%s",str+1);
int len=strlen(str+1),rt=0;
for(int j=1;j<=len;++j) {
if(!ch[rt][str[j] - '0'])
ch[rt][str[j] - '0'] = ++ tot;
rt = ch[rt][str[j] - '0'];
}
mark[rt] = 1;
}
build();
memset(f, -1, sizeof(f));
int ans = (dfs(1, 0, 1, 1)) % mod;
printf("%d\n", ans);
return 0;
}
Magic Numbers
来源：CF628D
简单数位DP.
只需要记录一下位数，余数，是否顶上界就行.
然后统计过程当然还是用递归（记忆化搜索）
然后由于这个数字很长，减 1 的话很麻烦.
特判一下左边界是否也是合法数字即可.
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 2009
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const int mod = (int)1e9 + 7;
int m, D, cnt, a[N],l1,l2;
char A[N], B[N];
ll f[N][N][2][2], pw[N];
// cur: 当前位数(编号小的是高位)
ll dfs(int cur, int mo, int d, int o) {
if(cur > cnt) {
return (mo == 0);
}
if(f[cur][mo][d][o] != -1) {
return f[cur][mo][d][o];
}
ll re = 0;
int lim = d ? a[cur] : 9;
for(int i = 0 ; i <= lim ; ++i) {
if((cur & 1) && i == D) {
continue;
}
if(cur % 2 == 0 && i != D) {
continue;
}
// 满足条件：
(re += dfs(cur + 1, (ll)(mo + (ll)pw[cnt - cur]*i%m)%m, d && (i == lim), o && (i ==0))) %= mod ;
}
return f[cur][mo][d][o] = re;
}
ll calc() {
memset(f, -1, sizeof(f));
return dfs(1, 0, 1, 1);
}
void init() {
pw[0] = 1;
for(int i = 1; i < N ; ++ i) {
pw[i] = (ll) pw[i - 1] * 10 % m;
}
}
int main() {
// setIO("input");
scanf("%d%d",&m,&D);
init();
scanf("%s", B + 1), l1=strlen(B+1), cnt = 0;
for(int i = 1; i <= l1; ++i) {
a[++cnt] = B[i] - '0';
}
ll s2 = calc();
scanf("%s", A + 1), l2=strlen(A+1), cnt = 0;
for(int i = 1; i <= l2; ++i) {
a[++cnt] = A[i] - '0';
}
ll s1 = calc();
int flag = 1, mo = 0;
for(int i = 1; i <= l1 ; ++ i) {
(mo += (ll)(B[i] - '0') * pw[l1 - i] % m ) % m;
if(i & 1) {
if(B[i] - '0' == D) flag = 0;
}
else {
if(B[i] - '0' != D) flag = 0;
}
}
if(mo) flag = 0;
s1 += flag;
printf("%lld\n", (s1 - s2 + mod) % mod);
return 0;
}
Flappy Bird
来源: bzoj4723
发现如果终态知道，可以 $O(1)$ 求答案.
所以只需求最后高度最小值就行.
中间过程可以到达的高度显然是一段区间.
特别注意的就是每次的横纵坐标之和必为偶数, 这个一定得满足.
所以如果算出来的做右端点不符合的话要人为调整.
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define N 1000009
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int cor[N],L[N],R[N];
int main() {
// setIO("input");
int n, X;
scanf("%d%d",&n,&X);
if(n == 0) {
printf("0\n");
return 0;
}
int pl=0,pr=0;
for(int i=1;i<=n;++i) {
scanf("%d%d%d",&cor[i],&L[i],&R[i]);
int det = cor[i] - cor[i - 1];
// 飞 det 步.
pl -= det;
pr += det;
pl = max(pl, L[i] + 1);
pr = min(pr, R[i] - 1);
if((pl + cor[i]) & 1) ++ pl;
if((pr + cor[i]) & 1) -- pr;
if(pl > pr) {
printf("NIE\n");
return 0;
}
}
int step = cor[n];
int fir = 0 - step;
printf("%d\n", (pl - fir) / 2);
return 0;
}
中国象棋
来源：[AHOI2009]中国象棋
显然每行/每列最多只能放两个棋子.
令 $\mathrm{f[i][a][b]}$ 表示前 $\mathrm{i}$ 行，放 $1,2$ 个棋子的列有 $\mathrm{a,b}$ 个的方案数.
转移的话直接转移就可以了.
没有什么细节，代码很好写.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 102
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const int mod = 9999973;
int f[N][N][N];
// (i, a, b)
// 前 i 行, a 个 1, b 个 2.
int C(int x) {
return (ll)(1ll*x*(x-1)/2)%mod;
}
int main() {
// setIO("input");
f[0][0][0] = 1;
int n ,m;
scanf("%d%d",&n,&m);
for(int i = 0; i < n ; ++ i) {
// 枚举每一行.
for(int a = 0 ; a <= m ; ++ a) {
for(int b = 0 ; b <= m ; ++ b) {
// 枚举 (a, b) -> 即 1 和 2 的个数.
if(a + b > m || !f[i][a][b]) {
continue;
// 状态不合法.
}
// 向下一层加入 0 个.
( f[i + 1][a][b] += f[i][a][b] ) %= mod;
// 向下一层加入一个.
if(b == m) {
continue;
// 无法继续加入.
}
// 考虑加入一个的状态：
if(a) {
// 存在一个的.
(f[i + 1][a - 1][b + 1] += (ll)f[i][a][b] * a % mod) %= mod;
}
if(m - a - b) {
// 加入到空位.
(f[i + 1][a + 1][b] += (ll)f[i][a][b] * (m - a - b) % mod) %= mod;
}
// 考虑加入两个的状态.
if(a >= 2) {
(f[i + 1][a - 2][b + 2] += (ll)f[i][a][b] * C(a) % mod) %= mod;
}
if(m - a - b >= 2) {
(f[i + 1][a + 2][b] += (ll)f[i][a][b] * C(m - a - b) % mod) %= mod;
}
if(a && (m - a - b)) {
(f[i + 1][a][b + 1] += (ll)f[i][a][b] * a % mod * (m - a - b) % mod) %= mod;
}
}
}
}
int ans = 0 ;
for(int i = 0 ; i <= m ; ++ i) {
for(int j = 0 ; j <= m ; ++ j) {
(ans += f[n][i][j]) %= mod;
}
}
printf("%d\n", ans);
return 0;
}
y-fast trie
来源：洛谷P6105 [Ynoi2010] y-fast trie
$\mathrm{(i+j)}$ $\mathrm{mod}$ $\mathrm{C}$.
显然可以先将数字取模，然后分和大于等于/小于 $C$ 的情况.
和大于等于 $\mathrm{C}$ 的情况好办，考虑如何解决和小于 $C$ 的情况.
定义 $(a,b)$ 为双向匹配当且仅当它们互为对方的最优匹配.
显然，对答案有贡献的数对一定是双向匹配.
不妨直接维护这个双向匹配.
每次加入/删除一个数的时候只会涉及 $\mathrm{2}$ 对最优匹配.
注意一下边界啥的，然后本题卡常.
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>
#define N 500009
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
namespace IO
{
char buf[100000],*p1,*p2;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd()
{
int x=0; char s=nc();
while(s<'0') s=nc();
while(s>='0') x=(((x<<2)+x)<<1)+s-'0',s=nc();
return x;
}
void print(int x) {if(x>=10) print(x/10);putchar(x%10+'0');}
};
int C,sz,n;
multiset<int>a,b,tmp;
multiset<int>::iterator it;
int best(int x, int op) {
if(x == -1) return -1;
it = a.upper_bound(C - 1 - x);
if(it == a.begin()) return -1;
it --;
if(op == 1 && (*it) == x && a.count(x) == 1)
return (it == a.begin()) ? -1: *(--it);
else return (*it);
}
void ins(int x) {
++sz ;
if(sz == 1) {
a.insert(x);
return ;
}
int y = best(x, 0);
int z = best(y, 1);
int w = best(z, 1);
if(x > z && y != -1) {
if(z != -1 && w == y) {
b.erase(b.find(y + z));
}
b.insert(x + y);
// 只加入进去双向匹配.
}
a.insert(x);
}
void del(int x) {
a.erase(a.find(x)), sz -- ;
if(!sz) return ;
int y = best(x, 0);
int z = best(y, 1);
int w = best(z, 1);
if(y != -1 && x > z) {
if(z != -1 && y == w) {
b.insert(y + z);
}
b.erase(b.find(x + y));
}
}
int query() {
it = tmp.end();
it -- ;
int re = (*it);
it -- ;
re += (*it);
return re;
}
int main() {
// setIO("input");
n = IO::rd();
C = IO::rd();
int lastans = 0;
for(int i=1;i<=n;++i) {
int op = IO::rd(), x = IO::rd();
x ^= lastans;
if(op == 1) {
ins(x % C);
tmp.insert(x % C);
}
else {
del(x % C);
tmp.erase(tmp.find(x % C));
}
if(sz < 2) printf("EE\n"), lastans = 0 ;
else {
printf("%d\n", lastans = max(query() - C, b.empty() ? 0 : *(--b.end())));
}
}
return 0;
}
双倍回文
来源：bzoj2342. [Shoi2011]双倍回文
双倍回文的合法条件：
1. 长度为 $\mathrm{4}$ 的倍数.
2. 该回文串的后一半也是一个回文串.
建立回文自动机，第一个条件好满足.
第二个条件等价于判断是否有 $\mathrm{\frac{len[x]}{2}}$ 的回文后缀.
$\mathrm{DFS}$ 一遍回文树然后开一个数组特判一下即可.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 500009
#define pb push_back
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
char str[N];
vector<int>G[N];
int len[N],pre[N],ch[N][26],mk[N],last,tot;
void init() {
pre[0] = 1, pre[1] = 1, len[1] = -1;
len[0] = 0, last = tot = 1;
}
int trans(int p, int pos) {
while((pos - len[p] - 1 < 1) || (str[pos] != str[pos - len[p] - 1])) {
p = pre[p];
}
return p;
}
void extend(int c, int pos) {
int p = trans(last, pos);
if(!ch[p][c]) {
int q = ++ tot;
pre[q] = ch[trans(pre[p], pos)][c];
len[q] = len[p] + 2;
ch[p][c] = q;
}
last = ch[p][c];
}
int ans ;
void dfs(int x) {
if((len[x] % 4 == 0) && mk[len[x] / 2])
ans = max(ans, len[x]);
mk[len[x]] = 1;
for(int i = 0 ; i < G[x].size(); ++ i) {
dfs(G[x][i]);
}
mk[len[x]] = 0;
}
int main() {
// setIO("input");
init();
int n ;
scanf("%d",&n);
scanf("%s", str + 1);
for(int i = 1; i <= n ; ++ i) {
extend(str[i] - 'a', i);
}
for(int i = 2; i <= tot; ++ i) {
G[pre[i]].pb(i);
}
dfs(0), dfs(1);
printf("%d\n", ans);
return 0;
}
回文串
来源：APIO2014
回文自动机裸题.
建立完回文自动机后建立回文树，然后遍历一遍回文树就行.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 300009
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
char str[N];
vector<int>G[N];
int pre[N], ch[N][26],len[N], size[N],last, tot;
void init() {
pre[0] = 1, pre[1] = 1, len[1] = -1;
len[0] = 0, last = tot = 1;
}
int trans(int p, int pos) {
while((pos - len[p] - 1 < 1) || (str[pos - len[p] - 1] != str[pos])) {
p = pre[p];
}
return p;
}
void extend(int c, int pos) {
int p = trans(last, pos);
if(!ch[p][c]) {
int q = ++ tot;
pre[q] = ch[trans(pre[p], pos)][c];
len[q] = len[p] + 2;
ch[p][c] = q;
}
last = ch[p][c];
++ size[last];
}
ll ans ;
void dfs(int x) {
for(int i = 0 ; i < G[x].size(); ++ i) {
dfs(G[x][i]);
size[x] += size[G[x][i]];
}
ans = max(ans, 1ll * size[x] * len[x]);
}
int main() {
// setIO("input");
scanf("%s", str + 1);
int n = strlen(str + 1);
init();
for(int i = 1; i <= n ; ++ i) {
extend(str[i] - 'a', i);
}
for(int i = 2; i <= tot; ++ i) {
G[pre[i]].pb(i);
}
dfs(0), dfs(1);
printf("%lld\n", ans);
return 0;
}
Case of Computer Network
来源：CF555E
考虑一棵树怎么做：
1. 对于树上的路径 $\mathrm{(u,v)}$, 所有边的方向都是确定的.
2. 用树上差分打一个标记，然后看一下向上的边和向下的边是否会矛盾.
将树的做法推广到图上：
1. 一个边双里的点对肯定可以互相到达.
2. 不同边双的点就变成了树的情况，缩点后按照树的方法做即可.
#include <cstdio>
#include <vector>
#include <cstring>
#include <stack>
#include <algorithm>
#define N 200009
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,m,Q;
stack<int>S;
vector<int>node[N], G[N];
int low[N], dfn[N], fin[N], id, scc;
int hd[N], to[N<<1], nex[N<<1], vis[N], m1[N], m2[N], dep[N], fa[20][N],edges;
struct UFS {
int p[N],size[N];
void init() {
for(int i=0;i<N;++i) p[i]=i, size[i]=1;
}
int find(int x) {
return p[x]==x?x:p[x]=find(p[x]);
}
void merge(int x, int y) {
x=find(x);
y=find(y);
if(x==y) return;
if(size[x]>size[y]) swap(x,y);
p[x]=y,size[y]+=size[x];
}
}T;
void add(int u, int v) {
nex[++edges]=hd[u];
hd[u]=edges;
to[edges]=v;
}
void tarjan(int x, int ff) {
S.push(x);
vis[x]=1;
low[x]=dfn[x]=++scc;
for(int i=hd[x];i;i=nex[i]) {
if(i==ff) continue;
int v=to[i];
if(!vis[v]) {
tarjan(v, i^1);
low[x]=min(low[x], low[v]);
}
else if(vis[v] != -1) low[x] = min(low[x], dfn[v]);
}
if(low[x] == dfn[x]) {
++ id;
for( ; ; ) {
int p = S.top();
S.pop();
fin[p] = id;
vis[p] = -1;
node[id].pb(p);
if(p == x) break ;
}
}
// printf("%d %d %d\n",x,dfn[x],low[x]);
}
void dfs(int x, int ff) {
vis[x]=1;
fa[0][x]=ff, dep[x]=dep[ff]+1;
for(int i=1;i<=19;++i) fa[i][x]=fa[i-1][fa[i-1][x]];
for(int i=0;i<G[x].size();++i) {
int v=G[x][i];
if(v==ff) continue;
dfs(v, x);
}
}
void dfs2(int x) {
for(int i=0;i<G[x].size();++i) {
int v=G[x][i];
if(v==fa[0][x]) continue;
dfs2(v);
m1[x]+=m1[v];
m2[x]+=m2[v];
}
}
int get_lca(int x, int y) {
if(dep[x]>dep[y]) swap(x,y);
if(dep[y]>dep[x]) {
for(int i=19;i>=0;--i)
if(dep[fa[i][y]]>=dep[x]) y=fa[i][y];
}
if(x==y) return x;
for(int i=19;i>=0;--i)
if(fa[i][x]!=fa[i][y]) x=fa[i][x],y=fa[i][y];
return fa[0][x];
}
int main() {
// setIO("input");
scanf("%d%d%d",&n,&m,&Q);
T.init();
edges = 1;
for(int i=1;i<=m;++i) {
int x,y;
scanf("%d%d",&x,&y);
add(x, y);
add(y, x);
T.merge(x, y);
}
for(int i=1;i<=n;++i) {
if(vis[i] == 0) {
tarjan(i, -1);
// 从 i 开始构建.
}
}
for(int i=1;i<=id;++i) {
for(int j=0;j<node[i].size();++j) {
int x=node[i][j];
for(int o=hd[x];o;o=nex[o]) {
int v=to[o];
if(fin[v] == i) continue;
G[i].pb(fin[v]);
}
}
}
memset(vis, 0, sizeof(vis));
for(int i=1;i<=id;++i) {
if(!vis[i]) {
dfs(i, 0);
}
}
for(int i=1;i<=Q;++i) {
int x, y;
scanf("%d%d",&x,&y);
// 根本不连通.
if(x==y) continue;
if(T.find(x)!=T.find(y)) {
printf("No\n");
return 0;
}
// 一个连通分量内的.
if(fin[x]==fin[y]) continue;
x=fin[x];
y=fin[y];
int lca=get_lca(x, y);
if(lca == x) {
// x->y, 向下一条链.
++m2[y];
--m2[x];
continue;
}
if(lca == y) {
// x->y, 向上一条链.
++m1[x];
--m1[y];
continue;
}
// x->lca, lca->y;
// x->lca 向上
// lca->y 向下.
++m1[x];
--m1[lca];
++m2[y];
--m2[lca];
}
for(int i=1;i<=id;++i) {
if(fa[0][i]==0) dfs2(i);
}
for(int i=1;i<=id;++i) {
if(m1[i]&&m2[i]) {
printf("No\n");
return 0;
}
}
printf("Yes\n");
return 0;
}
矿场搭建
来源：洛谷P3225 [HNOI2012]矿场搭建
对原图跑一个点双，然后标记所有的割点.
以任意一个割点为根再跑一次 $\mathrm{tarjan}$.
第二次运行 $\mathrm{tarjan}$ 的时候若 $\mathrm{x}$ 为 $\mathrm{v}$ 的割点：
1. $\mathrm{v}$ 的子树内没有安排出口，则安排一个.
2. $\mathrm{v}$ 的子树内已经安排出口了，则不用管.
运行完毕之后特判一下整个图都是点双的情况，此时要安排两个点.
这里特别说明一下以割点为根节点第二次运行 $\mathrm{tarjan}$ 的理由：
若根节点不是割点，则会出现非常麻烦的情况，而根节点为割点可以规避掉.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 509
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n, m, ans, root;
ll a2;
int fin[N], iscut[N], cnt;
int hd[N], size[N], to[N<<1], nex[N<<1],low[N], dfn[N], edges, scc;
void add(int u, int v) {
nex[++edges]=hd[u];
hd[u]=edges;
to[edges]=v;
}
void tarjan(int x, int ff) {
low[x]=dfn[x]=++scc;
int son=0;
for(int i=hd[x];i;i=nex[i]) {
int v=to[i];
if(i==ff) continue;
if(!dfn[v]) {
++son;
// c0=v;
tarjan(v, i^1);
low[x]=min(low[x], low[v]);
if(low[v]>=dfn[x]) iscut[x]=1;
}
else low[x]=min(low[x], dfn[v]);
}
if(x==root&&son==1) iscut[x]=0;
cnt += iscut[x];
}
void DFS(int x, int ff) {
size[x]=1;
low[x]=dfn[x]=++scc;
for(int i=hd[x];i;i=nex[i]) {
if(i==ff) continue;
int v=to[i];
if(!dfn[v]) {
DFS(v, i ^ 1);
// 遍历 v 这边.
low[x]=min(low[x], low[v]);
size[x] += size[v];
if(low[v] >= dfn[x]) {
// x 成为了割点.
// v 中选一个.
if(!fin[v]) {
fin[v] = 1;
a2*=size[v];
++ ans;
}
}
fin[x] += fin[v];
}
else low[x]=min(low[x], dfn[v]);
}
}
int TEST;
void solve() {
edges=1,n=0,cnt=0,scc=0,ans=0;
memset(fin,0,sizeof(fin));
memset(iscut,0,sizeof(iscut));
memset(size,0,sizeof(size));
memset(hd,0,sizeof(hd));
memset(to,0,sizeof(to));
memset(nex,0,sizeof(nex));
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
++TEST;
printf("Case %d: ",TEST);
n=0, edges = 1;
for(int i=1;i<=m;++i) {
int x, y;
scanf("%d%d",&x,&y);
add(x, y);
add(y, x);
n = max(n, max(x, y));
}
root=1,tarjan(1, 0);
// 得到 cnt, flag;
if(cnt == 0) {
// 无割.
size[1] = n ;
ans += min(2, size[1]);
ll p2 = (size[1] == 1 ? 1 : (ll)size[1]*(size[1]-1)/2);
printf("%d %lld\n",ans,p2);
}
else {
// cnt > 0, 有割点.
int tar = 0;
for(int i=1;i<=n;++i) if(iscut[i]) {
tar=i;
break;
}
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
a2=1ll;
DFS(tar, 0);
printf("%d %lld\n", ans,a2);
}
}
int main() {
// setIO("input");
while(1) {
scanf("%d",&m);
if(!m) {
break ;
}
solve();
}
return 0;
}
新年的毒瘤
来源：UOJ#67. 新年的毒瘤
1.被删的点不能是割点.
2.可能出现一棵树和一个点的情况，需要特判一下.
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100009
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int ans, si;
int low[N],dfn[N],iscut[N], mk[N], scc;
int n,m, deg[N],hd[N], to[N<<1], nex[N<<1], edges;
void add(int u,int v) {
nex[++edges]=hd[u];
hd[u]=edges;
to[edges]=v;
}
void tarjan(int x, int ff) {
++si;
low[x]=dfn[x]=++scc;
int son=0;
for(int i=hd[x];i;i=nex[i]) {
if(i==ff) continue;
int v=to[i];
if(!dfn[v]) {
tarjan(v, i^1);
++son;
low[x]=min(low[x], low[v]);
if(low[v]>=dfn[x]) iscut[x]=1;
}
else low[x]=min(low[x], dfn[v]);
}
if(x==1&&son==1) iscut[x]=0;
if(!iscut[x] && m - deg[x] == n - 2) mk[x] = 1, ++ ans;
}
int main() {
// setIO("input");
scanf("%d%d",&n,&m);
edges=1;
for(int i=1;i<=m;++i) {
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
++deg[x];
++deg[y];
}
tarjan(1, 0);
if(si == 1) {
if(n > 2) { printf("1\n"); printf("1"); }
else { printf("2\n"); printf("1 2\n"); }
}
else {
for(int i=1;i<=n;++i) {
if(!dfn[i]) {
printf("1\n");
printf("%d",i);
return 0;
}
}
printf("%d\n",ans);
for(int i=1;i<=n;++i) if(mk[i]) printf("%d ",i);
}
return 0;
}
Sum
来源：CF1442D
有一个结论：最终选数情况一定是若干个数组取满，一个数组不取满（或也去满）
单调性上考虑，可以把小的部分全部给大的部分, 所以去满是更优的.
枚举那个取不满的数组，其他数组做 01 背包，然后最后再枚举取不满的选几个.
直接枚举取不满的数组太慢，于是用分治来做这个过程即可.
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define N 3006
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,K,a[N][N],num[N];
ll sum[N],f[20][N],ans;
void solve(int l, int r, int dep) {
if(l == r) {
// get dep-1
ll ss=0;
ans=max(ans, f[dep-1][K]);
for(int i=1;i<=num[l];++i) {
if(i > K)
break;
ss+=a[l][i];
ans=max(ans, ss+f[dep-1][K-i]);
}
return ;
}
int mid=(l+r)>>1;
for(int i=K;i>=0;--i) f[dep][i]=f[dep-1][i];
for(int i=mid+1;i<=r;++i) {
// num[i]: 体积.
for(int j=K;j>=num[i];--j) {
f[dep][j]=max(f[dep][j], f[dep][j-num[i]]+sum[i]);
}
}
ans=max(ans, f[dep][K]);
solve(l, mid, dep+1);
for(int i=K;i>=0;--i) f[dep][i]=f[dep-1][i];
for(int i=l;i<=mid;++i) {
for(int j=K;j>=num[i];--j) {
f[dep][j]=max(f[dep][j], f[dep][j-num[i]]+sum[i]);
}
}
ans=max(ans, f[dep][K]);
solve(mid+1, r, dep+1);
}
int main() {
// setIO("input");
scanf("%d%d",&n,&K);
for(int i=1;i<=n;++i) {
scanf("%d",&num[i]);
for(int j=1;j<=num[i];++j) {
scanf("%d",&a[i][j]);
sum[i]+=a[i][j];
}
// 得到若干背包.
}
f[0][0]=0;
solve(1, n, 1);
printf("%lld\n",ans);
return 0;
}
Redundant Paths G
来源：洛谷P2860 [USACO06JAN]Redundant Paths G
跑一个边双，然后缩点.
树形结构的叶子可以两两配对，手画一下发现满足题意.
答案就是叶子数量/2 (向上取整）
#include <cstdio>
#include <stack>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 10009
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,m;
stack<int>s;
vector<int>node[N];
int low[N], dfn[N], vis[N], deg[N], scc,id;
int hd[N],to[N<<1],nex[N<<1],edges,fin[N];
void add(int u, int v) {
nex[++edges]=hd[u];
hd[u]=edges;
to[edges]=v;
}
void tarjan(int x, int fa) {
// printf("%d %d\n",x, fa);
s.push(x);
vis[x] = 1;
low[x] = dfn[x] = ++scc;
for(int i = hd[x]; i ; i = nex[i]) {
int v = to[i];
if( i == fa) continue;
if(!vis[v]) {
tarjan(v, i ^ 1);
low[x] = min(low[x], low[v]);
}
else if(vis[v] != -1) low[x] = min(low[x], dfn[v]);
}
if(low[x] == dfn[x]) {
++ id;
for( ; ; ) {
int p = s.top(); s.pop();
node[id].pb(p);
fin[p] = id, vis[p] = -1;
if(p == x) break ;
}
}
}
int main() {
// setIO("input");
scanf("%d%d",&n,&m);
edges = 1;
for(int i=1;i<=m;++i) {
int x, y;
scanf("%d%d",&x,&y);
add(x, y);
add(y, x);
}
// edges and edges^1
for(int i = 1; i <= n ; ++ i)
if(!vis[i]) tarjan(i, -1);
// printf("%d\n",id);
for(int i = 1; i <= id; ++ i) {
// 边双联通分量.
for(int j = 0; j < node[i].size(); ++j) {
int x = node[i][j];
for(int o = hd[x]; o; o = nex[o]) {
int v = to[o];
if(fin[v] == i) continue;
deg[fin[v]] ++ ;
}
}
}
int tot = 0;
for(int i = 1; i <= id ; ++ i) if(deg[i] == 1) ++ tot;
if(!tot) {
printf("0\n");
}
else {
printf("%d\n",(tot+1)/2);
}
return 0;
}
Choosing Ads
来源：CF643G
考虑这样一个模型：给定一个数列,求众数,空间大小为 1mb.
每次将两个不同的数拿出来消掉, 最后没被消掉的一定就是众数.
因为众数比其他数都多, 所以最后剩的一定是众数.
这道题求区间前 $\mathrm{k}$ 大数, 类比求众数的做法,每次将 $\mathrm{k+1}$ 个不同的一起消掉.
由于最多可以分 $\mathrm{\frac{len}{k+1}}$ 组, 故一定有没被消掉的前 $\mathrm{k}$ 大数.
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 150009
#define ll long long
#define pb push_back
#define ls now<<1
#define rs now<<1|1
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int tag[N<<2],P,len[N<<2],A[N],n,m;
struct data {
int num, a[5], b[5];
data operator = (const data &o){
num = o.num;
memcpy(a, o.a, sizeof a);
memcpy(b, o.b, sizeof b);
return *this;
}
void INI(int v, int l) {
a[0]=v, num=1, b[0]=l;
}
data operator+(const data o) const {
data B=o;
for(int i=0;i<num;++i) {
int flag=0;
for(int j=0;j<B.num;++j) {
if(a[i]==B.a[j]) {
flag=1,B.b[j]+=b[i];
break;
}
}
if(flag) continue;
if(B.num<P) {
B.a[B.num] = a[i];
B.b[B.num] = b[i];
++B.num;
continue;
}
int k=0;
for(int j=0;j<B.num;++j)
if(B.b[j]<B.b[k]) k=j;
if(b[i]<B.b[k]) {
for(int j=0;j<B.num;++j) B.b[j] -= b[i];
}
else {
int tmp=B.b[k];
B.a[k]=a[i];
B.b[k]=b[i];
for(int j=0;j<B.num;++j) B.b[j]-=tmp;
}
}
return B;
}
}s[N<<2];
void mark(int now, int v) {
s[now].INI(v, len[now]);
tag[now]=v;
}
void pushdown(int now) {
if(tag[now]) {
mark(ls, tag[now]);
mark(rs, tag[now]);
}
tag[now]=0;
}
void build(int l,int r,int now) {
len[now]=r-l+1;
if(l==r) {
s[now].INI(A[l], 1);
return ;
}
int mid=(l+r)>>1;
build(l,mid,ls);
build(mid+1,r,rs);
s[now]=s[ls]+s[rs];
}
void update(int l,int r,int now,int L,int R,int v) {
if(l>=L&&r<=R) {
mark(now, v);
return ;
}
pushdown(now);
int mid=(l+r)>>1;
if(L<=mid) update(l,mid,ls,L,R,v);
if(R>mid) update(mid+1,r,rs,L,R,v);
s[now]=s[ls]+s[rs];
}
data query(int l,int r,int now,int L,int R) {
if(l>=L&&r<=R) {
//printf("%d\n",s[now].a[0]);
return s[now];
}
pushdown(now);
int mid=(l+r)>>1;
if(L<=mid&&R>mid) return query(l,mid,ls,L,R)+query(mid+1,r,rs,L,R);
else if(L<=mid) return query(l,mid,ls,L,R);
else return query(mid+1,r,rs,L,R);
}
int main() {
// setIO("input");
scanf("%d%d%d",&n,&m,&P);
P=100/P;
for(int i=1;i<=n;++i) {
scanf("%d",&A[i]);
}
build(1,n,1);
for(int i=1;i<=m;++i) {
int op,l,r,z;
scanf("%d%d%d",&op,&l,&r);
if(op==1) scanf("%d",&z), update(1,n,1,l,r,z);
if(op==2) {
data e = query(1,n,1,l,r);
printf("%d ",e.num);
for(int j=0;j<e.num;++j)
printf("%d ",e.a[j]);
printf("\n");
}
}
return 0;
}
X-OR
来源：CF1364E
显然，如果知道 0 的位置整个排列就都知道了.
考虑如何求一个位置的数字：得到 $\mathrm{x}$ 与一些位置做 $\mathrm{or}$ 运算的答案并做与运算.
知道 $\mathrm{x}$ 位置的数字后不妨枚举数列中每个数并与 $\mathrm{x}$ 做或运算.
若或的结果等于 $\mathrm{p[x]}$，说明该位置的数为 $\mathrm{x}$ 的真子集，这样就会找到 $\mathrm{0}$.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <ctime>
#define ll long long
using namespace std;
int n ;
int ran(int o) {
return (ll) rand() * rand() % o + 1;
}
int RAN(int x) {
int y = ran(n);
while(y == x) y = ran(n);
return y;
}
int Query(int x, int y) {
cout << "? " << x << " " << y << endl;
fflush(stdout);
int an;
cin >> an;
return an;
}
int get(int x) {
int tmp = Query(x, RAN(x));
for(int i=1;i<=14;++i) {
tmp &= Query(x, RAN(x));
}
return tmp ;
}
int ans[4002];
int main() {
srand(time(NULL));
cin >> n;
int x = ran(n), v = get(x);
for(int i = 1; i <= n ; ++i)
if(x != i && v) {
int h = Query(x, i);
if(h == v) {
x = i;
v = get(i);
if(v == 0) break;
}
}
ans[x] = 0;
for(int i = 1; i <= n ; ++ i) {
if(i != x) ans[i] = Query(i, x);
}
cout << "! " ;
for(int i = 1; i <= n ; ++ i) {
cout << ans[i] << " ";
}
cout << endl;
fflush(stdout);
return 0;
}
Campus
来源：CF571D
对两个树分别离线建立 kruskal 重构树.
则只需对第一个树的 DFS 序可持久化, 第二个树查询一下清空时间.
但是本做法需要极大的空间（倍增数组和可持久化）
思路是对的, 但是在 OJ 上并不能通过.
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define N 1000009
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,m,M,W,rt[N];
struct PSGT {
int tot;
ll sum[N*20];
int ls[N*20],rs[N*20];
void build(int &x,int l,int r) {
x=++tot;
if(l==r) return ;
int mid=(l+r)>>1;
build(ls[x], l, mid);
build(rs[x], mid+1, r);
}
int update(int x, int l, int r, int p, int v) {
int now=++tot;
sum[now]=sum[x]+v;
ls[now]=ls[x];
rs[now]=rs[x];
if(l==r) return now;
int mid=(l+r)>>1;
if(p<=mid) ls[now]=update(ls[x], l, mid, p, v);
else rs[now]=update(rs[x], mid+1, r, p, v);
return now;
}
ll query(int x, int l, int r, int L, int R) {
if(!x) return 0;
if(l>=L&&r<=R) return sum[x];
int mid=(l+r)>>1;
ll re=0;
if(L<=mid) re+=query(ls[x], l, mid, L, R);
if(R>mid) re+=query(rs[x], mid+1, r, L, R);
return re;
}
ll Q(int L, int R, int p) {
if(L>R) return 0;
return query(rt[R], 1, M, 1, p) - query(rt[L-1], 1, M, 1, p);
}
}T;
// 区间赋值，单点查询.
struct SGT {
int tag[N<<2];
void update(int l,int r,int now,int L,int R,int v) {
if(l>=L&&r<=R) { tag[now]=v; return ; }
int mid=(l+r)>>1;
if(L<=mid) update(l, mid, now<<1, L, R, v);
if(R>mid) update(mid+1,r, now<<1|1,L,R,v);
}
int query(int l,int r,int now,int L,int R) {
if(l>=L&&r<=R) return tag[now];
int px=tag[now],mid=(l+r)>>1;
// printf("%d %d %d %d %d\n",l,r,L,R,tag[now]);
if(L<=mid) px=max(px, query(l,mid,now<<1,L,R));
if(R>mid) px=max(px, query(mid+1,r,now<<1|1,L,R));
return px;
}
}E;
struct Tree {
vector<int>G[N];
int size[N];
int cnt, fa[20][N], now[N], tim[N], val[N], st[N], ed[N], scc;
void init() {
cnt = n, scc = 0;
for(int i=1;i<=n;++i) {
now[i]=i;
}
}
void merge(int x, int y, int ti) {
++cnt;
x = now[x];
y = now[y];
fa[0][x] = cnt;
fa[0][y] = cnt;
now[x] = cnt;
tim[cnt] = ti;
val[cnt] = x;
// tim 时刻进行的合并.
}
void dfs(int x) {
st[x] = ++scc;
size[x] = (x<=n);
for(int i=0;i<G[x].size();++i) {
int v=G[x][i];
for(int j=1;j<20;++j)
fa[j][v]=fa[j-1][fa[j-1][v]];
dfs(v);
size[x] += size[v];
}
ed[x] = scc;
}
int jump(int x, int ti) {
for(int i=19;i>=0;--i)
if(tim[fa[i][x]] <= ti) x=fa[i][x];
return x;
}
void build_tree() {
for(int i=1;i<=cnt;++i) {
G[fa[0][i]].pb(i);
}
tim[0]=N, dfs(0);
}
}t1,t2;
struct node {
int op, x;
}a[N];
int main() {
// setIO("input");
// printf("paq\n");
scanf("%d%d",&n,&m);
t1.init();
t2.init();
for(int i=1;i<=m;++i) {
char op[10];
scanf("%s",op);
if(op[0]=='U') {
// 第一颗树的合并.
int x, y;
scanf("%d%d",&x,&y);
t1.merge(x, y, i);
}
if(op[0]=='M') {
int x, y;
scanf("%d%d",&x,&y);
t2.merge(x, y, i);
}
if(op[0]=='A') {
// 找到最靠上的 x, 可持久化修改（单点）
scanf("%d",&a[i].x),a[i].op=3;
}
if(op[0]=='Z') {
// 找到最靠上的 x, 进行区间赋值（最新的时间）
scanf("%d",&a[i].x),a[i].op=4;
}
if(op[0]=='Q') {
// 先在第二棵线段树中找到时间，再在第一颗线段树中去查询.
scanf("%d",&a[i].x),a[i].op=5;
}
}
t1.build_tree();
t2.build_tree();
M=t1.scc;
W=t2.scc;
for(int i=1;i<=m;++i) {
if(a[i].op == 3) {
int x = a[i].x;
int p = t1.jump(x, i);
int sz = t1.size[p];
rt[i] = T.update(rt[i-1], 1, M, t1.st[p], sz);
if(t1.ed[p] +1 <= M) rt[i] = T.update(rt[i], 1, M, t1.ed[p] + 1, -sz);
//printf("%lld\n",T.sum[rt[i]]);
}
else rt[i] = rt[i-1];
if(a[i].op == 4) {
int x = a[i].x;
int p = t2.jump(x, i);
// printf("%d %d\n",t2.st[p],t2.ed[p]);
E.update(1, W, 1, t2.st[p], t2.ed[p], i);
}
if(a[i].op == 5) {
int x = a[i].x;
int id1 = t1.st[x];
int id2 = t2.st[x];
int l = E.query(1, W, 1, id2, id2);
// printf("%d\n",l);
printf("%lld\n",T.Q(l+1, i, id1));
}
}
return 0;
}
Mike and Fish
来源：CF547D
不妨将每个点看成边, 在 $\mathrm{x[i], y[i]}$ 之间连一条无向边.
对于横坐标, 指出去的边表示染成红色, 指进来的边代表染成蓝色.
如果每条横/竖线上点的个数都是偶数的话跑一个欧拉回路定向即可.
如果是奇数则向虚拟点连一条无向边,在最后的总图上跑欧拉回路.
由于每个奇点和虚拟点只有一条边,所以满足条件.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 500003
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const int D=(int)2e5+3;
int vis[N];
int n,px[N],py[N],hd[N],deg[N<<1],to[N<<1],nex[N<<1],edges;
void add(int u, int v) {
nex[++edges]=hd[u];
hd[u]=edges;
to[edges]=v;
}
void dfs(int x) {
for(int &i=hd[x];i;i=nex[i]) {
int e = i >> 1;
if(!vis[e]) {
// 给 e 这个点定向.
vis[e] = 1;
if(to[i] <= D) vis[e] = -1;
dfs(to[i]);
}
}
}
int main() {
// setIO("input");
scanf("%d",&n);
edges = 1;
for(int i=1;i<=n;++i) {
scanf("%d%d",&px[i],&py[i]);
add(px[i], py[i]+D);
add(py[i]+D, px[i]);
++deg[py[i] + D];
++deg[px[i]];
}
for(int i=1;i<=2*D;++i)
if(deg[i] & 1) add(i, 0), add(0, i);
for(int i=1;i<=D;++i) {
dfs(i);
}
for(int i=1;i<=n;++i) {
if(vis[i] == 1) printf("r");
else printf("b");
}
return 0;
}
Lowbit
来源：“红旗杯”第十五届东北地区大学生程序设计竞赛
发现对于一个数来说，经过 $\log n$ 次操作后会变为 $2 ^ {\mathrm{i}}$ 的形式.
而对于形式为 $2 ^ { \mathrm{i}}$ 的数字来说，每次操作就等同于乘以 $2.$
显然可以用类似于势能线段树的东西来维护.
对于每一个区间维护一个 $\mathrm{si}$ 表示未达到 $2 ^ { \mathrm{i}}$ 形式的个数.
若更新区间的 $\mathrm{si}=0$, 则直接打区间乘法标记，否则暴力更新.
时间复杂度：$O(n \log^2 n).$
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <algorithm>
#define N 100009
#define ls now<<1
#define rs now<<1|1
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const int mod=998244353;
ll a[N];
ll lowbit(ll x) { return x&(-x); }
struct data {
int sum,tag,si;
}s[N<<2];
void pushup(int now) {
s[now].si=s[ls].si+s[rs].si;
s[now].sum=(ll)(s[ls].sum+s[rs].sum)%mod;
}
void build(int l, int r, int now) {
s[now].tag=1;
s[now].si=0;
s[now].sum=0;
if(l==r) {
int v=(int)a[l];
s[now].sum=v%mod;
if(lowbit(v)==v) {
s[now].si=0;
}
else {
s[now].si=1;
}
return ;
}
int mid=(l+r)>>1;
build(l,mid,ls);
build(mid+1,r,rs);
pushup(now);
}
void mark(int now, int v) {
s[now].tag=(ll)s[now].tag*v%mod;
s[now].sum=(ll)s[now].sum*v%mod;
}
void pushdown(int now) {
if(s[now].tag!=1) {
mark(ls, s[now].tag);
mark(rs, s[now].tag);
s[now].tag=1;
}
}
void update(int l, int r , int now, int L, int R) {
if(l==r) {
if(s[now].si==0) {
s[now].sum=(ll)s[now].sum*2%mod;
return ;
}
else {
ll v=lowbit(a[l]);
a[l]+=v;
s[now].sum=a[l]%mod;
if(a[l]==lowbit(a[l])) {
s[now].si=0;
}
else {
s[now].si=1;
}
}
return ;
}
if(l>=L&&r<=R) {
if(s[now].si==0) {
mark(now, 2);
}
else {
pushdown(now);
int mid=(l+r)>>1;
update(l,mid,ls,L,R);
update(mid+1,r,rs,L,R);
pushup(now);
}
return ;
}
pushdown(now);
int mid=(l+r)>>1;
if(L<=mid) update(l,mid,ls,L,R);
if(R>mid) update(mid+1,r,rs,L,R);
pushup(now);
}
int query(int l, int r, int now, int L, int R) {
if(l>=L&&r<=R) {
// printf("%d %d %d\n",l,r,s[now].sum);
return s[now].sum;
}
pushdown(now);
int mid=(l+r)>>1,re=0;
if(L<=mid) (re+=query(l,mid,ls,L,R))%=mod;
if(R>mid) (re+=query(mid+1,r,rs,L,R))%=mod;
return re;
}
void solve() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i) {
scanf("%lld",&a[i]);
}
build(1, n, 1);
int m;
scanf("%d",&m);
for(int i=1;i<=m;++i) {
int op,l,r;
scanf("%d%d%d",&op,&l,&r);
if(op==1) {
update(1, n, 1, l, r);
}
else {
printf("%d\n",query(1, n, 1, l, r));
}
}
}
int main() {
// setIO("input");
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
Expected Damage
来源：CF1418E
算期望的题要么就将所有情况的和算完除以阶乘，要么算概率.
这道题算概率更轻松一些，因为可以少考虑很多情况.
按照 $\mathrm{d_{i}}$ 是否大于等于 $\mathrm{a_{i}}$ 来讨论即可.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 200008
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const int mod=998244353;
int n,m,d[N],a[N],b[N],sum[N];
int qpow(int x, int y) {
int tmp=1;
for(;y;y>>=1,x=(ll)x*x%mod)
if(y&1) tmp=(ll)tmp*x%mod;
return tmp;
}
int get_inv(int x) {
return qpow(x, mod-2);
}
int GET(int l,int r) {
if(l>r) return 0;
return (ll)(sum[r]-sum[l-1]+mod)%mod;
}
int main() {
// setIO("input");
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) {
scanf("%d",&d[i]);
}
sort(d+1,d+1+n);
for(int i=1;i<=n;++i) {
sum[i]=(ll)(sum[i-1]+d[i])%mod;
}
for(int i=1;i<=m;++i) {
scanf("%d%d",&a[i],&b[i]);
int x=0,p=n+1,ans=0;
if(b[i]<=d[n]) {
p=lower_bound(d+1,d+1+n,b[i])-d;
x=n-p+1;
}
if(x>a[i]) {
// p = ( x-a[i] ) / x
// v = d[j]
// 则 delta = p * v
int per = (ll)(x + mod - a[i])%mod*get_inv(x)%mod;
int v = (ll)GET(p, n);
(ans+=(ll)per*v%mod)%=mod;
}
if(x>=a[i]) {
int p2 = (ll)(x + 1 + mod - a[i])%mod*get_inv(x+1)%mod;
int v2 = GET(1, p-1);
// printf("%d %d\n",p2,v2);
(ans+=(ll)p2*v2%mod) %=mod;
}
printf("%d\n",ans);
}
return 0;
}
Roads and Ramen
来源：CF1413F
如果没有 $1$ 的个数为偶数的限制答案显然是树的直径.
如果树的直径中 $1$ 的个数为偶数答案也为树的直径.
不妨猜一下答案的一个端点一定是树的直径的两个端点之一.
那么就用两颗线段树分别维护两个端点为根时的 DFS 序的情况.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 500002
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,edges;
int dep[N],hd[N],to[N<<1],nex[N<<1],val[N<<1],bes[N];
struct DIA {
int mx,u,v;
DIA(int mx=0,int u=0,int v=0):mx(mx),u(u),v(v){}
}an;
// f(0): number of 1 is even
// f(1): number of 1 is odd
// max0: max of even
// max1: max of add
// if(tag) swap(max0,max1)
struct Tree {
#define ls now<<1
#define rs now<<1|1
int d1[N],dis[N],st[N],ed[N],bu[N],fa[N],scc;
void dfs(int x,int ff) {
st[x]=++scc;
bu[scc]=x;
fa[x]=ff;
for(int i=hd[x];i;i=nex[i]) {
int v=to[i];
if(v==ff) continue;
dis[v]=dis[x]+1;
d1[v]=d1[x]+(val[i]==1);
dfs(v,x);
}
ed[x]=scc;
}
struct data {
int tag,m0,m1;
data() { tag=m0=m1=0; }
}s[N<<2];
void mark(int now) {
s[now].tag^=1;
swap(s[now].m0,s[now].m1);
}
void pushdown(int now) {
if(s[now].tag) {
mark(ls);
mark(rs);
s[now].tag=0;
}
}
void pushup(int now) {
s[now].m0=max(s[ls].m0,s[rs].m0);
s[now].m1=max(s[ls].m1,s[rs].m1);
}
void update(int l,int r,int now,int L,int R) {
if(l>=L&&r<=R) {
mark(now);
return ;
}
pushdown(now);
int mid=(l+r)>>1;
if(L<=mid) update(l,mid,ls,L,R);
if(R>mid) update(mid+1,r,rs,L,R);
pushup(now);
}
int query(int l,int r,int now,int L,int R) {
if(l>=L&&r<=R) return s[now].m0;
pushdown(now);
int mid=(l+r)>>1,re=0;
if(L<=mid) re=max(re,query(l,mid,ls,L,R));
if(R>mid) re=max(re,query(mid+1,r,rs,L,R));
return re;
}
void build(int l,int r,int now) {
if(l==r) {
s[now].m0=s[now].m1=0;
if(d1[bu[l]]%2==0) {
s[now].m0=dis[bu[l]];
}
else {
s[now].m1=dis[bu[l]];
}
return ;
}
int mid=(l+r)>>1;
build(l,mid,ls);
build(mid+1,r,rs);
pushup(now);
}
void solve(int u,int v) {
if(fa[v]==u) swap(u, v);
// printf("%d %d\n",v,fa[u]);
// fa[u] = v
// flip (st[u], ed[u])
update(1,n,1,st[u],ed[u]);
}
}t[2];
struct Edge {
int u,v,c;
Edge(int u=0,int v=0,int c=0):u(u),v(v),c(c){}
}e[N];
void add(int u,int v,int c) {
nex[++edges]=hd[u];
hd[u]=edges;
to[edges]=v;
val[edges]=c;
}
void dfs1(int x,int ff) {
bes[x]=x;
for(int i=hd[x];i;i=nex[i]) {
int v=to[i];
if(v==ff) continue;
dep[v]=dep[x]+1;
dfs1(v,x);
if(an.mx<dep[bes[x]]+dep[bes[v]]-2*dep[x]) {
an=DIA(dep[bes[x]]+dep[bes[v]]-2*dep[x],bes[x],bes[v]);
}
if(dep[bes[v]]>dep[bes[x]])
bes[x]=bes[v];
}
// printf("%d %d\n",x,dep[bes[x]]-dep[x]);
}
int main() {
// setIO("input");
scanf("%d",&n);
for(int i=1;i<n;++i) {
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
e[i]=Edge(x,y,z);
}
dfs1(1,0);
// printf("%d\n",an.mx);
// get (an.u, an.v);
// dfs(u) and dfs(v)
t[0].dfs(an.u, 0);
t[1].dfs(an.v, 0);
t[0].build(1,n,1);
t[1].build(1,n,1);
int Q;
scanf("%d",&Q);
for(int i=1;i<=Q;++i) {
int id;
scanf("%d",&id);
t[0].solve(e[id].u, e[id].v);
t[1].solve(e[id].u, e[id].v);
printf("%d\n",max(t[0].s[1].m0, t[1].s[1].m0));
}
return 0;
}
x-prime Substrings
来源：CF1400F
打一个表发现不合法的子串个数很少.
不妨对这些子串建立一个 AC 自动机.
然后就是经典问题：构造一个长度为 $\mathrm{n}$ 的串且不能走到 AC 自动机中的危险节点的方案数.
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#define N 100006
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
queue<int>q;
char str[1005];
int a[30],sum[30][30],dp[1003][5003];
int cnt,ch[N][10],fail[N],dan[N],X;
void check(int x, int bu) {
for(int i=1;i<=x;++i) for(int j=0;j<=x;++j) sum[i][j]=0;
// int flag=0;
for(int i=1;i<=x;++i)
for(int j=i;j<=x;++j) {
sum[i][j]=sum[i][j-1]+a[j];
if(i==1&&j==x)
continue;
if(bu%sum[i][j]==0)
return ;
}
// 将 array a of length x 插入.
int o=0;
for(int i=1;i<=x;++i) {
// insert(a[i])
if(!ch[o][a[i]]) ch[o][a[i]]=++cnt;
o=ch[o][a[i]];
}
// 将 o 插入了.
dan[o]=1;
}
void dfs(int x, int sum) {
if(sum==X) check(x, sum);
for(int i=1;i<=9;++i) {
if(sum+i<=X)
a[x+1]=i, dfs(x+1, sum+i), a[x+1]=0;
}
}
void init() {
dfs(0, 0);
for(int i=1;i<=9;++i)
if(ch[0][i]) q.push(ch[0][i]);
while(!q.empty()) {
int u=q.front(); q.pop();
for(int i=1;i<=9;++i) {
int v=ch[u][i];
if(!v) {
ch[u][i]=ch[fail[u]][i];
continue;
}
if(dan[u])
dan[v]=1;
fail[v]=ch[fail[u]][i];
q.push(v);
}
}
}
int main() {
// setIO("input");
scanf("%s",str+1);
scanf("%d",&X);
init();
int n=strlen(str+1);
// dp[i][j]: DP 到 i, 在后缀自动机上位于 j 的最小删除.
memset(dp, 0x3f, sizeof(dp));
dp[0][0]=0;
for(int i=0;i<n;++i)
for(int j=0;j<=cnt;++j) {
if(dp[i][j]>N) continue;
// dp[i][j] 有值.
dp[i+1][j]=min(dp[i+1][j], dp[i][j]+1);
int v=ch[j][str[i+1]-'0'];
if(!dan[v]) dp[i+1][v]=min(dp[i+1][v], dp[i][j]);
}
int ans=N;
for(int j=0;j<=cnt;++j) ans=min(ans, dp[n][j]);
printf("%d\n",ans);
return 0;
}
Sky Full of Stars
来源： CF997C
计数题中出现恰好时一般要用容斥.
这道题显然可以用二项式反演来做.
推式子的时候发现很多项可以用二项式定理来化简.
$f(k)=\sum_{\mathrm{i}=k}^{n} \binom{i}{k} g(i) $
则 $g(k)=\sum_{i=k}^{n} (-1)^{i-k} \binom{i}{k} f(i)$
这是二项式反演的使用条件，满足第一条才可以使用反演.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const int N=(int)1e6+4;
const int mod=998244353;
int fac[N],inv[N];
int qpow(int x,ll y) {
int tmp=1;
for(;y;y>>=1,x=(ll)x*x%mod)
if(y&1) {
tmp=(ll)tmp*x%mod;
}
return tmp;
}
int get_inv(int x) {
return qpow(x, (ll)mod-2);
}
void init() {
fac[0]=inv[0]=1;
for(int i=1;i<N;++i) {
fac[i]=(ll)fac[i-1]*i%mod;
inv[i]=get_inv(fac[i]);
}
}
int C(int x, int y) {
return (ll)fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main() {
// setIO("input");
init();
int n ;
scanf("%d",&n);
int con=qpow(3, 1ll*n*n),an1=0;
for(int i=1;i<=n;++i) {
int d=(i&1)?(mod-1):1;
(an1+=(ll)d*C(n, i)%mod*qpow(3, i)%mod*get_inv(qpow(3, 1ll*n*i))%mod)%=mod;
}
an1=(ll)con*2%mod*an1%mod;
int con2=qpow(3, 1ll*n*n+1),an2=0;
for(int i=1;i<=n;++i) {
int d=(i&1)?(mod-1):1;
(an2+=(ll)d*C(n, i)%mod*get_inv(qpow(3, 1ll*n*i))%mod*(ll)(qpow(mod+1-get_inv(qpow(3, n-i)), n)+mod-1)%mod)%=mod;
}
an2=(ll)an2*con2%mod;
an1=mod-an1;
an2=mod-an2;
printf("%d\n",(ll)(an1+an2)%mod);
return 0;
}
XOR on Segment
来源：CF242E
对于每一个二进制位建立一颗线段树.
区间异或 $\mathrm{x}$ 的时候将 $\mathrm{x}$ 分位对于对应位异或.
在线段树中的操作就是将 $num(x)$ 变为 $len(x)-num(x).$
时间复杂度和空间复杂度都是 $n \log ^ 2 n $ 的.
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100001
#define ll long long
#define ls now<<1
#define rs now<<1|1
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int a[N],n;
struct Segment_Tree {
int o;
int sum[N<<2],len[N<<2],tag[N<<2];
void pushup(int now) {
sum[now]=sum[ls]+sum[rs];
}
void build(int l, int r, int now) {
sum[now]=0;
len[now]=r-l+1;
tag[now]=0;
if(l==r) {
if(a[l]&(1<<o))
sum[now]=1;
return ;
}
int mid=(l+r)>>1;
build(l,mid,ls);
build(mid+1,r,rs);
pushup(now);
}
void mark(int now) {
tag[now]^=1;
sum[now]=len[now]-sum[now];
}
void pushdown(int now) {
if(tag[now]) {
mark(ls);
mark(rs);
tag[now]=0;
}
}
void update(int l, int r, int now, int L, int R) {
if(l>=L&&r<=R) {
mark(now);
return ;
}
pushdown(now);
int mid=(l+r)>>1;
if(L<=mid) update(l, mid, ls, L, R);
if(R>mid) update(mid+1, r, rs, L, R);
pushup(now);
}
int query(int l, int r, int now, int L, int R) {
if(l>=L&&r<=R) return sum[now];
pushdown(now);
int mid=(l+r)>>1,re=0;
if(L<=mid) re+=query(l,mid,ls,L,R);
if(R>mid) re+=query(mid+1,r,rs,L,R);
return re;
}
}T[20];
int main() {
// setIO("input");
scanf("%d",&n);
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
}
for(int i=0;i<=19;++i) {
T[i].o=i;
T[i].build(1, n, 1);
}
int m ;
scanf("%d",&m);
for(int i=1;i<=m;++i) {
int op,l,r,x;
scanf("%d",&op);
if(op==1) {
scanf("%d%d",&l,&r);
ll ans=0;
for(int j=0;j<=19;++j) {
int num=T[j].query(1,n,1,l,r);
ans+=1ll*(1<<j)*num;
}
printf("%lld\n",ans);
}
else {
scanf("%d%d%d",&l,&r,&x);
for(int j=0;j<=19;++j) {
if(x&(1<<j))
T[j].update(1,n,1,l,r);
}
}
}
return 0;
}
Easy Math Problem
来源：The 15th Chinese Northeast Collegiate Programming Contest
降智水题.
6p=p+2p+3p，按照这个来构造即可.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define pb push_back
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
void solve() {
ll p;
scanf("%lld",&p);
ll mo=p*6;
printf("%lld %d\n",mo,3);
printf("%lld %lld %lld\n",mo/6,mo/3,mo/2);
}
int main() {
// setIO("input");
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
Standing Out from the Herd P
来源：洛谷P4081 [USACO17DEC]Standing Out from the Herd P
复习一下广义 SAM.
这道题暴力跳 father 打标记即可，或者 dfs 的时候特判都行.
刚开始后缀自动机板子中 nq 打成 np 错了半天.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 100009
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
char str[N];
ll ans[N];
int last,tot;
vector<int>G[N<<1];
int col[N<<1],dan[N<<1];
int ch[N<<1][26],pre[N<<1],len[N<<1];
void init() {
last=tot=1;
}
void extend(int c, int id) {
if(ch[last][c]) {
int p=last,q=ch[last][c];
if(len[q]==len[p]+1) last=q;
else {
int nq=++tot;
len[nq]=len[p]+1;
dan[nq]=dan[q], col[nq]=col[q];
memcpy(ch[nq], ch[q], sizeof(ch[q]));
pre[nq]=pre[q], pre[q]=nq;
for(;p&&ch[p][c]==q;p=pre[p]) ch[p][c]=nq;
last=nq;
}
}
else {
int np=++tot,p=last;
len[np]=len[p]+1,last=np;
for(;p&&!ch[p][c];p=pre[p])
ch[p][c]=np;
if(!p) pre[np]=1;
else {
int q=ch[p][c];
if(len[q]==len[p]+1) pre[np]=q;
else {
int nq=++tot;
len[nq]=len[p]+1;
dan[nq]=dan[q], col[nq]=col[q];
memcpy(ch[nq],ch[q],sizeof(ch[q]));
pre[nq]=pre[q], pre[np]=pre[q]=nq;
for(;p&&ch[p][c]==q;p=pre[p])
ch[p][c]=nq;
}
}
}
for(int p=last;p;p=pre[p]) {
if(col[p]) {
if(col[p]!=id) dan[p]=1;
break;
}
else {
col[p]=id;
}
}
}
void dfs(int x) {
for(int i=0;i<G[x].size();++i) {
int y=G[x][i];
dfs(y);
dan[x]|=dan[y];
if(col[x]!=col[y])
dan[x]=1;
}
if(!dan[x]) {
ans[col[x]]+=len[x]-len[pre[x]];
}
}
int main() {
// setIO("input");
init();
int T;
scanf("%d",&T);
for(int i=1;i<=T;++i) {
scanf("%s",str+1);
int n=strlen(str+1);
last=1;
for(int j=1;j<=n;++j) {
extend(str[j]-'a', i);
}
}
for(int i=2;i<=tot;++i) {
G[pre[i]].pb(i);
}
dfs(1);
for(int i=1;i<=T;++i) {
printf("%lld\n",ans[i]);
}
return 0;
}
k-th Smallest Common Substring
来源：The 15th Chinese Northeast Collegiate Programming Contest
对 n 个串建立广义后缀自动机.
显然可以在线性时间内标记出后缀自动机哪些节点是包含 $n$ 个串的.
如果是一次询问可以贪心按照转移边来遍历自动机.
多次询问的话需要用到一个技巧：将串翻转，则新串后缀树上对应新串后缀就是原串前缀.
在新的后缀树上，点 $x$ 的所有儿子的 $\mathrm{lcp}$ 就是 $\mathrm{len[x]}$.
这样可以对于每个点预处理出该点所有串的排名（求一遍前缀和）
询问的时候在所有串的排名上二分一下就行.
#include <cstdio>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#define ll long long
#define pb push_back
#define N 200009
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
char str[N];
ll sum[N<<1];
int last,tot,n,cnt;
vector<int>G[N<<1];
int len[N<<1],pre[N<<1],ch[N<<1][27],vis[N<<1],col[N<<1],tar[N<<1],s1[N<<1],idx[N<<1];
void extend(int c, int id) {
if(ch[last][c]) {
int p=last,q=ch[last][c];
if(len[q]==len[p]+1) last=q;
else {
int nq=++tot;
len[nq]=len[p]+1;
vis[nq]=vis[q], col[nq]=col[q];
memcpy(ch[nq], ch[q], sizeof(ch[q]));
pre[nq]=pre[q], pre[q]=nq;
for(;p&&ch[p][c]==q;p=pre[p])
ch[p][c]=nq;
last=nq;
}
}
else {
int np=++tot,p=last;
len[np]=len[p]+1,last=np;
for(;p&&!ch[p][c];p=pre[p])
ch[p][c]=np;
if(!p) pre[np]=1;
else {
int q=ch[p][c];
if(len[q]==len[p]+1) pre[np]=q;
else {
int nq=++tot;
len[nq]=len[p]+1;
col[nq]=col[q],vis[nq]=vis[q];
memcpy(ch[nq], ch[q], sizeof(ch[q]));
pre[nq]=pre[q], pre[np]=pre[q]=nq;
for(;p&&ch[p][c]==q;p=pre[p])
ch[p][c]=nq;
}
}
}
for(int p=last;p;p=pre[p]) {
if(col[p]==id) break;
else col[p]=id, ++vis[p];
}
}
void dfs1(int x) {
// if(vis[x]!=n) return ;
for(int i=0;i<G[x].size();++i) dfs1(G[x][i]);
for(int i=0;i<G[x].size();++i) {
int y=G[x][i];
tar[x]=max(tar[x], tar[y]);
}
}
struct data {
int c, x;
data(int c=0,int x=0):c(c),x(x){}
};
vector<data>g[N<<1];
bool cmp1(data i,data j) { return i.c<j.c; }
void dfs2(int x) {
if(vis[x]!=n)
return ;
sum[++cnt]=len[x]-len[pre[x]];
idx[cnt]=x;
g[x].clear();
for(int i=0;i<G[x].size();++i) {
int y=G[x][i];
if(vis[y]!=n) continue;
// printf("%d ",tar[y]-len[x]);
g[x].pb(data(s1[tar[y] - len[x]], y));
}
if(!g[x].size()) return ;
sort(g[x].begin(), g[x].end(), cmp1);
for(int i=0;i<g[x].size();++i) {
dfs2(g[x][i].x);
}
}
void solve() {
scanf("%d",&n);
last=tot=1;
int len1;
for(int i=1;i<=n;++i) {
scanf("%s",str+1);
int x=strlen(str+1);
if(i==1) len1=x;
last=1;
for(int j=1;j<=x/2;++j)
swap(str[j], str[x-j+1]);
for(int j=1;j<=x;++j) {
extend(str[j]-'a', i);
if(i==1) {
tar[last]=j;
s1[j]=str[j]-'a';
}
}
}
for(int i=2;i<=tot;++i)
G[pre[i]].pb(i);
dfs1(1);
dfs2(1);
for(int i=1;i<=cnt;++i)
sum[i]+=sum[i-1];
int Q;
scanf("%d",&Q);
while(Q--) {
int k;
scanf("%d",&k);
if(1ll*k>sum[cnt]) {
printf("-1\n");
}
else {
int pos=lower_bound(sum+1,sum+1+cnt,k)-sum;
int lst=k-sum[pos-1];
int length=len[pre[idx[pos]]]+lst;
printf("%d %d\n",(len1-tar[idx[pos]]), (len1-tar[idx[pos]]+1)+length-1);
}
}
for(int i=0;i<=cnt;++i) sum[i]=0;
for(int i=1;i<=tot;++i) {
G[i].clear();
memset(ch[i], 0, sizeof(ch[i]));
pre[i]=len[i]=col[i]=vis[i]=tar[i]=idx[i]=s1[i]=0;
}
tot=last=n=cnt=0;
}
int main() {
// setIO("input");
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
Carrying Conundrum
来源：CF1567C
降智题.
不难看出进位的时候奇数位与偶数位互不影响，故可将一个数分成奇数和偶数.
最后方案数乘一起即可.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int len,a[12];
void divide(int x) {
len=0;
while(x) {
a[++len]=x%10;
x/=10;
}
}
void solve() {
int n;
scanf("%d",&n);
divide(n);
int s1=0,s2=0;
for(int i=len;i>=1;--i) {
if(i&1) {
s1=s1*10+a[i];
}
else {
s2=s2*10+a[i];
}
}
printf("%d\n",(s1+1)*(s2+1)-2);
}
int main() {
// setIO("input");
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
Sum of Prefix Sums
来源：CF1303G
路径问题考虑用点分治进行处理.
在处理分治中心的时候只伸向一个子树的路径是好处理的.
若路径要伸向两个子树，则固定一个子树，对于第二个子树来说深度+1，第一个子树的贡献是线性的.
那么就将第一个子树的贡献看作是一次函数，用李超线段树进行维护.
特别注意求前缀和的前缀和的最大值时要注意方向，所以要正反跑两次.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 170002
#define ll long long
#define pb push_back
#define ls (now<<1)
#define rs (now<<1|1)
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
vector<int>G[N];
ll ans,d1[N],d2[N],d3[N],d4[N],a[N];
int size[N],dep[N],f[N],vis[N],sn,n,root,cnt;
struct Line {
ll k,b;
Line() { k=b=0; }
}line[N];
ll calc(Line o, int pos) {
return 1ll*o.k*pos+o.b;
}
struct SGT {
ll ma[N<<2];
int tree[N<<2];
vector<int>clr;
void modify(int l,int r,int now,int x) {
int mid=(l+r)>>1;
clr.pb(now);
if(calc(line[x], mid) > calc(line[tree[now]], mid))
swap(tree[now], x);
if(l!=r&&calc(line[x], l) > calc(line[tree[now]], l))
modify(l,mid,ls,x);
if(l!=r&&calc(line[x], r) > calc(line[tree[now]], r))
modify(mid+1,r,rs,x);
if(l!=r) ma[now]=max(ma[now], max(ma[ls], ma[rs]));
ma[now]=max(calc(line[tree[now]], l), calc(line[tree[now]], r));
}
ll query(int l,int r,int now,int L,int R) {
if(l>=L&&r<=R) {
return ma[now];
}
int mid=(l+r)>>1;
ll re=max(calc(line[tree[now]], max(l,L)), calc(line[tree[now]], min(r,R)));
if(L<=mid) re=max(re, query(l,mid,ls,L,R));
if(R>mid) re=max(re, query(mid+1,r,rs,L,R));
return re;
}
void CLR() {
for(int i=0;i<clr.size();++i) {
tree[clr[i]]=ma[clr[i]]=0;
}
clr.clear();
}
}T;
void getroot(int x, int ff) {
size[x]=1,f[x]=0;
for(int i=0;i<G[x].size();++i) {
int v=G[x][i];
if(v==ff||vis[v]) continue;
getroot(v, x);
size[x]+=size[v];
f[x]=max(f[x], size[v]);
}
f[x]=max(f[x], sn-size[x]);
if(f[x]<f[root]) root=x;
}
void getans(int x, int ff) {
ans=max(ans, T.query(1, n, 1, dep[x], dep[x])+1ll*d1[x]*dep[x]+d2[x]);
for(int i=0;i<G[x].size();++i) {
int v=G[x][i];
if(vis[v]||v==ff) continue;
dep[v]=dep[x]+1;
d1[v]=d1[x]+a[v];
d2[v]=d2[x]+1ll*a[v]*(1-dep[v]);
getans(v, x);
}
}
void update(int x, int ff) {
++cnt;
line[cnt].b=d3[x];
line[cnt].k=(ll)d4[x];
T.modify(1,n,1,cnt);
ans=max(ans, d3[x]);
for(int i=0;i<G[x].size();++i) {
int v=G[x][i];
if(vis[v]||v==ff) continue;
d3[v]=d3[x]+1ll*a[v]*(dep[v]+1);
d4[v]=d4[x]+a[v];
update(v, x);
}
}
void dfs(int x) {
// 将 x 插入.
vis[x]=1;
cnt=1;
line[cnt].b=a[x];
line[cnt].k=a[x];
T.modify(1, n, 1, cnt);
for(int i=0;i<G[x].size();++i) {
int v=G[x][i];
if(vis[v]) continue;
dep[v]=1;
d1[v]=a[v];
d2[v]=0;
getans(v, x);
d3[v]=a[x]+2ll*a[v];
d4[v]=a[x]+a[v];
update(v, x);
}
T.CLR();
cnt=1;
line[cnt].b=a[x];
line[cnt].k=a[x];
T.modify(1,n,1,cnt);
for(int i=G[x].size()-1;i>=0;--i) {
int v=G[x][i];
if(vis[v]) continue;
dep[v]=1;
d1[v]=a[v];
d2[v]=0;
getans(v, x);
d3[v]=a[x]+2ll*a[v];
d4[v]=a[x]+a[v];
update(v, x);
}
T.CLR(),cnt=1;
for(int i=0;i<G[x].size();++i) {
int v=G[x][i];
if(vis[v]) continue;
sn=size[x], root=0;
getroot(v, x);
dfs(root);
}
}
int main() {
// setIO("input");
scanf("%d",&n);
for(int i=1;i<n;++i) {
int x,y;
scanf("%d%d",&x,&y);
G[x].pb(y);
G[y].pb(x);
}
for(int i=1;i<=n;++i) {
scanf("%lld",&a[i]);
ans=max(ans, a[i]);
}
sn=n;
f[root=0]=N;
getroot(1, 0);
dfs(root);
printf("%lld\n",ans);
return 0;
}
Number of Components
来源：CF1303F
连通块个数与连通性有关，不妨用并查集来维护连通性.
对于每种颜色，单独考虑.
将 $\mathrm{col[x][y]}$ 改为 $\mathrm{c}$ 可以看作是 $\mathrm{col[x][y]}$ 的断边与 $\mathrm{c}$ 的加边.
加边好处理，但是断边不好处理.
好在题目保证 $\mathrm{c[i]} \leqslant \mathrm{c[i+1]}$，故对于颜色 $c$ 来说，一定先有加边后有断边.
这意味着一旦颜色 $c$ 进行断边，则不会再碰到颜色 $c$ 的加边情况.
将断边操作按照时间倒叙枚举，变成加边，然后对于答案的增量取相反数即可.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 302
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int dx[]={-1, 0, 1, 0};
int dy[]={0, -1, 0, 1};
int n,m,Q,scc;
int p[N*N],a[N][N],id[N][N],is[N][N],ans[2000005];
struct data {
int x, y, ti;
data(int x=0,int y=0,int ti=0):x(x),y(y),ti(ti){}
};
vector<data>add[2000003],del[2000003];
void init() {
for(int i=1;i<=n*m;++i) p[i]=i;
}
int find(int x) {
return p[x]==x?x:p[x]=find(p[x]);
}
int merge(int x, int y) {
x=find(x);
y=find(y);
if(x==y) return 0;
p[x]=y;
return 1;
}
void work(const vector<data>&g, int d) {
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) is[i][j]=0;
init();
for(int i=0;i<g.size();++i) {
data e=g[i];
int x=e.x;
int y=e.y;
int t=e.ti;
int cur=1;
is[x][y]=1;
for(int j=0;j<4;++j) {
int xx=x+dx[j];
int yy=y+dy[j];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&is[xx][yy]) {
cur-=merge(id[xx][yy], id[x][y]);
}
}
ans[t]+=d*cur;
// 合并完毕.
}
}
int main() {
// setIO("input");
scanf("%d%d%d",&n,&m,&Q);
init();
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) id[i][j]=++scc;
int mx=1;
for(int i=1;i<=Q;++i) {
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
if(a[x][y]==c) continue;
del[a[x][y]].pb(data(x, y, i));
add[a[x][y]=c].pb(data(x, y, i));
mx=max(mx, c);
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) del[a[i][j]].pb(data(i, j, Q+1));
for(int i=0;i<=mx;++i) {
reverse(del[i].begin(), del[i].end());
}
for(int i=0;i<=mx;++i) {
work(add[i], +1);
work(del[i], -1);
}
int fin=1;
for(int i=1;i<=Q;++i) {
fin+=ans[i];
printf("%d\n",fin);
}
return 0;
}
Fill The Bag
来源：CF1303D
设 $\mathrm{sum}=\sum_{\mathrm{i=1}}^{\mathrm{m}} \mathrm{a[i]}$.
显然若 $n \leqslant sum$ 则一定合法，否则不合法.
先将 $\mathrm{m}$ 个数都选上，然后我们要减掉 $\mathrm{sum-n}$
有两种操作：
1. 将两个 $2^{\mathrm{i}}$ 形式的数字合并，无代价.
2. 将一个 $2^{\mathrm{i}}$ 形式的数字除以 2，代价为 $1$.
不妨从低位向高位考虑.
若前面的低位需要补一个 $2^{\mathrm{i}}$，则能给就给.
这样做正确是因为 $2^{\mathrm{i}}$ 做除法覆盖的是一个区间，所以与更靠前的匹配一定最优.
若当前位还剩一些数，则将这些数合并起来，可以贡献给更高位.
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <algorithm>
#define N 200009
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
ll n,a[N];
int m,cnt[70];
map<ll,int>mp;
void init() {
for(int i=0;i<=32;++i)
mp[1ll<<i]=i;
}
ll calc(ll x) {
// printf("%lld\n",x);
int lst=-1;
ll ans=0;
for(int i=0;i<=32;++i) {
if(cnt[i]&&lst!=-1) {
--cnt[i],ans+=i-lst;
lst=-1;
}
if((x >> i) & 1) {
// 当前需要.
if(cnt[i]) --cnt[i];
else if(lst==-1) lst=i;
}
cnt[i+1]+=(cnt[i]>>1);
// cnt[i]=cnt[i]&1;
}
return ans;
}
void solve() {
scanf("%lld%d",&n,&m);
memset(cnt, 0, sizeof(cnt));
for(int i=1;i<=m;++i) {
scanf("%lld",&a[i]);
cnt[mp[a[i]]]++;
}
ll sum=0;
for(int i=1;i<=m;++i) sum+=a[i];
if(n>sum) printf("-1\n");
else printf("%lld\n",calc(sum-n));
}
int main() {
// setIO("input");
int T;
init();
scanf("%d",&T);
while(T--) solve();
return 0;
}
Network Coverage
来源：CF1373F
如果知道 $\mathrm{b[1]}$ 分多少给 $\mathrm{a[1]}$ 的话就能知道其他位置如何分配了.
考虑 $\mathrm{b[1]}$ 分给 $\mathrm{a[1]}$ 时会发生什么情况：
1. 分配少了，导致最终 $\mathrm{1}$ 号位置不合法.
2. 分配多了，导致中间某个位置不合法.
如果发生情况 $1$，则要多给 $1$ 号位置，发生情况 2 则要少给.
这显然是一个可以二分的模型，于是直接二分答案即可.
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define N 1000009
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n ;
int a[N], b[N], ne[N];
int check(int p1) {
for(int i=1;i<=n;++i) {
ne[i]=0;
}
ne[1]=p1;
ne[2]=min(b[1]-p1, a[2]);
for(int i=2;i<=n;++i) {
if(b[i] < a[i] - ne[i]) return 1;
int det = b[i] - (a[i] - ne[i]);
if(i + 1 <= n) ne[i + 1] += min(a[i + 1], det);
else ne[1] += det;
}
if(ne[1] < a[1]) return 2;
return 3;
}
void solve() {
scanf("%d",&n);
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
}
for(int i=1;i<=n;++i) {
scanf("%d",&b[i]);
}
// 二分给 a[1] 多少.
int l=0, r=min(a[1],b[1]);
while(l<=r) {
int mid=(l+r)>>1;
int type=check(mid);
// type=1, 分多了.
// type=2, 分少了.
// type=3, YES 了.
if(type == 1) {
r = mid - 1;
}
if(type == 2) {
l = mid + 1;
}
if(type == 3) {
printf("YES\n");
return ;
}
}
printf("NO\n");
}
int main() {
// setIO("input");
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
Find a Gift
来源：CF1354G
交互题.
注意到 $2k \leqslant n$，故一半以上的位置是石子.
不妨用随机化的方式确认第一个位置的状态，随机 20 次的错误率仅为 $10 ^{-6}$.
最终答案的构成一定是石头的连续段加上第一个礼物.
不妨采用倍增的方式来枚举石子的连续段，具体的话就是前后长为 $2^k$ 的段比较大小.
若大小相同，则说明后面段仍然是石子，若不同则后面段一定有一个礼物.
这个礼物再用二分的方式确认即可.
总询问次数为 $O(20+\log n + \log n)$.
#include <iostream>
#include <vector>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <string>
#include <algorithm>
#define ll long long
using namespace std;
// fflush(stdout);
int ran(int len) {
return (ll)rand()*rand()%len+1;
}
int n,k;
int check(int l, int r) {
int len=r-l+1;
cout << "?"<< " " << len << " " << len << endl;
for(int i=1;i<=len;++i) {
cout << i << " ";
}
cout << endl;
for(int i=l;i<=r;++i) {
cout << i << " ";
}
cout << endl;
fflush(stdout);
string s;
cin >> s;
if(s[0] == 'E') return 0;
return 1;
}
void calc(int L, int R) {
// binary search between [L, R]
int ans = 0, l = L, r = R;
while(l <= r) {
int mid = (l + r) >> 1;
// [L, mid];
if(check(L, mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
cout << "! "<< ans << endl;
fflush(stdout);
}
void solve() {
cin >> n >> k;
for(int i=1;i<=20;++i) {
int p=ran(n);
if(p==1) continue;
cout << "? 1 1" << endl;
cout << 1 << endl;
cout << p << endl;
fflush(stdout);
string s;
cin >> s;
if(s[0] == 'S') {
cout << "! 1" << endl;
fflush(stdout);
return ;
}
}
// 确定 1 是石子.
int p=1;
while(1) {
int l=1,r=1+p-1;
int l2=r+1, r2=l2+p-1;
if(r2<=n) {
cout << "?" << " " << p << " " << p << endl;
for(int i=1;i<=p;++i)
cout << i << " ";
cout << endl;
for(int i=l2;i<=r2;++i)
cout << i << " ";
cout << endl;
fflush(stdout);
string s;
cin >> s;
if(s[0]=='E') {
p <<= 1;
continue;
// 全是石子.
}
else {
// 有戏.
calc(l2, r2);
return ;
}
}
else {
calc(l2, n);
return ;
}
}
}
int main() {
srand(time(NULL));
int T;
cin >> T;
while(T--) solve();
return 0;
}
Escape Through Leaf
来源：CF932F
写一下 DP 式子发现是 $\mathrm{dp[x]=dp[y]+a[x] \times b[y]}$.
对于子树中的 $\mathrm{y}$，对祖先每一个 $\mathrm{dp[x]}$ 的贡献是关于 $\mathrm{a[x]}$ 的一次函数.
如果只有一次子树询问显然可以用李超线段树来做.
由于每一个点都要求解答案，故采用 $\mathrm{DSU}$ 的方式进行求解，时间复杂度为 $O(n \log^2 n)$.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define ll long long
#define pb push_back
#define ls now<<1
#define rs now<<1|1
#define N 200009
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const int inf=100003;
const ll MA = 1ll<<50;
struct Line {
ll k,b;
}line[N<<2];
vector<int>G[N];
ll dp[N];
int cn,n,a[N],b[N],size[N],son[N];
ll calc(Line o,int pos) {
return 1ll*o.k*pos+o.b;
}
struct SGT {
int tree[N<<2];
vector<int>clr;
void update(int l,int r,int now,int L,int R,int x) {
int mid=(l+r)>>1;
if(!tree[now]) tree[now]=x,clr.pb(now);
else {
if(calc(line[tree[now]], mid) > calc(line[x], mid))
swap(tree[now], x);
if(calc(line[x], l) < calc(line[tree[now]], l) && l!=r)
update(l, mid, ls, L, R, x);
if(calc(line[x], r) < calc(line[tree[now]], r) && l!=r)
update(mid+1,r,rs,L,R,x);
}
}
ll query(int l,int r,int now,int p) {
if(l==r) {
return tree[now] ? calc(line[tree[now]], l) : MA;
}
int mid = (l + r) >> 1;
ll re=MA;
if(tree[now]) re=min(re, calc(line[tree[now]], p));
if(p<=mid) return min(re, query(l,mid,ls,p));
else return min(re, query(mid+1,r,rs,p));
}
void CLR() {
for(int i=0;i<clr.size();++i)
tree[clr[i]]=0;
clr.clear();
}
}T;
int Son;
void upd(int x, int ff) {
// y = b[x] ( ) + dp[x]
++cn;
line[cn].k=b[x];
line[cn].b=dp[x];
T.update(-inf, inf, 1, -inf, inf, cn);
for(int i=0;i<G[x].size();++i) {
int v=G[x][i];
if(v==ff) continue;
upd(v, x);
}
}
void dfs1(int x, int ff) {
size[x]=1,son[x]=0;
for(int i=0;i<G[x].size();++i) {
int v=G[x][i];
if(v==ff) continue;
dfs1(v, x);
size[x]+=size[v];
if(size[v]>size[son[x]])
son[x]=v;
}
}
void dfs2(int x, int ff, int op) {
for(int i=0;i<G[x].size();++i) {
int v=G[x][i];
if(v==ff||v==son[x]) continue;
dfs2(v, x, 0);
// 不计子树影响.
}
// 计算重儿子影响.
if(son[x]) dfs2(son[x], x, 1);
// 算进轻儿子影响.
for(int i=0;i<G[x].size();++i) {
int v=G[x][i];
if(v==ff||v==son[x]) continue;
upd(v, x);
}
// 计算当前点答案.
if(size[x]==1) dp[x]=0;
else {
dp[x]=T.query(-inf, inf, 1, a[x]);
}
++cn;
line[cn].k=b[x];
line[cn].b=dp[x];
T.update(-inf, inf, 1, -inf, inf, cn);
// 需要清除.
if(op==0) T.CLR(),cn=0;
}
int main() {
// setIO("input");
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) scanf("%d",&b[i]);
for(int i=1;i<n;++i) {
int x,y;
scanf("%d%d",&x,&y);
G[x].pb(y);
G[y].pb(x);
}
dfs1(1, 0);
dfs2(1, 0, 1);
for(int i=1;i<=n;++i) {
printf("%lld ",dp[i]);
}
return 0;
}
Perfect Triples
来源：CF1338C
本题需要打表找规律.
设每次加入的数为 $(a,b,c)$，$a$ 的取值为 $[2^{\mathrm{2i}}, 2^{\mathrm{2i+1}})$.
然后 $b$ 的规律可以通过将 $b$ 进行二进制展开，发现 $b$ 从后向前每两位都呈现周期性变化.
打表程序：
#include <cstdio>
#include <set>
#include <cstring>
#include <algorithm>
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
set<int>se;
void DIV(int x) {
for(int i=8;i>=0;--i) {
if(x&(1<<i)) printf("1");
else printf("0");
}
}
int main() {
freopen("input.out","w",stdout);
for(int i=1;i<=300;++i) {
if(se.find(i)!=se.end()) continue;
for(int j=i+1;j<=300;++j) {
if(se.find(j)!=se.end()) continue;
int flag=0;
for(int k=j+1;k<=300;++k) {
if(se.find(k)!=se.end()) continue;
if((i^j) == k) {
se.insert(i);
se.insert(j);
se.insert(k);
flag=1;
printf("%d %d ",i, j);
DIV(j);
printf("\n");
break;
}
}
if(flag) break;
}
}
return 0;
}
正解：
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
ll n;
ll pw[62];
int vis[70];
void solve() {
scanf("%lld",&n);
ll re=n,dd=n;
while((re%3)!=0) ++re,++dd;
re/=3;
dd/=3;
// re : 块的编号.
for(int i=0;;++i) {
ll st=1ll<<(2*i);
ll len=st;
if(re <= len) {
// 在当前块中.
ll det=re-1; // 距离起点的位置.
ll a=st+det;
// 可先求得 a.
// 有 i 对.
memset(vis, 0, sizeof(vis));
// printf("%lld %d\n",det,i);
for(int j=1;j<=i;++j) {
// 枚举 2*j-1 与 2*j 位的 0/1.
ll tot=det;
ll cy=pw[j-1]*4ll; // 周期.
ll res=(det+1)%cy;
// printf("%lld %lld\n",cy,res);
if(!res) {
vis[2*j-2]=1;
vis[2*j-1]=0;
}
else {
ll bu=res/pw[j-1];
ll o=res%pw[j-1];
//printf("%lld %lld\n",bu,o);
if(!o) {
//printf("%lld\n",bu);
if(bu==1) vis[2*j-2]=0,vis[2*j-1]=0;
if(bu==2) vis[2*j-2]=0,vis[2*j-1]=1;
if(bu==3) vis[2*j-2]=1,vis[2*j-1]=1;
if(bu==4) vis[2*j-2]=1,vis[2*j-1]=0;
}
else {
++bu;
if(bu==1) vis[2*j-2]=0,vis[2*j-1]=0;
if(bu==2) vis[2*j-2]=0,vis[2*j-1]=1;
if(bu==3) vis[2*j-2]=1,vis[2*j-1]=1;
if(bu==4) vis[2*j-2]=1,vis[2*j-1]=0;
}
}
}
ll b=0ll;
for(int j=0;j<=2*i;++j) {
if(vis[j]) b+=(1ll<<j);
}
b+=st*2;
ll c=a^b;
n -= (dd-1)*3;
if(n==1) printf("%lld\n",a);
if(n==2) printf("%lld\n",b);
if(n==3) printf("%lld\n",c);
// printf("%lld %lld %lld\n",a,b,c);
return ;
}
else {
re -= len;
}
}
}
int main() {
// setIO("input");
pw[0]=1ll;
for(int i=1;i<=30;++i)
pw[i]=1ll*4*pw[i-1];
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
You
来源：CF1554E
可以将问题转化：给每条树边定向，最终每个点的点权为每个点的入度.
如果 $\mathrm{k=1}$, 则有 $2^{\mathrm{n-1}}$ 种定向方式.
若 $2 \leqslant \mathrm{k}$，不妨从叶子开始考虑问题，发现如果有方案，则方案唯一.
而所有点的权值和等于 $\mathrm{n-1}$，故 $\mathrm{gcd}$ 一定为 $\mathrm{n-1}$ 的约数.
直接枚举 $\mathrm{n-1}$ 的约数然后挨个跑一遍就行了.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 100009
#define pb push_back
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const int mod=998244353;
vector<int>G[N];
int n,ans[N],d,flag,a[N];
void dfs(int x, int ff) {
if(!flag) return ;
for(int i=0;i<G[x].size();++i) {
int v=G[x][i];
if(v==ff) continue;
dfs(v, x);
if(!flag) return ;
}
if(a[x] % d) {
++a[x];
if(a[x] % d) {
flag=0;
return ;
}
}
else ++a[ff];
}
int qpow(int x, int y) {
int tmp=1;
for(;y;y>>=1,x=(ll)x*x%mod)
if(y&1) tmp=(ll)tmp*x%mod;
return tmp;
}
void solve() {
scanf("%d",&n);
for(int i=1;i<n;++i) {
int x,y;
scanf("%d%d",&x,&y);
G[x].pb(y);
G[y].pb(x);
}
for(int i=1;i<=n;++i) ans[i]=0;
for(int i=2;i<=(n-1);++i) {
if((n-1)%i==0) {
flag=1,d=i;
dfs(1, 0);
ans[i] += flag;
for(int j=0;j<=n;++j) a[j]=0;
}
}
ans[1]=qpow(2, n-1);
for(int i=n;i>=1;--i) {
for(int j=i+i;j<=n;j+=i)
ans[i] = (ll)(ans[i] - ans[j] + mod)%mod;
}
for(int i=1;i<=n;++i) printf("%d ",ans[i]);
printf("\n");
for(int i=1;i<=n;++i) G[i].clear(),ans[i]=a[i]=0;
}
int main() {
// setIO("input");
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
Common Divisor Graph
来源：CF1553G
显然答案不会超过 2.
答案为 0 的情况用并查集判断就行.
答案为 1 的情况分两种情况讨论：
1. $\mathrm{a[k]}$ 在其中一个集合中.
2. $\mathrm{a[k]}$ 不在任何一个集合.
第一种情况好处理，第二种情况枚举质因数然后暴力存起来即可.
#include <cstdio>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 150009
#define M 1000066
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
vector<int>arr,prime[M];
int n,Q,a[N],vis[M];
struct UFS {
int size[M],p[M];
void init() {
for(int i=0;i<M;++i) p[i]=i,size[i]=1;
}
int find(int x) {
return p[x]==x?x:p[x]=find(p[x]);
}
void merge(int x, int y) {
x=find(x);
y=find(y);
if(x == y) return ;
if(size[x] > size[y]) p[y] = x, size[x] += size[y];
else p[x] = y, size[y] += size[x];
}
}T1,T2;
set<int>mp[M];
set<pair<int,int> >ED;
int main() {
// setIO("input");
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
vis[a[i]]=1;
}
T1.init();
for(int i=2;i<=1000002;++i) {
arr.clear();
for(int j=i;j<=1000002;j+=i) {
if(vis[j]) arr.pb(j);
}
for(int j=1;j<arr.size();++j) {
T1.merge(arr[j-1], arr[j]);
}
// 合并完毕.
}
for(int i=2;i<=1000002;++i) {
int fa=0;
for(int j=i;j<=1000002;j+=i) {
if(vis[j]) {
fa=T1.find(j);
break;
}
}
if(!fa) continue;
for(int j=i;j<=1000002;j+=i) {
// j = a[k] + 1;
int pp=T1.find(j-1);
mp[fa].insert(pp);
// 将对方的 root 加入进去.
}
}
for(int i=2;i<=1000002;++i) {
if(!prime[i].size())
for(int j=i;j<=1000002;j+=i)
prime[j].pb(i);
}
T2.init();
for(int i=1;i<=n;++i) {
for(int j=0;j<prime[a[i]].size();++j)
T2.merge(a[i], prime[a[i]][j]);
}
// prime[j]: j 能够整除的质数.
for(int i=1;i<=n;++i) {
int num = a[i] + 1;
for(int l=0;l<prime[num].size();++l)
for(int r=l+1;r<prime[num].size();++r) {
int n1=prime[num][l];
int n2=prime[num][r];
n1=T2.find(n1);
n2=T2.find(n2);
if(n1 != n2)
{
if(n1 > n2) swap(n1, n2);
ED.insert( pair<int,int>(n1, n2) );
}
}
}
for(int i=1;i<=Q;++i) {
int x, y;
scanf("%d%d",&x,&y);
int v1=a[x];
int v2=a[y];
if(T1.find(v1) == T1.find(v2)) {
printf("0\n");
}
else {
int p1=T1.find(v1), p2=T1.find(v2);
if((mp[p1].find(p2) != mp[p1].end()) || (mp[p2].find(p1) != mp[p2].end()))
printf("1\n");
else {
v1=T2.find(v1);
v2=T2.find(v2);
if(v1 > v2) swap(v1, v2);
if(ED.count( pair<int,int>(v1, v2)) ) printf("1\n");
else printf("2\n");
}
//printf("2\n");
}
}
return 0;
}