A.Yet Another Promotion
算法本质
模拟、思维
题目大意
食物商店只卖2次土豆：
- 第一次A元/斤，每买m斤送1斤
- 第二次B元/斤
求2次合计购买n斤土豆的最低花费。
思路推演
这类题目，分类讨论模拟，最好的方法之一就是：
将可能是最便宜的方法列出，然后都求出，取min值。
可以简单分为三类：
仅买第一次
仅买第二次
混合买
B.Fedya and Array
算法本质
思维
题目大意
给定你a b两个数，需要你给定一个环形数组，要求：
- 极大值（局部最大值）之和为a
- 极小值之和为b
- 相邻元素之差<=1
- 尽可能短
思路推演
先手动玩一下数组。
随机创造一个数组，比如最基础的波浪形，然后改变一下其形状。
发现在差值固定为1时，改变形状只是会引起极大值、极小值之和此消彼长。
于是尝试直接做到极端——保留一个为a的极大值、一个为b的极小值。
发现可行，而且是最好实现的。
C.Dora and Search
算法本质
思维
题目大意
给定一个排列，找到一个区间l r，使得这个区间中的最大、小值都不在l r下标上。
可能有多解，找到其一即可（不可返回-1）。
思路推演
首先肯定想，要是1 n都不在边缘，那岂不是直接找到了。
考虑1 n在边缘的情况：
- 如果
1在边缘，则直接不管这个点，然后看2 n - 如果
n在边缘，则丢这个点，看1 n-1
哦，递推呀。
写成双指针即可。
D.Moscow Gorillas
算法本质
思维
题目大意
给出2个排列：p q
计算满足条件的l r数目：
MEX(p[l~r]) == MEX(q[l~r])
思路推演
一看题还是不知所措，那就上手玩一下把。
看能不能找一些东西，合并简算。
MEX，那岂不是没有1就全部为1，那先算l r都取不了p q的1值的情况。
那剩下的情况全是需要取1的，欸，这个时候考虑一下不取2的情况……
递推思考，同C题一样的，只是其中情况稍微复杂度一点。
最后实际表现出来的就是，分别计算MEX值为1、2、……、n+1的情况即可。
E.Velepin and Marketing
算法本质
思维
题目大意（改）
将n个人分配到若干房间，保证每个房间至少一人。对于第i人，当其所在房间人数>=ai时，他会感到安全。
下面给出m次询问，每次询问会给出具体的房间数，请问最多可以使得多少人感到安全。
n、ai、m、房间数<=3e5
思路推演
通过查看题目的范围，可以很明确的发现，这种题最经典的流程是：预处理a[]数据，使得之后每次查询可以log级别得到结果。
但同时请注意房间数<=3e5这个条件，这说明是有可能求出全部情况然后打表输出的——通常是房间数x的答案可以借助小于x的答案。
随后找到两个限制条件：
- 房间至少一人
- 使得感到安全的人尽量多
通过手动模拟了一会，可以发现，我们优先满足房间至少一人这个条件，思考会方便很多。
继续模拟思考找规律，发现目前的条件不足以让我们直接得到答案，所以想到了二分——二分可以先假设一个信息，使得手中信息+1。
于是开始尝试思考：现在目标是判断，在当前情况下能否满足x个人可以获得安全感。
注意，这里并没有确认用二分做，只是有可能。
同时这里有漏掉正解的可能，从二分的角度去思考也可以帮助我们理解。
思考单调性——满足。
再转过头回顾大局，解题的方向就只有2个了，一是二分，二是找到不同房间数答案之间的关联打表做。
做题要注意大局观
思路推演 - 二分
要求人数最多思路推演即人的收益都一样，但是成本ai不同，所以先按照成本排序，优先处理ai小的。
已经要满足前x人的需求，则后面n-x人可以视作永远无法满足的人，结合优先铺满房间的思路，把这些人先都拿来铺房间。
如果房间能够铺满，那就很简单了，把房间铺满后，剩下的人（包括前x个人）都放在一个房间，看房间人数是否可以超过a[x]即可。
重点在于无法铺满的情况，首先能铺多少是多少，然后回过头来看，前x个人能否在剩下的y个房间中满足。
我们都知道，想要用少的人办多的事，先用成本较低的人，于是有了下面的思考：
对于排序后的a[]，形成一个组的概念。
将ai加入组中，当组的元素个数==ai时，增加一个新组。
比如[1,2,3,3,4,5,7]就可以分为3个组：[1] [2,3,3] [4,5,7] （其中最后一个组不完备）- 前
x个人形成的完备组数<y时
则肯定是无法完成的。 - 前
x个人形成的完备组数>=y时
将靠后多出的组全部加入第y组，查看第y是否能满足所有人（第x个人）。（贪心思维）
至此二分的做法已完成。
思路推演 - 打表
这里的打表并非利用上面的关系来做，而是更加广义一点。
我们可以逐个探讨，当我们想要强制保证前x个人可以被满足的时候，最多可以有多少个房间。
于是先设：
f[x]：在仅有前x个人且满足他们的前提下，最多放置房间数 （注意f[]可能存在无解情况）
g[x]：在仅有前x个人 的前提下，最多放置房间数- 当
ar[x] <= x则有解（全部放一起就是其中一个解）
其转移公式f[x] = g[x-ar[x]] + 1，
理解为g[x-ar[x]]的房间数 + 后面ar[x]个人一起组成的一个房间，其中g[x-ar[x]]部分人没有被满足的可以放在后面那个房间。
此时前面有f[x]个房间，还可以找来n-x个人一人一间，所以可以占f[x]+n-x个房间。 - 当
ar[x] > x则无解
但是又要强制保证前x人可以被满足，于是我们凑前ar[x]到第一房间，剩下的人一人一间，可以占n-ar[x]+1个房间。
同时记得维护g[x] = max(f[x], g[x-1])。
ac核心代码 - 二分
头文件、宏定义、快读模板、常见变量、常见变量等略。
struct Person
{
int id, rank; //小组下标、组内排名
};
Person per[maxn]; //pos为主键
int group[maxn], pre[maxn]; //小组下标(0开始)-->小组大小
bool judge(int x, int room)
{
int y=n-x; //有y个人去铺房间
if (y>=room) //能铺满
return y-room+1+x >= ar[x]; //剩下的人挤一起就好
int zu=per[x].id; //zu表示可以生产的完备组
if (zu-(per[x].rank != group[per[x].id]) < room-y) //完备组数<剩下的房间，直接完蛋
return 0;
else
return x - pre[room-y] + group[room-y] >= ar[x];
}
inline void solve()
{
//init
cin>>n;
rep(i,1,n) cin>>ar[i];
sort(ar+1, ar+1+n);
//cal 预处理
int cnt=1;
for (int i=1; i<=n; i++)
{
group[cnt]++;
per[i].id = cnt;
per[i].rank = group[cnt];
if (group[cnt] == ar[i])
cnt++;
}
for (int i=1; i<=cnt; i++)
pre[i] = pre[i-1] + group[i];
//cal
int q;
cin>>q;
while (q--)
{
int x;
cin>>x;
int l=0, r=n;
int res=l;
while (l<=r)
{
int mid=(l+r)/2;
if (judge(mid, x))
{
res = mid;
l = mid+1;
}
else
r = mid-1;
}
cout<<res<<endl;
}
return;
}ac核心代码 - 打表
头文件、宏定义、快读模板、常见变量、常见变量等略。
int f[maxn], g[maxn], ans[maxn];
inline void solve()
{
//init
cin>>n;
rep(i,1,n) cin>>ar[i];
sort(ar+1, ar+1+n);
//cal
f[0] = 0;
for (int i=1; i<=n; i++)
{
if (ar[i] <= i) //说明有解
{
f[i] = g[i-ar[i]] + 1;
ans[ f[i]+n-i ] = max(ans[ f[i]+n-i ], i);
}
else
ans[ n-ar[i]+1 ] = max(ans[ n-ar[i]+1 ], i);
g[i] = max(f[i], g[i-1]);
}
for (int i=n-1; i>=1; i--) //补全空解
ans[i] = max(ans[i], ans[i+1]);
//out
int q, x;
cin>>q;
while (q--)
{
cin>>x;
cout<<ans[x]<<endl;
}
return;
}
评论 (0)