2020-2021:teams:manespace:codeforces_round_641_div._2
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:codeforces_round_641_div._2 [2020/05/16 20:06] intouchables |
2020-2021:teams:manespace:codeforces_round_641_div._2 [2020/05/19 16:22] (当前版本) intouchables [B] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | FRI/MAY | + | Feb/May |
| 比赛链接[[https://codeforc.es/contest/1350]] | 比赛链接[[https://codeforc.es/contest/1350]] | ||
| 行 9: | 行 9: | ||
| 题意：t次操作，每次给定n，k，求k次$n=n+f(n)$之后的n值，其中$f(n)$求取n的最小质因子。 | 题意：t次操作，每次给定n，k，求k次$n=n+f(n)$之后的n值，其中$f(n)$求取n的最小质因子。 | ||
| - | 题解：签到（之后就罚坐）题，分三类情况： | + | <hidden 思路：> |
| + | |||
| + | 签到（之后就罚坐）题，分三类情况： | ||
| *偶数最小质因子就是2，加完还是偶数，直接 $n + 2k$ | *偶数最小质因子就是2，加完还是偶数，直接 $n + 2k$ | ||
| 行 16: | 行 18: | ||
| $1≤n≤2*10^6$，$1≤t≤10^2$，暴力不放心可以线性筛 | $1≤n≤2*10^6$，$1≤t≤10^2$，暴力不放心可以线性筛 | ||
| + | |||
| + | </hidden> | ||
| AC代码=>[[https://codeforc.es/contest/1350/submission/79832106]] | AC代码=>[[https://codeforc.es/contest/1350/submission/79832106]] | ||
| 行 23: | 行 27: | ||
| 题意：t 次询问($1≤t≤10^2$)，每次给定长为 n ($1≤n≤10^5$)的正整数序列{s<sub>1</sub>,s<sub>2</sub>,...,s<sub>n</sub>}，求子序列满足对任意$i≤j$有s<sub>i</sub> < s<sub>j</sub>且j % i == 0的最长子序列长度 | 题意：t 次询问($1≤t≤10^2$)，每次给定长为 n ($1≤n≤10^5$)的正整数序列{s<sub>1</sub>,s<sub>2</sub>,...,s<sub>n</sub>}，求子序列满足对任意$i≤j$有s<sub>i</sub> < s<sub>j</sub>且j % i == 0的最长子序列长度 | ||
| - | 题解：不难想到LIS，dp可以过，注意一下细节防止TLE | + | <hidden 思路：> |
| + | |||
| + | 不难想到LIS（最长上升子序列），dp可以过，注意一下细节防止TLE | ||
| + | |||
| + | </hidden> | ||
| AC代码=>[[https://codeforc.es/contest/1350/submission/79954462]] | AC代码=>[[https://codeforc.es/contest/1350/submission/79954462]] | ||
| 行 29: | 行 37: | ||
| =====C===== | =====C===== | ||
| - | =====题意===== | + | 题意：给定长为 n ($2≤n≤10^5$)的正整数序列{s<sub>1</sub>,s<sub>2</sub>,…,s<sub>n</sub>}，求由任意两元素 LCM（最小公倍数）组成新序列{a<sub>1</sub>,a<sub>2</sub>,…,a<sub>n</sub>}(1$≤$a<sub>i</sub>$≤2*10^5$)的 GCD（最大公约数），即LCM(GCD(s<sub>i</sub>,s<sub>j</sub>))($i ≤j$) |
| - | 给定长为 n ($2≤n≤10^5$)的正整数序列{s<sub>1</sub>,s<sub>2</sub>,…,s<sub>n</sub>}，求由任意两元素 LCM（最小公倍数）组成新序列{a<sub>1</sub>,a<sub>2</sub>,…,a<sub>n</sub>}(1$≤$a<sub>i</sub>$≤2*10^5$)的 GCD（最大公约数），即LCM(GCD(s<sub>i</sub>,s<sub>j</sub>))($i ≤j$) | + | <hidden 思路：> |
| - | + | ||
| - | =====题解===== | + | |
| 将答案 ans 质因数分解，有 $ans =$ p<sub>1</sub><sup>k1</sup>p<sub>2</sub><sup>k2</sup>...p<sub>m</sub><sup>km</sup> | 将答案 ans 质因数分解，有 $ans =$ p<sub>1</sub><sup>k1</sup>p<sub>2</sub><sup>k2</sup>...p<sub>m</sub><sup>km</sup> | ||
| 行 44: | 行 50: | ||
| 注意用vector，不要处处longlong，否则会MLE | 注意用vector，不要处处longlong，否则会MLE | ||
| + | |||
| + | </hidden> | ||
| AC代码=>[[https://codeforc.es/contest/1350/submission/79957224]] | AC代码=>[[https://codeforc.es/contest/1350/submission/79957224]] | ||
| 行 50: | 行 58: | ||
| 题意：t 次询问，每次给定长为 n 的正整数序列{a<sub>1</sub>,a<sub>2</sub>,...a<sub>n</sub>}和正整数 k。可以无数次对任意区间$[l, r]$进行如下操作：求其中位数（角标向下取整）并将区间内所有值变为中位数。问能否将此序列同化为k。 | 题意：t 次询问，每次给定长为 n 的正整数序列{a<sub>1</sub>,a<sub>2</sub>,...a<sub>n</sub>}和正整数 k。可以无数次对任意区间$[l, r]$进行如下操作：求其中位数（角标向下取整）并将区间内所有值变为中位数。问能否将此序列同化为k。 | ||
| - | 题解：数一下 k 在序列中出现了多少次，首先出现 0 次肯定是不行的。只有 1 个元素且等于 k 可行；只有 2 个元素时保证不等于 k 的元素大于 k 则可行；多个元素时从 2 到 n-1 遍历一次，任何相邻的三个数中只要有两个数大于等于 k 则可行。 | + | <hidden 思路：> |
| + | |||
| + | 数一下 k 在序列中出现了多少次，首先出现 0 次肯定是不行的。只有 1 个元素且等于 k 可行；只有 2 个元素时保证不等于 k 的元素大于 k 则可行；多个元素时从 2 到 n-1 遍历一次，任何相邻的三个数中只要有两个数大于等于 k 则可行。 | ||
| + | |||
| + | </hidden> | ||
| AC代码=>[[https://codeforc.es/contest/1350/submission/79960457]] | AC代码=>[[https://codeforc.es/contest/1350/submission/79960457]] | ||
| =====E===== | =====E===== | ||
| - | 不急 | + | 咕咕咕 |
| =====F===== | =====F===== | ||
| 没看，不补 | 没看，不补 | ||
2020-2021/teams/manespace/codeforces_round_641_div._2.1589630816.txt.gz · 最后更改: 2020/05/16 20:06 由 intouchables
