当前位置:网站首页>[learning notes] agc010
[learning notes] agc010
2022-07-07 13:09:00 【Ants looking up at the starry sky】
Do more AGC Long brain
No samples , Just rely on your brain
Rearranging
- Consider if two numbers are not mutually prime , Then their relative positions in the final sequence remain unchanged
- So for two numbers that are not coprime , At the same time, orient each edge DAG
- The answer is the largest topological order , Because considering that a point can be exchanged with any other point without entering
- Greedy structure . Start from the point with the lowest number dfs , Find the edge with the lowest node number every time , It can be understood as constructing a tree .
- Then simulate it (
Tiling
- Greedy to consider how to maximize the grid
- Obviously, the mesh is divided into several 2x2 The matrix of is optimal
- The leftover materials are paved with corresponding horizontal bricks or vertical bricks
- This will definitely maximize the number of bricks
- Hand play discovery n=3,m=3,A=2,B=2 There will be problems ( Here hack Data is the difficulty
- That is to say, for the last 2x2 Of the lattice , There is one horizontal brick and one vertical brick left , Theoretically, it can lay two bricks , But due to the shape, only one piece can be paved
- Notice that there is a space in the lower right corner , You can put it down by adjusting .
- There are two schemes directly check that will do .
- Notice the grid problem Nastia and a Beautiful Matrix , from Maximize the use of grid space Starting with , Find the local optimum , Then the global optimal solution is constructed .
Three Circuits
- The degree of each point must be even
- The title gives that this is a connected graph , So there must be an Euler circuit
- If there are degrees of points >=6 , Then there must be a solution ( Consider proving from the perspective of Euler loop
- Count the degree = 4 The number of points is cnt
- If cnt=0 , Then only one ring can be constructed at most
- If cnt=1 , Then only two rings can be constructed at most
- If cnt=2 , So there are two situations ( Drawing perception : It is possible to construct two rings or three rings
- If cnt>=3 , Then remove a simple ring and conclude cnt=2 The situation of , At least three rings can be constructed
Decrementing
- If there is a i = 1 a_i=1 ai=1 , So judge ∑ ( a i − 1 ) \sum{(a_i-1)} ∑(ai−1) Parity .
- Definition ∑ ( a i − 1 ) \sum{(a_i-1)} ∑(ai−1) Odd numbers are wins , Even numbers are negative
- If the person currently operating wins , So no matter what the other person does , At present, this person will win
- Because if you don't divide all numbers by the greatest common divisor , ∑ a i \sum a_i ∑ai The parity of does not change , that ∑ ( a i − 1 ) \sum (a_i-1) ∑(ai−1) The parity of will not change , The outcome is fixed
- Now it's equivalent to ∑ a i → ∑ a i x \sum{a_i}\to \frac{\sum{a_i}}{x} ∑ai→x∑ai , If and only if x x x It's even and ∑ a i x \frac{\sum{a_i}}{x} x∑ai Only when it is an odd number
- Note that the number of odd numbers in the sequence is cnt , At first, because of mutual prime cnt>=1 , Then two people take turns , Those who are behind can never let cnt=0 (n>=3 when )
- If the current operation fails , Then operate on the only odd number , This may reverse the outcome .
- So direct simulation . Not more than log a \log a loga Time .
边栏推荐
- 关于 appium 启动 app 后闪退的问题 - (已解决)
- “新红旗杯”桌面应用创意大赛2022
- leecode3. 无重复字符的最长子串
- Coscon'22 community convening order is coming! Open the world, invite all communities to embrace open source and open a new world~
- Go语言学习笔记-结构体(Struct)
- 详解ThinkPHP支持的URL模式有四种普通模式、PATHINFO、REWRITE和兼容模式
- .Net下极限生产力之efcore分表分库全自动化迁移CodeFirst
- Day-24 UDP, regular expression
- @What is the difference between resource and @autowired?
- .Net下極限生產力之efcore分錶分庫全自動化遷移CodeFirst
猜你喜欢
Adopt a cow to sprint A shares: it plans to raise 1.85 billion yuan, and Xu Xiaobo holds nearly 40%
Leetcode skimming: binary tree 20 (search in binary search tree)
PACP学习笔记一:使用 PCAP 编程
Leetcode skimming: binary tree 23 (mode in binary search tree)
为租客提供帮助
关于 appium 启动 app 后闪退的问题 - (已解决)
COSCon'22 社区召集令来啦!Open the World,邀请所有社区一起拥抱开源,打开新世界~
About how appium closes apps (resolved)
[untitled]
Blog recommendation | Apache pulsar cross regional replication scheme selection practice
随机推荐
《开源圆桌派》第十一期“冰与火之歌”——如何平衡开源与安全间的天然矛盾?
LIS 最长上升子序列问题(动态规划、贪心+二分)
博文推荐|Apache Pulsar 跨地域复制方案选型实践
Isprs2021/ remote sensing image cloud detection: a geographic information driven method and a new large-scale remote sensing cloud / snow detection data set
【学习笔记】zkw 线段树
Go language learning notes - structure
Pay close attention to the work of safety production and make every effort to ensure the safety of people's lives and property
MySQL入门尝鲜
Query whether a field has an index with MySQL
谷歌浏览器如何重置?谷歌浏览器恢复默认设置?
.Net下极限生产力之efcore分表分库全自动化迁移CodeFirst
Go语言学习笔记-结构体(Struct)
云检测2020:用于高分辨率遥感图像中云检测的自注意力生成对抗网络Self-Attentive Generative Adversarial Network for Cloud Detection
Conversion from non partitioned table to partitioned table and precautions
Cookie
Common text processing tools
【无标题】
Star Enterprise Purdue technology layoffs: Tencent Sequoia was a shareholder who raised more than 1billion
File operation command
[binary tree] delete points to form a forest