还是很开心的，第一次CF打出来D题，嘎嘎上132分，目前1584分，紫名指日可待。
A.Red Versus Blue
题目描述：
/1.png)
题目分析
知道双方赢球场次，要求构造一个输赢序列使得总比赛中最大连赢场数最小，即给定两种字符及个数，输出一个字符串使得由相同字符构成的子串最短。
首先题目给定了B的数目严格小于R，那么最优的情况一定是一输一赢，考虑在 b 个 B 中插入R，容易得到总共有 b+1 个可以插入的位置。若 r 可以整除 b+1，则可以得出答案为 r/(b+1)，若否，则得到 r/(b+1)+1。
我们先在b+1个位置中每个放上 r/(b+1) 个 R，剩下r%(b+1)个R则随便给，只要不要一个位置给两次就可以了。
标程
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
| #include<bits/stdc++.h>
using namespace std;
void solve(){
int n,r,b;
cin>>n>>r>>b;
int k=r/(b+1);
int res=r%(b+1);
for(int i=1;i<=b;i++){
for(int j=1;j<=k;j++){
printf("R");
}
if(res){
printf("R");
res--;
}
putchar('B');
}
for(int j=1;j<=k;j++){
printf("R");
}
if(res){
printf("R");
res--;
}
putchar(10);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int t;
cin>>t;
while(t--)solve();
return 0;
}
|
B. Bit Flipping
题目描述：
/2.png)
题目分析
给定二进制字符串和k次的操作，要求输出最大字典序的字符串。一次操作会使任意一个位置的字符不变，其它的全部取反。那么容易得到一个结论：对任意一个位置操作偶数次不会该边整体字符串。
如果k为偶数，则未操作过的数（或者说操作次数为偶数）的数将不变，操作过的数（或者说操作次数为奇数）的数将取反。
如果k为奇数，则与偶数情况刚好相反。
我们考虑偶数情况，字符串高位开始，若碰到0则取反变成1，减少一次操作次数并记录在这个位置。若操作到所有序列为全1，则将剩余的操作全部甩给最后一位，使得最后的结果只存在 $111…1$ 和 $111…0$。如果为奇数的话，把0当成1，1当成0即可，我们最后输出的时候把0输出为1，1输出为0，操作按偶数方法操作并且尽量使得字符串结果为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
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
| #include<bits/stdc++.h>
using namespace std;
char s[1000005];
int a[1000005];
void solve(){
int n,k;
cin>>n>>k;
scanf("%s",s);
int p=k%2;
for(int i=0;i<n;i++){
if(p){
if(s[i]=='1'&&k){
s[i]='0';
a[i]=1;
k--;
}
else{
a[i]=0;
}
}
else{
if(s[i]=='0'&&k){
s[i]='1';
a[i]=1;
k--;
}
else{
a[i]=0;
}
}
}
a[n-1]+=k;
if(k%2){
if(p){
s[n-1]='1';
}
else{
s[n-1]='0';
}
}
for(int i=0;i<n;i++){
if(p^(s[i]=='1'))putchar('1');
else putchar('0');
}putchar(10);
for(int i=0;i<n;i++){
printf("%d ",a[i]);
}
putchar(10);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int t;
cin>>t;
while(t--)solve();
return 0;
}
|
C. Line Empire
题目描述
/3.png)
题目分析
给定占领的国家的位置和占领花费系数以及迁都花费系数，求最少花费占领所有王国。
我们可以算迁都产生的花费和产生的收益进行比较，当收益>=花费时我们选择迁都，否则选择直接攻打那些国家。
不难得到迁都产生的花费为 $b|x_i-pos|$，pos为当前首都的位置，得到的收益为：$a|x_i-pos|*(n-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
32
33
34
35
36
37
38
| #include<bits/stdc++.h>
#define int long long
using namespace std;
int x[1000005];
void solve(){
int n,a,b;
scanf("%lld %lld %lld",&n,&b,&a);
for(int i=1;i<=n;i++){
scanf("%lld",&x[i]);
}
x[0]=0;
int ans=0;
int pos=0;
for(int i=1;i<=n;i++){
ans+=a*(x[i]-pos);
int cost=(n-i)*a*(x[i]-pos);
if(cost>=b*(x[i]-pos)){
ans+=b*(x[i]-pos);
pos=x[i];
}
}
printf("%lld\n",ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int t;
cin>>t;
while(t--)solve();
return 0;
}
|
D. Reverse Sort Sum
题目描述
/4.png)
题目分析
给你描述了一个序列 A 的值为 $\sum _{i=1}^{n}f(i,A)$，$f(i,A)$ 函数得到的序列就是将序列 A 的前 i 个数排序，数的取值只有0,1。现在给定最终的结果，让你逆向分析初始可能的0,1序列。
这个我写了个假算法，我自己也无法证明这个算法的正确性，但是他就是过了。。
首先分析序列后半部分，容易得到，若$a_i<i$，那么 $x_i=0$，否则$x_i=1$，因为后半部分至少有一半的值是来自自己贡献的。拿最后一个举例，如果最后一个值为1或0，那么原序列最后一个值必是0。否则是最后一个值一定是 n，没有其它情况，可以很容易得到的。
对于前半部分的序列的值确定了第$i$个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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include<bits/stdc++.h>
using namespace std;
int x[1000005];
int a[1000005];
void solve(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&x[i]);
a[i]=1;
}
for(int i=n;i>n/2;i--){
if(x[i]<i){
a[i]=0;
}
else{
a[i]=1;
}
}
for(int i=1;i<=n/2;i++){
if(!x[i]){
a[i]=0;
continue;
}
if(a[i]==0)x[i]+=i-1;
if(x[i]==n)break;
a[x[i]+1]=0;
}
for(int i=1;i<=n;i++){
printf("%d ",a[i]);
}
putchar(10);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int t;
cin>>t;
while(t--)solve();
return 0;
}
|
D题可能有点问题，欢迎大家hack。
总之第一次Div2能做出四题，还是很开心的。
提交记录：
/5.png)
/6.png)
