还是很开心的，第一次CF打出来D题，嘎嘎上132分，目前1584分，紫名指日可待。

A.Red Versus Blue

题目描述：

题目分析

知道双方赢球场次，要求构造一个输赢序列使得总比赛中最大连赢场数最小，即给定两种字符及个数，输出一个字符串使得由相同字符构成的子串最短。

首先题目给定了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

题目描述：

题目分析

给定二进制字符串和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

题目描述

题目分析

给定占领的国家的位置和占领花费系数以及迁都花费系数，求最少花费占领所有王国。

我们可以算迁都产生的花费和产生的收益进行比较，当收益>=花费时我们选择迁都，否则选择直接攻打那些国家。

不难得到迁都产生的花费为 \(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++){
        //attack
        ans+=a*(x[i]-pos);
//        printf("attack %d %d %d\n",i,x[i],a);
//        printf("ans=%d\n",ans);
        int cost=(n-i)*a*(x[i]-pos);
        if(cost>=b*(x[i]-pos)){
            ans+=b*(x[i]-pos);
            pos=x[i];
//            printf("move in pos %d\n",i);
//            printf("ans=%d\n",ans);
        }
    }
    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

题目描述

题目分析

给你描述了一个序列 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>
//#define int long long
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能做出四题，还是很开心的。

提交记录：