2022.8.8 心态爆炸记录
2022/8/9 23:22:47
本文主要是介绍2022.8.8 心态爆炸记录,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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
这篇关于2022.8.8 心态爆炸记录的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-25初学者必备:订单系统资料详解与实操教程
- 2024-12-24内网穿透资料入门教程
- 2024-12-24微服务资料入门指南
- 2024-12-24微信支付系统资料入门教程
- 2024-12-24微信支付资料详解:新手入门指南
- 2024-12-24Hbase资料:新手入门教程
- 2024-12-24Java部署资料
- 2024-12-24Java订单系统资料:新手入门教程
- 2024-12-24Java分布式资料入门教程
- 2024-12-24Java监控系统资料详解与入门教程