把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。
题目大意：
CF1553E Permutation Shift
题目大意：给一个长为n（3e5）的permutation和一个m（<=n/3），问是否存在k，使得原permutation在经过一个距离为k的旋转之后只需要m以内次数的两两交换就能变成递增序列，如果能的话输出所有可能的k。
解：
首先是常识：对于一个permutation，要将其通过两两交换来使得其变回増序列需要的交换次数等同于(N-原序列和增序列中对应建图形成的连通块数)。
证明：对于一个长度为n的闭环，我们需要n-1次交换来时期变为n个单独的连通块，而所谓的使原序列变为递增序列的本质其实就是把原序列变成n个单独的连通块，那么假设其能分成m个连通块，则每个连通块需要的交换次数都是len-1，总共的交换次数就是n-m。
但是本题来说k有N个，每个都要通过建图检验（复杂度为N）来计算的话实在是太过苛刻。
M<=n/3，这里肯定有问题，其实对于我们来讲，假设一共需要交换m次能回到原位（接下来我都用原位来表示増序列中每个数的位置），那么交换之前不在原位的数最多只有2m个，也就是说，至少需要有n-2*m个数是在原位的，在这里交换的次数最多是n/3，也就是说至少要有n/3个数在原位我们才能够保证成立。
而旋转k次之后在原位的数的数量我们可以预处理求出（即对于每个数，求出它需要多少步旋转来回到原位，用一个数组ksize来记录）
但即使如此，如何知道一共有多少个k呢？其实已经很清楚了，当ksize>n/3时才有成功的可能，m如果小于n/3的话这个阈值会更大，而所有ksize的总和是n，换句话说，即使m取到最大值，也只可能有3个合格的k出现，不合格的k会被ksize>=n-2m这个条件筛掉，而只有符合条件的k才去进行建图检验，复杂度为O(3n)。
非常优秀的题目，考验依靠数学来化简复杂度的能力，同时也考验了对于题目中常数范围的理解，算是范围压缩的经典题目。
代码
代码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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
#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>
#define ll long long
#define maxn 300005
#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 (a < b)swap(a, b);
if (b == 0)return a;
return gcd(b, a % b);
}
ll cpow(ll x, ll n) {
ll ans = 1;
while (n > 0) {
if (n & 1) ans = (ans * x) % mdl;
x = (x * x) % mdl;
n >>= 1;
}
return ans;
}
vector<int> tree[maxn];
bool vis[maxn];
int a[maxn],ksize[maxn];
void dfs(int n, int dad) {
vis[n] = 1;
inc(i, 0, tree[n].size()) {
int son = tree[n][i];
if (son == dad||vis[son]==1)continue;
dfs(son, n);
}
}
int cntnum(int n) {
int cnt = 0;
inc(i, 0, n) {
if (vis[i] == 0) {
dfs(i, -1);
cnt++;
}
}
return n - cnt;
}
vector<int> ans;
int main() {
cfast;
int t=1;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
inc(i, 0, n) {
ksize[i] = 0;
}
ans.clear();
inc(i, 0, n) {
cin >> a[i];
a[i]--;
if (a[i] <= i) {
ksize[i-a[i]]++;
}
else {
ksize[i + n - a[i]]++;
}
}
inc(k, 0, n) {
if (ksize[k] >= n - 2 * m) {
inc(i, 0, n) {
int mc = (i + n - k) % n;
tree[mc].push_back(a[i]);
tree[a[i]].push_back(mc);
}
int c = cntnum(n);
if (c <= m)ans.push_back(k);
inc(i, 0, n) {
tree[i].clear();
vis[i] = 0;
}
}
}
cout << ans.size() << " ";
inc(i, 0, ans.size()) {
cout << ans[i] << " ";
}cout << endl;
}
}
|
Copyright Notice: 此文章版权归EmiteInna所有，多看看吧。
