Feb/May 比赛链接[[https://codeforc.es/contest/1350]] ~~CN的题真要命~~ ------ =====A===== 题意：t次操作，每次给定n，k，求k次$n=n+f(n)$之后的n值，其中$f(n)$求取n的最小质因子。签到（之后就罚坐）题，分三类情况： *偶数最小质因子就是2，加完还是偶数，直接 $n + 2k$ *非质奇数加一次最小质因子后会变偶数，所以 $n + f(n) + 2(k-1)$ *质数第一次必定加本身，变成偶数，所以 $n*2 + 2(k-1)$ $1≤n≤2*10^6$，$1≤t≤10^2$，暴力不放心可以线性筛 AC代码=>[[https://codeforc.es/contest/1350/submission/79832106]] =====B===== 题意：t 次询问($1≤t≤10^2$)，每次给定长为 n ($1≤n≤10^5$)的正整数序列{s₁,s₂,...,s_n}，求子序列满足对任意$i≤j$有s_i < s_j且j % i == 0的最长子序列长度不难想到LIS（最长上升子序列），dp可以过，注意一下细节防止TLE AC代码=>[[https://codeforc.es/contest/1350/submission/79954462]] =====C===== 题意：给定长为 n ($2≤n≤10^5$)的正整数序列{s₁,s₂,…,s_n}，求由任意两元素 LCM（最小公倍数）组成新序列{a₁,a₂,…,a_n}(1$≤$a_i$≤2*10^5$)的 GCD（最大公约数），即LCM(GCD(s_i,s_j))($i ≤j$) 将答案 ans 质因数分解，有 $ans =$ p₁^k1p₂^k2...p_m^km 对于每个 p_i，一定在序列 s 中出现至少 $n - 1$ 次，每次出现由小到大可能为 p_i^c1， p_i^c2， ...p_i^cki GCD(LCM(p_i^c1， p_i^c2， ...p_i^cki))一定为第二小的c2 所以可以对序列 s 每个数的每个质因子统计次数，将大于 $n-1$ 次的因子幂次方排序，取第二小累乘即可注意用vector，不要处处longlong，否则会MLE AC代码=>[[https://codeforc.es/contest/1350/submission/79957224]] =====D===== 题意：t 次询问，每次给定长为 n 的正整数序列{a₁,a₂,...a_n}和正整数 k。可以无数次对任意区间$[l, r]$进行如下操作：求其中位数（角标向下取整）并将区间内所有值变为中位数。问能否将此序列同化为k。数一下 k 在序列中出现了多少次，首先出现 0 次肯定是不行的。只有 1 个元素且等于 k 可行；只有 2 个元素时保证不等于 k 的元素大于 k 则可行；多个元素时从 2 到 n-1 遍历一次，任何相邻的三个数中只要有两个数大于等于 k 则可行。 AC代码=>[[https://codeforc.es/contest/1350/submission/79960457]] =====E===== 咕咕咕 =====F===== 没看，不补