AtCoder Regular Contest 159 C https://atcoder.jp/contests/arc159/tasks/arc159_c 题解 当最终每个数都一样时,总和一定是 nnn 的倍数。而每次操作都是给总和加上了 s=n(n+1)2s=\dfrac{n(n+1)}{2}s=2n(n+1)。所以如果初始的总和 sumsumsum 和 sum+ssum+ssum+s 都不是 nnn 的倍数那么一定无解。 否则一定有解。考虑两次操 2023-10-15 ACM #思维
The 2023 CCPC Online Contest https://codeforces.com/gym/104651 A. Almost Prefix Concatenation 题解 容易发现对于固定的起始位置 iii,符合almost prefix的结束位置一定是一段连续的区间。具体地,我们求出 lcp(最长公共前缀),然后往后移动一位,然后再求一次lcp,得到的就是最远的结束位置,记为 lcpilcp_ilcpi。 题目中要求平方和,我们 2023-10-10 ACM #dp #哈希 #计算几何 #2023CCPC #三分 #gcd #补图最短路
Codeforces Round 901 (Div. 1) https://codeforces.com/contest/1874 C. Jellyfish and EVA 题意 给出一张DAG(保证每个点只连向编号比自己大的结点)。有两个人,初始在 111 号结点,希望走到 nnn 号结点。每次其中一人随机选择一个后继结点,另一个人可以安排自己选择的结点。若两人选择同一个后继结点,则移动到该结点,否则将选择的两个结点都删除。若没有可选的后继结点,就停留在 2023-10-08 ACM #概率dp
The 2022 ICPC Asia Hangzhou Regional Programming Contest https://codeforces.com/gym/104090 C. No Bug No Game 题解 显然,部分被放入的物品只有一个。我们可以枚举物品 iii 和它被放入的体积。然后枚举它前面的物品一共占用的体积 jjj,就能得到后面的物品一共占用的体积 k−i−jk-i-jk−i−j。对前缀和后缀分别做一遍背包就可以了。 G. Subgraph Isomorphism 题解 当 m=n− 2023-10-07 ACM #随机 #2022ICPC #背包 #树哈希
The 2022 ICPC Asia Xian Regional Contest https://codeforces.com/gym/104077 B. Cells Coloring 题解 当我们选定一个 kkk 后,所有每行每列选择不超过 kkk 个的方案数都是合法的。所以我们可以建立网络流模型:源点向每行连容量为 kkk 的边,若第 iii 行第 jjj 列为空,第 iii 行向第 jjj 列连容量为 111 的边,每列向汇点连容量为 kkk 的边。 我们从小到大增加 k 2023-09-29 ACM #倍增 #网络流 #2022ICPC
The 2022 ICPC Asia Nanjing Regional Contest https://codeforces.com/gym/104128 A. Stop, Yesterday Please No More 题解 首先不考虑这个洞。我们不模拟袋鼠的移动,而是模拟边界的移动,最终留下的袋鼠一定位于中间的一块矩形区域,也有可能没有袋鼠剩下,后者可以特判掉。 然后考虑这个洞。同样的,我们模拟洞的移动,看它能“吃掉“几只袋鼠。具体地,我们求出每一步洞相对于初始位置的偏移量,然 2023-09-26 ACM #dp #前缀和 #2022ICPC #模拟 #二分 #计算几何 #长链剖分
AtCoder Beginner Contest 320 https://atcoder.jp/contests/abc320 F - Fuel Round Trip 题意 题意很简单就是要在从 000 位置走到 XnX_nXn 位置,然后倒回来回到 000 位置。并且每走一格需要 111 的油,油箱最多携带 HHH 的油,途中有一些只能使用一次的加油站,选择加油只能强制花费 pip_ipi 元加入 fif_ifi 的油,装不下只能抛弃。现在问你从 2023-09-24 ACM #dp
AtCoder Regular Contest 165 https://atcoder.jp/contests/arc165 D - Substring Comparison 题意 给定一个长度为 nnn 的序列 xxx,给出 mmm 组限制。每组限制 (ai,bi,ci,di)(a_i,b_i,c_i,d_i)(ai,bi,ci,di) 表示 xai,ai+1,⋯ ,bix_{a_i,a_{i+1},\cdots,b_i}xai,ai+1 2023-09-19 ACM
牛客练习赛115 https://ac.nowcoder.com/acm/contest/64819 A Mountain sequence 题意 定义序列 aaa 为山峰序列当存在一个 jjj 满足: ai≤ai+1(1≤i≤j−1),ai≥ai+1(j≤i≤n−1)a_i\leq a_{i+1}(1\leq i\leq j-1),a_i\geq a_{i+1}(j\leq i\leq n-1)ai≤ai+1 2023-09-11 ACM
2023 Jiangsu Collegiate Programming Contest, 2023 National Invitational of CCPC (Hunan), The 13th Xiangtan Collegiate Programming Contest https://codeforces.com/gym/104396 E. LCM Plus GCD 题意 给定 x,kx,kx,k,求满足条件的 (a1,a2,⋯ ,ak)(a_1,a_2,\cdots,a_k)(a1,a2,⋯,ak) 的个数。 a1,a2,⋯ ,aka_1,a_2,\cdots,a_ka1,a2,⋯,ak 各不相同。 gcd(a1,a2,⋯ ,ak)+lcm(a 2023-09-10 ACM #数论 #容斥 #2023省赛