首页 > 其他分享 >贪心选讲-几个套路

贪心选讲-几个套路

时间:2024-04-10 12:22:33浏览次数:26  
标签:10 le 宝箱 套路 选讲 times 给定 texttt 贪心


凸性


CF1428E Carrots for Rabbits

给 \(n\) 个胡萝卜,再 \(n-k\) 次选出一个胡萝卜切一刀成俩,最小化最后所有胡萝卜平方和.


CF1661F Teleporters

给定数轴上 \(n\) 个点和 \(m\) ,要再建立若干点,使得存在一条路径 \(a_1\ldots a_n\) 的 \(\sum {(a_i-a_{i-1})}^2\le m\) .求最少再建几个点.
\(n\le 2\times 10^5,a_i\le 10^9\)


CF1344D Résumé Review

好像是咱们上面那个 Teleporters 啊.凸的-二分就做完了.


操作策略


1400E Clear the Multiset

给定 \(1\ldots n\) 每个数的个数 \(a\) ,每次给一个区间个数减1或对一个数减去任意,求清空次数. \(n\le 5000, a_i\le 10^9\)


1537E2. Erase and Extend (Hard Version)

给定一个字符串,可以任意多次删掉末尾字符或者把当前字符串复制一份接在后面,求能得到的字典序最小的,长度恰好为 \(k\) 的字符串.
\(n,k\le 5\times 10^5\)


CF37E Trial for Chief

给一个 \(n\times m\) 黑白两色的网格图,要全染白,每次把一个连续颜色块反色,求最少次数. \(n,m\le 50\)


无敌构造


CF1599A Weights

给定序列 \(a_{1\ldots n}\) 和由 \(\texttt{LR}\) 组成的长 \(n\) 字符串 \(S\) ,两个集合 \(L,R\) 初始为空,要求给一个方案使得我们第 \(i\) 次选择一个数添加进去后集合 \(S_i\) 更大.
\(n\le 2\times 10^5,a_i\le 10^9\)


CF1158D Winding polygonal line

给定平面上 \(n\) 个点和 \(\texttt{LR}\) 构成的长 \(n-2\) 的字符串,求一条不自交路径经过每一个点一次,且第 \(i+1\) 个点是在 \(i-1\) 到 \(i\) 的基础上忘 \(s_i\) (左或右)的方向拐的.
\(n\le 2000\)


上来排序


CF1601D Difficult Mountain

\(n\) 个人相约去爬山.
山的初始攀登难度为 \(d\) .
每位登山者有两个属性:技巧 \(s\) 和整洁度 \(a\) .

技巧为 \(s\) 的登山者能登上攀登难度为 \(p\) 的山当且仅当 \(p\leq s\) .
在一位整洁度为 \(a\) 的登山者登上攀登难度为 \(p\) 的山后,山的攀登难度会变为 \(\max(p,a)\) .

请给这些登山者指定一个爬山的先后顺序,最大化登上山的人数.
如果轮到一位登山者时他能登上山,则他一定会选择登山.
\(n\le 5\times 10^5,d,s_i,a_i\le 10^9\)


CF1380G Circular Dungeon

简单题

在游戏中,有 \(n\) 个排列在环上的房间,第 \(i\) 个房间只能到达第 \(i+1\) 个房间(特别地,第 \(n\) 个房间只能到达第 \(1\) 个房间).

同时有 \(n\) 个宝箱,第 \(i\) 个宝箱的价值是 \(c_i\) ,其中恰好有 \(k\) 个宝箱是假宝箱,其余均为真宝箱,每个房间有且仅放置一个宝箱.

玩家等概率地从 \(n\) 个房间中选取一个房间开始移动,如果当前房间有真宝箱,他将获得此宝箱的价值,否则立刻结束游戏.最后获得的总收益等于之前收集的宝箱的总价值.

对于每一个 \(k\in[1,n]\) ,你可以决定宝箱的排列顺序和宝箱的真假,使玩家收益的期望值最小,请求出最小的期望值 \(\pmod {998244353}\) .
\(n\le 3\times 10^5\)


次数忽悠


CF725E Too Much Money

给定常数 \(c\) 和 \(n\) 个整数,每个数只能用一次,求加到 \(c\) 的一个方案.求法是每次选择不超过 \(c\) 的最大的加进去,那么现在让你再添加任意多个数hack它,或者判断hack不掉,最小化添加的数的和.
\(n,c\le 2\times 10^5\)


CF1685C Bring Balance

给定一个括号序列,每次可以翻转一个区间,求最少的操作次数使得括号串合法.保证左右括号数量相等.
\(n\le 2\times 10^5\)


一摞序列


CF578E Walking!

给定长度为 \(n\) 的01串 \(s\) ,构造一个排列使得 \(s_{p_i}\ne s_{p_{i+1}}\) ,最小化排列的逆序对个数,输出方案. \(n\le 10^5\)


「JOI 2013 Final」T4 JOIOI 塔

给定 \(\texttt{J},\texttt{O},\texttt{I}\) 三个字母组成的字符串 \(S\) ,从中拿出若干的不交的 \(\texttt{JOI}\) 和, \(\texttt{IOI}\) 子序列,最大化拿的数量总和.
不交是指不能选同一个字符两遍,但 \(IIOOII\) 这种是可以取出来两个的,就是说可以跨越.
\(\vert S\vert \le 10^6\)


奇思妙想


CF1658F Juju and Binary String

给定一个长 \(n\) 01串,要从中选取若干个不相交子串,使得:

  • 所有子串长度加起来为 \(m\)
  • 所有子串拼起来后1的个数占总长的比与原字符串相等.
    最小化你选的子串个数.输出方案.

CF1672H Zigu Zagu

给定一个长 \(n\) 01串, \(q\) 次询问对于一个区间,若你每次可以删除这个区间的一个01相间子区间(没有00或11),那么最少要删多少次.
\(n,q\le 2\times 10^5\)

标签:10,le,宝箱,套路,选讲,times,给定,texttt,贪心
From: https://www.cnblogs.com/WJChp/p/18125766

相关文章

  • Day34代码随想录(1刷)贪心
    435.无重叠区间给定一个区间的集合 intervals ,其中 intervals[i]=[starti,endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。示例1:输入:intervals=[[1,2],[2,3],[3,4],[1,3]]输出:1解释:移除[1,3]后,剩下的区间没有重叠。示例2:输入:in......
  • 三种算法实例(二分查找算法、插入排序算法、贪心算法)
    当我们听到“算法”这个词时,很自然地会想到数学。然而实际上,许多算法并不涉及复杂数学,而是更多地依赖基本逻辑,这些逻辑在我们的日常生活中处处可见。在正式探讨算法之前,有一个有趣的事实值得分享:你已经在不知不觉中学会了许多算法,并习惯将它们应用到日常生活中了。下面我将举......
  • 贪心算法
    1、基本概念贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法。贪心算法解决问题的策略是:做出选择时,每次都选择对当前状态最优的解,而不考虑整个问题的解空间。它通常用来解决最优化问题,如最小生成树、哈夫曼编......
  • 贪心算法|1005.K次取反后最大化的数组和
    力扣题目链接classSolution{staticboolcmp(inta,intb){returnabs(a)>abs(b);}public:intlargestSumAfterKNegations(vector<int>&A,intK){sort(A.begin(),A.end(),cmp);//第一步for(inti=0;i<A.size......
  • 贪心算法|53.最大子序和
    力扣题目链接classSolution{public:intmaxSubArray(vector<int>&nums){intresult=INT32_MIN;intcount=0;for(inti=0;i<nums.size();i++){count+=nums[i];if(count>result){......
  • 贪心算法|376.摆动序列
    力扣题目链接classSolution{public:intwiggleMaxLength(vector<int>&nums){if(nums.size()<=1)returnnums.size();intcurDiff=0;intpreDiff=0;intresult=1;for(inti=0;i<nums.size(......
  • 【每日一题】补档 CF730I. Olympiad in Programming and Sports | 反悔贪心 | 困难
    题目内容原题链接给定nnn个学生,第iii个学生的编程能力为......
  • 贪心算法——多机调度问题
    问题描述下面用一道2013上半年软件设计师的软考题来说明这个问题。   设有M台完全相同的机器运行N个独立的任务(任务不可分割),运行任务i所需要的时间为,要求确定一个调度方案,使得完成所有任务所需要的时间最短,任务运行时独占机器。   这里要求定义的变量如......
  • 代码随想录 Day34 贪心算法 1005.K次取反后最大化的数组和 134. 加油站 135. 分发糖果
    1005.K次取反后最大化的数组和 classSolution{public:intlargestSumAfterKNegations(vector<int>&nums,intk){sort(nums.begin(),nums.end());intsum=0;inti=0;while(k>0){nums[i]=0-nums[i]......
  • 蓝桥备赛——贪心(2)
    题干 我的代码dic={'*':1,'o':0}s1=input()s2=input()s1=list(s1)s2=list(s2)num1=''num2=''foriins1:#print(i)num1=num1+str(dic[i])forjins2:num2+=str(dic[j])#print(num1)#print(num2)num1=l......