https://www.ybtoj.com.cn/contest/113

不注册应该是看不了的

A. 通技进阶

第一步可以抛弃题目性质转换成最大团

先随机一个排列p,然后每次尝试将 $p_i$ 加入当前团中

如果当前团和p的边交集达到团大小,就直接冲

然后有的同学退火学的好就直接过了

考虑正解咋办啊

用一个动平面去截取一个直线

没有和x轴垂直的那么都会有一个交点

把一个直线看成和平面上的动点

即时间 $x_1$ 的时候坐标是 $(y_1,z_1)$

就是我们先算出 $t=0$ 时候的位置

这样就能算出来任意一个t的位置了

那考虑一个满足条件的集合

一定满足两个情况之一

某个时刻全部交在一个点
所有直线共面,但是没有直线平行

第一种情况处理方法是

枚举那个点,然后枚举剩下的点,计算剩下那些点他们在什么时候和这个点重合,排序然后就能知道哪个时间点所有点都会和他相交了

怎么知道相交时间?你考虑这两个点一定位于两条直线上

所以我们可以枚举另一条直线,如果这两个直线相交,那个横坐标就是时间

第二种情况处理方法是

我们会发现这样竖着的一个面去截他们的结果一定有一条斜率固定的直线在平面上,因为他们一定共面啊,而面面相交只有直线

那么我们可以枚举这条直线上的一个点为原点,然后其他点相对于这个点的做一个极角排序,极角序就是极坐标系中的角度

然后只要在同一条直线上(同一极角序)的两个点,如果他们速度不相同,就一定能有一个位置使得他们共点

速度是什么?是相对于原点的速度,就是你可以暴力的求出t+1时刻每个点,然后就能知道所有点基于原点的向量了,就能知道有没有点完全平行了

然后我们发现其实可以每次求出答案后如果可以更新暴力扫描整个集合有没有共线的直线这样子,因为最多更新O(n)次所以也是对的

然后我们考虑这样会不会因为同一条线上速度方向不同自闭呢?

不会,我们选取最左边的一个点和最右边的一个点做两遍就完了,而我们要枚举所有点跑极角排序,所以一定统计得到

极角排序是什么?我们按照极坐标排序

极坐标就是模长+极角建立的坐标系

向量是一个起点不确定有向线段

傻子排序法

用 $atan2(y,x)$ 先传y再传x即可,会返回一个极角

然后还有叉积法

大于0前者在后者顺时针方向,小于0在逆时针方向,否则在一条直线上

$x_1y_2-x_2y_1$

B. 序列合并

考虑第一个数最终是什么,如果我们能合乘一个j,然后让这个j保持不变,限制这个不变的前提下,后面是一个独立的问题

注意每个数的上界是 $n+m-1$

你考虑每次合并出一个数x,都需要先合并出所有小于他的数直到m,然后再一路合并上去,就能得到这个上界

$p_{i,j}$ 表示限制序列最长长度为i整个过程出现的第一个数为j的概率

然后转移就有

第一步直接放入j

我们是 $\frac{1}{m}$

先放入了 $j-1$ ,再放入了 $j-1$

$p_{i-1,j-1}*p_{i,j-1}$

$p_{i,j}=p_{i-1,j-1}*p_{i,j-1}+\frac{1}{m}*[j\leq m]$

条件概率

在定义 $q_{i,j}$ 为从第一个位置产生了j的前提下,第一个数不变的概率

这个只需要钦定第二个位置最后不是j,或者 $j=L$ !

$q_{i,j}=1-[j<L]p_{i-1,j}$

$g_{i,j}$ 表示限制序列最长长度为i,然后第一个位置产生了j,然后第一个数不变的前提下,序列各个数最后和的期望

$ans=\sum (p_{i,j}*q_{i,j}*g_{i,j})$

怎么求g

$P_j(x)$ 表示限制第一个位置为j且不变的概率最后和s的期望的生成函数

这里我们直接钦定第一个条件j成立就不用管后面的了

然后我们写一下转移,可以考虑多条件概率全概率公式展开

=j+\sum_s s*p(和为s且第一个数不变)\\ =j+\sum_s s*\frac{p(和为s,第一个数不变)}{p(第一个数不变|第一个数为j)}\\ =j+\sum s*\frac{p(和为s)-p(和为s第一个数改变)}{p(第一个数不变|第一个数为j)}\\ =j+\frac{ans_{i-1}-\sum s*p(2为j)p(和为s|2产生j)}{q_{i,j}}

前面一项,我们考虑这个就是2~i的PGF吧,然后后面那一项,我们考虑就是钦定第二个数是j,但是没有不变的限制,因为我们一旦产生j,不管变不变都会和1先合并

所以我们定义另一个PGF,表示只需要已知第一个为j,然后长度限制是k的期望的生成函数

有

\sum_s p(和为s|第一个数为j)\\ =\sum_s p(和为s,第一个数不变|第一个数为j)+p(和为s,第一个数改变|第一个数为j)\\

再仔细思考发现,第一数改变只能变大

也就是说,如果我们2~i凑出一个j,就能让第一个数变成j+1

所以

$G_j(x)=q*P_j(x)+(1-q)G_{j+1}(x)$

=j+\frac{ans_{i-1}-\sum s*p(2为j)p(和为s|2产生j)}{q_{i,j}}\\ =j+\frac{ans_{i-1}-p_{i-1,j}*f_{i-1,j}}{q_{i,j}}

直接递推即可

顺序先g再f再ans

注意到这个 $q_{i,j}$ 可以绑定g,就是直接求 $q_{i,j}*g_{i,j}$

条件期望,我们可以使用条件概率

$P(A|B)=P(AB)/P(B)$

也可以使用贝叶斯公式

$P(A|B)=\frac{P(B|A)*P(A)}{P(B)}$

全概率公式由这个可以得出,对于概率空间任意划分我们有

$P(A)=\sum_{i=1}^{n_i}P(A,B_i)=\sum_{i=1}^nP(A|B_i)P(B_i)$

C. 机器决斗

显然我们可以排序

比较关键字为两个物品谁放在前面更优

将问题按照贪心顺序排序后,我们考虑怎么优化 $n^2$ 枚举的过程

先把所有的贡献都算上,问题变成我们要扣掉两个点,最大化扣掉点的贡献

然后写一下式子就会发现有一项是和两个点的乘积有关的

于是我们维护一个那一项和另一项的凸包即可

发现我们需要维护的是前i个点构成的凸包

平衡树维护凸包即可

这里树上二分找后继直接找子树最大最小值即可!不要再暴力findpre,findnxt了

zx爷爷说我们直接维护凸包上的边是很好的做法,就和之前完全动态凸包中隐式树结构一样??

但是一听就好阴间啊,我要把边转成点才能回答

维护的时候我不会写树上二分和插入点导致自闭了QAQ(就是啥也不会呗)

还有李超树,二进制分组,cdq分治,还有ljh的单调队列,就是转换式子的时候变成剪掉 $f_i+f_j-cst(i,j)$

然后就发现我们如果i,j的顺序反了会使得这个变小...就更劣了/ll

所以就是平凡的凸包了

//用平衡树实现动态上凸包
//然后支持查询点积最大值即可
#include<bits/stdc++.h>
#define db double
#define ll long long
#define int long long
using namespace std;
const db eps = 1e-13;
const int MAXN = 1e6 + 7;

int n, m;
struct rec {
	ll a, b;
	bool operator<(const rec &x)const {
		int cst1 = b * ((a - 1) / m) + x.b * ((a - 1) / m + 1 + (x.a - 1) / m);
		int cst2 = x.b * ((x.a - 1) / m) + b * ((x.a - 1) / m + 1 + (a - 1) / m);
		return cst1 < cst2;
	}
} a[MAXN], b[MAXN];
ll suma[MAXN], sumb[MAXN], ans;

namespace fastIO {
#define BUF_SIZE (1<<21)
	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;

inline db slope(int d, ll x, ll y) {
	if(b[d].b <= -1e17 || b[d].a == x)return -1e18;
	return (b[d].b - y) / (1.0 * b[d].a - x);
}

namespace fhq {
	int siz[MAXN], rt[MAXN], lt[MAXN], rnd[MAXN];
	int val[MAXN], id[MAXN];
	int T, cnt, x, y, z, p, root;

	inline void update(int x) {
		siz[x] = 1 + siz[lt[x]] + siz[rt[x]];
	}

	inline int nw_(int x, int y) {
		siz[++cnt] = 1;
		val[cnt] = x;
		id[cnt] = y;
		rnd[cnt] = rand();
		return cnt;
	}

	inline int merge(int A, int B) {
		if(!A || !B)return A + B;
		if(rnd[A] < rnd[B]) {
			rt[A] = merge(rt[A], B);
			update(A);
			return A;
		} else {
			lt[B] = merge(A, lt[B]);
			update(B);
			return B;
		}
	}

	inline void split(int now, int k, int &x, int &y) {
		if(!now)x = y = 0;
		else {
			if(val[now] <= k) {
				x = now;
				split(rt[now], k, rt[now], y);
			} else {
				y = now;
				split(lt[now], k, x, lt[now]);
			}
			update(now);
		}
	}

	inline int kth(int now, int k) {
		while(1) {
			if(k <= siz[lt[now]]) {
				now = lt[now];
			} else if(k == siz[lt[now]] + 1) {
				return now;
			} else {
				k -= siz[lt[now]] + 1;
				now = rt[now];
			}
		}
	}
	inline void ins(ll a, ll b) {
		split(root, a, x, y);
		root = merge(merge(x, nw_(a, b)), y);
	}
	inline void del(int a) {
		split(root, a, x, z);
		split(x, a - 1, x, y);
		y = merge(lt[y], rt[y]);
		root = merge(merge(x, y), z);
	}
	inline int findpre(int a) {
		split(root, a - 1, x, y);
		if(siz[x] == 0)return -1;
		z = id[kth(x, siz[x])];
		root = merge(x, y);
		return z;
	}
	inline int findnxt(int a) {
		split(root, a, x, y);
		if(siz[y] == 0)return -1;
		z = id[kth(y, 1)];
		root = merge(x, y);
		return z;
	}
	inline void ins2(ll x, ll y, int qwq) {
		int d1 = findpre(x + 1); //返回id,小于等于
		int d2 = findnxt(x - 1); //大于等于
		if(~d1 && ~d2 && slope(d1, x, y) - slope(d2, x, y) < eps)return ; //这个点不需要插入
		for(d1 = findpre(x);; d1 = findpre(x)) {
			d2 = findpre(b[d1].a);
			if(d2 == -1)break;//没有点了
			if(slope(d1, x, y) < slope(d2, b[d1].a, b[d1].b))break;
			del(b[d1].a);
		}
		for(d1 = findnxt(x);; d1 = findnxt(x)) {
			d2 = findnxt(b[d1].a);
			if(d2 == -1)break;
			if(slope(d1, x, y) > slope(d2, b[d1].a, b[d1].b))break;
			del(b[d1].a);
		}
		ins(x, qwq);
	}
	inline int qry(ll x) {
		int l = 1, r = siz[root] - 1, mid = 0;
		ll ans = 0;
		while(l <= r) {
			mid = (l + r) >> 1;
			int d1 = id[kth(root, mid)];
			int d2 = findnxt(b[d1].a);
			if(x > slope(d1, b[d2].a, b[d2].b)) {
				ans = b[d1].a * x + b[d1].b;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return ans;
	}
};
using namespace fhq;
inline void solve() {
	ins(1e4 + 1, 0);
	b[0].a = 1e4 + 1;
	b[0].b = -1e18;//这个不可能自闭了吧??应该比可能最小斜率都小了..
	b[1].a = ((a[1].a - 1) / m + 1);
	b[1].b = ((a[1].a - 1) / m + 1) * (sumb[n] - sumb[1]) + a[1].b * ((a[1].a - 1) / m);
	ins(b[1].a, 1);
	ll qans = 0;
	for(int i = 2; i <= n; ++i) {
		b[i].a = (a[i].a - 1) / m + 1;
		b[i].b = ((a[i].a - 1) / m + 1) * (sumb[n] - sumb[i]) + a[i].b * (suma[i - 1] + (a[i].a - 1) / m);
		qans = max(qans,
				   qry(-a[i].b) +
				   (suma[i - 1] + (a[i].a - 1) / m) * a[i].b +
				   (sumb[n] - sumb[i]) * ((a[i].a - 1) / m + 1));
		ins2(b[i].a,
			 b[i].b, i);
		//x,y插入,维护上凸壳
	}
	printf("%lld\n", ans - qans);
	return;
}

signed main() {
	freopen("fittest.in", "r", stdin);
	freopen("fittest.out", "w", stdout);
	n = read();
	m = read();
	for(int i = 1; i <= n; ++i)a[i].b = read(), a[i].a = read();
	sort(a + 1, a + n + 1);
	ll t = 0;
	for(int i = 1; i <= n; ++i) {
		t += (a[i].a - 1) / m;
		ans += a[i].b * t;
		t++;
		suma[i] = t;
		sumb[i] = sumb[i - 1] + a[i].b;
	}
	solve();
	return 0;
}

641. 「平衡树」神秘物质

如果只有max,merge和insert都不需要手写平衡树就能维护

min,可以证明,一定存在一种最优方案,是使用长度为2的区间组成的

因为随着区间长度加长,答案不会变小

这告诉我们维护差分数组的最小值

会看merge操作,可以直接兼容,用平衡树维护两个数组即可

当然如果离线下来我觉得总可以线段树做

642. 「平衡树」生产工作

也不难啊

考虑对于这个询问操作,维护4个变量,一个表示上升段的i的和,然后上升段满足条件的数的数量,然后下降段i的和,下降段的数的数量,然后这四个量考虑怎么和区间翻转兼容

比如 $[l,r]$ ,我们先把这棵子树提出来,然后你会神奇的发现,翻转他等价于交换上面四个量中的其中两个量,上升段变成下降段

然后我们再考虑能不能维护update,对于一个根rt,左子树u,右子树v

特殊判断 $h_u$ 和u在左子树中的前驱的 $h$ 大小关系以及 $h_u$ v在右子树内后继h大小关系即可,就能相应的给四个量产生贡献,然后直接update

子树内前驱后继只需要记录一个子树内的最大值即可,这个很简单

还有友好的取模?话说这个只开 $5e4$ 是为啥啊,显然是一个log吧,可能是update和pushdown太慢了,毕竟平衡树就慢在这里

451. 「概率期望 DP」礼物购买

这不就条件期望练习题吗...

考虑所有物体相当独立,然后喵一眼样例解释,他告诉我们要计算一种物品被需要的概率

那么对于所有物品,第一次被需要至少一次的概率应该是总概率减去一次都没有的概率,再乘上权值就是期望,也就是那个样例解释

而对于已经选了k次物品i的情况下,我们的期望应该变成至少需要k次该物品的期望值

这个咋算啊 $n^2m$ 很好做吧,就是直接dp!

或者半在线dp qaq

否则我们可能要容斥

李超树

Laurie讲的好!

首先我们一个区间内维护的是最具有优势的线段

就是在 $[l,r]$ 区间内暴露最长的线段

然后我们单点查询最大值的时候其实就是查询此区间中的最优线段是什么

即暴露最长的线段

根据单调性,我们计算这条线段和区间中另一条线段的交点,如果他在交点左侧,而且某一条斜率大,那么那一条就是最优线段,另一条递归左侧

实现起来不需要这样麻烦,我们用中点测试,如果中点a大,而且斜率也a大,那么b线段递归左侧,否则b线段递归右侧,因为相当于a左边区间都是他的

然后如果斜率反过来也是一样,交换a,b即可

我们如果在中点处相交,那么你就会发现保留哪一个斜率更小的即可就是把第一个的判断条件变为小于等于

但是你再仔细想想,你把斜率大的向右和斜率小的向左是一样的...

也可以实现区间,直接log定位到所有区间,然后查询到底部即可,复杂度 $O(log^2)$ ,~~实数区间~~

# include<iostream>
# include<cstdio>
# include<algorithm>
# include<cstring>
# include<cmath>
using namespace std;
const int mn = 50005;
int n,tot,tr[mn*4];
double b[100005],k[100005];
char s[200];
double f(int id,int x)
{
    return k[id]*(x-1)+b[id];
}
void update(int cur,int l,int r,int z)
{
    if(l==r)
    {
        if(f(z,l) > f(tr[cur],l)) tr[cur]=z;
        return ;
    }
    int mid=l+r>>1;
    if(k[tr[cur]] < k[z])
    {
        if(f(z,mid) > f(tr[cur],mid)){
            update(cur<<1,l,mid,tr[cur]);
            tr[cur]=z;
        }
        else update(cur<<1|1,mid+1,r,z);
    }
    if(k[tr[cur]] > k[z])
    {
        if(f(z,mid) > f(tr[cur],mid))
        {
            update(cur<<1|1,mid+1,r,tr[cur]);
            tr[cur]=z;
        }
        else update(cur<<1,l,mid,z);
    }
}
double query(int cur,int l,int r,int x)
{
    if(l==r)
        return f(tr[cur],x);
    int mid=l+r>>1;
    if(mid>=x)
        return max(f(tr[cur],x),query(cur<<1,l,mid,x));
    else return max(f(tr[cur],x),query(cur<<1|1,mid+1,r,x));
}
int main()
{
    int x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s);
        if(s[0]=='P')
        {
            ++tot;
            scanf("%lf%lf",&b[tot],&k[tot]);
            update(1,1,mn-10,tot);
        }
        else {
            scanf("%d",&x);
            printf("%d\n",int(query(1,1,mn-10,x)/100));
        }
    }
    return 0;
}

461. 「数据结构优化 DP」区间覆盖

所有区间按照右端点排序

dp, $f_{i}$ 表示钦定第i个区间选上/没选上的,让所有i右端点之前的关键点都被覆盖了的方案数

然后转移就枚举i之前的某一个区间,这样的两个区间要保证左右端点之间没有一个关键点才行!

然后这个区间到最后一个区间的信息求和...就么了

最后我们要考虑n区间不选的情况,也很简单,枚举n之前合法第一个选上的即可

夏晓光(loveJY)的博客

某金牌训练营Day1