A - Glutton Takahashi
给定\(n\)道菜，每道菜要么是甜的（用
sweet表示），要么是咸的（用salty表示）。必须按顺序吃，如果连续吃到\(2\)个甜的菜，就会浑身难受吃不下去了。请问是否能吃完这些菜。
按题意模拟即可，只要前\(n-1\)个元素中有连续的sweet就输出No。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,sweet;
int main(){
cin>>n;
for(int i=1;i<n;i++){
string s;
cin>>s;
if(s=="sweet") sweet++;
else sweet=0;
if(sweet==2){
cout<<"No\n";
return 0;
}
}
cout<<"Yes\n";
return 0;
}
B - Grid Walk
给定一个地图，有些位置有障碍，给定一个起始位置，再给定若干次操作。每次操作给定一个字符表示移动命令：
U向上、D向下、L向左、R向右。对于每个命令，向指定方向移动\(1\)格，如果有障碍物则不移动。输出最后位置。
按题意模拟即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y;
string s[60];
int main(){
cin>>n>>m>>x>>y;
for(int i=1;i<=n;i++){
cin>>s[i];
s[i]=' '+s[i];
}
string t;
cin>>t;
for(auto i:t){
int px=x,py=y;
if(i=='U') x--;
else if(i=='D') x++;
else if(i=='L') y--;
else if(i=='R') y++;
if(x<1||x>n||y<1||y>m||s[x][y]=='#') x=px,y=py;
}
cout<<x<<" "<<y<<"\n";
return 0;
}
C - Minimum Glutton
给定\(n\)道菜，每道菜有自己的甜度\(a_i\)，咸度\(b_i\)。可以顺序随意地吃这些菜，如果中途摄入的总甜度\(>X\)或者 总咸度\(>Y\)就会浑身难受吃不下去了。请问最少吃多少道菜？
为了尽可能快地结束用餐，我们应该考虑两种情况：
- 按甜度从大到小排序，记录下最多吃多少盘不会超标，记为\(a\)。
- 按咸度从大到小排序，记录下最多吃多少盘不会超标，记为\(b\)。
则答案就是\(\min(\max(a,b)+1,n)\)。为什么还要\(+1\)呢？因为\(a,b\)的含义是“最多吃多少盘不会超标”，那么其实应该再多吃一盘才超标的。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct dish{
int x,y;
}a[200010];
int n,x,y,ans=INT_MAX;
signed main(){
cin>>n>>x>>y;
for(int i=1;i<=n;i++) cin>>a[i].x;
for(int i=1;i<=n;i++) cin>>a[i].y;
sort(a+1,a+1+n,[](dish a,dish b){
return a.x>b.x;//按甜度从大到小
});
int sum=0,i;
for(i=1;i<=n;i++){
sum+=a[i].x;
if(sum>x) break;
}
ans=min(ans,i);
sort(a+1,a+1+n,[](dish a,dish b){
return a.y>b.y;
});
sum=0;
for(i=1;i<=n;i++){
sum+=a[i].y;
if(sum>y) break;
}
ans=min(ans,i);
if(ans==n+1) ans=n;
cout<<ans<<"\n";
return 0;
}
D - K-th Nearest
给定数轴上的\(n\)个点\(A_1\sim A_n\)，\(q\)次询问，每次给定一个点\(B\)和一个\(k\)，询问这\(n\)个点中到\(B\)第\(k\)远的点，到\(B\)的距离是多少。
实际上，每次询问的答案，就是满足“\([B-dis,B+dis]\)中，\(A_i\)的个数\(\ge k\)”的最小\(dis\)，所以说可以二分\(dis\)。
判断\([l,r]\)内有多少个\(A_i\)，仍然是一个二分（首先需要将\(A\)从小到大排序）：
- 找到满足\(A_i\ge l\)的最小\(i\)，记为\(x\)。
- 找到满足\(A_i>r\)的最小\(i\)，记为\(y\)。
答案就是\(y-x\)。因为根据定义，满足\(A_i\le r\)的最大\(i\)即为\(y-1\)。而我们的答案就是\(x\)到\(y-1\)之间的元素个数，即为\((y-1)-x+1\ \ =\ \ y-x\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define N 100010
using namespace std;
int n,q,a[N];
bool cmp(int a,int b){return a<b;}
int cntrange(int l,int r){//[l,r]有多少点A
int lp=lower_bound(a+1,a+1+n,l)-a;
int rp=upper_bound(a+1,a+1+n,r)-a-1;
return rp-lp+1;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+1+n,cmp);
while(q--){
int b,k;
cin>>b>>k;
int l=0,r=2e8+10;
while(l<r){
int mid=(l+r)>>1;
if(cntrange(b-mid,b+mid)>=k) r=mid;
else l=mid+1;
}
cout<<l<<"\n";
}
return 0;
}
E - Maximum Glutton
给定\(n\)道菜，每道菜有自己的甜度\(a_i\)，咸度\(b_i\)。可以顺序随意地吃这些菜，如果中途摄入的总甜度\(>X\)或者 总咸度\(>Y\)就会浑身难受吃不下去了。请问最多吃多少道菜？
首先我们可以发现这是一个二位费用的背包问题，每个物品价值都为\(1\)。当然背包得出的最大值\(x\)并不是答案，真正的答案是\(\min(x+1,n)\)，原因见C题。
设计出\(f[i][j][k]\)表示前\(i\)道菜，甜度和咸度的最大限度分别是\(j,k\)，所能吃下的最多数量（即最大价值）。然后就可以像背包一样转移：
\(f[i][j][k]=\begin{cases}
\max(f[i-1][j][k],f[i-1][j-a[i]][k-b[i]]+1)&j\ge a[i]\text{ and }k\ge b[i]\\
f[i-1][j][k]&\text{otherwise}
\end{cases}\)
但是！这道题的\(X,Y\)达到了\(10^5\)，这么设计状态，就算能滚掉第\(1\)维也会超限。
我们已经想到背包了，或许就可以想到“超大背包问题”，即物品体积范围很大、而价值范围很小的背包问题。我们用到了一个技巧来解决这个问题——交换键和值的位置，具体来说：
- \(f[i][j]\)表示前\(i\)个物品，总体积最大为\(j\)的最大价值
变成了 - \(f[i][j]\)表示前\(i\)个物品，总价值正好为\(j\)的最小容量
放在这个题中，我们同样可以这样优化。互换一下键和值，用\(f[i][j][k]\)表示前\(i\)道菜，正好选\(k\)道菜吃（即总价值正好为\(k\)），使得总甜度正好为\(j\)的最小咸度。
注意优化后变成了“正好装满”的背包问题，所以初始化除了\(f[i][0][0]=0\)以外都要置为\(+\infty\)。
转移方程：
\(f[i][j][k]=\begin{cases}
\min(f[i-1][j][k],f[i-1][j-a[i]][k-1]+b[i])&j\ge a[i]\\
f[i-1][j][k]&\text{otherwise}
\end{cases}\)
转移完成后，将满足\(f[n][j][k]\le y\)的最大\(k\)记为\(x\)，答案就是\(\min(x+1,n)\)。
同样这里的\(f\)可以滚掉第\(1\)维（注意倒序枚举），我没弄(^^;
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define N 90
#define W 10010
using namespace std;
int n,a[N],b[N],x,y;
int f[N][W][N];
signed main(){
cin>>n>>x>>y;
for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
memset(f,0x3f,sizeof f);
for(int i=0;i<=n;i++) f[i][0][0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=x;j++){
for(int k=1;k<=n;k++){
if(j>=a[i]) f[i][j][k]=min(f[i-1][j][k],f[i-1][j-a[i]][k-1]+b[i]);
else f[i][j][k]=f[i-1][j][k];
}
}
}
for(int k=n;k;k--){
for(int j=1;j<=x;j++){
if(f[n][j][k]<=y){
cout<<min(k+1,n);
return 0;
}
}
}
cout<<1;
return 0;
}
F - Range Connect MST
给定\(n+q\)个节点，一开始点之间都没有边。接下来对于\(i\in[1,q]\)，执行下面的操作：
- 对于\(j\in[l_i,r_i]\)，在\(i+n\)和\(j\)之间连一条权值为\(c_i\)的边。
所有操作完成后，如果该图不连通，输出
-1，否则请输出它的最小生成树权值之和。
保证\(1\le l_i\le r_i\le n\)。
如果暴力模拟的话会超时，考虑更好的做法。
我们为了方便，把\([n+1,n+q]\)这\(q\)个节点叫做红色节点，把\([1,n]\)这\(n\)个节点叫做蓝色节点。
这道题的突破口，就是“对于每个\(i\)处理完后，互相连通的蓝色点，编号都是连续的”。
那么很容易想到一个贪心的思路：把红色节点按照\(c\)的值从小到大排序，然后把连通的蓝色点写成区间的形式（比如初始状态就是\([1,1],[2,2],[3,3],[4,4],[5,5]\)），考虑某个红色节点时，就看这个红色节点的\([l,r]\)跨越了多少个区间，跨越多少个区间，该节点就需要用去多少条边。然后把跨越的所有区间合并成一个大区间。
用某种数据结构，动态维护每个区间即可。
这里使用set，存储每个区间的右端点。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define N 200010
using namespace std;
int n,q,ans;
struct bl{
int l,r,c;
}a[N];
bool cmp(bl a,bl b){return a.c<b.c;}
set<int> s;
signed main(){
cin>>n>>q;
for(int i=1;i<=n;i++) s.insert(i);
for(int i=1;i<=q;i++)
cin>>a[i].l>>a[i].r>>a[i].c;
sort(a+1,a+1+q,cmp);
for(int i=1;i<=q;i++){
auto lp=s.lower_bound(a[i].l);
int cnt=1;
for(auto it=lp;it!=s.end()&&(*it)<a[i].r;it=s.erase(it))
cnt++;
ans+=cnt*a[i].c;
}
if(s.size()==1) cout<<ans<<"\n";
else cout<<"-1\n";
return 0;
}
花\(34\)分钟打到了D题，然后对着E磕了半天没做出来……想到超大背包了，但没有提炼出“键值交换”的精髓来，当时想的做法挺离谱的（汗）。
F题只是过了一眼，完全没想到其实思路还是挺简单的，代码也很短。如果调整一下做题策略，或许剩下\(1\)个小时不至于对着屏幕红温（笑）。