把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。
题目大意：
CF1548B Intergers Have Friend
题目大意：一个数组（2e5），要求其最大的一个子段，使得存在一个整数m>=2，该段内所有数模m后得到的结果相同。
解：
通过观察（猜测）很容易发现，该子段的差分数组gcd一定大于1，实际上这个gcd就是整数m，于是问题就转化成了求得一个最大子段，使得该段gcd>=2。
关于这题本人有一个惨烈的历程，首先想到了正解，后来t了，以为是这个解法的问题，之后去写了线段树，然后线段树是真正的t了，但我以为是我树的问题，于是坐牢一个小时，看题解发现说是可以用线段树和st表，仔细想想st表确实可以（但我不会？），我坚持线段树是不行的，于是去看人家的代码，点开榜一代码一看，草这不是我最开始的做法吗？然后发现自己vector没开long long，给负数求gcd导致t了……然后找了好久也没找到线段树做法，百思不得其解，后来发现官方一共有54个点，我的线段树t了第57个点，欧亨利式结尾了属于是。
那么这个正确的解法是什么呢？如果暴力地去求区间gcd肯定是不行的，但是我们可以递推的去求，因为一旦对于一个数来讲，如果它和前面某段区间的gcd为1，那么这段即使延伸到后面，它的gcd也一定为1了，因此我们可以果断地抛弃这段，而如果它和前面这段的gcd不为1，假设其为g，显然如果原来之前那段的gcd为f，那么g=f/k，这里被舍弃的这个k由于无法通过当前这个数传递到后面，也可以作废，换句话说，对于每个数，传递到下一个数的可能的gcd数量一定<=前面传来的gcd数量（因为可能会出现重复和1）+1，+1是因为自己本身一定是作为一个数传递到下面的gcd的，但是这个数本身一定是g的倍数，所以对于下一个数a[i]来讲，如果它和g的gcd大于1，那么这个新的gcd一定等于它和上一个a[i-1]的gcd，而如果不是这样的话，它虽然有可能是和a[i]的gcd>1，但还是绝对不可能和g跟a[i]产生两个不同的gcd，所以每个数传递到后面的gcd数量一定<=2，我可以直接用vector记录下这些gcd，滚不滚动都无所谓，这样解法就是O(nlog1e18)了。
而线段树的解法是O(2nlognlognlog1e18)，st表是O(nlognlog1e18)，全然不如这个dp做法。
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
#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>
#include <fstream>
#include <unordered_map>
#define ll long long
#define maxn 200005
#define mdl 1000000007
#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 pii pair<int,int>
#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;
#define endl '\n'
#define pi 3.141592657
using namespace std;
ll gcd(ll a, ll b) {
if (b == 0)return a;
return gcd(b, a % b);
}
ll a[maxn], cf[maxn];
vector<ll> nums[maxn];
map<pll, ll> dp;
unordered_map<ll, ll> vis;
int main() {
cfast;
int t;
cin >> t;
while (t--) {
dp.clear();
int n;
cin >> n;
inc(i, 0, n) {
nums[i].clear();
cin >> a[i];
if (i > 0) {
cf[i] = abs(a[i] - a[i - 1]);
}
}
if (n == 1) {
cout << 1 << endl;
continue;
}
ll ans = 0;
inc(i, 1, n) {
vis.clear();
int len = nums[i - 1].size();
inc(j, 0, len) {
ll g = gcd(nums[i - 1][j], cf[i]);
if (g > 1 && vis[g] == 0) {
vis[g] = 1;
nums[i].push_back(g);
pll p, pf;
p.first = i, p.second = g;
pf.first = i - 1, pf.second = nums[i - 1][j];
dp[p] = max(dp[p], dp[pf] + 1);
ans = max(ans, dp[p]);
}
}
if (vis[cf[i]] == 0) {
nums[i].push_back(cf[i]);
}
pll p;
p.first = i, p.second = cf[i];
if (cf[i] == 1)dp[p] = max(dp[p], 0ll);
else dp[p] = max(dp[p], 1ll);
ans = max(ans, dp[p]);
}
cout << ans + 1 << endl;
}
}
|
Copyright Notice: 此文章版权归EmiteInna所有，多看看吧。
