Codeforces Round 633 (Div. 2)

可能是到目前为止最成功的一次 cf 了,下次要做到没人带我也这么强。

A. Filling Diamonds

题目描述

给定形如下图的形状,问用形如 $n=1$ 时的图形完全填充的方案数。

解法

模拟发现每种方案有且仅有一个竖着摆放的形状,答案即为 $n$ 。

代码

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;
int _,n;
int main() {
for(scanf("%d",&_);_;_--) {
scanf("%d",&n);
printf("%d\n",n);
}
return 0;
}

B. Sorted Adjacent Differences

题目描述

给定数组 $a$ 要求重排使得 $|a1 - a_2| \le |a_2 - a_3| \le \ldots \le |a{n-1} - a_n|$。

解法

最大的和最小的放一起,产生的差当然是最大的,直接放到最后,接着是次大值和次小值。

推一下就知道每个元素最后的位置是什么了,可以按照官方题解所说的确定中间位置之后一左一右就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int _,n,a[maxn];
int main(){
for(scanf("%d",&_);_;_--) {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
int m=(n+1)>>1;
for(int i=1;i<=n;i++){
printf("%d ",a[m]);
m+=i&1?i:-i;
}
printf("\n");
}
return 0;
}

C. Powered Addition

题目描述

给定数组 $a$,可以在第 $x$ 秒给 $a$ 中任意一段连续的数加上 $2^{x-1}$(或者不加),问至少多少秒后使得数组不递减。

解法

每次加 $a_i$ 的时候将连续的一段 $a_j \leq a_i (j>i)$ 全部也加上,判断是否不递减

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100005;
ll _,n,a[maxn],maxa,ans,j,k,sum;
int main() {
for(scanf("%lld",&_);_;_--) {
scanf("%lld",&n);
k=1,sum=ans=0,maxa=-0x3f3f3f3f;
for(int i=1;i<=n;i++) {
scanf("%lld",&a[i]);
while(a[i]+sum<maxa) {//加上 sum 还是不行,只能加更多
sum+=k,ans++;
if(k<=1e10-1) k=k<<1;//k = 2^{x-1}
else break;
}
maxa=maxa>a[i]?maxa:a[i];//更新当前一段已知最大值,之后的必须大于等于 maxa
}
printf("%lld\n",ans);
}
return 0;
}

D. Edge Weight Assignment

太神仙了,先gugugu

总结

这次比较明显的感受就是想法全是对的,这是思维得到训练的结果,但是实现起来非常复杂,还搞错了好几次,其实就是练少了。

文章作者: answerend42
文章链接: http://answerend42.github.io/2020/04/24/cf1339/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 answerend42的Blog