补题计划-CF DIv2.ABC题-1

这只是个test

CF Div2.

除了正常的学习算法以及每周一次的周赛,现在每天有时间就写写CF的div2.的前几题,具体是ABC这三题左右难度。遇到好题,以及不会的题目都会放在这里,每4场Div 2.放在一起。

Codeforces Round 987 (Div. 2)

B 题

中文题目

挺有意思的,很像冒泡排序,就是对于一个数,它与它后面一个数的差值等于 \(1\) 就交换,否则不动,判断是否能成为一个有序的。

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
#include<bits/stdc++.h>

using namespace std;
const int maxn = 200010;
int a[maxn];

int main()
{
int T;cin>>T;
while(T--){
int n;scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d",&a[i]);}
while(1){
int cnt = 0;
for(int i=1;i<n;i++)
if(a[i] - a[i+1] == 1) swap(a[i],a[i+1]),cnt ++;
if(cnt == 0) break;
}
int flag = 1;
for(int i=1;i<=n;i++){
if(a[i] != i){flag = 0;}
}
cout<<(flag == 1 ? "YES" : "NO")<<endl;
}
return 0;
}

C 题

中文题面

刚开始想的是对于 \(n\) 分成奇数与偶数判断。偶数非常简单,就是每个相邻就行了。

如果是奇数,那么一定会存在三个一样的数字,也就是符合 \(x + y = z\)\(x,y,z\) 都是完全平方数,我列了几项,发现确实存在。(\(9,16,25\))就符合。但是具体怎么实现是根本想不到。

题解的想法非常妙就是可以说是递归实现。如果是 \(n < 25\) 的偶数就一定不存在方案。大于 \(25\) 后可以递归实现,就是将小于25的部分分成 \(1(14个)\dots 16 (15个) \dots 25\),后面的 \(15\) 可以和后面 \(25\) 后的一个组一个,间距也是 \(25\) 个.

在实现是前面的 \(25\) 个直接打表。

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
#include<bits/stdc++.h>

using namespace std;

int main()
{
int T;
cin>>T;
while(T--){
int n;
scanf("%d",&n);
if(n % 2 == 1 && n <= 25){cout<<(-1)<<endl;continue;}
if(n % 2 == 0){
for(int i=1;i<=n/2;i++)
cout<<i<<" "<<i<<" ";
cout<<endl;
continue;
}
else{
cout<<"1 3 3 4 4 5 5 6 6 1 2 7 7 8 8 9 9 10 10 11 11 12 12 13 13 1 2 ";
for(int i=14;i<=n/2;i++) cout<<i<<" "<<i<<" ";
cout<<endl;
}
}
return 0;
}

Codeforces Round 986 (Div. 2)

B 题

中文题目

首先观察到如果 \(b = 0\) 时,整个数列是一个常数列 \(c\)

通过分析样例以及一些其他情况可以想到 \(c \geq n - 2\) 是可以变成排列,其中 \(c = n-2\) 时步骤为 \(n-1\),其他时候为 \(n\) , 如果小于 \(n-2\) 就不存在,可以在纸上模拟模拟就了解了。

如果 \(b \neq 0\),那么就更一般的情况,整个数列是一个等差数列 \(b \times (i - 1) + c\),判断出来小于 \(n\) 的数字不贡献操作数。

本来想着一个数一个数的列举,但是好像超时了,就直接改成了直接算个数,计算每个的时间复杂度为 \(O(1)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>

using namespace std;
map<int,bool> m;

int main()
{
int T;
cin>>T;
while(T--){
m.clear();
long long n,b,c;
scanf("%lld %lld %lld",&n,&b,&c);
if(b == 0){
if(c >= n) cout<<n<<endl;
else if(c >= n-2) cout<<n-1<<endl;
else cout<<(-1)<<endl;
continue;
}
long long cnt = ceil(1.0*(n-c)/b);
cout<<(n - (cnt <= 0 ? 0 : cnt))<<endl;
}
return 0;
}

C 题

中文题目

这道题本来是想用线段树来解决的,但是想了想还是想不到,感觉超越我的程度了,就看了看 Hint,就只是想到了用前缀和与类似于滑动窗口的类型解决,但是实现起来好像挺难的就放弃了,没想到题解的思路能懂,但是实现方法感觉有点看不懂了,就直接copy了一份题解(汗。

就是用 \(px_i\) 来表示从 \(1 \sim i\) 时能够分的最大生物数,\(py_j\) 表示从 \(j \sim n\) 时能够分的最大生物数。

我们可以让一个区间分成三份 \(1 \sim i \sim j \sim n\),我们枚举 \(i \sim j\) 也就是生物吃的区间,那么剩下两个区间就是爱丽丝能所在区间。

\(px_i\)\(py_i\) 实现方法,就是用双指针的方式,刚开始都在开头,如果这个区间总和不到 \(v\) ,那么后面一个指针往后移动,使窗口更大一个,如果大于 \(v\) ,就可以更新了,\(px_{end} = px_{start} + 1\)。每次更新前面的。

能力有限,也就能理解到这了。

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
#include<bits/stdc++.h>

using namespace std;

const long long maxn = 200010;
long long a[maxn],px[maxn],py[maxn],sum[maxn];


int main()
{
long long T;
cin>>T;
while(T--){
long long n,m,v;
scanf("%lld %lld %lld",&n,&m,&v);
memset(a,0,sizeof(a));
memset(py,0,sizeof(py));
memset(px,0,sizeof(px));
for(long long i=1;i<=n;i++)
scanf("%d",&a[i]);

for(long long i=1;i<=n;i++)
sum[i+1] = sum[i] + a[i];

long long start = 1,end = 1,ans = 0;
for(start = 1;start <= n;start ++){
while(end <= n && ans < v){
ans += a[end];
++ end;
px[end] = max(px[end],px[end-1]);
}
if(ans >= v){
px[end] = px[start] + 1;
}
ans -= a[start];
}

for(long long i=1;i<=n;i++)
px[i] = max(px[i] , px[i-1]);
reverse(a+1,a+n+1);

start = 1,end = 1,ans = 0;
for(start = 1;start <= n;start ++){
while(end <= n && ans < v){
ans += a[end];
++ end;
py[end] = max(py[end],py[end-1]);
}
if(ans >= v){
py[end] = py[start] + 1;
}
ans -= a[start];
}
for(long long i=2;i<=n+1;i++)
py[i] = max(py[i] , py[i-1]);

reverse(a+1,a+n+1);
reverse(py+1,py+n+2);

// for(long long i=1;i<=n;i++) cout<<py[i]<<endl;

if (px[n+1] < m) {
cout << "-1\n";
continue;
}

long long tmp = 0,j = 1;
ans = 0;
for(long long i=1;i<=n;i++){
while(j <= n && px[i] + py[j + 1] >= m) ++j;
if(px[i] + py[j] >= m)
ans = max(ans,sum[j]-sum[i]);
}
cout<<ans<<endl;
}
return 0;
}

Codeforces Round 983 (Div. 2)

B 题

中文题目

这题还挺有意思的,给你一个奇数列,从 \(1 \sim n\),最后让你求能不能通过合理的划分找到给定的 \(k\),使得 \(k\) 为中位数。

刚开始想的是用线段树维护每一段的中位数,但是看了看线段树的定义发现好像不太行,因为每次递归就只能是奇数,没办法变成连续的一段区间,最主要是中位数不能维护。

就开始想那个第 \(k\) 个数一定在子数组中一定是中位数,这样才能被选出去,那么在子数组形成的中位数数组中也一定是中位数。那么最简单可以想到直接划分为三个子数组,需要的数在中间,其他的在两边。这样就一定可以。

对了,还需要中位数一定不能再左右断点,特判就好。

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
#include<bits/stdc++.h>

using namespace std;

int T;

int main()
{
cin>>T;
while(T--){
int n,k;
cin>>n>>k;
if(n == 1 && k == 1){cout<<1<<endl<<1<<endl;continue;}
if(k == 1 || k >= n){cout<<(-1)<<endl;continue;}
int start = k,end = k;
while(start >= 1 && end <= n){
int lenl = start - 1,lenr = n - end;
if(lenl % 2 != 0 && lenr % 2 != 0){break;}
else{start --;end ++;}
}
if(start != 1 && end != n){
cout<<3<<endl;
cout<<1<<" "<<start<<" "<<end+1<<endl;
}
else{
cout<<1<<endl;
cout<<1<<endl;
}
}
}

C 题

中文题目

这道题感觉就差一点点就推出来了,但是临门一脚没想到。

题目主要是让你求出使得 \(a_x + a_y \geq a_z\) 的数组的最小操作次数,每次操作都可以让任意一个 \(a_i\) 变成数组里任意一个数。

可以想想上限,首先我们可以让除了\(a_1,a_n\) 的所有数变成 \(a_n\) 这样就全部成了,所以答案最多为 \(n - 2\)

首先想到可以先排序,这样就有序了,对于每个 \(i\) 用双指针的方法,判断出大于 \(a_i\) 的最小和的的两个,这样我们只需要改其他的,这些的在区间因为是有序的,中间的必然符合,那么不用改变。

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
#include<bits/stdc++.h>

using namespace std;

vector<int> a;
int T;

int main()
{
cin>>T;
while(T--){
a.clear();
int n;
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
a.push_back(x);
}
sort(a.begin(),a.end());

int ans = n - 2;
int l = 0;
for(int r=2;r < n;r++){
if(r - l >= 2 && a[l] + a[l+1] <= a[r]) l++;
ans = min(ans,n - (r - l + 1));
}
cout<<ans<<endl;
}
return 0;
}

Codeforces Round 982 (Div. 2)

B 题

中文题目

这道题感觉不像 1100 的,感觉看懂题都挺难的。当时看完这个题目一点思路都没有, 还是看了题解之后才理解题目让我干啥的,看了评论区的发现有许多人也说这次的 B 有点怪,而且感觉题目没有说清楚到底要干啥。

定义一种排序叫斯大林排序,就是如果一个数小于它前面的数,则删掉它,直到按照非递减顺序

定义一个数组为脆弱数组,就是对任意子序列任意使用这种排列可以使整个数组递减。

用贪心,当第一个为最大时,那我一定可以通过从他到倒数第二个用一次斯大林排序变成递减序列。 所以他后面比他大的我要全部提前删掉

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
#include<bits/stdc++.h>

using namespace std;
const int maxn = 10000;
vector<int> v;

int main()
{
int T;
cin>>T;
while(T--){
int n;cin>>n;
v.clear();
v.push_back(0);
for(int i=1;i<=n;i++){
int x;cin>>x;
v.push_back(x);
}

int ans = 999999;
for(int i=1;i<=n;i++){
int sum = i - 1;
for(int j=i+1;j<=n;j++)
if(v[i] < v[j]) sum ++;
ans = min(ans,sum);
}
cout<<ans<<endl;
}
return 0;
}

C 题

中文题目

这道题我只会的暴力 \(O(n^2)\),再进一步就想不出来了。只好看题解,才发现题解用了数组当前大小来DFS。

正解应该是,将每个 \(a_i\) 能够加零的数组当前大小给存起来,然后从长度为 \(n\) 开始DFS,在DFS区间内取最大值。

时间复杂度为(估计) \(O(n \log n)\)

对了注意 vis 数组,要用 map 实现,因为数组没有那么大 \(10^9\) 左右(就因为这个改了半天)。

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
#include<bits/stdc++.h>

using namespace std;
const int maxn = 300010;
long long a[maxn];
map<long long,vector<long long>> mp;
map<long long,bool> vis;
long long ans = 0;

void dfs(long long t){
vis[t] = 1;
ans = max(ans,t);
for(auto it : mp[t]){
if(!vis[t + it - 1]){
dfs(t + it - 1);
}
}
return;
}

int main()
{
int T;cin>>T;
while(T--){
long long n;
cin>>n;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);

vis.clear();
mp.clear();
for(int i=2;i<=n;i++)
mp[a[i] + i - 1].push_back(i);
ans = 0;
dfs(n);
cout<<ans<<endl;
}
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!