夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

qbxt D5 && NOIP提高组考前刷题冲刺班（第五场）

2020-11-26 15 min read # 计数题 # 二分答案 # 线段树 # 动态规划

A

暴力可以设计四维DP

然后正解:

会发现我们能做到如果只有三个颜色的问题,因为假设分为4个颜色

1 2 A B

定下一个1,2的序列

1 1 1 2 2 2

根据中间相邻颜色相同的数量,我们就能知道,插入的A,B数量关系至多为

A=B+1

A=B

A=B-1

然后我们就有一个四维dp的状态

fi,j,k,lf_{i,j,k,l}表示用了i个1,j个2,有k个相邻颜色,最后一个为l的方案数

转移?其实非常显然,因为我们只需要dp出每一个相邻颜色的个数的方案数而已

枚举下一个位置放1/2

现在我们有i个位置相邻相同

那我们至少要插入这么多的字符串Y

然后我们发现,这个总共的还有X个位置

那我们可以枚举一个j表示我们一共有多少位置加入字符串,这个j从Y~X枚举

但是每个位置能加的字符串形式还不同,

ABA,BAB,AB三类

再枚举一个k,表示我们j个位置中有k个ABA

然后我们有

n3-n4-k个A

如果这个数还大于0,说明A的个数比B多,剩下位置还需要ABA形式字符串

不可能的

只有当n3−n4−k<0n3-n4-k<0才可能

而剩下的,就要把B的个数拉到和一一样多

即BAB=k−n3−n4BAB=k-n3-n4

AB=j−ABA−BABAB=j-ABA-BAB

最后推个大式子

一定有gig_i,i个位置一定要加的方案数

总共有n1+n2+1n_1+n_2+1位置,i个位置么了

再组合数一下j−ij-i个位置

gi∗(n1+n2+1−ij−i)g_i*\binom{n_1+n_2+1-i}{j-i}

我们再从j个位置中找找放ABA,BAB

gi∗(n1+n2+1−ij−i)∗(jABA)∗(j−ABABAB)g_i*\binom{n_1+n_2+1-i}{j-i}*\binom{j}{ABA}*\binom{j-ABA}{BAB}

然鹅,我们还没有考虑ABA的形态

怎么分配A啊

知道A三者就知道长度了

ABA最少是1

AB最少是1

BAB最少是0

不等价,完蛋了

我们给所有BAB强行补A

剩下n3+BABn_3+BAB

每个数都大于0?

隔板法

我们有n3+ABA−1n_3+ABA-1个空位置放隔板

(n3+ABA−1j−1)\binom{n_3+ABA-1}{j-1}

gi∗(n1+n2+1−ij−i)∗(jABA)∗(j−ABABAB)∗(n3+ABA−1j−1)g_i*\binom{n_1+n_2+1-i}{j-i}*\binom{j}{ABA}*\binom{j-ABA}{BAB}*\binom{n_3+ABA-1}{j-1}

B

排序,贪心

扰动法(交换两个位置)

设∑=x\sum=x,c0=yc_0=y

c1=max(x+a1,y)+b1c_1=max(x+a_1,y)+b_1

而这个b_1可以写进去

c1=max(x+a1+b1,y+b1)c_1=max(x+a_1+b_1,y+b_1)

这时候c2=max(x+a1+a2+b2,c1+b2)c_2=max(x+a_1+a_2+b_2,c_1+b_2)

带入c_1

max(x+a1+a2+b2,x+a1+b1+b2,y+b1+b2)max(x+a_1+a_2+b_2,x+a_1+b_1+b_2,y+b_1+b_2),这是c2c_2(2在后的)值

然后我们想怎么把它变成另一个,1在后

max(x+a1+a2+b1,x+a2+b2+b1,y+b2+b1)max(x+a_1+a_2+b_1,x+a_2+b_2+b_1,y+b_2+b_1)

然后比较下谁大谁小即可

首先最后一项没有意义,删除

然后x可以消掉

然后我们提出每一项的公共项

max(a1,b2)+a2+b1<=max(a2,b1)+a1+b2max(a_1,b_2)+a_2+b_1<=max(a_2,b_1)+a_1+b_2

移项,minmax反演

min(a2,b1)<=min(a1,b2)min(a_2,b_1)<=min(a_1,b_2)

唯一可能出问题就是这个<=

这里我们要做的是这个=特判一下

相当的时候,我们要设计新的判断标准

引入第三个元素,并且钦点他最靠后

1
2
3

c3=max(x+a1+b1+b2+b3,y+b1+b2+b3,x+a1+a2+b2+b3,x+a1+a2+c3+b1)c_3=max(x+a_1+b_1+b_2+b_3,y+b_1+b_2+b_3,x+a_1+a_2+b_2+b_3,x+a_1+a_2+c_3+b_1)

中间的有点问题

当min(a1,b2)=min(a2,b1)min(a_1,b_2)=min(a_2,b_1)时,我们按照a从小到大排序即可

C

首先算贡献

ljh:打表!

inv  1 2 3 4 5 6 7 8 9

1 1 1 1 1 1 1 1 1 1
2 1 2 2 2 2 2 2 2 1
3 1 2 3 3 3 3 3 2 1
4 1 2 3 4 4 4 3 2 1
5 1 2 3 4 5 4 3 2 1
6 1 2 3 4 4 4 3 2 1
7 1 2 3 3 3 3 3 2 1
8 1 2 2 2 2 2 2 2 1
9 1 1 1 1 1 1 1 1 1

下面6,7,8,9和4,3,2,1对称/se

把这个贡献用线段树维护一个,当做区间长度,去维护一个乘法标记推平标记和加法标记即可

时间复杂度O(nlogn)

code:


//tsx线段树
//关门弟子
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 1e9 + 7;
const int MAXN = 5e5 + 7;
int n, m, lz[MAXN], a[MAXN];
ll b[MAXN];

namespace fastIO {
#define BUF_SIZE (1<<20)
	static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
	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;

//x * mlt + adt
struct rec {
	ll mlt, adt;//铺平tag,乘法tag,加法tag
	//维护的先乘后加
	ll rsum, xsum;
	//真实的和,另一些权值和
	rec (ll MLT = 1, ll ADT = 0, ll R = 0, ll X = 0): mlt(MLT), adt(ADT), rsum(R), xsum(X) {};
	bool operator!=(const rec &x) {
		return mlt != x.mlt || adt != x.adt;
	}
} tr[MAXN];


inline void add(ll &x, ll y) {
	x += y;
	if(x >= P)x -= P;
	return ;
}

//加,合并标记
rec operator+(const rec &x, const rec &y) {
	rec nw = rec();
	nw.adt = 1ll * x.adt * y.mlt % P;
	add(nw.adt, y.adt);
	nw.mlt = 1ll * x.mlt * y.mlt % P;
	nw.rsum = (1ll * x.rsum * y.mlt % P + 1ll * x.xsum * y.adt % P) % P; //因为我们加的是一个数吗~~
	nw.rsum %= P;
	nw.xsum = x.xsum;
	// printf("%lld %lld  %lld %lld %lld %lld %lld?? %lld\n", y.mlt, y.adt, x.mlt, x.adt, nw.mlt, nw.adt, nw.rsum, nw.xsum);
	return nw;
}


inline void cal2(int k, int v) {
	tr[k].rsum = 1ll * tr[k].xsum * v % P;
	tr[k].mlt = 1;
	tr[k].adt = 0;
	lz[k] = v;
	return ;
}

//这个只维护带权和
//真实和第一次就解决了
inline void update(int k) {
	tr[k].rsum = (tr[k << 1].rsum + tr[k << 1 | 1].rsum) % P;
	return ;
}

//下传标记
//我们先传铺平再传加加加
inline void pushdown(int k) {
	if(~lz[k]) {
		cal2(k << 1, lz[k]);
		cal2(k << 1 | 1, lz[k]);
		lz[k] = -1;//偷袭!
	}
	if(tr[k] != rec()) {
		// printf("xiafang :%d\n", k);
		tr[k << 1] = tr[k << 1] + tr[k];
		tr[k << 1 | 1] = tr[k << 1 | 1] + tr[k];
		tr[k] = rec(1, 0, tr[k].rsum, tr[k].xsum);
	}
	return ;
}

inline void tadd(int k, int l, int r, int L, int R, rec jk) {
	// printf("tadd : %d %d %d %d %d output: %lld %lld %lld\n", k, l, r, L, R, tr[k].mlt, tr[k].adt, tr[k].rsum);
	if(L <= l && r <= R) {
		tr[k] = tr[k] + jk;
		// printf("final in this %d %d rsum %lld xsum %lld %lld %lld\n", l, r, tr[k].rsum, tr[k].xsum, tr[k].mlt, tr[k].adt);
		return ;
	}
	pushdown(k);
	int mid = (l + r) >> 1;
	if(L <= mid)tadd(k << 1, l, mid, L, R, jk);
	if(R > mid)tadd(k << 1 | 1, mid + 1, r, L, R, jk);
	update(k);
	return ;
}

inline void ttrs(int k, int l, int r, int L, int R, int v) {
	if(L <= l && r <= R) {
		cal2(k, v);
		return ;
	}
	pushdown(k);
	int mid = (l + r) >> 1;
	if(L <= mid)ttrs(k << 1, l, mid, L, R, v);
	if(R > mid)ttrs(k << 1 | 1, mid + 1, r, L, R, v);
	update(k);
	return ;
}

//建树
//只要系数不出错,三观跟着五官跑
inline void build(int k, int l, int r) {
	// printf("%d %d %lld?\n", l, r, tr[k].mlt);
	if(l == r) {
		tr[k].xsum = b[l];
		tr[k].rsum = 1ll * a[l] * b[l] % P;
		return ;
	}
	int mid = (l + r) >> 1;
	build(k << 1, l, mid);
	build(k << 1 | 1, mid + 1, r);
	update(k);
	add(tr[k].xsum, tr[k << 1].xsum);
	add(tr[k].xsum, tr[k << 1 | 1].xsum);
	// printf("%d %d %d %lld %lld\n", k, l, r, tr[k].rsum, tr[k].xsum);
}

ll fac[MAXN], ifac[MAXN], inv[MAXN], cf[MAXN], sum[MAXN];

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;
}

inline void preinit() {
	fac[0] = ifac[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;
	for(int i = 1; i <= n; ++i)inv[i] = ifac[i] * fac[i - 1] % P;
	for(int i = 1; i <= n; ++i)add(sum[i], inv[i]), add(sum[i], sum[i - 1]);
	// printf("%lld %lld\n", inv[2], inv[3] * 3 % P);
	// for(int i = 1; i <= n; ++i) {
	// 	printf("%d inv is %lld \n", i, inv[i]);
	// 	printf("%d suminv is %lld\n", i, sum[i]);
	// }
	// printf("%lld\n", ifac[n]);
}

//处理系数
//要是这个挂了我就跟着三观跑了
inline void init() {
	preinit();//预处理预处理
	int N = (n + 1) / 2;
	for(int i = 1; i <= n; ++i)cf[i] = 0;
	for(int i = 1; i <= N; ++i) {
		ll v = (sum[n - i + 1] - sum[i - 1] + P) % P; //就是系数啊
		// printf("%d is cf now,Value is :%lld ?\n", i, v);//真的是吧??
		cf[i] = (cf[i] + v) % P;
		cf[n - i + 2] = (cf[n - i + 2] - v + P) % P;
	}
	for(int i = 1; i <= n; ++i) {
		// printf("i xishu : %d %lld  ? \n", i, cf[i]);
		cf[i] = (cf[i - 1] + cf[i]) % P;
		b[i] = cf[i];
		// printf("so is ?%lld\n", b[i]);
	}//跑了跑了/se
	// ll ans = 0;
	// for(int i = 1; i <= n; ++i)ans += a[i] * b[i] % P;
	// printf("%lld\n", ans % P);
	// for(int i = 1; i <= n; ++i)b[i] = 1;//先这样调
	build(1, 1, n);
	return ;
}

int main() {
	// freopen("c.in", "r", stdin);
	// freopen("test1.out", "w", stdout);
	n = read();
	m = read();
	for(int i = 1; i <= n; ++i) {
		a[i] = read();
	}
	init();//预处理系数和建树!!
	memset(lz, -1, sizeof(lz));
	for(int i = 1, t, x, y, v; i <= m; ++i) {
		t = read();
		if(t != 4) {
			x = read();
			y = read();
			v = read();
		} else {
			printf("%lld\n", tr[1].rsum);
			continue;
		}
		if(t == 1)tadd(1, 1, n, x, y, rec(1, v, 0, 0));//后两个根本没意思
		if(t == 2)tadd(1, 1, n, x, y, rec(v, 0, 0, 0));
		if(t == 3)ttrs(1, 1, n, x, y, v);
	}
	return 0;
}
/*
5 1
2 3 1 4 5
4
*/

D

答案不会超过O(n2)O(n^2)

考虑n2n^2枚举一下点对?

然后答案只可能是这两个点对距离和/2或者这两个点距离

如果是距离,枚举那个端点被点了

我们找到这个中点(可能在边上)

然后从这个中点出发跑最短路,得到到每个点的最短路

于是我们可以知道,大于我们枚举的时间的点都是要被点的,所以我们都点上

然后这些点都被设置成关键点

枚举所有的点,所有的边,计算每个点/边被染上的最大时间

边染色时间就是两个端点和/2

然后找到这个最大时间就解决了!

如果不等于就暴毙了

Powered by Gridea RSS