|
|
CF1768A Greatest Convex
代码实现
#include<iostream>
#include<cstring>
using namespace std;
using LL = long long;
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--){
int k;
cin >> k;
cout << k - 1 << &#39;\n&#39;;
}
}
CF1768B Quick Sort
代码实现
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
using LL = long long;
const int maxn = 1e5 + 5;
int a[maxn], b[maxn];
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--){
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> a;
b = a;
}
sort(b + 1, b + n + 1);
int len = n;
for(int i = 1, j = 1; i <= n; i++){
while(j <= n && a[j] != b) j++;
if (j <= n) j++;
else{
len = i - 1;
break;
}
}
cout << (n - len + k - 1) / k << &#39;\n&#39;;
}
}
CF1768C Elemental Decompress
分析
对于每个位置i,一定满足某个排列该位置的值为a_i,另一个位置该位置的值\le a_i.
模拟从大到小填入a_i的过程(逆序枚举保证之前贡献的位置后面的数都可以填入),模拟的过程中维护所有可以填数的位置.
如果当前a_i没在原序列中出现过,那么说明在两个排列中a_i都和比他大的元素填在一起,从两个排列可以填数的位置各自任取一个填入a_i即可.
如果a_i在原序列中出现了一次,那么显然可以把一个a_i填在a_i出现的位置,而另一个a_i可以一起填在这个位置,这样操作可以保证两个排列中可以填数的位置是相等的.
如果a_i在原序列中出现了两次,那么就把两个a_i填到这两个位置去,并且会贡献出两个可以填数的位置.
在模拟的过程中如果需要填数但是没有地方可以填或者某个数字出现了超过两次则无解.
代码实现
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;
const int maxn = 2e5 + 5;
int p[maxn], q[maxn];
vector<int> pos[maxn];
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
for(int i = 1; i <= n; i++) pos.clear();
for(int i = 1; i <= n; i++){
int x;
cin >> x;
pos[x].push_back(i);
}
bool success = 1;
vector<int> cand0, cand1;
for(int i = n; i >= 1; i--){
if (pos.size() > 2){
success = 0;
break;
}
if (pos.size() == 0){
if (cand0.empty() || cand1.empty()){
success = 0;
break;
}
p[cand0.back()] = i, cand0.pop_back();
q[cand1.back()] = i, cand1.pop_back();
}
else if (pos.size() == 1){
p[pos[0]] = i, cand1.push_back(pos[0]);
q[cand1.back()] = i, cand1.pop_back();
}
else{
p[pos[0]] = i, cand1.push_back(pos[0]);
q[pos[1]] = i, cand0.push_back(pos[1]);
}
}
if (!success) cout << &#34;NO&#34; << &#39;\n&#39;;
else{
cout << &#34;YES&#34; << &#39;\n&#39;;
for(int i = 1; i <= n; i++)
cout << p << &#34; \n&#34;[i == n];
for(int i = 1; i <= n; i++)
cout << q << &#34; \n&#34;[i == n];
}
}
}
CF1768D Lucky Permutation
分析
本题可能需要了解群论里的部分结论.
首先逆序对为1其实就是在1, 2, 3, \cdots, n单位排列的基础上交换任意一对相邻的数字.
此时排列一定有n - 2个自环和1个二元置换组成,并且这个二元置换里两个元素只差1.
一次交换操作可以造成两种效果
- 把一个大环拆成两个小环.
- 把两个小环合并成一个大环.
所以我们可以处理出初始排列中的所有置换环,设共有m个环,每个环的长度为c_i,令s = \sum\limits_{i = 1}^m(c_i - 1),则s就是把原排列变成1, 2, 3, \cdots, n单位排列需要的交换次数.
- 如果初始排列是1, 2, 3, \cdots, n单位排列,显然需要一次操作.
- 如果某个长度大于等于2的环中存在两个相邻的元素,则我们在拆这个存在相邻元素的环时可以最后留下一个相邻元素组成的二元环,所以答案为\sum\limits_{i = 1}^m(c_i - 1) - 1.
- 否则所有环中均不存在相邻元素,我们需要先把初始排列还原成单位排列然后任意交换一对相邻元素,答案为\sum\limits_{i = 1}^m(c_i - 1) + 1
代码实现
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;
const int maxn = 2e5 + 5;
int p[maxn];
bool v[maxn];
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> p, v = 0;
int sum = 0;
bool flag = 0;
for(int i = 1; i <= n; i++){
if (v) continue;
vector<int> a;
for(int j = i; !v[j]; j = p[j]){
a.push_back(j);
v[j] = 1;
}
sort(a.begin(), a.end());
sum += a.size() - 1;
for(int j = 1; j < a.size(); j++)
flag |= (a[j - 1] + 1 == a[j]);
}
if (sum == 0) cout << 1 << &#39;\n&#39;;
else if (flag) cout << sum - 1 << &#39;\n&#39;;
else cout << sum + 1 << &#39;\n&#39;;
}
}
CF1768E Partial Sorting
分析
首先最少操作次数只可能是0, 1, 2, 3,我们分别来讨论.
首先证明一下最少操作次数最大为3.
首先排序前2n个元素,此时前2n个元素中所有大于2n的元素一定都跑到了区间[n + 1, 2n]中.
此时所有大于2n的元素一定都在[n + 1, 3n]区间中,所以排序后2n个元素,一定可以让所有大于2n的元素都排到对应的位置上去.
然后我们再排一次前2n个元素排列就有序了.
所以任意排列经过这三步都会变得有序.
最少操作次数为0
显然只可能是1, 2, 3, \cdots, 3n单位排列这一种方案.
最少操作次数不超过1
有两种可能:
(1) 前n个元素已经排好了,即a_{1 \sim n} = \{1, 2, 3, \cdots, n\},只需要排序一次最后2n个元素.
(2) 后n个元素已经排好了,即a_{2n + 1 \sim 3n} = \{2n + 1, 2n + 2, 2n + 3, \cdots, 3n\},只需要排序前2n个元素.
注意两部分会有重复,需要容斥一下减去同时满足(1)和(2)的方案数.
此外,要得到最少操作次数等于1还需要减去最少操作次数为0的方案数(因为我们这里求得是不超过1的方案数).
最少操作次数不超过2
同样有两种可能:
(1) 小于等于n的所有元素已经在区间[1, 2n]中,此时只需排序前2n个元素就能让小于等于n的所有元素到对应的位置,然后再排序后2n个元素就能让排列有序.
(2) 类似地,大于2n的所有元素已经在区间[n + 1, 3n]中时也只需要两次操作.
同样根据容斥我们这里要减去同时满足(1)和(2)的方案数,这里满足(1)和(2)的方案数可以通过枚举小于等于n的数有多少个在区间[n + 1, 2n]来计算.
当然我们需要减去最少操作次数不超过1的方案数才能得到等于2的方案数.
最少操作次数等于3的方案数
只需用全部方案数减去不超过2的方案数即可.
代码实现
#include<iostream>
#include<cstring>
using namespace std;
using LL = long long;
const int maxn = 3e6 + 5;
LL fact[maxn], invfact[maxn];
int n, mod;
LL qpow(LL a, LL b, LL mod){
LL res = 1;
while (b){
if (b & 1) res = 1LL * res * a % mod;
a = 1LL * a * a % mod;
b >>= 1;
}
return res;
}
LL C(int a, int b){
return fact[a] * invfact % mod * invfact[a - b] % mod;
}
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> n >> mod;
fact[0] = invfact[0] = 1;
for(int i = 1; i < maxn; i++)
fact = fact[i - 1] * i % mod;
invfact[maxn - 1] = qpow(fact[maxn - 1], mod - 2, mod);
for(int i = maxn - 2; i >= 1; i--)
invfact = invfact[i + 1] * (i + 1) % mod;
LL ans = 0;
// x = 0
LL t0 = 1;
ans += 0 * t0 % mod;
ans %= mod;
// x = 1
LL t1 = (2 * (fact[2 * n] - 1) - (fact[n] - 1)) % mod;
ans += 1 * t1 % mod;
ans %= mod;
// x = 2
LL k = C(2 * n, n) * fact[n] % mod * fact[2 * n] % mod;
LL t2 = 2 * k % mod;
for(int i = 0; i <= n; i++){
t2 -= C(n, i) * C(n, n - i) % mod * fact[n] % mod *
C(2 * n - i, n) % mod * fact[n] % mod * fact[n] % mod;
t2 %= mod;
}
t2 -= t0 + t1;
t2 %= mod;
ans += 2 * t2 % mod;
ans %= mod;
// x = 3
ans += 3 * (fact[3 * n] - t0 - t1 - t2) % mod;
ans %= mod;
cout << (ans % mod + mod) % mod << &#39;\n&#39;;
}
CF1768F Wonderful Jump
分析
具体方法和证明见官方题解,这里做一些补充.
关键结论: 当满足\min\limits_{i \le k \le j}a_k \cdot (i - j)^2 > A \cdot (i - j)时,其中A表示a_i的最大值,一定不可能由从j转移到i,因为此时从一步一步转移一定花费代价更小.
式子化简后可得如果能够转移一定由i - j \le \frac{A}{\min\limits_{i \le k \le j}a_k}
设块长为len = \sqrt{n}.
当a_i \ge len时
i - j \le \sqrt{n},所以可转移的状态数量级为O(\sqrt{n})级别.
当a_i \le len时
还有一个性质,必须有\min\limits_{i \le k \le j}a_k = a_i或a_j才可以转移,否则从从最小值处切开分两次转移答案一定更优.
对于a_j为最小值我们可以用单调栈维护可能成为最小值的维护,不会超过O(\sqrt{n})个.
对于a_i为最小值的情况,我们可以直接暴力往前枚举,然后遇到a_j \le a_i就停止,均摊复杂度为O(\sqrt{n}).
这个均摊复杂度是如何计算的呢?其实很简单,对于每个位置和每个小于\sqrt{n}的值,每个位置向同一个值最多转移1次,假设有a_i, a_j, a_k其中a_i < a_j = a_k,那么i只会向j转移,不会再向后面值与a_i相等的地方转移.所以总的转移次数是O(n\sqrt{n}),均摊下来就是O(\sqrt{n})的.
代码实现
#include<iostream>
#include<cstring>
using namespace std;
using LL = long long;
const int maxn = 4e5 + 5, len = 650;
int a[maxn], stk[maxn];
LL f[maxn];
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
auto sqr = [](int x){
return 1LL * x * x;
};
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a;
memset(f, 0x3f, sizeof f);
f[1] = 0;
int top = 0;
cout << f[1] << &#39; &#39;;
stk[++top] = 1;
for(int i = 2; i <= n; i++){
int mn = a;
for(int j = i - 1; j >= max(1, i - len); j--){
mn = min(mn, a[j]);
f = min(f, f[j] + mn * sqr(i - j));
}
if (a <= len){
for(int j = i - 1; j >= 1; j--){
f = min(f, f[j] + a * sqr(i - j));
if (a[j] <= a) break;
}
}
for(int j = 1; j <= top; j++)
f = min(f, f[stk[j]] + a[stk[j]] * sqr(i - stk[j]));
if (a <= len){
while(top && a[stk[top]] >= a) top--;
stk[++top] = i;
}
cout << f << &#39; &#39;;
}
}
本文使用 Zhihu On VSCode 创作并发布
|
|
发表于 2023-1-8 14:36:41