Preface
又是颓废的一天！
Content
[CF1251E2]Voting(Hard Version)
一共有 /(n/) 个选民，你可以付出 /(p_i/) 的代价让第 /(i/) 个选民为你投票，或者，在为你投票的人数达到 /(m_i/) 时，他会主动为你投票而不用你付出任何代价。
问得到所有选民投票的最小代价。
/(1/le n /le 2/times 10^5,1/le p_i/le 10^9,0/le m_i/lt n/)。
神仙贪心，思路难想，代码也难理解。
这道题里肯定就不能延续 Easy Version 的 DP 了，那这个问题大概率就是贪心。
首先要发现若干个性质：
-
如果已经确定要花钱收买一些人，那么肯定是在一开始就收买他们。（这点一定要记牢，我们接下来贿赂的人并不是按处理顺序，而是一开始就先贿赂好）
-
基于 Easy Version 的思路，把 /(m/) 升序排序，那么处理 /(m_i=x/) 时，/(m=1/sim x-1/) 的人一定都已经投了票，否则一定更劣。至于是收买还是跟风我们不知道，也不需要知道。
性质 1 不难理解，至于性质 2，我的理解是：这是基于性质 1 的推断。
当我们处理到 /(m_i=x/) 的时候，肯定是希望这些人尽可能地跟风，减少花费。
那这就要求已经投过的人尽量地多。
如果 /(m_i/) 的人无法跟风，那 /(m/gt m_i=x/) 的人肯定更没法跟风。
所以只能考虑 /(m/lt m_i=x/) 的人，先让他们都投了，如果此时还没法让 /(m_i/) 跟风，那就只能在 /(m_i/ge x/) 的人里选一些贿赂。
还是要记住，我们贿赂的这些人是在一开始就贿赂了的。
综上，设计出一个贪心算法：
用 std::vector 存储 /(m_i/) 每种取值对应的 /(p_i/)。
倒序遍历 /(0/sim n-1/)，如果后面买的人加上前面所有人的数量仍然小于当前的 /(m/)，就从后面没买的人里选择若干个贿赂。
时间复杂度 /(O(N/log N)/)，描述得很乱，建议参考代码。
Code
// Problem: CF1251E2 Voting (Hard Version)
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1251E2
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int maxn = 2e5 + 5;
typedef long long ll;
int n;
vector<ll> G[maxn];
multiset<ll> s;
void work() {
scanf("%d",&n);
for(int i = 0;i < n;++ i)G[i].clear();
s.clear();
for(int i = 1;i <= n;++ i) {
int x;
ll y;
scanf("%d %lld",&x,&y);
G[x].pb(y);
}
int tot = n,cur = 0;
//cur:当前买了多少个
//tot:前面已经有多少人投了
ll ans = 0;
for(int i = n - 1;~ i;-- i) {
if(G[i].empty())continue ;
tot -= G[i].size();
for(auto& v : G[i]) {
s.insert(v);
}
for(;cur < i - tot;++ cur) {
ans += *s.begin();
s.erase(s.begin());
}
}
printf("%lld/n",ans);
return ;
}
int main() {
int T;
scanf("%d",&T);
while(T --)work();
return 0;
}
[CF853C]Boredom
调了 /(/infin/) 年调不出来，心态爆炸，于是直接对着 7KByte 大佬的题解写，虽然有些地方无法理解，但我不管，摆烂了，不写题解，有兴趣可以看看 7KByte 大佬的题解。只放代码。
Code
// Problem: CF853C Boredom
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF853C
// 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 = 2e5 + 5;
struct query {
int x,y,l,r,id,v;
query() {
x = y = l = r = id = v = 0;
}
query(int x,int l,int r,int id,int v):x(x),l(l),r(r),id(id),v(v){}
}Q[maxn];
typedef long long ll;
ll ans[maxn];
int c[maxn],a[maxn];
int n,m;
int lowbit(int x) {
return x & -x;
}
void add(int x,int y) {
for(;x <= n;x += lowbit(x))c[x] += y;
return ;
}
int Query(int x) {
int ans = 0;
for(;x;x -= lowbit(x))ans += c[x];
return ans;
}
int b[maxn];
void rev() {
for(int i = 1;i <= n;++ i)b[a[i]] = i;
for(int i = 1;i <= n;++ i)a[i] = b[i];
for(int i = 1;i <= m;++ i) {
int x = Q[i].x,y = Q[i].y;
Q[i].x = n + 1 - Q[i].r;
Q[i].y = n + 1 - Q[i].l;
Q[i].l = x;
Q[i].r = y;
}
return ;
}
void calc() {
sort(Q + 1 , Q + 1 + m , [&](const query& p,const query& q) {
return p.l < q.l;
});
memset(c , 0 , sizeof(c));
for(int i = 1,j = 1;i <= m;++ i) {
for(;j < Q[i].l;++ j) {
add(a[j] , 1);
}
int cur = Query(Q[i].x - 1);
ans[Q[i].id] -= 1ll * (j - 1) * (j - 2) / 2 - 1ll * cur * (cur - 1) / 2ll;
}
return ;
}
int main() {
scanf("%d %d",&n,&m);
for(int i = 1;i <= n;++ i)scanf("%d",&a[i]);
for(int i = 1;i <= m;++ i) {
scanf("%d %d %d %d",&Q[i].l,&Q[i].x,&Q[i].r,&Q[i].y);
Q[i].id = i;
ans[i] = 1ll * n * (n - 1) / 2ll;
}
calc();
rev();
calc();
rev();
calc();
rev();
calc();
for(int i = 1;i <= m;++ i)printf("%lld/n",ans[i]);
return 0;
}
[CF768D]Jon and Orbs
无数个物品，种类有 /(N/) 种，每天可以随机取其中一个。
/(Q/) 次询问，询问将 /(N/) 种物品都取到的概率不小于 /(/frac{p}{2000}/) 的最小天数。
/(1 /le N,Q,p /le 10^3/)。
简单题，就是洛谷翻译的题面让我晕了好久。
设 /(f(i,j)/) 表示 /(i/) 天取到 /(j/) 种物品的概率。
初始状态：/(f(0,0)=1/)。
状态转移方程：/(f(i,j)=f(i-1,j)/times /frac{j}{n}+f(i-1,j-1)/times /frac{n-j+1}{n}/)。
在 /(N,p/) 均取极值的情况下，实测得出约为 /(7500/)，数组开 /(10^4/times 10^3/) 即可。
每次询问直接暴力查找就行。
Code
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/279672.html