2020-2021:teams:manespace:codeforces_642_div2
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:codeforces_642_div2 [2020/05/15 17:23] quantumbolt |
2020-2021:teams:manespace:codeforces_642_div2 [2020/05/16 18:00] (当前版本) iuiou |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| + | ===== codeforces 641 (div2) ===== | ||
| + | ==== A ==== | ||
| - | <HTML><ul></HTML> | + | 题意：给定一个数n，经行k次操作，每次将n最小的非1约数加在n上。 |
| - | <HTML><li></HTML><HTML><p></HTML>A<HTML></p></HTML> | + | |
| - | <HTML><ul></HTML> | + | |
| - | <HTML><li></HTML>题意：给一个数$n$ ，进行$k$次运算 运算规则，得到$n$除了1之外能够整除$n$的最小数字，然后将结果$f(n)$加到$n$上，在经过k次运算，得到最终结果<HTML></li></HTML> | + | |
| - | <HTML><li></HTML>思路：将$n$分为偶数和奇数两部分，如果$n$为偶数,$f(n)$2，$n+f(n)$也是偶数，之后的迭代就直接加$2$就行了，如果$n$为奇数，有两种情况，第一，他为质数，第二，他的$f(n)$为质数，但是无论如何，他在一次迭代后得到的数都是偶数，然后再用一的情况就行了。<HTML></li></HTML> | + | |
| - | <HTML><li></HTML>代码：<HTML></li></HTML><HTML></ul></HTML> | + | |
| - | <code cpp> | + | 解：对于奇数加上最小约数后变偶数(素数当然也是奇数，所以同理)，最小约数为2，而对于偶数最小约束一直是2。需要做的就是O(√n)的时间复杂度下处理出最小非1约数即可。 |
| - | #include <bits/stdc++.h> | + | |
| - | using namespace std; | + | |
| - | int sdiv(int n){ | + | |
| - | for(int i = 2; i <= sqrt(n); i++){ | + | |
| - | if(n % i == 0) return i; | + | |
| - | } | + | |
| - | return n; | + | |
| - | } | + | |
| - | int main(){ | + | |
| - | int n; | + | |
| - | scanf("%d",&n); | + | |
| - | while(n--){ | + | |
| - | int k, t; | + | |
| - | scanf("%d%d",&k,&t); | + | |
| - | if(sdiv(k) % 2 == 1){ | + | |
| - | k += sdiv(k); | + | |
| - | k += (t-1)*2; | + | |
| - | } | + | |
| - | else | + | |
| - | { | + | |
| - | k += t *2; | + | |
| - | } | + | |
| - | printf("%d\n",k); | + | |
| - | } | + | |
| - | return 0; | + | |
| - | } | + | |
| - | </code><HTML></li></HTML> | + | |
| - | <HTML><li></HTML><HTML><p></HTML>B<HTML></p></HTML> | + | |
| - | <HTML><ul></HTML> | + | |
| - | <HTML><li></HTML><HTML><p></HTML>题意：给你一串数$s$<html><sub></html>$1$<html></sub></html>,$s$<html><sub></html>$2$<html></sub></html>,$s$<html><sub></html>$3$<html></sub></html>,$\ldots$,$s$<html><sub></html>$n$<html></sub></html>. 如果满足下标$i$<html><sub></html>$j$<html></sub></html>,$i$<html><sub></html>$j+1$<html></sub></html>满足$i$<html><sub></html>$j$<html></sub></html><$i$<html><sub></html>$j+1$<html></sub></html>并且有$s$<html><sub></html>$i$<html><sub></html>$j$<html></sub></html><html></sub></html> <$s$<html><sub></html>$i$<html><sub></html>$j+1$<html></sub></html><html></sub></html> .则称这样的安排是美的，题目要你找出一串序列中最长的，具有美感的数列长度。<HTML></p></HTML><HTML></li></HTML> | + | |
| - | <HTML><li></HTML><HTML><p></HTML>题解：不多bb<HTML></p></HTML><HTML></li></HTML> | + | |
| - | <HTML><li></HTML><HTML><p></HTML>代码：<HTML></p></HTML><HTML></li></HTML> | + | |
| - | <HTML><li></HTML><code cpp> | + | |
| - | # include <bits/stdc++.h> | + | |
| - | using namespace std; | + | ==== B ==== |
| - | void solve() { | + | 题意：大致意思是要你从一段序列中选择一段不一定要连续的子列，使其满足上升且，下标满足，i<j且i|j。 |
| - | int n; | + | |
| - | cin >> n; | + | |
| - | vector <int> a(n + 1), dp(n + 1); | + | |
| - | for (int i = 1; i <= n; i++) { | + | |
| - | cin >> a[i]; | + | |
| - | } | + | |
| - | int answer = 0; | + | |
| - | for (int i = 1; i <= n; i++) { | + | |
| - | int mx = 0; | + | |
| - | for (int j = 1; j * j <= i; j++) { | + | |
| - | if (i % j == 0) { | + | |
| - | if (a[j] < a[i]) mx = max(mx, dp[j]); | + | |
| - | if (a[i / j] < a[i]) mx = max(mx, dp[i / j]); | + | |
| - | } | + | |
| - | } | + | |
| - | dp[i] = mx + 1; | + | |
| - | answer = max(answer, dp[i]); | + | |
| - | } | + | |
| - | cout << answer << endl; | + | |
| - | } | + | |
| - | int main() { | + | 解：明显是dp，转移也不是很难，从1到n遍历一遍，然后再分别枚举倍数，复杂度O(n√n) |
| - | int tt = 1; | + | |
| - | cin >> tt; | + | |
| - | while (tt--) | + | |
| - | solve(); | + | |
| - | } | + | |
| - | </code><HTML></li></HTML><HTML></ul></HTML> | + | |
| - | <HTML></li></HTML> | + | |
| - | <HTML><li></HTML><HTML><p></HTML>C<HTML></p></HTML> | + | |
| - | <HTML><ul></HTML> | + | |
| - | <HTML><li></HTML>题意：给你一串数$s$<html><sub></html>$1$<html></sub></html>,$s$<html><sub></html>$2$<html></sub></html>,$s$<html><sub></html>$3$<html></sub></html>,$\ldots$,$s$<html><sub></html>$n$<html></sub></html>. 先算这串数的lcm，再算这串数的 gcd。<HTML></li></HTML> | + | |
| - | <HTML><li></HTML>题解：开始没仔细思考就直接暴力，直接按题意来算，提交后就后悔了，暴力肯定会超时的啊，后来想到了STL大法，然后就过了。<HTML></li></HTML> | + | |
| - | <HTML><li></HTML>代码：<HTML></li></HTML><HTML></ul></HTML> | + | |
| - | <code cpp> | + | 借着代码解释一下 |
| - | #include <bits/stdc++.h> | + | <code c++> |
| + | for(int i=1;i<=n;i++) | ||
| + | { | ||
| + | for(int j=1;i*j<=n;j++) | ||
| + | { | ||
| + | if(a[i]<a[i*j]) dp[i*j]=max(dp[i*j],dp[i]+1),ans=max(ans,dp[i*j]); | ||
| + | else continue; | ||
| + | } | ||
| + | } | ||
| + | </code> | ||
| - | using namespace std; | + | ==== C ==== |
| + | 题意：大致意思是，给定一段序列，然后任取两个数取其最小公倍数，然后放入新序列，问将所有情况取遍后，那整个序列的最大公约数。 | ||
| - | int main() { | + | 解：数论……脑阔疼…… |
| - | int n; | + | |
| - | cin >> n; | + | **官方版**：听说巨佬推出公式，<del>反正我是不会推</del>，对于序列{a<sub>i</sub>}(1≤i≤n),有一个公式为：gcd({a<sub>i</sub>,a<sub>j</sub>})== lcm{a<sub>i</sub>,gcd(a<sub>j</sub>)}(1≤j≤n且j≠i)则这里a<sub>j</sub>取遍所有可能情况，这样我们就可以，预处理出，gcd的前缀，然后再求gcd。 |
| - | vector<int> a(n); | + | |
| - | for (int i = 0; i < n; i++) { | + | **暴力版**:太难了，我只会暴力……记过一系列简单计算，不难发现，结果即为，将所有数的素因子集合起来，筛选出在序列中出现过至少n-1次的素因子(否则答案中一定不存在)，对于所有满足条件的素因子i，遍历一遍序列求出序列所有数中素因数分解式中i的指数，取第二大的，则答案的素因数分解中一定存在这个项。接下来线性筛暴力筛出所有素数然后暴力循环找即可。 |
| - | cin >> a[i]; | + | |
| - | } | + | ==== D ==== |
| - | vector<int> pref(n + 1); | + | 题意：给一段序列，给定一个数k，操作为：每次取一段区间，求出区间中位数，将区间所有数变成那个数，问能不能全刷成给定的数。 |
| - | for (int i = 0; i < n; i++) { | + | |
| - | pref[i + 1] = __gcd(pref[i], a[i]); | + | |
| - | } | + | |
| - | vector<int> suf(n + 1); | + | |
| - | for (int i = n - 1; i >= 0; i--) { | + | |
| - | suf[i] = __gcd(suf[i + 1], a[i]); | + | |
| - | } | + | |
| - | long long ans = 1; | + | |
| - | for (int i = 0; i < n; i++) { | + | |
| - | int x = __gcd(pref[i], suf[i + 1]); | + | |
| - | ans = ans / __gcd(ans, (long long) x) * x; | + | |
| - | } | + | |
| - | cout << ans << '\n'; | + | |
| - | return 0; | + | |
| - | } | + | |
| - | </code><HTML></li></HTML> | + | |
| - | <HTML><li></HTML><HTML><p></HTML>D<HTML></p></HTML> | + | |
| - | <HTML><ul></HTML> | + | |
| - | <HTML><li></HTML>题目：https:%%//%%codeforces.com/contest/1350/problem/D<HTML></li></HTML> | + | |
| - | <HTML><li></HTML>题解：哦时间不够了，没做完，提交了也没过。。<HTML></li></HTML> | + | |
| - | <HTML><li></HTML>咕咕中，会补的，别催了。<HTML></li></HTML><HTML></ul></HTML> | + | |
| - | <HTML></li></HTML> | + | |
| - | <HTML><li></HTML><HTML><p></HTML>E<HTML></p></HTML> | + | |
| - | <HTML><ul></HTML> | + | |
| - | <HTML><li></HTML>题目：https:%%//%%codeforces.com/contest/1350/problem/E<HTML></li></HTML> | + | |
| - | <HTML><li></HTML>咕咕中，会补的，别催了。<HTML></li></HTML><HTML></ul></HTML> | + | |
| - | <HTML></li></HTML> | + | |
| - | <HTML><li></HTML><HTML><p></HTML>F<HTML></p></HTML> | + | |
| - | <HTML><ul></HTML> | + | |
| - | <HTML><li></HTML>题目：https:%%//%%codeforces.com/contest/1350/problem/F<HTML></li></HTML> | + | |
| - | <HTML><li></HTML>咕咕中，会补的，别催了。<HTML></li></HTML><HTML></ul></HTML> | + | |
| - | <HTML></li></HTML><HTML></ul></HTML> | + | |
| + | 解：找规律的题，找不出来就罚坐(<del>真毒瘤</del>)，大致我们要判定这样一件事情，只有一个数，判定是不是那个数，给许多数，若序列中都不存在那个数，明显不满足，若满足，则是否存在三个数(两个数就判定两个数),满足有两个数大于等于k。 | ||
2020-2021/teams/manespace/codeforces_642_div2.1589534627.txt.gz · 最后更改: 2020/05/15 17:23 由 quantumbolt
