沟槽的 NOIP2025 还在追我。G 建议改名 Sale Sale Sale。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
A
我懒得打循环，然后盲猜 STL 有 count 函数，然后真就自己试出来了 std::count，绷。
时间复杂度：O(∣S∣)O(|S|)O(∣S∣)。
B
按题意模拟即可。
时间复杂度：O(n)O(n)O(n)。
C
何意味。
我们可以把它当完全图，然后加边看成删边。最后的答案就是与它相连的边任选三个，答案就是 (degi3)\text{deg}_i\choose 3(3degi )。
只需要记录度。
时间复杂度：O(n+m)O(n+m)O(n+m)。
D
这题小时候抱过我。
注意到交换 Ai,Ai+1A_i,A_{i+1}Ai ,Ai+1 后，所有前缀和中只有 [1,Ai][1,A_i][1,Ai ] 的前缀和会变。
所以直接更新即可。
时间复杂度：O(n+q)O(n+q)O(n+q)。
F
题意解析：给定一个 n×nn\times nn×n 的 .# 矩阵。你需要将它重新染色，使得每一行与每一列都是前面的 . 后面的 #。问最小修改格数。
不难发现这个的形状大概是这样的：
令 dp[i][j]\text{dp}[i][j]dp[i][j] 为第 iii 行，前 jjj 个元素是 000，后面的是 111 的答案最小值，Bi,jB_{i,j}Bi,j 为前面的 # 的个数，Ci,jC_{i,j}Ci,j 为后面的 . 的个数。则有：
dp[i][j]=mink=jndp[i−1][k]+Bi,j+Ci,j+1\text{dp}[i][j]=\min_{k=j}^n \text{dp}[i-1][k]+B_{i,j}+C_{i,j+1} dp[i][j]=k=jminn dp[i−1][k]+Bi,j +Ci,j+1
前缀和优化。
时间复杂度：O(n2)O(n^2)O(n2)。
