Preface

真的摆了一整天啊啊啊啊啊啊。

Content

昨晚打比赛睡太晚，导致今天起得很晚。

早上去看题，写了道构造题，不出意外崩了，果断跑路。

下午打入门月赛，G 题死活三个点过不去，H 题想都懒得想。

然后把电脑给弟弟玩了好久，晚上九点才拿回来 QAQ。

[CF500E]New Year Domino

\(N\) 个多米诺骨牌，第 \(i\) 个坐标为 \(p_i\)，高度为 \(l_i\)，骨牌 \(i\) 能撞倒骨牌 \(j(i\lt j)\) 当且仅当 \(p_i +l_i \ge p_j\)。和现实中的骨牌一样，具有传递性。

比如，\(A\) 能撞倒 \(B,C\) 不能撞倒 \(D\)，但 \(C\) 能撞倒 \(D\)，那么推倒 \(A\) 后 \(D\) 也会被 \(C\) 撞倒。

你可以花费 \(1\) 的代价让某个骨牌高度加 \(1\)。

\(Q\) 次询问，每次询问推倒第 \(L\) 块骨牌，要撞倒第 \(R\) 块骨牌的最小代价。

\(1\le N,Q \le 2\times 10^5\)。

这题一看就大概知道了解法，但不知道为啥在一个脑弹的地方卡了很久，只能看题解了 qwq。

不难发现每个骨牌能撞倒的最右端固定，而继续往右撞的花费就是下一个骨牌的坐标减去当前骨牌撞倒的骨牌中 \(p_i+l_i\) 的最大值。

这玩意其实不难处理，具体看代码。

知道了花费和每次前进的端点，很显然可以用倍增。

时间复杂度 \(O((N+Q)\log N)\)。

Code

// Problem: CF500E New Year Domino
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF500E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n,a[maxn],b[maxn];
int f[maxn][20],dp[maxn][20],maxv[maxn];
int main() {
	scanf("%d",&n);
	for(int i = 1;i <= n;++ i)scanf("%d %d",&a[i],&b[i]);
	int m = log2(n);
	for(int i = n - 1;i;-- i) {
		int cur = i + 1;
		maxv[i] = a[i] + b[i];
		for(;cur&&a[i] + b[i] >= a[cur];cur = f[cur][0])maxv[i] = max(maxv[i] , maxv[cur]);
		f[i][0] = cur;
		dp[i][0] = a[cur] - maxv[i];
	}
	for(int k = 1;k <= m;++ k) {
		for(int i = 1;i <= n;++ i) {
			f[i][k] = f[f[i][k - 1]][k - 1];
			dp[i][k] = dp[i][k - 1] + dp[f[i][k - 1]][k - 1];
		}
	}
	int Q;
	scanf("%d",&Q);
	while(Q --) {
		int l,r;
		scanf("%d %d",&l,&r);
		if(f[l][0] > r) {
			puts("0");
			continue ;
		}
		else {
			int ans = 0;
			for(int k = m;~ k;-- k)
				if(f[l][k]&&f[l][k] <= r)ans += dp[l][k],l = f[l][k];
			printf("%d\n",ans);
		}
	}
	return 0;
}

[CF1251E1]Voting (Easy Version)

有一群选民，你想获得他们全部的选票，对于第 \(i\) 个选民，有着一个跟风值 \(m_i\)，如果有其它不低于 \(m_i\) 个选民已经投票给你，那么他就会跟风一起投票给你。还有着一个贿赂值 \(p_i\)，如果你可以付出 \(p_i\) 个硬币，那么他就会把票投给你。

这种投票是分阶段进行的。例如，现在有五个选民他们的跟风值分别是 \(m_1​=1,m_2​=2,m_3​=2,m_4​=4,m_5​=5\)，然后你可以贿赂第五个选民，然后所有选民就会都投票给你，投票给你的选民变化为：\(5\to1,5\to1,2,3,5\to1,2,3,4,5\)。

计算出最少需要多少个硬币来让所有选民投票给你。

\(1\le n\le 5\times 10^3,0\le m_i\lt n,1\le p_i\le 10^9\)。

莫名感觉题面有点危险（逃

想出了 DP，却卡在了第一步的处理上，甚至还觉得这个 DP 是错误的 qwq。

发现这题支持 \(O(n^2)\) 的算法，而且状态很多，考虑 DP。

首先将选民按 \(m\) 升序排序。设 \(dp(x,p)\) 表示后面已经贿赂了 \(p\) 个选民时，使前 \(x\) 个选民投票的最小花费。

讨论一下当前的情况：

• \(x-1+p \ge m_x\)，那么 \(x\) 可以不花钱，则 \(dp(x,p)=dp(x-1,p)\)。

• 在第 \(x\) 个人身上花钱，则 \(dp(x,p)=dp(x-1,p+1)+p_x\)。

方程不难理解，两者去最小值即可。

至于开始时按 \(m\) 升序排序那一步，我的理解是这样具有决策包容性，\(m\) 升序得到的状态必然包含 \(m\) 乱序的状态，并且只多不少，可以理解一下。

时空复杂度 \(O(n^2)\)。

Code

// Problem: CF1251E1 Voting (Easy Version)
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1251E1
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 5;
typedef long long ll;
const ll INF = 1e18;
ll dp[maxn][maxn];
int n;
struct node {
	int x;
	ll y;
	node() {
		x = y = 0;
	}
	node(int x,ll y):x(x),y(y){}
}a[maxn];
ll DP(int x,int p) {
	if(x == 0)return 0;
	if(dp[x][p] ^ INF)return dp[x][p];
	if(x - 1 + p >= a[x].x)dp[x][p] = min(dp[x][p] , DP(x - 1 , p));
	dp[x][p] = min(dp[x][p] , DP(x - 1 , p + 1) + a[x].y);
	return dp[x][p];
}
void work() {
	scanf("%d",&n);
	for(int i = 1;i <= n;++ i) {
		scanf("%d %lld",&a[i].x,&a[i].y);
	}
	sort(a + 1 , a + 1 + n , [&](const node& p,const node& q) {
		return p.x < q.x;
	});
	for(int i = 1;i <= n;++ i)
		for(int j = 0;j <= n;++ j)
			dp[i][j] = INF;
	printf("%lld\n",DP(n , 0));
	return ;
}
int main() {
	int T;
	std::cin >> T;
	while(T --)work();
	return 0;
}

Hard Version 本来还想写，但已经太晚了，马上开学了，为了调整作息，就先去睡觉了，放到明天再写吧 ~