首页 > 其他分享 >暑期集训 Day5 —— 模拟赛复盘

暑期集训 Day5 —— 模拟赛复盘

时间:2024-02-24 17:25:11浏览次数:21  
标签:color Day5 mid 暑期 int 100 White 复盘 mathrm





${\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

相关文章

  • 暑期集训 Day9 —— 模拟赛复盘
    ${\color{Green}\mathrm{Problem\1:大河的序列}}$巨思维...其实只需要输出序列max即可。死因:\({\tiny去你的}\)快速幂intFast_power(intbase,intpower,intmod){longlongres=1;while(power){if(power&1){res......
  • 暑期集训 Day10 —— 模拟赛复盘
    ${\color{Green}\mathrm{Problem\0:water}}$题如其名,可以用单调队列做,但是数据范围直接暴力枚举每一高度就行。最不会打错的,还是暴力,所以用暴力。${\color{White}\mathrm{}}$${\color{White}\mathrm{}}$${\color{White}\mathrm{}}$${\color{Green}\mathr......
  • 暑期集训 Day12 —— 模拟赛复盘
    ${\color{Green}\mathrm{Problem\1:Subarray}}$Map.${\color{Green}\mathrm{Problem\2:小z玩游戏}}$数学题YYDS。我的做法是:首先枚举x的所有二进制位,找里面的\(1\),由于y要比x小,于是我们可以把y的当前位变为\(0\),然后后面的位从全0到全1,用前缀和统......
  • 暑期集训 Day11 —— 模拟赛复盘
    ${\color{Green}\mathrm{Problem\1:Subarray}}$签到失败...直接二进制分组,找出所有二进制位=0的方法。死因:二进制分组没想出来...${\color{White}\mathrm{}}$${\color{White}\mathrm{}}$${\color{White}\mathrm{}}$${\color{Green}\mathrm{Problem\2:......
  • 代码随想录 day59 两个字符串的删除操作 编辑距离
    两个字符串的删除操作两种思路如果是以最长公共子序列去理解求出这个子序列长度然后原长减一下就行如果是直接正面求解就是如下解法递推式很好理解初始化意思是当一个串为0长度时需要操作另一个字符串长度次也就是直接赋予下标编辑距离dp[i-1][j-1]+1意......
  • winter week5 day5
    2024牛客寒假算法基础集训营6A思路:暴力宇宙的终结查看代码#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong//#defineint__int128#definedoublelongdoubletypedefpair<int,int>PII;typedefpair<string,int>PSI;typedefpair<string,stri......
  • 代码随想录 day58 判断子序列 不同的子序列
    判断子序列dp[i][j]表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]。if(s[i-1]==t[j-1])t中找到了一个字符在s中也出现了if(s[i-1]!=t[j-1])相当于t要删除元素,继续匹配不同的子序列dp[i][j]:以i-1为结尾的s子序列中......
  • 代码随想录 day57 最长公共子序列 不相交的线 最大子数组和
    最长公共子序列dp[i][j]:长度为[0,i-1]的字符串text1与长度为[0,j-1]的字符串text2的最长公共子序列为dp[i][j]主要就是两大情况:text1[i-1]与text2[j-1]相同,text1[i-1]与text2[j-1]不相同如果text1[i-1]与text2[j-1]相同,那么找到了一个公共元素,所以dp......
  • 代码随想录 day56 最长递增子序列 最长连续递增序列 最长重复子数组
    最长递增子序列dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度状态转移方程的含义:位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列+1的最大值。最长连续递增序列dp[i]:以下标i为结尾的连续递增的子序列长度为dp[i]。如果nums[i]>nums[i-1......
  • Codeforces Round 928 (Div. 4) (小白的复盘)
    A.VladandtheBestofFive思路:给你一个长度字符串只包含A和B输出最多的字符解法:按题意来Code:#include<bits/stdc++.h>usingnamespacestd;intmain(){intt;cin>>t;while(t--){strings;cin>>s;intcnt=0;fo......