夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

某金牌训练营Day3

2021-02-17 21 min read

突然意识到一遍过的重要性/cy

A

第一个条件告诉我们一些东西要放在一起

首先我们要合并区间

先找到所有每个位置最靠后的不合法位置

然后我们每个数暴力向后扩展,每次把区间右端点向后扩展即可

这样就处理好条件1了

然后我们再考虑并起来的区间a就是等价于区间最大值,然后b就是区间的和

然后二分答案,我们相当于限制每一段b的最大值和不超过mid,然后要求a的最大值之和最小

然后可以考虑最小化方案去dp一下,如果这个情况下都是大于则说明不行

这个转移是这样的,j是最后满足的合法位置

fi=min⁡fj+max(i,j)f_i=\min f_j+max(i,j)

可以发现我们能用一个单调栈维护所有前缀最大值

然后每次更新单调栈的时候,弹出一个数等价于某一段的dp值-最大值然后+新的最大值

这个东西可以随意的使用线段树优化,但是很慢/kk

观察到dp值单调递增

然后我们发现一种方案的最优决策点有两个性质

  1. 要么aja_j取到最大值
  2. si−sj−1>mids_i-s_{j-1}>mid,即j是满足条件最小的j

证明很显然,如果不满足1,2,我们一定存在一个小于他且不会使最大值改变的一个决策点

然后满足条件2的只会有一个,可以直接O1O1回答,因为这个只会单调递增,可以双指针

另外一个条件比较复杂,我们要把每一个满足条件的j都拿出来最大值

fj+maxj<i(a)f_j+max_{j<i}(a)

使用set维护即可,因为两端点都单调递增就很快很快

#include<bits/stdc++.h>
#define ins insert
#define int long long
#define pb push_back
using namespace std;
const int MAXN = 8e5 + 7;

int n, m, K, tot, dw;
struct rec {
	int a, b;
} p[MAXN];
int a[MAXN], b[MAXN], c[MAXN], d[MAXN], pd[MAXN];
int sum[MAXN];
vector<int> v;

namespace seg {
#define mid ((l+r)>>1)
	int mx[MAXN], tag[MAXN];
	inline void mdf(int k, int l, int r, int p, int g) {
		if(l == r) {
			mx[k] = max(mx[k], g);
			return;
		}
		if(p <= mid)mdf(k << 1, l, mid, p, g);
		else mdf(k << 1 | 1, mid + 1, r, p, g);
		mx[k] = max(mx[k << 1], mx[k << 1 | 1]);
	}
	inline void pushR(int k, int x) {
		tag[k] += x;
		mx[k] += x;
	}
	inline void pushdown(int x) {
		if(tag[x]) {
			pushR(x << 1, tag[x]);
			pushR(x << 1 | 1, tag[x]);
			tag[x] = 0;
		}
	}
	inline void mdf(int k, int l, int r, int L, int R, int q) {
		if(L <= l && r <= R) {
			pushR(k, q);
			return ;
		}
		pushdown(k);
		if(L <= mid)mdf(k << 1, l, mid, L, R, q);
		if(R > mid)mdf(k << 1 | 1, mid + 1, r, L, R, q);
		mx[k] = min(mx[k << 1], mx[k << 1 | 1]);
	}
	inline int qry(int k, int l, int r, int L, int R) {
		if(L <= l && r <= R)return mx[k];
		pushdown(k);
		if(R <= mid)return qry(k << 1, l, mid, L, R);
		else if(L > mid)return qry(k << 1 | 1, mid + 1, r, L, R);
		else return max(qry(k << 1, l, mid, L, R), qry(k << 1 | 1, mid + 1, r, L, R));
	}
	inline int qry2(int k, int l, int r, int L, int R) {
		if(L <= l && r <= R)return mx[k];
		pushdown(k);
		if(R <= mid)return qry2(k << 1, l, mid, L, R);
		else if(L > mid)return qry2(k << 1 | 1, mid + 1, r, L, R);
		else return min(qry2(k << 1, l, mid, L, R), qry2(k << 1 | 1, mid + 1, r, L, R));
	}
#undef mid
}
using namespace seg;

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

inline void init2() {
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	for(int i = 1; i <= n; ++i)a[i] = getid(p[i].a), b[i] = getid(p[i].b);
	m = v.size();
	return ;
}

inline void init() {
	init2();//离散化真实的
	for(int i = 2; i <= n; ++i)
		mdf(1, 1, m, a[i], i);
	for(int i = 1; i < n; ++i) {
		int t = qry(1, 1, m, b[i], m);
		if(t > i)pd[i] = t;
	}
	for(int i = 1; i <= n; ++i) {
		c[++tot] = p[i].a;
		d[tot] = p[i].b;
		if(pd[i]) {
			int w = pd[i];
			for(int j = i + 1; j <= w; ++j) {
				w = max(pd[j], w);
				c[tot] = max(p[j].a, c[tot]);
				d[tot] += p[j].b;
			}
			i = w;
		}
	}
	for(int i = 1; i <= tot; ++i)
		sum[i] = sum[i - 1] + d[i], dw = max(dw, d[i]);
	return ;
}

//先写一个n^2爽爽
int f[MAXN], st[MAXN], tp;
inline int chk(int x) {
	memset(mx, 0, sizeof(mx));
	memset(tag, 0, sizeof(tag));
	memset(f, 0x3f3f3f3f, sizeof(f));
	memset(st, 0, sizeof(st));
	tp = 0;
	for(int i = 1; i <= n; ++i) {
		while(c[st[tp]] < c[i] && tp) {
			mdf(1, 0, n, st[tp - 1], st[tp] - 1, -c[st[tp]]);
			--tp;
		}
		int p = lower_bound(sum, sum + i + 1, sum[i] - x) - sum;
		mdf(1, 0, n, st[tp], i - 1, c[i]);
		st[++tp] = i;
		f[i] = qry2(1, 0, n, p, i - 1); //直接查询即可
		mdf(1, 0, n, i, i, f[i]);
	}
	return f[n] <= K;//最大值之和
}

signed main() {
	freopen("sequence.in", "r", stdin);
	freopen("sequence.out", "w", stdout);
	scanf("%lld%lld", &n, &K);
	for(int i = 1; i <= n; ++i)scanf("%lld%lld", &p[i].a, &p[i].b), v.pb(p[i].a), v.pb(p[i].b);
	init();
	n = tot;
	int l = dw, r = sum[n], mid = 0, ans = -1;
	while(l <= r) {
		mid = (l + r) >> 1;
		if(chk(mid)) {
			r = mid - 1;
			ans = mid;
		} else {
			l = mid + 1;
		}
	}
	printf("%lld\n", ans);
	return 0;
}
/*
4 12
6 12
4 4
3 7
3 11

3 12
3 11
6 11
8 8

*/

真他妈调到逝世了!!!

首先是i的系数和i+1有关....

然后是nmd每次单调栈一定是只管i和i-1的那些数的关系!!因此我们需要特判新的数加入的时候.....

然后线段树两个询问函数不要递归调用!!!nmd!!

李队还有一种方法不缩点而是修改dp值

就是对于一个数,如果满足他左边的b最小值要小于大于右边的a最大值的话,就把这一段的b,dp值都变成1e9就好了,因为这个告诉我们至少有一个不合法的状态

后缀表达式,如果一些是同种运算符他们可以任意交换

然后建立表达式树,就是对于中缀表达式A*B,我们先有一个星号的中间节点,然后左右子树为A,B,然后没有交换结合律可以构建唯一的树

但是本题有交换结合律,相当于如果相邻运算符节点相同则可以合并起来,然后我们会发现相当于原表达式一些节点的顺序是没有影响的

他们的儿子可以任意排列(没用)

同时你会发现我们可以任意合并叶子节点,他们的信息不会发生改变

然后我们考虑每个子树在后缀表达式是一个区间,这些子树相当于可以任意排列

那么我们考虑树形dp,先让子区间最优化,再让剩下的最优化

考虑一个区间让什么顺序开头会影响答案的,因为如果有一些叶子和这个区间开头相同,也是可以压缩的

这个压缩至多使答案减少1

然后aviu,iavi_{u,i}表示答案最小的情况下能否以字母i开头(是否存在一个最优方案)

ansu=1+∣x∣+∑ansvans_u=1+|x|+\sum ans_v

即最多就这么大了(答案上界)

然后我们还可以通过上述过程压缩大小

这个怎么转移呢?因为我们一个子树有多种可能的情况,所以考虑网络流,保证一个子树只会选择一个类,即可

到底怎么建图?

首先相同叶子全部合并

然后每个叶子放在左边,然后每个子树放在右边,让叶子匹配子树,一个子树拆成26个点,并且限制这26个点共用1点流量即可

然后怎么转移avi呢?如果已经出现就不用说了,否则说明我们可以让某个子树选择到某个字母,然后仍然能够转移

在二分图上删掉一个节点,然后让最大匹配数不会减少即可,这个相当于找到有哪些是必须匹配点

直接让这个点的匹配点找匹配点即可,如果有一条增广路,说明我们就能让另一个点匹配成功也就是说这个点并不是最大匹配点

找每个点是不是在最大匹配中还有O(n)做法/se!!

C

考场上写了NTT,然后有一个巨大的循环卷积的坑!

一定要开结果多项式两倍的空间,然后模长也处理到他的两倍

而且要注意如果我们modn要清空多出来的那些项的系数

否则就会因为循环卷积,多出来的结果会跑到低位,你就挂了

直接反演显然是一个O(n2)O(n^2)大小的矩阵消元,是上三角矩阵所以可以O(n2)O(n^2)消元

这个系数是可以背包得到的,其实就是(ex−1)i(e^x-1)^i每次卷那个阶乘就好了,NTT优化卷积有O(n2logn)O(n^2logn)

首先恰好只能n2n^2考虑变成至多,然后再容斥

j个格子至多i种颜色染色,就是iji^j

ci=∑j=0najijc_i=\sum_{j=0}^n a_j i^j

然后反演出恰好就是二项式反演

ci=∑j=0i(ij)cjc_i=\sum_{j=0}^i\binom{i}{j}c_j

写一下

ci=∑j=0ii!j!∗(i−j)!bjc_i=\sum_{j=0}^i\frac{i!}{j!*(i-j)!}b_j

cii!=∑j=0i1(i−j)!bjj!\frac{c_i}{i!}=\sum_{j=0}^i\frac{1}{(i-j)!}\frac{b_j}{j!}

随便NTT

求c咋做?

考虑我们c的形式很像是给出了多项式在i处的取值,然后问多项式所有系数,就是一个插值形式

多项式快速插值

怎么实现多项式快速插值?首先有一步能加快就是求

di=yi(∏j!=ixi−xj)d_i=\frac{y_i}{(\prod_{j!=i} {x_i-x_j})}

然后这个东西在本题就是一个下降幂,否则要多项式多点求值得出这些点值

就是我们有g(x)=∏i=1n(x−xi)g(x)=\prod_{i=1}^n(x-x_i),然后下面那个东西就是g(xi)(x−xi)\frac{g(x_i)}{(x-x_i)}

仔细一看做你妈,这里分子分母都是0

然后可以洛必达法则,如果

lim⁡x−>af(x)=0,lim⁡x−>ag(x)=0\lim_{x->a}f(x)=0,\lim_{x->a}g(x)=0

我们求得是

lim⁡x−>af(x)g(x)=lim⁡x−>af′(x)g′(x)\lim_{x->a} \frac{f(x)}{g(x)}=\lim_{x->a}\frac{f'(x)}{g'(x)}

然后洛必达法则是什么呢?是用来求函数不定型极限的一种东西,不定型是我们没有足够多的信息确定这个极限的取值(??),比如00,∞∞\frac{0}{0},\frac{\infty}{\infty},他们可能是具有实际意义的值,但是这个和我们赋予他们的含义有关,比如00=10^0=1

然后wiki告诉我们,如果f(x),g(x)当x趋于a时无穷大或者为0,这个分式的值就可以洛,就是我写的第二个式子成立

然后带入啊,我们x−xix-x_i求导之后为1,所以有

g(xi)(x−xi)=g′(xi)\frac{g(x_i)}{(x-x_i)}=g'(x_i)

这告诉我们把g(x)g(x)求出来,然后求导,然后多项式多点求值(艹

本题NTT即可

然后怎么加速剩下的求和式子?分治NTT维护两个式子

fl,r=∑i=lryig′(xi)∏j=l,j!=ir(x−xj)=∑i=lmidyig′(xi)∏j=l,j!=ir(x−xj)+∑i=mid+1ryig′(xi)∏j=l,j!=ir(x−xj)=∏j=mid+1r(x−xj)∑i=lmidyig′(xi)∏j=l,j!=imid(x−xj)+∏j=lmid(x−xj)∑i=mid+1ryig′(xi)∏j=mid+1,j!=ir(x−xj)=∏j=mid+1r(x−xj)fl,mid+∏j=lmid(x−xj)fmid+1,rf_{l,r}=\sum_{i=l}^r\frac{y_i}{g'(x_i)}\prod_{j=l,j!=i}^{r}(x-x_j)\\ =\sum_{i=l}^{mid}\frac{y_i}{g'(x_i)}\prod_{j=l,j!=i}^{r}(x-x_j)+\sum_{i=mid+1}^{r}\frac{y_i}{g'(x_i)}\prod_{j=l,j!=i}^{r}(x-x_j)\\ =\prod_{j=mid+1}^{r}(x-x_j)\sum_{i=l}^{mid}\frac{y_i}{g'(x_i)}\prod_{j=l,j!=i}^{mid}(x-x_j)+\prod_{j=l}^{mid}(x-x_j)\sum_{i=mid+1}^{r}\frac{y_i}{g'(x_i)}\prod_{j=mid+1,j!=i}^{r}(x-x_j)\\ =\prod_{j=mid+1}^r(x-x_j)f_{l,mid}+\prod_{j=l}^{mid}(x-x_j)f_{mid+1,r}

901. 「拉格朗日插值」生成树和

这个怎么这么眼熟?

一看长乐集训2017原题

首先要算每一位的贡献

然后考虑构建多项式,让加法变成乘法

对于

1+1=2,1+2=0,2+2=1

1+0=1,2+0=2

这种运算法则,我们不难发现加法就是相当于mod  3\mod 3意义下的多项式乘法

然后我们矩阵树统计得到的应该是所有方案的这个权值和,此时因为是系数相加,所以不是乘法了

然后我们发现这样不太够,因为我们不能带着多项式去乘啊,加强版是T的,要写成三次单位根的形式

有什么神仙1+w+w2=01+w+w^2=0?

证明可能只有再乘上一个ww后发现左边的值没有变,然后w不是0说明他就只能是0了

(a+bw)−1=1a+bw(a+bw)^{-1}=\frac{1}{a+bw}

=(a−b)+(−b)wa2+b2−ab=\frac{(a-b)+(-b)w}{a^2+b^2-ab}

这样就有求逆了....qaq也就能够高斯消元解出三个边权具体是什么了....

这个为什么有插值的标签啊

是不是因为我们可以猜测答案是一个次数不是很多的多项式就是O(n3)O(n^3)次多项式,然后直接插值啊/jk

这个好像不太行吧...

902. 「拉格朗日插值」距离之和

猜测一下答案是关于N的若干次多项式

而且这个多项式次数应该不会很大

至少不可能是K次多项式,盲猜应该是10次左右,然后暴力插值出前几十个点值就能做了??

不太现实,我觉得是关于n的k次多项式,但是这个k大的离谱啊

兔手把手教我做题/se

首先是对于切比雪夫距离小于i的点数为O(k∗ik−1)O(k*i^{k-1})

同时距离和为O(k2)O(k^2)

也就是说我们可以发现答案确实是k+1次多项式/cy

问题在于如何快速求出前k+2个点值??要一个log吧?

高人指点我OEIS,但是这太不友好了!

真不会log了

然后兔又教教我了/ll

切比雪夫小于等于i的,减去切比雪夫小于等于i-1的就是答案吧

nmd这个是切比雪夫距离和

然后就是考虑生成函数一下,每一维有(2n+1)种选择,小于等于的总点数就是(2n+1)k(2n+1)^k

然后得到n的总点数,乘上n就好了/ll

我怎么这么傻啊/ll

然后线性插值即可

这题还卡常啊能省快速幂就省一个吧...


#include<bits/stdc++.h>
#define ll long long
const int P = 1e9 + 7;
const int MAXN = 2e6 + 7;

int T, n, k;
ll a[MAXN], fac[MAXN], jc2, ifac[MAXN], b[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 init() {//k*(2N+1)^(k-1) * n
   fac[0] = 1;
   b[0] = 1;
   for(int i = 1; i <= k + 2; ++i) {
   	b[i] = ksm(2 * i + 1, k);
   	a[i] = (b[i] - b[i - 1] + P) % P * i % P;
   	a[i] = (a[i] + a[i - 1]) % P;
   	fac[i] = fac[i - 1] * i % P;
   }
   ifac[k + 2] = ksm(fac[k + 2], P - 2);
   for(int i = k + 1; i >= 1; --i)ifac[i] = ifac[i + 1] * (i + 1) % P;
   ifac[0] = 1;
   jc2 = 1;
   for(int i = 1; i <= k + 2; ++i)jc2 = jc2 * (n - i) % P;//i次下降幂
   return ;
}

inline ll chazhi() {
   ll ans = 0;
   for(int i = 1; i <= k + 2; ++i) {
   	if(n != i) {
   		if((k + 2 - i) & 1)
   			ans = (ans + P - a[i] * jc2 % P * ksm(n - i, P - 2) % P * ifac[i - 1] % P * ifac[k + 2 - i] % P) % P;
   		else
   			ans = (ans + a[i] * jc2 % P * ksm(n - i, P - 2) % P * ifac[i - 1] % P * ifac[k + 2 - i] % P) % P;
   	} else return a[i];
   }
   return ans;
}

ll chazhi2() {
   ll ans = 0;
   for(int i = 1; i <= k + 2; ++i) {
   	ll tmp = a[i];
   	for(int j = 1; j <= k + 2; ++j) {
   		if(i == j)continue;
   		tmp = 1ll * tmp * (n - j) % P * ksm(i - j, P - 2) % P;
   	}
   	ans = (ans + tmp) % P;
   }
   return ans;
}

int main() {
   freopen("distance.in", "r", stdin);
   freopen("distance.out", "w", stdout);
   scanf("%d", &T);
   while(T-- > 0) {
   	scanf("%d%d", &k, &n);
   	init();//预处理
   	printf("%lld\n", chazhi());
   } return 0;
}

572. 「二分图匹配」不同缩写

看上去就不是阳间的题

Powered by Gridea RSS