首页 > 其他分享 >第 13 届山东省 icpc 省赛 vp

第 13 届山东省 icpc 省赛 vp

时间:2024-04-04 21:55:38浏览次数:39  
标签:13 nk 赛时 然后 icpc vp 操作 省赛

第 13 届山东省 icpc 省赛 vp

总结:

2024 / 4 / 4

赛时:7 / 12:A B D G I J L

https://codeforces.com/gym/104417

最近开始康复训练,和昊哥 vp 了一场省赛。

前期签到蛮顺利,基本 1个多小时就出了 5 题,然后卡在了 E,后面 B 的实现也弄了蛮久,好在过了 J 题,vp 在省内应该是可以排到前 30 左右。

SUA 出的题很有区分度,出的很好!!

值得总结的题:

E:

  • 赛时发现了先坐操作 \(1\),然后在做操作 \(2\) 显然是抵消的,所以最优操作必然是先不停的除 \(k\),然后再用操作 \(1\)。

  • 然后后面昊哥发现了两个操作可以看成在 \(k\) 进制下的操作,每次相当于左移一位然后可以任意添加某个数到末尾位,或者直接右移,除掉一位。

  • 后面卡在了如何判断一个 \(x\) 通过若干次操作 \(1\) 弄成 \(m\) 的倍数,钻进了如何精确知道某个 \(m\) 的倍数的思维定式,其实我们不难发现操作 \(1\) 形成的数是有范围的:\([nk^p,nk^p+k^p-1]\),故我们只要看是否存在一个 \(m\) 的倍数落在这个区间,就变成了一个简单的问题,只要看第一个大于等于 \(nk^p\) 的 \(m\) 的倍数是否在超过右边界即可。

  • 不难发现这样一直做操作 \(1\) 必然会有解的,当这个值域区间范围长度超过了 \(m\),那么必然存在一个 \(m\) 的倍数。

  • 所以只要暴力枚举操作 \(2\) 然后暴力做操作 \(1\) 即可,这里可以考虑 \(nk^p\mod m\) 的值,还差多少到 \(0\),然后就可以看看这个区间长度是否够,这样就可以判断了,否则实现起来可能要 __int128

B:

  • 自己的反思,赛时是昊哥做的,赛时我没想到怎么实现,后面下来补了一下。
  • 不难发现我们其实要考虑能接就接任务,对于某一种类的人的需求数量,我们肯定贪心的做要求少的先,然后尽可能获得奖励人员,再去做,这里就可以用堆来维护,然后观察到我们每完成一个任务,然后我们下一次只要在检查该任务带来奖励的人员种类即可,因为其它种类的人员数量不变,显然不会导致能够继承新的任务,只有可能是我某一项人变多了满足了某一个任务才可以,想到这里就很关键了,这样复杂度就是对的。
  • 故我们只要弄个哈希表套堆,然后每次把完成的任务弄进队列,然后下一次检查奖励的种类,以此进行,最后答案就是出队次数。

L:

  • 赛时和昊哥快速讨论出了思路,我们给出了每次就相当于从一个 \(1\times 1\) 的放个往外扩展,每次的 \(L\) 形就只有 \(4\) 种摆放,只要有一种可以摆就按此摆放,由于给出的是一个正方形,我们必然可以通过 \(n-1\) 次扩展完成构造。

D:

  • 很快发现可以二分答案,然后检查 \(k\) 这个答案行不行,然后我列出了式子和昊哥讨论了一下,很快就发现了两侧分别按照 \(v+w-k\) 和 \(w\) 排序,贪心按照大对应大搞一下即可。

G:

  • 我很快发现 \(i-j=a_i-a_j\iff i-a_i=j-a_j\)
  • 然后可以把这个式子一样值的分在一组,那么显然贪心每次选组内最大的两个连边即可。

J:

  • 比较 trick 的题,对于二进制问题,不难想到高位到低位贪心,我们只要枚举到底答案在哪一位比 \(V\) 大即可,相当于枚举二进制公共前缀,然后每次做一次连通性,把所有有这个这个公共前缀的边权的变弄进来,那么显然在一个连通块的任意两个点 \(u,v\) 都存在满足条件的路径。
  • 所以思路就是弄 \(60\) 个并查集搞一下完事了,最后别忘了检查 \(=V\) 的情况。

标签:13,nk,赛时,然后,icpc,vp,操作,省赛
From: https://www.cnblogs.com/xiaole-jackle/p/18114999

相关文章

  • P2613 【模板】有理数取余
    原题链接题解然后就变成了求解同余方程code#definelllonglong#include<bits/stdc++.h>constllmod=19260817;usingnamespacestd;llx,y;llc;lla,b;inlinevoidread(ll&x){x=0;llflag=1;charc=getchar();while(c<'0......
  • CMT313个人投资组合评估方法
    课程评估形式模块代码:CMT313课程名称:软件工程评估题目:个人投资组合评估编号:第3个,共3个日期设置:19/02/2024提交日期和时间:春季工作周,2024年5月2日上午9:30反馈返回日期:2024年6月5日如果您因情有可原的情况获得延期,那么提交截止日期和返回日期将晚于上述日期。当您的延期获得批准时,......
  • [CVPR2023]Detecting and Grounding Multi-Modal Media Manipulation-DGM4
    DGM4人造DeepFake数据——Multi-ModalMediaManipulationDataset再造数据集的意义此前的其他相关数据集要么是单模态的Fake图片篡改:文本篡改要么是多模态小规模数据human-generated:outofcontextpairs:并且都是二分类问题(单纯分类为“是否”为fake数据)DGM......
  • 使用VPS搭建本地可以访问的gemini(个人记录)参考github,cloudflare,nginx
    第一步:购买一台VPS服务器,可以正常ping通google和baidu,不可细说 第二步:参考这个网站的docker部分,docker到linux服务器中,不使用vercel部署(被墙)https://juejin.cn/post/7317700926826922035docker项目地址:https://github.com/babaohuang/GeminiProChat/blob/main/README_cn.......
  • ctfshow--web13 .user.ini上传和bak源码泄露
    upload.php.bak源码泄露了审计一下点击查看代码<?php header("content-type:text/html;charset=utf-8"); $filename=$_FILES['file']['name']; $temp_name=$_FILES['file']['tmp_name']; $size=$_FILES['file'......
  • Android 13.0 系统限制上网系列之iptables用IOemNetd实现删除子链功能的实现
    1.前言在13.0的系统rom定制化开发中,对于限制系统上网功能中,在system中netd网络这块的产品开发中,会要求设置屏蔽ip地址之内的功能,liunx中iptables命令也是比较重要的,接下来就来在IOemNetd这块实现删除创建子链的相关功能2. 系统限制上网系列之iptables用IOemNetd实现删除创......
  • 中间件 ZK分布式专题与Dubbo微服务入门 6-13 acl - ip权限
    0课程地址https://coding.imooc.com/lesson/201.html#mid=12729 1重点关注1.1本节内容通过schema为ip的方式设置权限,只有指定ip才能操作 1.2关键代码//ip方式的aclList<ACL>aclsIP=newArrayList<ACL>();......
  • Nginx 配置反向代理时出现 502 Bad Gateway (13_ Permission denied) while connectin
    我们在Nginx配置反向代理后,可能会出现如下报错:502BadGateway(13:Permissiondenied)whileconnectingtoupstreamSorry,thepageyouarelookingforiscurrentlyunavailable.<br/>Pleasetryagainlater.这些错误,一般是由SELinux引起的(https://stackoverf......
  • leetcode每日一题 1379. 找出克隆二叉树中的相同节点
    问题描述给你两棵二叉树,原始树original和克隆树cloned,以及一个位于原始树original中的目标节点target。其中,克隆树cloned是原始树original的一个副本。请找出在树cloned中,与target相同的节点,并返回对该节点的引用(在C/C++等有指针的语言中返回节点指针,其他......
  • 酷睿i7 14650HX和i7 13700hx选哪个 i714650HX和i713700hx对比
    i713700hx采用10nm工艺16个核和24个线程,基本的频率为2.1GHZ,甚至可以提升到4.96ghz。三级缓存55MB热设计功耗(TDP)55W支持最大内存128GB内存类型DDR43200MHzDDR54800MHz集成显卡IntelUHDGraphics选i713700hx还是i714650HX这些点很重要看过你就懂了http://ww......