夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

20省选day2

2021-01-11 19 min read # 圆方树 # 主席树 # 分治 # 计数题 # 卡特兰数 # 比赛题

A. [20省选day2]魔法宝石

怎么做呢?首先肯定要按照最大值进行分治

然后考虑启发式分裂来保证复杂度:每次我们只会浪费那边划分较小处的复杂度qwq

也就是说,我们对于找到的mid,将区间分为l,mid-1,mid+1,r,然后枚举较小一边的每一个数,较大的一边用数据结构来快速判断qwq,这样均摊一个log,而且是在完全均分的时候最慢,即最大值第一次在n/2n/2处,第二次在n/4n/4和3n/43n/4

为什么复杂度是对的?你发现对于一个长度为l的区间,只有上方至少有2l2l的母区间时,他才会被算一次qwq所以一个数最多被算loglog次

然后我的做法是用了一颗主席树维护较大的一边,实践证明只要能够离散化,主席树还是很快的qwq

然鹅有更加优美的做法,因为显然不能预处理了,考虑继续利用这个启发式分裂的性质,每次我们对于[l,mid−1][l,mid-1]枚举的时候,考虑令[mid+1,r][mid+1,r]已经处理出来了,那么此时直接查询即可,不难发现哈希表可以胜任

也很简单了,我们每次[l,mid−1][l,mid-1]的那边递归下去信息顺带清空,而[mid+1,r][mid+1,r]那边递归下去信息不清空

那么清空会导致我们把[mid+1,r][mid+1,r]这部分清掉复杂度,但是你会发现清空一定是成为了小于一半的子区间,也就是说母区间至少是两倍,所以一个数清空不超过loglog次qwq

考场上用一个暴力O(nlog^2n)跑过去了.....这个主席树迭代就是快啊



//两个巨大的logQAQ
#include<bits/stdc++.h>
#define db double
#define ll long long
#define pb push_back
using namespace std;
const int MAXN = 7e5 + 7;
const int MAXL = 21;
const int MAXT = 10500000;//Node
int n, a[MAXN], root[MAXN], lgq[MAXN], b[MAXN];
ll ans;
db lg2;
vector<int> v;
struct seg {
#define mid ((l+r)>>1)
	int sum[MAXT], ls[MAXT], rs[MAXT], T;
	inline void add(int &x, int y, int l, int r, int P, int v) {
		if(!x || x == y) {
			x = ++T;
			sum[x] = sum[y];
			ls[x] = ls[y];
			rs[x] = rs[y];
		}
		if(l == r) {
			sum[x] += v;
			return ;
		}
		if(P <= mid)add(ls[x], ls[y], l, mid, P, v);
		else add(rs[x], rs[y], mid + 1, r, P, v);
	}
	inline int qry(int x, int y, int l, int r, int p) {
		while(l != r) {
			if(p <= mid) {
				x = ls[x];
				y = ls[y];
				r = mid;
			} else {
				x = rs[x];
				y = rs[y];
				l = mid + 1;
			}
		}
		return sum[x] - sum[y];//前缀差
	}
#undef mid
} tr;

int st[MAXN][MAXL], stp[MAXN][MAXL];

inline int getid(int x) {
	return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

inline int qrym(int l, int r) {
	int a = lgq[r - l + 1];
	if(st[l][a] > st[r - (1 << a) + 1][a])return stp[l][a];
	else return stp[r - (1 << a) + 1][a];
}

inline void init() {
	lg2 = log(2.0);
	for(int i = 1; i <= n; ++i)lgq[i] = log(i) / lg2;
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	for(int i = 1; i <= n; ++i) {
		b[i] = a[i];
		a[i] = getid(a[i]);
	}
	for(int i = 1; i <= n; ++i)tr.add(root[i], root[i - 1], 1, n, a[i], 1); //离散化不会锅了吧?
	for(int j = 1; j <= 20; j++) {
		for(int i = 1; i <= n; i++) {
			if(i + (1 << j) - 1 <= n) {
				st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
				if(st[i][j] == st[i][j - 1])stp[i][j] = stp[i][j - 1];
				else stp[i][j] = stp[i + (1 << (j - 1))][j - 1];
			}
		}
	}
	return;
}

inline void solve(int L, int R) {
	if(L >= R)return ;
	int mid = qrym(L, R);
	if(mid - L <= R - mid) {
		for(int i = L; i < mid; ++i) {
			int up = getid(b[mid] - b[i]);
			if(b[mid] - b[i] != v[up - 1])continue;
			ans += tr.qry(root[R], root[mid], 1, n, up);
		}
	} else {
		for(int i = mid + 1; i <= R; ++i) {
			int up = getid(b[mid] - b[i]);
			if(b[mid] - b[i] != v[up - 1])continue;
			ans += tr.qry(root[mid - 1], root[L - 1], 1, n, up);
		}
	}
	solve(L, mid - 1);
	solve(mid + 1, R);
	return ;
}

namespace fastIO {
#define BUF_SIZE (1<<20)
	static char buf[BUF_SIZE], *p1 = buf, *pend = buf;
	inline char nc() {
		if(p1 == pend) {
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
			p1 = buf;
		}
		return *p1++;
	}
	inline int read() {
		int x = 0;
		char s = nc();
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
}
using namespace fastIO;


int main() {
	// freopen("test.in", "r", stdin);
	// freopen("test2.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		v.pb(a[i]);
		st[i][0] = a[i];
		stp[i][0] = i;
	}
	init();//build
	solve(1, n);
	printf("%lld\n", ans);
	return 0;
}

B. [20省选day2]商人

问题等价于括号匹配成功k个的方案数计数

首先有引理:对于(0,0)走到(n,m),使用(1,1)和(1,-1)向量的方案数是(nn+m2)\binom{n}{\frac{n+m}{2}}

注意,这里n,m大于0!

这个形式并不唯一,我们证明一下,对于加入使用x次第一个,y次第二个有:x+y=n,x−y=mx+y=n,x-y=m

所以解出这个x,y有从一共n步中选出某一种步数，就有这个答案

再去考虑对于一个答案大于等于z的方案计数

钦定左括号较多(超过一半),再假设前缀最小和为-y(即没有匹配的右括号为y),那么我们有n−y−xn-y-x为成功匹配答案

那么n−y−x>=zn-y-x>=z即y>=z−n+xy>=z-n+x,即我们不能经过直线y=z−n+x−1y=z-n+x-1,碰都不能碰

有这个我们就考虑最后走到的是那个点即可,因为左括号相当于(1,1)(1,1),故应该走到(n,2x−n)(n,2x-n)

不能经过这条直线,有对称法解决,把(n,2x−n)(n,2x-n)对称过去,有(n,−n+2z−2)(n,-n+2z-2),套用上式,从(0,0)(0,0)走过去的方案数是(nn−z+1)\binom{n}{n-z+1},方案数是(nx)−(nn−z+1)\binom{n}{x}-\binom{n}{n-z+1}

这个问题也可以推广,如果我们想要走到(n,n)(n,n),不经过y=xy=x,使用(0,1)(1,0)(0,1)(1,0),我们可以首先变为从(1,0)(1,0)走到(n,n−1)(n,n-1)

那么你会发现相当于(0,1)(0,1)走到(n,n−1)(n,n-1),然后求一下相减即可

于是我们有对于答案大于等于z的方案为(枚举一个x)

∑x=zn−z((nx)−(nn−z+1))\sum_{x=z}^{n-z}(\binom{n}{x}-\binom{n}{n-z+1})

观察到这个相当于一个杨辉三角的一行区间和与另一个常数....就做完了

对于右括号较多,我们有后缀最大和为y,那么右括号数量为x,有n−y−xn-y-x是答案qwq

于是仔细思考,左右括号是完全对称的,所以上式是完全正确的,我们不用变化,根据组合数对称性相当于算了两遍


#include<bits/stdc++.h>
#define ll long long
const int P = 998244353;
const int inv2 = (P + 1) / 2;
const int MAXN = 2e6 + 7;
using namespace std;

int n, L;
int tp;


inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

ll fac[MAXN], ifac[MAXN], sum[MAXN];
inline void add(ll &x, ll y) {
	x += y;
	if(x >= P)x -= P;
}
inline ll C(int x, int y) {
	if(x < y)return 0;
	return fac[x] * ifac[y] % P * ifac[x - y] % P;
}

inline void init() {
	fac[0] = 1;
	for(int i = 1; i <= n; ++i)fac[i] = fac[i - 1] * i % P;
	ifac[n] = ksm(fac[n], P - 2);
	for(int i = n - 1; i >= 1; --i)ifac[i] = ifac[i + 1] * (i + 1) % P;
	ifac[0] = 1;
	sum[0] = 1;
	for(int i = 1; i <= n; ++i) {
		add(sum[i], sum[i - 1]);
		add(sum[i], C(n, i));
	}
	return ;
}

ll f[MAXN];

inline void solve() {
	ll ans = 0;
	for(int A = 1; A <= n / 2; ++A) {
		add(f[A], ((sum[n - A] - sum[A - 1] - C(n, n - A + 1) * (n - A - A + 1) % P) % P + P) % P);
	}
	f[0] = n + 1;
	for(int i = 1; i <= n / 2; ++i) {
		add(f[i], P - f[i + 1]);
	}
	if(tp == 1)
		printf("%lld\n", f[L]);
	else {
		ll tp = 1;
		for(int i = 0; i <= n / 2; ++i) {
			add(ans, f[i] * tp % P);
			tp = tp * 233 % P;
		}
		printf("%lld\n", ans);
	}
	return ;
}

int main() {
	scanf("%d", &tp);
	scanf("%d", &n);
	init();
	if(tp == 1)scanf("%d", &L);
	solve();
	return 0;
}

C. [20省选day2]防御工事

考场上写了nmq暴力,就是枚举这个防御工事,然后用连通性直接搞定首都

正解:如果原图是一棵树,我们不难想到问题等价于(Ki∗(n−1)−∑sizeofsubtreeu)(K_i*(n-1)-\sum sizeofsubtree_u)

即统计每个点子树内的军队数(在这个点修工事)

这个可以换根dp,就是我们维护每个点子树有多少军队,然后从根u向v走一步,有v变成整颗树,u减去v子树信息

然后如果询问次数可能很多,我们对于原图建立虚树即可,易发现答案一定在虚树上某点上

如果图不是树呢?

发现问题和点双连通分量关系很大,所以可以建立圆方树,然后在圆方树上dp,即统计圆点的子树和,因为原图中到达不了等价于圆方树上到达不了

但是虚树?

你会发现此时方点是不能选的,因为他不是实际的点,我们只统计圆点的子树和

那么就一定会有一些奇怪的情况,我们可能选择边上的一个点最优...因为我们方点不能成为答案点!所以可能卡在一个奇怪的边上....qaq

感觉圆方树很重要但是懒得学啊

也是,点双可承担不起两个点的损失啊


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e6 + 7;
int n, m, q, ccnt;
int home[MAXN], nxt[MAXN], to[MAXN], K[MAXN], top[MAXN], w[MAXN];
inline void ct(int x, int y, int z) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
	w[ccnt] = z;
	ccnt++;
	nxt[ccnt] = home[y];
	home[y] = ccnt;
	to[ccnt] = x;
	w[ccnt] = z;
}
inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}
int cccnt, ljh[MAXN], xtt[MAXN], dfn[MAXN], wsy[MAXN];
inline void ct2(int x, int y) {
	cccnt++;
	xtt[cccnt] = ljh[x];
	ljh[x] = cccnt;
	wsy[cccnt] = y;
}
inline void Sort(int *l, int *r) {
	static int cnt[10], mx, key[MAXN], tmp[MAXN];
	mx = 1;
	for(int *i = l; i < r; ++i)
		while(dfn[*i] >= mx) mx *= 10;
	for(int o = 1; o < mx; o *= 10) {
		for(int i = 0; i < 10; ++i) cnt[i] = 0;
		for(int *i = l; i < r; ++i) key[*i] = dfn[*i] / o % 10;
		for(int *i = l; i < r; ++i) ++cnt[key[*i]];
		for(int i = 1; i < 10; ++i) cnt[i] += cnt[i - 1];
		for(int *i = r - 1; i >= l; --i) tmp[cnt[key[*i]]--] = *i;
		for(int *i = l; i < r; ++i) *i = tmp[i - l + 1];
	}
}
int  low[MAXN], bel[MAXN], st[MAXN], tp, Dep, cnt;
inline void tarjan(int u) {
	dfn[u] = low[u] = ++Dep;
	st[++tp] = u;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if(low[v] == dfn[u]) {
				++cnt;
				for(int x = 0; x != v; --tp) {
					x = st[tp];
					ct2(cnt, st[tp]);
					ct2(st[tp], cnt);
				}
				ct2(u, cnt);
				ct2(cnt, u);//注意u要连边,但是不退栈
			}
		} else low[u] = std::min(low[u], dfn[v]);
	}
}

int siz[MAXN], son[MAXN], dep[MAXN], fa[MAXN];

inline void dfs1(int u, int F, int depth) {
	dep[u] = depth;
	fa[u] = F;
	siz[u] = 1;
	for(int i = ljh[u]; i; i = xtt[i]) {
		int v = wsy[i];
		if(v == F)continue;
		dfs1(v, u, depth + 1);
		siz[u] += siz[v];
		if(siz[v] > siz[son[u]])son[u] = v;
	}
}

inline void dfs2(int u, int topf) {
	top[u] = topf;
	dfn[u] = ++Dep;
	if(!son[u])return ;
	dfs2(son[u], topf);
	for(int i = ljh[u]; i; i = xtt[i]) {
		int v = wsy[i];
		if(v == fa[u] || v == son[u])continue;
		dfs2(v, v);
	}
}

inline int getLCA(int x, int y) {
	while(top[x] != top[y]) {
		if(dep[fa[top[x]]] < dep[fa[top[y]]])x ^= y ^= x ^= y;
		x = fa[top[x]];
	}
	if(dep[x] > dep[y])swap(x, y);
	return x;
}

inline void ins(int u) {
	if(!tp) {
		st[tp = 1] = u;
		return;
	}
	int ance = getLCA(u, st[tp]);
	while(tp > 1 && (dfn[ance] < dfn[st[tp - 1]])) {
		ct(st[tp - 1], st[tp], dep[st[tp]] - dep[st[tp - 1]]);
		--tp;
	}
	if(dfn[st[tp]] > dfn[ance]) {
		ct(ance, st[tp], dep[st[tp]] - dep[ance]); //说明这个tp是很要命的
		--tp;
	}
	if((!tp) || (st[tp] != ance))st[++tp] = ance;
	st[++tp] = u;
	return ;
}

int sz[MAXN], dp[MAXN];
inline bool cmp(int x, int y) {
	return dfn[x] < dfn[y];
}
inline int dist(int x, int y) {
	return dep[x] + dep[y] - 2 * dep[getLCA(x, y)];
}
ll ans;
inline void getsz(int u, int F, int d) {
	ans += 1ll * d * sz[u];
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		getsz(v, u, d + w[i]);
		sz[u] += sz[v];
	}
	return ;
}
int SZ, rt, que[MAXN], tot;
inline void getrt(int u, int F) {
	siz[u] = sz[u];
	dp[u] = 0;
	que[++tot] = u;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		getrt(v, u);
		siz[u] += siz[v];
		dp[u] = max(dp[u], siz[v]);
	}
	dp[u] = max(dp[u], SZ - siz[u]);
	if(dp[u] < dp[rt])rt = u;
	return ;
}

namespace fastIO {
#define BUF_SIZE (1<<20)
	static char buf[BUF_SIZE], *p1 = buf, *pend = buf;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0;
		char s = nc();
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
}
using namespace fastIO;

int main() {
	n = read(), m = read(), q = read();
	for(int i = 1, x, y; i <= m; ++i) {
		x = read(), y = read();
		ct(x, y);
		ct(y, x);
	}
	cnt = n;
	for(int i = 1; i <= m; ++i)if(!dfn[i])tarjan(i), --tp;//把根根退栈
	dfs1(1, 0, 1);
	Dep = 0;
	dfs2(1, 1);
	tp = 0;
	ccnt = 0;
	memset(home, 0, sizeof(home));
	int mk;
	while(q-- > 0) {
		mk = read();
		for(int i = 1; i <= mk; ++i) {
			K[i] = read();
			sz[K[i]]++;
		}
		Sort(K + 1, K + mk + 1);
		for(int i = 1; i <= mk; ++i) {
			if(K[i] == K[i - 1])continue;
			ins(K[i]);
		}
		while(tp > 1) {
			ct(st[tp - 1], st[tp], dep[st[tp]] - dep[st[tp - 1]]);
			--tp;
		}
		rt = 0;
		SZ = mk;
		dp[0] = 1e9;
		getrt(K[1], 0);
		ans = 0;
		getsz(rt, 0, 0);
		if(rt > n) {
			int mxs = 0;
			for(int i = home[rt]; i; i = nxt[i]) {
				int v = to[i];
				mxs = max(mxs, sz[v]);
			}
			ans += -mxs + (mk - mxs);
		}
		printf("%lld\n", 1ll * (n - 1) * mk - ans / 2);
		ccnt = 0;
		for(int i = 1; i <= tot; ++i) {
			sz[que[i]] = home[que[i]] = 0;
		}
		tot = 0;
		tp = 0;
	}
	return 0;
}
/*
9 12 3
1 2
1 3
2 3
2 4
3 4
4 5
4 8
5 8
4 7
4 6
6 7
7 9
4 5 9 9 3
3 5 4 6
5 1 4 9 8 7

*/
Powered by Gridea RSS