${\color{Green} \mathrm{Problem\ 1 :选数 }} $
签到题,一眼二分,但是打模板时死循环了:
while(L<R){
int mid=(L+R)>>1;
if(check(mid)) L=mid;
else R=mid+1;
}
后来发现 +1
要写在 check
通过的地方,不然容易 mid
值永远不变。
while(L<R){
int mid=(L+R)>>1;
if(check(mid)) L=mid+1;
else R=mid;
}
二分模板不够熟,需要多打。
${\color{White} \mathrm{}} $
${\color{White} \mathrm{}} $
${\color{White} \mathrm{}} $
${\color{Green} \mathrm{Problem\ 2 :搬砖 }} $
乍一看像是01背包的变种,只要改一下内层循环的范围就行,于是便有了开始的代码:
#include <bits/stdc++.h>
using namespace std;
struct Node{
int w;
int c;
}A[1005];
int N,M,DP[40005],ans;
int main()
{
scanf("%d",&N);
for(int i=1;i<=N;i++){
scanf("%d%d",&A[i].w,&A[i].c);
M=max(M,A[i].c*2);
}sort(A+1,A+1+N,[](Node a,Node b){return a.c<b.c;});
for(int i=1;i<=N;i++){
for(int j=A[i].w+A[i].c;j>=A[i].w;j--){
DP[j]=max(DP[j],DP[j-A[i].w]+A[i].c);
}
}
for(int i=1;i<=M;i++){
ans=max(ans,DP[i]);
}printf("%d",ans);
return 0;
}
后来样例和大样例都过了,准备打 T3
,听老师说,他到现在为止没看到一个 T2
正确的排序,于是慌慌又张张,再检查一遍,发现物品的顺序要满足 j
的最大范围递增,于是把排序规则改成了 a.w+a.c<b.w+b.c
,把 j
的初值改成了 min(A[i].w+A[i].c,M)
,终于过了。
${\color{White} \mathrm{}} $
${\color{White} \mathrm{}} $
${\color{White} \mathrm{}} $
${\color{Green} \mathrm{Problem\ 3 :语文1 }} $
下次是不是有语文2
看到题目中的这句话,立马明白是线段树。
但是区间排序怎么实现啊喂?!
赛时没想出来,打了暴力,后来才知道,需要建 26
棵线段树来维护这个字符串。线段树变化真的多。
要多打线段树题QwQ。
${\color{White} \mathrm{}} $
${\color{White} \mathrm{}} $
${\color{White} \mathrm{}} $
${\color{Green} \mathrm{Problem\ 4 :旅行者 }} $
思路考场上没想出来,一直想不到可以把编号二进制分组。打了一个 36
分的暴力,吸氧 63
分。
后来知道了思路,写代码时最后一个点一直 TLE
,后来用 bitset
代替 bool
才卡过。
${\color{White} \mathrm{}} $
${\color{White} \mathrm{}} $
${\color{White} \mathrm{}} $
总结
期望(不开 O2
):\(100+100+30+20=250\)
实际(不开 O2
):\(100+100+21+36=257\)
实际( \({\color{White} \mathrm{\ \!}}\) 开 ${\color{White} \mathrm{\ !}} $ O2
):\(100+100+21+63=284\)
这次比赛的分数还是比较满意的。但是时间没有规划好,导致最后一分钟才写完最后一题的暴力,大样例测完只剩几十秒了。以后要做好时间分配,正解不要想太久。
标签:color,Day5,mid,暑期,int,100,White,复盘,mathrm From: https://www.cnblogs.com/Sundar-2022/p/18031310