The 2022 ICPC 南京 ADG
The 2022 ICPC Asia Nanjing Regional Contest
A.Stop, Yesterday Please No More
思路:因为袋鼠是同时移动的,所以我们可以不考虑袋鼠怎么动,而去考虑边界怎么动。所以我们先不考虑洞的影响,先确定哪些会因为边界而离开。确定好最终边界,再进行一次模拟,加入有洞的情况,发现洞产生的路径都可以通过平移获得,那么就只维护一条路径.
然后我们来统计这个小矩形里活的袋鼠经过在移动过程中经过的格子,也就是统计m*n个格子中每个经过了这个小矩形中多少只袋鼠(注意这个洞可以在m*n的任意位置,而并非只是这个小矩形)然后计算经过数目为(x-k)的格子的数目。我们通过模拟剩余的袋鼠的矩阵,每次将这个矩阵范围的格子++(记得初始矩阵也要统计),由于矩阵的大小已经是唯一确定的了,我们只需要开一个二维布尔数组统计左上(或右下)是否已经计过数,就可以很轻松的判重了,最后再用二维前缀和统计出答案输出即可。
1 | // AC one more times |
D. Chat Program
思路:二分+差分
二分第
对于加上一段等差数列有什么影响呢?一个数刚被等差数列右端点经过时候是最大的,之后慢慢变小,最后恢复成本身。我们可以确定当加上一个等差数列,每个数的贡献范围(用差分处理),最后再做一次前缀和操作即可。
1 | // AC one more times |
G. Inscryption
思路:反悔贪心。题目中
1 | // AC one more times |
- Title: The 2022 ICPC 南京 ADG
- Author: Nannan
- Created at : 2023-10-04 12:44:00
- Updated at : 2024-09-30 17:08:22
- Link: https://redefine.ohevan.com/2023/10/04/The 2022 ICPC Asia Nanjing Regional Contest/
- License: This work is licensed under CC BY-NC-SA 4.0.
Comments