Codeforces Round 1045 (Div. 2)
2025-09-09 10:30:59
# codeforces
Codeforces Round 1045 (Div. 2)
A. Painting With Two Colors
注意到blue和red重叠时仍为blue，而cell个数n总共可以分为奇数个和偶数个。可以根据奇偶型考虑对称分布。
-
n为奇数时，
- a<=b时，如果b为奇数，显然blue可以放在cell中间位置，并且可以覆盖red区域()；如果b为偶数，blue无法满足对称条件。
- a>b时，因为red和blue重叠区域仍为blue，a相对于b多出来的区域要满足对称分布就需要要求a为奇数，同时重叠区域也要满足对称就需要要求b也为奇数。
-
n为偶数时，同上。
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
|
#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false),cin.tie(nullptr)
#define c_y cout<<"YES"<<endl
#define c_n cout<<"NO"<<endl
typedef long long ll;
using namespace std;
const int N = 2e5+10;
int main() {
int t;
scanf("%d",&t);
while(t--) {
int n,a,b;
cin>>n>>a>>b;
if(n%2) {
if(a<=b && b%2) c_y;
else if(a%2 && b%2) c_y;
else c_n;
}
else {
if(a<=b && !(b%2)) c_y;
else if(!(a%2) && !(b%2)) c_y;
else c_n;
}
}
return 0;
}
|
B. Add 0 or K
不会，急死我了。
用的mod (k+1)，表示总共添加的数量，c=0为没添加，因为最多k次操作，所以。
考虑array中的某一项，
加上 后正好被(k+1)整除，其它项也满足，且因式(k+1)>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
| #include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false),cin.tie(0)
#define c_y cout<<'YES'<<endl
#define c_n cout<<'NO'<<endl
typedef long long ll;
const int N = 1e5+10;
int main()
{
IO;
int t;
cin>>t;
while(t--){
int n,k;
ll a[N],m;
cin>>n>>k;
for(int i=0;i<n;i++) {
cin>>a[i];
a[i]+=(a[i]%(k+1))*k;
}
for(int i=0;i<n;i++) cout<<a[i]<<' ';
cout<<endl;
}
return 0;
}
|
C. Even Larger
索引从1开始，并且任意subarray中的所有偶数索引元素之和要大于奇数索引元素之和，求操作次数。
为了满足偶数索引元素之和要大于奇数索引元素之和，减去的必定是奇数索引位置上的数，这样才能更加确保大于。
考虑极限情况：三个连续位置的数并且中间为偶数索引，两边为奇数索引，如果其满足条件，那么向后延伸其它subarray也会满足,对奇数索引位置的数据进行更新时要对右边的奇数索引位置先更新(该位置的数据会在后面继续用到，尽可能先更新)。为了达到所有的偶数索引位置都有右奇数索引邻居，对n为偶数的末尾追加a[++n]=0便于统一处理。
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
|
#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false),cin.tie(nullptr);
typedef long long ll;
using namespace std;
const int N = 2e5+10;
int main() {
int t;
scanf("%d",&t);
while(t--) {
int n;
ll a[N];
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
if(!(n%2)) a[++n]=0;
ll ans=0;
for(int i=2;i<=n-1;i++){
if(!(i%2) && a[i]<a[i-1]+a[i+1]) {
ans+=a[i-1]+a[i+1]-a[i];
a[i+1]=max((ll)0,a[i]-a[i-1]);
}
}
printf("%lld\n",ans);
}
return 0;
}
|
null
后面不会
