夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

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

2020-11-29 13 min read # 斜率优化 # 凸包 # 决策单调性 # 比赛题 # 暴力

全场最佳 A

A

显然操作顺序和最后结果无关

因为我们最后都是从两边移走1

具体的我们可以枚举一下哪个是1哪个是0,以及两边的a1,a2a_1,a_2

a1−2x1+x2=0/1a_1-2x_1+x_2=0/1

x1x_1是操作多少次,a1a_1是位置1的值,对二取模

第二个

a2+x1−2x2+x3=0/1a_2+x_1-2x_2+x_3=0/1

我们对于这些方程高斯消元....

然鹅只有一组整数解

−2x1+x2=b+0/1-2x_1+x_2=b+0/1

第二个

x1−2x2+x3=c+0/1x_1-2x_2+x_3=c+0/1

然后我们有n个方程....

假设x1x_1操作了k次,那么换序之后还是操作了k次,消完之后会发现x1x_1的系数为n+1n+1

那么就是n+1倍x1=b+[0,n]x_1=b+[0,n]

所以只能有一个整数解(不可能两倍...)

接着第二个到最后一个也这样做

就可以递归证明

具体实现,你会发现操作一次相当于前面的一个0向后移动一位

然后我们就能用一个栈模拟一下了...


#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n, st[20000005], tp, a[20000005];
char s[20000005];
int main() {
	// freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);
	scanf("%s", s + 1);
	n = strlen(s + 1);
	for(int i = 1; i <= n; i++)
		a[i] = s[i] - '0';
	for(int i = 1; i <= n; i++) {
		if(a[i] == 0) {
			st[++tp] = i;
			continue;
		}
		if(a[i] == 1) continue;
		st[++tp] = i;
		while(tp && i - st[tp] + 1 <= a[i]) {
			int nw = i - st[tp] + 1;
			a[i] -= nw;
			a[i + 1] += nw - 1;
			tp--;
		}
		//	printf("a=%d\n",a[i]);
		if(tp) {
			int nw = a[i];
			a[i + 1] += nw;
			st[tp] += nw;
		} else {
			a[i + 1] += a[i] - a[i] / (i + 1);
			int q = a[i] % (i + 1);
			if(q) st[++tp] = q;
		}
		/*	printf("i=%d,tp=%d\n",i,tp);
			for(int j=1;j<=tp;j++)
				printf("%d ",st[j]);
			printf("\n");*/
	}
	for(int i = 1; i <= n; i++)
		s[i] = '1';
	for(int i = 1; i <= tp; i++)
		s[st[i]] = '0';
	s[n + 1] = 0;
	printf("%s", s + 1);
	return 0;
}

B

怎么不重啊??

对于[l,r][l,r],会发现这个区间有一些数i是满足的,当且仅当⌈il⌉!=⌊ir⌋\lceil \frac i l \rceil!=\lfloor \frac i r \rfloor

那么会发现这两个只有根号个区间,然后区间差分加法即可....

做法2

对于第i步,小于i的区间一定最多只会计算1次

然鹅大于等于i的区间一定都计入....

所以说我们第一个直接nlnnlognnlnnlogn统计

后一个直接双指针



#include<bits/stdc++.h>
using namespace std;
const int MAXN = 6e5 + 7;
int n, m, l[MAXN], r[MAXN];
struct qwq {
	int l, r;
	bool operator<(const qwq &x) {
		return r - l + 1 < x.r - x.l + 1;
	}
} e[MAXN];
struct rec {
#define lowbit(x) (x&(-x))
	int tr[MAXN];
	inline void add(int x, int v) {
		for(; x <= n; x += lowbit(x))tr[x] += v;
	}
	inline int qry(int x) {
		int ret = 0;
		for(; x; x -= lowbit(x))ret += tr[x];
		return ret;
	}
} tr;
int main() {
	// freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);
	scanf("%d%d", &m, &n);
	for(int i = 1; i <= m; ++i)scanf("%d%d", &e[i].l, &e[i].r);
	sort(e + 1, e + m + 1);
	int L = 1;
	for(int i = 1; i <= n; ++i) {
		for(; L <= m && e[L].r - e[L].l + 1 < i; ++L) {
			tr.add(e[L].l, 1);
			tr.add(e[L].r + 1, -1);
			// printf("%d %d\n", i, L);
		}
		int ans = 0;
		for(int j = i; j <= n; j += i) {
			ans += tr.qry(j);
		}
		ans += m - L + 1;
		printf("%d\n", ans);
	}
	return 0;
}

C

所有相邻的波峰-波谷

然鹅不需要维护峰,直接维护这个差分数组

区间加也变成sb了!甚至不需要pushdownpushdown

就能轻松过第一问

然后第二问,我们要维护一下开头和结尾的差分值,以及每个位置向后第一个大于0的值是啥

看看实现吧!


#include<bits/stdc++.h>
#define ll long long
const int MAXN = 5e5 + 7;
int T, n, q;
ll a[MAXN], b[MAXN];
struct rec {
	ll st, ed, cnt, stf, edf;
	ll ans;
	//开头,结尾的权值
	//一共的答案
	//cnt的记录
	//合并的时候,如果能拼起来,我们就拼,开头大于等于结尾
	//查询某个数前面第一个数<=0?
	//嗯嗯额!
	//stf是除去0的第一个数
} tr[MAXN];
namespace fastIO {
#define BUF_SIZE (1<<20)
	static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE, IOerror;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		if(p1 == pend)IOerror = -1;
		if(IOerror == -1)return IOerror;
		return *p1++;
	}
	inline int read() {
		int x = 0, f = 1;
		char s = nc();
		for(; !isdigit(s); s = nc())if(s == '-')f = -1;
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x * f;
	}
}
using namespace fastIO;
#define mid ((l+r)>>1)

inline void pushup(int k) {
	tr[k].stf = tr[k << 1].stf;
	tr[k].edf = tr[k << 1 | 1].edf;
	if(tr[k].stf == 0) {
		tr[k].stf = tr[k << 1 | 1].stf;
	}
	if(tr[k].edf == 0) {
		tr[k].edf = tr[k << 1].edf;
	}
	tr[k].st = tr[k << 1].st;
	tr[k].ed = tr[k << 1 | 1].ed;
	tr[k].ans = tr[k << 1].ans + tr[k << 1 | 1].ans;
	tr[k].cnt = tr[k << 1].cnt + tr[k << 1 | 1].cnt;
	if(tr[k << 1].edf > 0 && tr[k << 1 | 1].stf > 0 && tr[k << 1 | 1].st >= 0)--tr[k].cnt;
	// printf("%d %lld %d qwq\n", k, tr[k].ans, tr[k].cnt);
	//开头大于等于0,且两端第一个数都是大于0的,那么我们就可以拼起来
}

inline void build(int k, int l, int r) {
	if(l == r) {
		tr[k].st = tr[k].ed = tr[k].stf = tr[k].edf = b[l];
		if(tr[k].st > 0) {
			tr[k].ans = tr[k].st;
			tr[k].cnt = 1;
		} else {
			tr[k].ans = 0;
			tr[k].cnt = 0;
		}
		return;
	}
	// printf("build : %d %d %d ?? \n", k, l, r);
	build(k << 1, l, mid);
	build(k << 1 | 1, mid + 1, r);
	pushup(k);
}

inline void mdf(int k, int l, int r, int P, int v) {
	// printf("mdf : %d %d %d %d %d %d %d %d %d\n", k, l, r, P, v, tr[k].st, tr[k].ed, tr[k].edf, tr[k].stf);
	if(l == r) {
		tr[k].st += v;
		tr[k].ed = tr[k].stf = tr[k].edf = tr[k].st;
		if(tr[k].st > 0) {
			tr[k].ans = tr[k].st;
			tr[k].cnt = 1;
		} else {
			tr[k].ans = 0, tr[k].cnt = 0;
		}
		return ;
	}
	if(P <= mid)mdf(k << 1, l, mid, P, v);
	else mdf(k << 1 | 1, mid + 1, r, P, v);
	pushup(k);
	return ;
}

int main() {
	// freopen("test2.in", "r", stdin);
	// freopen("test3.out", "w", stdout);
	T = read();
	while(T-- > 0) {
		n = read();
		q = read();
		for(int i = 1; i <= n; ++i)a[i] = read();
		for(int i = 2; i <= n; ++i)b[i] = a[i] - a[i - 1];
		b[1] = -1e16;//来来
		build(1, 1, n);
		for(int i = 1, x, y, z; i <= q; ++i) {
			x = read();
			if(x == 1)printf("%lld %lld\n", tr[1].ans, tr[1].cnt * 2);
			else {
				x = read();
				y = read();
				z = read();
				if(x > 1)
					mdf(1, 1, n, x, z);
				if(y + 1 <= n)
					mdf(1, 1, n, y + 1, -z);
			}
		}
	}
	return 0;
}

D

第一问n<=300,直接枚举那一列跳下去

因为我们显然会选择一列走下去而不会多列

subtask 3

所有xix_i都相同?

那么我们可以考虑发现这个东西从哪拐下去对于最大的那个y,之后的y这个选择都是单调递减的

所以说我们可以发现这个东西有决策单调性,也就是说我们决策单调递增....

所以说我们走到第i个点花费为(x,y)(x,y),sy−si+(x−y+i)∗ais_y-s_i+(x-y+i)*a_i就是对于i的决策点

那每一列对于后面的贡献是一次函数

每次加入一个新的决策(列)y,我们可以弹掉最后一段决策....

然后我们就能分治决策单调性?!

首先最优方案不会劣于我们的当前决策点

而对于一个点,他的最优决策向下,那之后状态他的最优决策也是向下

对于同一行也是一样的

你会发现从k到k+1列,他同行决策点只能单调向右上移动

所以说新的一列,我们会发现他只存在从y轴下到上的一群决策点他们是变为向下走的!

那也就是说我们可以把所有询问离线挂到一列上

然后一下改一群决策点的答案,于是我们就可以一下回答一群

tyy:

设(x,y),然后发现这个东西转移很斜率优化

而这个东西不是很能斜率优化....因为我们会走到小于y的,不能做[1,n][1,n]的凸包斜率优化

但是提前n个点都知道,可以线段树建立凸包

排序要归并排序

然后会发现询问要定位到logn个节点,然后每次都二分又是两个log

所以说我们可以按照斜率排序所有询问,然后每个节点记录一下当前匹配到那个位置,然后从那个位置向后跳....

E

有些数是随便的,然后我们要向其中填入数,使得序列逆序对个数最小

n<=1e4,k<=100n<=1e4,k<=100

dp,fi,jf_{i,j}表示前i个数,最后一个数放j的逆序对数

会发现这个j单调递增,所以直接转移即可

然鹅小心这个东西T了,可以前缀和优化或者内部转移

F

Bzoj4361:isn

容斥?

fi,jf_{i,j}表示前i个数长度为j的递增子序列方案数

然后转移直接枚举树状数组优化

统计gig_i表示长度为i递增子序列方案数

ans1=gi∗(n−i)ans1=g_i*(n-i)这样算重了,因为可能在n−i+1n-i+1已经删成递增了....

然后容斥....你会发现−gi+1∗fac[n−i−1]∗(i+1)-g_{i+1}*fac[n-i-1]*(i+1)即可容斥

G

n<=50n<=50

划分成两个集合,满足两个集合and起来为一个数

那么显然枚举一个数大小,钦点这个集合内的数都选上,然后容斥即可

H

  1. 所有x->y

  2. 查询两两颜色相邻最小距离

分块

预处理每个大颜色和所有小颜色距离

预处理一个要并进去的答案,然后如果并进去的大小大于根号就暴力重构

I

三个相同颜色的卡死一个集合

Powered by Gridea RSS