传送门 https://codeforces.com/contest/1257
A. Two Rival Students
签到.
- Code
- B. Magic Stick
分情况讨论一下即可.
神志不清讨论地很乱
- Code
- C. Dominated Subarray
题意:
给出 \(n\) 个数, 找到长度最短的区间, 满足区间长度大于 \(1\) 且存在一个数其出现次数严格大于其它数.
思路:
显然最终的答案区间两端点为同一个数, 考虑一个这样的区间, 如果其不合法, 说明存在一个答案更优的区间.
并且若那个数出现次数超过 \(2\) 次, 我们选择一个更小的区间使得这个数只出现 \(2\) 次, 此时有两种情况: 一个是合法, 那显然答案更优; 另一个是不合法, 说明答案也可以更优.
就这样归纳一下, 发现答案就是两个相同数的最小间隔.
然而我神智不清, 写了个线段树
- Code
- D. Yet Another Monster Killing Problem
题意:
现在有 \(n\) 只怪, 每只怪有力量 \(a_i\).
同时有 \(n\) 个英雄, 每个英雄有 \(p_i,s_i\) 分别代表力量和耐力.
每一天只能选派一个英雄去打怪兽, 每个英雄最多打 \(s_i\) 只怪, 一个英雄能打败一只怪, 当且仅当其力量不低于怪兽的力量.
一个英雄可以被选派多次.
问最少需要多少天能打败所有的怪兽.
思路:
考虑 \(dp:dp[i]\) 表示打败前 \(i\) 只怪兽最少需要多少天, 显然 \(dp[i]=min\{dp[j]+1\}\)
\(j\) 满足存在一个英雄, 能从 \(j+1\) 打到 \(i\), 显然这个 \(j\) 的位置具有单调性.
发现 \(dp\) 值也是单调不降的, 那么我们就可以找一个最远的 \(j\) 进行转移, 二分即可.
二分的话, 可以对英雄的耐力维护一个后缀最大值, 即 \(maxv[s]\) 表示耐力 \(\geq s\) 的英雄中, 最大的力量为多少; 同时维护怪兽力量的区间最大值, 这里 \(rmq\) 维护即可. 两个判断一下就行.
神志不清写了一年
- Code
- E. The Contest
题意:
给出三个集合, 每个集合里面装了一些数, 这些数的并集为 \(1\)~\(n\) 的排列.
现在可以移动任意一个数从一个集合到另外一个集合.
问最少的移动次数使得 \(1\) 集合中为一个前缀 \(1,\cdots,k\), 然后 \(2\) 集合中 \(k+1,\cdots,p\),\(3\) 集合中 \(p+1,\cdots,n\).(可以有集合为空集).
思路:
考虑枚举 \(1\) 集合中装的前缀的长度, 然后将其余的所有数我们先移到 \(3\) 集合中, 并且给这些数打上标记, 表示删除这些数不消耗额外的次数.
之后我们要操作一些数, 使得 \(3\) 集合中的数为一个后缀.
显然我们对 \(3\) 集合的操作是删掉前面的一些数, 然后填补后面的空格. 假设 \(3\) 集合中的数为 \(p\)~\(n\), 那么我们用 \(pre[i]\) 表示 \(3\) 集合中原来有的数的前缀,\(suf[i]\) 表示后缀空格的数量. 那么显然我们枚举 \(i,i\geq p\), 求出 \(min\{pre[i]-pre[p-1]+suf[i+1]\}\) 即可.
显然 \(p\) 随着枚举 \(1\) 集合前缀个数时在不断增大, 那么直接维护后缀 \(pre[i]+suf[i+1]\) 的最小值即可.
时间复杂度 \(O(n)\). 也可以 \(dp\) 来做,\(dp[i][j]\) 表示第 \(i\) 个数在第 \(j\) 个集合的最小操作次数. 因为分布连续, 直接分情况考虑即可.
然而神志不清, 想了好久都没想清楚
- Code
- F. Make Them Similar
题意:
给出 \(n,n\leq 100\) 个数, 现在定义两个数相似为其二进制 \(1\) 的个数相同.
现在问能否找到一个数 \(x\), 使得这 \(n\) 个数都异或上 \(x\), 并且最终都相似.
\(a_i\leq 2^{30}-1\).
思路:
显然我们要从二进制的每一位来考虑, 但是直接来考虑又显然不行.
注意到二进制位不超过 \(30\), 那么可以考虑 \(meet\ in\ middle\) 的方法: 即折半处理, 预处理出一边, 然后枚举这一边.
预处理一边后随便用个 \(map\) 或哈希一下存储即可.
感觉这个比前几个稍微还简单点?
可能是因为我之前神志不清 hhh
- Code
来源: http://www.bubuko.com/infodetail-3287981.html