把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。
题目大意：
CF 1614D1 Divan and Kostomuksha (easy version)
题目大意：给一个数组，长度为n（级别为1e5），每个数字范围在（1-5e6），现在你可以任意改变数组的顺序，使得∑gcd(a1,a2,…,ai)最大，求这个最大值。
解：
看见gcd就一定要想到倍数，想到倍数就想到了之前那个O(1+1/2+…+1/n)的暴力算法，一看数据5e6，好像有点惊险，但好在常数几乎等于没有并且数据只有一组，感觉可行。
显而易见，如果用g[i]表示前i个数的gcd的话，g[i]随着i的增加一定是减小的，而一旦g[i]降低到一个值，使得i之后的数都无法继续降低这个值的时候，后面的排列方式就已经无所谓了。
换句话说，我的gcd是不断降低的，并且降低只能从它的倍数到它自己，那么就存在子问题的转移，我们知道，对于一个数a，如果它是从ak转来的，那么除了ak的倍数以外，所有a的倍数与它的gcd都是a，其他数则暂时不谈，因为他们会导致gcd继续下降，这样我们就知道了：对于gcd等于a时g[i]数组的前缀和可以通过ak转移得到，那么复杂度是多少呢？就是那个O(1+1/2+…+1/n)了。
原数组中数字的顺序已经无所谓了，但我需要记录每个数字出现的个数，如果用dp[i]表示当前g[i]为i并且g[i+1]不等于g[i]时g的前缀和的话，我们首先需要判一下它自己没有转移来源的情况，也就是它作为g[i]第一个的情况dp[i]=cnt[i]i，之后对于每个倍数已经处理过的数来讲，dp[i]=max(dp[ik]+i(cnt[i*k]-cnt[i]))。
最后我们要求的是g[i]达到最小值时的前缀和，但由于这个值并不确定，而我又嫌麻烦，所以我在原有的数里多添加一个1，这样我g[i]的最小值就一定是1了，最后我只要在答案里减去一个1就行。
Gcd相关的dp题一定要想到倍数，暴力算法是在1e6范围内都能500ms暴杀的，本题的5e6范围实际上也只会跑到2500ms，因为只有一组样例，我就直接跑完了。
嗯，优点是无论n多大跑得都一样快，缺点是无论n多小跑得都一样慢，哈哈，一个样例2.5秒，交一次等几分钟，不愧是我。
补充hard version,就是把5e6改成了2e7，原来的筛法直接寄了，改为用类似欧筛的素数筛法，不同的是要把素数放在循环最外围，目的是保证筛的时候不会出现同一个数的两个不同路径添加两次的情况，之后的结果处理同样用素数处理，没什么细节。
想到gcd就想到倍数，想到倍数就想到素数，想到素数就想到……
再想想吧。
代码
代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 200005
#define mdl 998244353
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(int i=0;i<n;i++)a[i]=m;
using namespace std;
ll a[maxn], cnt[20000005], dp[20000005];
ll is_prime[20000005], prime[20000005];
int Eratosthenes(ll n) {
ll p = 1;
for (ll i = 0; i <= n; ++i) is_prime[i] = 1;
is_prime[0] = is_prime[1] = 0;
for (ll i = 2; i <= n; ++i) {
if (is_prime[i]) {
prime[p++] = i;
if (i * i <= n)
for (ll j = i * i; j <= n; j += i)
is_prime[j] = 0;
}
}
return p;
}
int main() {
cfast;
int era = Eratosthenes(20000005);
int n;
cin >> n;
inc(i, 0, n) {
cin >> a[i];
cnt[a[i]]++;
}
cnt[1]++;
for (ll j = 1; j < era; j++) {
for (ll i = 2e7 / prime[j]; i >= 1; i--) {
cnt[i] += cnt[i * prime[j]];
}
}
ll ans = 0;
for (ll i = 2e7; i >= 1; i--) {
dp[i] = cnt[i] * i;
for (ll j = 1; i * prime[j] <= 2e7; j++) {
dp[i] = max(dp[i * prime[j]] + i * (cnt[i] - cnt[i * prime[j]]), dp[i]);
}
}
cout << dp[1] - 1;
}
|
Copyright Notice: 此文章版权归EmiteInna所有，多看看吧。
