最新要闻
- 每日看点!大过年的临时工玩呢 AMD又搞了个乌龙:锐龙7000X3D不能超频
- 天天简讯:彻底离开中国制造不现实 未来苹果将有25%产品来自印度
- 世界关注:“终极功率半导体”获突破性进展!金刚石有望成为终极半导体材料
- 每日动态!NASA第一架电动飞机即将上天 官宣至今已过去7年
- 世界实时:全球最高安全标准 我国自研第三代核电华龙一号稳步推进:1台年发电100亿度
- 天天日报丨RTX 4060 Ti性能、价格逼近RTX 3070 网友质疑:升级图啥
- steam春节特卖:11款热卖大作 部分游戏低至2折
- 全球视点!猪肉没有以前香了 我们的餐桌已被洋猪肉占据 鲜香早已不复当年
- 天天亮点!马斯克为“特斯拉私有化推文案”辩护:本可通过出售SpaceX的股份完成融资
- 环球快报:阿里云盘TV版上线 电视上直接看网盘里的大片
- 中科院研发新一代“电力银行”:充满可供20万人用一天
- 载人登月巨无霸 长征九号重型火箭将于2035年前后首飞
- 天天实时:国产2TB PCIe 4.0 SSD只要749元:搭载长江存储TLC颗粒 京东自营5年质保
- 当前报道:俄罗斯黑客攻破《暗黑破坏神4》测试版 自己开私服
- 世界头条:猫人石墨烯抗菌男士内裤三条装下单9折 29元
- AMD官方确认:锐龙7000X3D系列将支持超频
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
2023牛客寒假算法基础集训营1 个人题解(ACDHKL)
A.World Final? World Cup! (I)
题意:
给10场比赛的点球输赢情况,奇数为A队点球,偶数为B队点球
思路:
用两个变量x,y来分别存A队当前赢的场次和B队当前赢的场次
然后就就扫一遍01字符串,如果为当前为奇数且为"1",x++,当前为偶数且为"1",y++
(资料图)
这里最主要的是判断是否当前可以直接终结比赛(后面比赛打不打没有意义)
相当于就算后面的场次全输且对面的队伍全赢也可以赢的局面就可以终结比赛
每次都判断一下是否A队当前赢的场次 > B队赢的场次+后面B队剩余的场次
或者B队当前赢的场次 > A队赢的场次+后面A队剩余的场次
这里算后面的场次的时候我WA了一发
因为我默认都搞成向上取整了(
正确的方法如下:
算A队后面的场次:$(n - i) / 2$
算B队后面的场次:$(n - i + 1) / 2$
最后遍历完了还算不出来就输出-1
代码:
void solve(){string s1;cin >> s1;n = s1.size();int x = 0,y = 0;s1 = " " + s1;for(int i = 1;i <= n;i++){if((i&1)&&(s1[i] == "1")) x++;else if(s1[i] == "1") y++;if(x > y + (n - i + 1) / 2||y > x + (n - i) / 2){cout << i << endl;return;}}cout << -1 << endl;}
总结:
在向上取整的时候一定要考虑奇偶,大概率会不一样(
C.现在是,学术时间 (I)
题意:
给n个数字随意分配到n个位置上
定义每一个位置的价值为(位置上的数大小 > 位置上的数字数量)的最大数量
求经过分配后的每个位置价值之和的最大值
思路:
最开始的思路是贪心
每个数的承载量就是数字的大小
比如一个3就可以和另外两个3放在一个位置上有一个为3的贡献
然后就用map处理一下
然后就喜提WA
原因是没去考虑最大贡献,最大贡献其实就是n
因为把数字叠在一起并不能增大总值,反而有可能降低总值
所以最优策略就是不分配,然后算一下>0的值即可
代码:
void solve(){int ans = 0;cin >> n;for(int i = 1;i <= n;i++){cin >> temp;if(temp >= 1) ans++;}cout << ans << endl;}
总结:
贪心之前想想哪样会更优,算算理论最优值是多少
前面用map做法就是典型的负面贪心
D.现在是,学术时间 (II)
题意:
给一个矩形由$(a,b)$和$(0,0)$构成
再给一个点$(x,y)$,要你找个点和这个点再构成一个矩形
要求这两个矩形的交集面积 / 并集面积最大
思路:
肯定是交集面积越大,并集面积越小越好
然后根据两个点的大小关系我觉得可以分为以下四种情况来讨论
1.x >= a&&y >= b
这种情况很好判断,无脑选原点就完事了
交集为:$a * b$
并集为:$x * y$
2.x <= a&&y <= b
点在第一个矩形里面
显然选第一个矩形的四个点分别讨论一下取交集面积最大的即可
那么交集面积为:$max({x * y,(a - x) * y,x * (b - y),(a - x) * (b - y)})$
并集面积为:$a * b$
3.x >= a&&y <= b
这种情况就比较容易错
因为并集不是$x * y$或者$a * b$了,而且这种情况里又分为两种情况,每个情况的并集不一样
情况1:以原点和(x,y)画第二个矩形
交集:$a * y$
并集:$a * b + (x - a) * y$
情况2:以(0,b)和(x,y)画第二个矩形
交集:$a * (b - y)$
并集:$a * b + (x - a) * (b - y)$
4.x <= a&&y >= b
与第三种情况对称即可,详细见代码
代码:
void solve(){cout<> a >> b >> x >> y;if(x >= a&&y >= b){op = x * y,uu = a * b;ans = max(ans,uu * 1.0 / (op * 1.0));}else if(x <= a&&y <= b){op = a * b;uu = max({x * y,(a - x) * y,x * (b - y),(a - x) * (b - y)});ans = max(ans,uu * 1.0 / (op * 1.0));}else if(x >= a&&y <= b) {op = a * b + (x - a) * y;uu = a * y;ans = max(ans,uu * 1.0 / (op * 1.0));op = a * b + (x - a) * (b - y);uu = a * (b - y);ans = max(ans,uu * 1.0 / (op * 1.0));} else if(x <= a&&y >= b){op = a * b + (y - b) * x;uu = b * x;ans = max(ans,uu * 1.0 / (op * 1.0));op = a * b + (y - b) * (a - x);uu = b * (a - x);ans = max(ans,uu * 1.0 / (op * 1.0));}cout << ans << endl;}
总结:
这种分类讨论题一定要画图,而且画图不要太潦草(
之前画图画潦草了迟迟分类不出来,最后重新画了一张就完事了
G.鸡格线
题意:
给一个长为n的数组,每次有两种操作
1:对l到r的数字进行$f(x) = round(10 * \sqrt{x})$
2:求所有数字之和
思路:
第一眼看起来是线段树,也确实能用线段树写(
但是这题还用不着线段树(
打个表看下规律,发现所有>0and<=99的数都会向99靠拢
所有>99的数都会向100靠拢
最大的数操作次数不超过20次就会变成目标数字
那么我们按照题意模拟即可
但是我们不知道哪些数是已经被操作完了的,所以这里有个小技巧
就是用set来存没有完成的数字
然后每次二分找比l大的数去操作$min(20,k)$次,并且更新相关数据即可
注意这里要存下标,不能存数字,因为是对l,r进行操作
每次操作完一个数字看是否还需要操作,不需要就删去这个数字
代码:
int f(int x){return round(10 * sqrt(x));}void solve(){int sum = 0;set s;cin >> n >> m;vector a(n + 1);for(int i = 1;i <= n;i++){cin >> a[i];sum += a[i];if(a[i] != f(a[i])) s.insert(i);}int l,r,k;while(m--){cin >> temp;if(temp == 1){cin >> l >> r >> k;while(1){auto it = s.lower_bound(l);int x = *it;if(it == s.end()||x > r) break;for(int i = 1;i <= min(20ll,k);i++){sum += f(a[x]) - a[x];a[x] = f(a[x]);}if(a[x] == f(a[x])) s.erase(it);l = x + 1;}}else cout << sum << endl;}}
总结:
看到有这种函数就尝试一下打表,一般都能出规律
对于一些数字只操作有限次,就可以用set存下标配合二分去寻找下一个有效值
H.本题主要考察了DFS
题意:
给$n * n - 1$块积木,然后问缺了哪一块,输出缺的那一块的形状数字
思路:
这里被套了,一看题目有dfs,然后长得也很像个dfs
写dfs写到一半突然发现好像不用dfs
因为最后题目问的缺的那一块并没有具体问是啥形状
只要知道有几个凹的和几个凸的的就行了
那这题就很简单了,统计一下出现的1和2的个数
因为1和2肯定是一一对应的,所以看哪个缺就补哪个就完事了
代码:
void solve(){int x = 0,y = 0,z = 0;string s1;cin >> n;char c;for(int i = 1;i <= n * n - 1;i++){for(int j = 1;j <= 4;j++){cin >> c;if(c == "0") x++;else if(c == "1") y++;else z++;}}if(y < z) cout << 10 - abs(y - z) << endl;else if(y == z) cout << 10 << endl;else if(y > z) cout << 10 + abs(y - z) << endl;// cout << x << " " << y << " " << z << endl;}
总结:
一定要先看题目问的啥,不要脑补题目条件(
还有看到题目有很明显的知识点大概率是误导(
K.本题主要考察了dp
题意:
要你构造一个长度为n的01串,并且其中1的数量为m
问构造出这样的串中所有长度为3的子区间中1的个数>0的个数的子区间数最少有几个
思路:
由于不想让1的个数>0的个数,考虑用2个0去匹配1个1
很容易这样构造:100100100100....1111
就是先构造上面的100100100这样看剩下几个0和几个1
把1全部放在最后面就是最小值
答案为1的个数-1
但是这样要注意边界问题
如果1的个数为0就会 出现负数,所以要对0取max
另外如果整个串全是1,输出就是n - 1,但是答案是$n - 2$
所以要再对$n - 2$取个min
代码:
void solve(){cin >> n >> m;int x = n - m,y = m;// cout << x << " " << y << endl;while(x >= 2&&y >= 1){x -= 2;y--;}cout << min(max(y - 1,0ll),n - 2) << endl;}
总结:
有时候猜出构造方法了还需要注意边界问题,最好交题前测测极限数据
M.本题主要考察了找规律
题意:
有n个人,m个物品来分配,每次分配得到的贡献值为给这个人分配的物品数 / 未给这个人分配前的物品总数
问获得的贡献值最大为多少
思路:
看范围,好了是dp
状态表示为:前i个人给了j个物品的最大贡献值
状态转移:i - 1个人就给了j - k个物品 + 本次贡献值
就是$dp[i][j] = dp[ i - 1][j - k] + k / m - j + k$
枚举$[0,k]$次即可
然后就出来了
代码:
void solve(){cout<> n >> m;for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){for(int k = 0;k <= j;k++){dp[i][j] = max(dp[i][j],dp[i - 1][j - k] + k * 1.0 / (m - j + k));}}}cout << dp[n][m] << endl;}
总结:
最基础的概率dp
dp还是练的太少太少了,平时遇到dp就跳过((
找个时间专项训练一下(
-
2023牛客寒假算法基础集训营1 个人题解(ACDHKL)
A WorldFinal?WorldCup!(I)题意:给10场比赛的点球输赢情况,奇数为A队点球,偶数为B队点球思路:用两个变...
来源: 2023牛客寒假算法基础集训营1 个人题解(ACDHKL)
每日看点!大过年的临时工玩呢 AMD又搞了个乌龙:锐龙7000X3D不能超频
天天简讯:彻底离开中国制造不现实 未来苹果将有25%产品来自印度
世界关注:“终极功率半导体”获突破性进展!金刚石有望成为终极半导体材料
每日动态!NASA第一架电动飞机即将上天 官宣至今已过去7年
世界实时:全球最高安全标准 我国自研第三代核电华龙一号稳步推进:1台年发电100亿度
环球今日报丨学习笔记——CentOS中的时间日期类命令;用户管理类命令(useradd,passwd ,id,su ,userdel,who ,usermod,
天天日报丨RTX 4060 Ti性能、价格逼近RTX 3070 网友质疑:升级图啥
steam春节特卖:11款热卖大作 部分游戏低至2折
读函数式编程思维笔记05_现实应用
每日热点:学习笔记——CentOS中的帮助命令;常用快捷键;文件目录类命令
全球视点!猪肉没有以前香了 我们的餐桌已被洋猪肉占据 鲜香早已不复当年
天天亮点!马斯克为“特斯拉私有化推文案”辩护:本可通过出售SpaceX的股份完成融资
环球快报:阿里云盘TV版上线 电视上直接看网盘里的大片
中科院研发新一代“电力银行”:充满可供20万人用一天
载人登月巨无霸 长征九号重型火箭将于2035年前后首飞
天天实时:国产2TB PCIe 4.0 SSD只要749元:搭载长江存储TLC颗粒 京东自营5年质保
当前报道:俄罗斯黑客攻破《暗黑破坏神4》测试版 自己开私服
世界头条:猫人石墨烯抗菌男士内裤三条装下单9折 29元
AMD官方确认:锐龙7000X3D系列将支持超频
春节档票房破30亿 暂列2023全球第一:《流浪地球2》独占10亿
世界今头条!游客遭遇山寨兵马俑、秦皇陵 大喊退票:专家科普真景点只看这两处
雷军安利MIUI“称呼计算器”:再也不怕过年喊错亲戚了
全球热头条丨499元买iPhone SE的羊毛没了!苹果bug已修复:下单的不认账
滚动:九旬老人花21万买17个金镯子送晚辈!网友羡慕了:满满都是爱
全球即时看!大神挑战32MB内存运行Win7系统 花2年时间减少4MB占用
万兆25Gbps:胜为万兆八类网线7.5米23.9元
清仓抄底:太平鸟夹克/棒球服等199-259元大额券
天天热消息:魔兽等7款暴雪游戏关服 网易公布退款说明:2月1日开放
环球快资讯:C919大飞机即将迎来兔年第一飞:很快就能商业载客了
今日热议:中国暴雪玩家的“最后一天”:走过地图每一处 把自己存进骨灰盒
环球热推荐:男子回应特斯拉充14次电回东北:并没有特别多的充电焦虑
热点!windows11 彻底修改c盘中文用户名
热资讯!8、CSS权威指南--第四章(p121)值和单位
18年青春结束了 魔兽世界国服正式关闭:期待再相逢
世界新动态:通用8位SPI接口模块——verilog实现
【环球报资讯】[概率论与数理统计]笔记:4.2 统计量
【世界聚看点】国产DDR5价格屠夫 金百达32GB 6400MHz内存999元(CL32低延迟)
http基础(随缘更新)
两人合作小品成春晚亮点 马丽回应离开沈腾就不行了:我俩都是1
春节看哪部电影?雷军没选《流浪地球2》 听网友的看了《无名》
易烊千玺主演电影票房破150亿:新片《满江红》正在热映
春节警惕“节日病”:过度饮酒易引发胰腺疾病
【报资讯】气温最低零下53℃ 大兴安岭女子回家发现单元门冻成冰窖
网络编程
【教程】配置多个SSH-Key
世界简讯:MySQL笔记01: MySQL入门_1.2 MySQL下载安装与配置
环球最资讯丨时隔3年 一加将再发概念机:搭载颠覆性技术
全球播报:吴孟达再现《流浪地球2》引热议 网友:看到达叔泪目
天天快播:学习笔记——Liunx中CentOS中的有关(network)的命令;其他命令;关机重启命令
天天快讯:区块链基础入门(一)
全球视点![概率论与数理统计]笔记:4.1 总体与样本
热点在线丨曝iPhone 15 Pro屏幕边框收窄:全系都是灵动岛设计
资讯推荐:漠河零下53℃是什么体验?冻梨能把板砖敲稀碎
PDF划词翻译
带薪撸猫!95后宠托师春节保底收入过万:工作氛围很轻松
最长已经12年了!聊聊那些龟速进步的笔记本电脑部件
全球消息!今晚停服!网易发布致暴雪国服玩家的告别信:会服务到最后一刻
当前热讯:小米2023年安卓之光!小米13 Ultra现身:1英寸徕卡影像之王预定
世界新消息丨黑鲨唯一在售机型!黑鲨5 RS京东有货:2499元
全球热推荐:不过兔年过猫年 越南也有春晚 网友:有VCD卓依婷那味了
天天微速讯:不锈钢保温又保冷 富光316L畅饮杯59元包邮(日常99元)
环球时讯:春节档总票房破20亿:《流浪地球2》领衔 同步冲击好莱坞
“中国造”的土耳其最快地铁正式开跑:时速120km 全自动驾驶
学习笔记——Liunx;Linux文件与目录结构;VI/VIM编辑器(一般模式、编辑模式、命令模式)
天天快播:微软Windows系统开发生变:Win10渐成弃儿 Win12呼之欲出
卷轴屏短期量产无望:困难重重
春节档破19亿 《流浪地球2》领跑:主演吴京总票房即将突破300亿
网友晒山东过年名场面:家族人共行磕头礼 仪式感拉满
iPhone 14 Pro不再是美国5G网速最快:被三星、谷歌超越
张艺谋执导!孙红雷谈《满江红》:超出预期 预测票房20亿起
【天天新要闻】曝iPad Pro明年有重大升级:玻璃材质、OLED屏幕
当前信息:今天上演2023年首场“星月童话”:肉眼可见金星、土星相伴月球
读函数式编程思维笔记04_语言与范式_模式与重用
头条:你看了吗?2023央视春晚触达110亿人次 年轻人占比过半
天天头条:气象台发布寒潮蓝色!山东断崖式降温:冷成了“山冻”
微资讯!魔兽世界国服关服最后一天 别忘了电子骨灰盒:24日停止
邓超王二妮春晚登台演唱!导演组:“一稳一疯”
全球视讯!小米汽车机密信息被曝光 设计神似特斯拉Model 3
焦点速读:夏普推出了NEC P627UL激光投影机:亮度高达6200ANSI流明
学习笔记——SSM整合(思路、步骤)
《流浪地球2》看不懂?专业科普来了 刷完电影来看看
焦点滚动:美国海关拆坏任天堂游戏稀有原封卡带:价值离谱
每年在中国收入500亿:连苹果都惹不起它
环球要闻:牌面!曙光新型计算机亮相《流浪地球2》
全球热点评!高端顶级大屏Win掌机!AYANEO KUN官宣:中文名叫“鲲”
世界信息:女子网购短裤7个月后异地签收 包裹跑遍广州、北京全国多地
【世界热闻】老外愤怒!2000块的旗舰SSD 990PRO 写了2T寿命暴跌至95%:竟遭三星拒保
焦点消息!适配器模式
环球百事通!《流浪地球2》上映首日吸金4.4亿!吴京主演作品票房突破290亿元
世界报道:男子包饺子放金戒指被网友质疑 霸气回应称自家开金店、寓意长寿多福
吃年夜饭鱼刺卡喉 医生一晚接诊近40例 提醒:切勿自行处理
沈腾可能要请很多人吃饭了!讲述小品《坑》背后:临场改词
山东一大妈首次放加特林烟花犹如上战场:网友评价“入戏太深”
学习笔记——SpringMVC拦截器的两种装配方式;SpringMVC拦截器工作原理;SpringMVC中的异常处理器;SpringMVC工作原理
【环球新要闻】俄宇航员从太空拍到除夕夜的中国:灯火通明、烟火璀璨
热推荐:雷军拍小米贺年照害羞了 现场即兴幽默:祝愿“暴富”会不会价值观有问题?
亚马逊、微软、谷歌之后:消息称苹果已经开始裁员
【天天新要闻】OPPO Find X6标准版屏幕素质拉满:支持2160Hz高频PWM调光
当前观察:网飞美剧《三体》杀青:美女云集!网友直呼汪淼演员毁三观