当前位置:网站首页>【学习笔记】AGC010
【学习笔记】AGC010
2022-07-07 10:59:00 【仰望星空的蚂蚁】
多做 AGC 长脑子
不给样例,光靠脑子想
Rearranging
- 考虑如果两个数不互质,那么它们在最终序列相对位置不变
- 因此对两个不互质的数连边,同时对每条边定向构造 DAG
- 答案就是最大的拓扑序,因为考虑一个点没有入度的话可以和任何其他的点交换
- 贪心的构造 。从编号最小的点开始 dfs ,每次找节点编号最小的出边,可以理解成构造了一颗树 。
- 然后模拟就行了 (
Tiling
- 贪心的考虑如何最大限度将网格铺满
- 显然将网格剖分成若干个 2x2 的矩阵是最优的
- 边角料就铺对应的横砖或竖砖
- 这样一定能最大化铺砖的数量
- 手玩发现 n=3,m=3,A=2,B=2 的情况会有问题(这里找 hack 数据是难点
- 也就是说对于最后一个 2x2 的方格,还剩横砖和竖砖各一个,理论上能铺两块砖,但是由于形状原因只能铺一块
- 注意到右下角还空了一个位置,可以通过调整放下 。
- 直接分两种方案 check 即可 。
- 注意到网格问题 Nastia and a Beautiful Matrix ,从 最大化利用网格空间 入手,找到局部最优,进而构造出全局最优解 。
Three Circuits
- 每个点的度数都必须是偶数
- 题目给了这是一个连通图,所以一定存在欧拉回路
- 如果存在点的度数 >=6 ,那么必然有解(考虑从欧拉回路角度去证
- 记度数 = 4 的点个数为 cnt
- 如果 cnt=0 ,那么最多只能构造出一个环
- 如果 cnt=1 ,那么最多只能构造出两个环
- 如果 cnt=2 ,那么有两种情况(画图感知:可能构造出两个环或三个环
- 如果 cnt>=3 ,那么去掉一个简单环后归纳到 cnt=2 的情况,最少能构造出三个环
Decrementing
- 如果存在 a i = 1 a_i=1 ai=1 ,那么判断 ∑ ( a i − 1 ) \sum{(a_i-1)} ∑(ai−1) 的奇偶性 。
- 定义 ∑ ( a i − 1 ) \sum{(a_i-1)} ∑(ai−1) 奇数时为胜态,偶数时为负态
- 如果当前正在操作的人为胜态,那么无论另一个人怎么操作,当前这个人必胜
- 因为考虑如果没有所有数都除以最大公约数这个操作的话, ∑ a i \sum a_i ∑ai 的奇偶性不会变化,那么 ∑ ( a i − 1 ) \sum (a_i-1) ∑(ai−1) 的奇偶性也不会变化,胜负态是固定的
- 现在相当于 ∑ a i → ∑ a i x \sum{a_i}\to \frac{\sum{a_i}}{x} ∑ai→x∑ai ,当且仅当 x x x 是偶数且 ∑ a i x \frac{\sum{a_i}}{x} x∑ai 为奇数时才行
- 记序列中奇数的个数为 cnt ,初始因为互质所以 cnt>=1 ,那么两个人轮流操作,后手的人永远无法让 cnt=0 (n>=3 时)
- 如果当前操作的人为败态,那就操作唯一的奇数,这样有可能逆转胜负 。
- 因此直接模拟 。最多不会超过 log a \log a loga 次 。
边栏推荐
- 智云健康上市:市值150亿港元 SIG经纬与京新基金是股东
- Sample chapter of "uncover the secrets of asp.net core 6 framework" [200 pages /5 chapters]
- Day-20 file operation, recursive copy, serialization
- test
- PHP调用纯真IP数据库返回具体地址
- Cookie
- Importance of database security
- CMU15445 (Fall 2019) 之 Project#2 - Hash Table 详解
- COSCon'22 社区召集令来啦!Open the World,邀请所有社区一起拥抱开源,打开新世界~
- 测试下摘要
猜你喜欢
红杉中国完成新一期90亿美元基金募集
【无标题】
如何将 @Transactional 事务注解运用到炉火纯青?
Connect to blog method, overload, recursion
ISPRS2021/遥感影像云检测:一种地理信息驱动的方法和一种新的大规模遥感云/雪检测数据集
DHCP 动态主机设置协议 分析
Blog recommendation | Apache pulsar cross regional replication scheme selection practice
博文推荐|Apache Pulsar 跨地域复制方案选型实践
达晨与小米投的凌云光上市:市值153亿 为机器植入眼睛和大脑
通过Keil如何查看MCU的RAM与ROM使用情况
随机推荐
[爬虫]使用selenium时,躲避脚本检测
免费手机号码归属地API查询接口
SSM框架搭建的步骤
. Net ultimate productivity of efcore sub table sub database fully automated migration codefirst
[statistical learning method] learning notes - support vector machine (I)
API query interface for free mobile phone number ownership
NPM instal reports agent or network problems
Sed of three swordsmen in text processing
聊聊Redis缓存4种集群方案、及优缺点对比
opencv的四个函数
How to reset Google browser? Google Chrome restore default settings?
Unity 构建错误:当前上下文中不存在名称“EditorUtility”
What if the xshell evaluation period has expired
Layer pop-up layer closing problem
Several ways to clear floating
Day-24 UDP, regular expression
Talk about four cluster schemes of redis cache, and their advantages and disadvantages
Connect to blog method, overload, recursion
认养一头牛冲刺A股:拟募资18.5亿 徐晓波持股近40%
Leetcode question brushing: binary tree 26 (insertion operation in binary search tree)