CF系列题解(这场好阴间)


题目

A. Red Versus Blue

原题链接

A. Red Versus Blue

题意

给定三个整数

n

,

r

,

b

n,r,b

n,r,b,满足

n

=

r

+

b

n=r+b

n=r+b,输出一个长度为

n

n

n 的字符串满足有

r

r

rR

b

b

bB。字符串需要保证连续的 RB 的长度最小。

输入格式
第一行包含一个整数

t

(

1

t

1000

)

t (1≤t≤1000)

t(1t1000) ,表示有t组测试数据。
每个测试数据第一行包含三个整数

n

,

r

,

b

(

3

n

100

;

1

b

<

r

n

,

r

+

b

=

n

)

.

n, r, b (3≤n≤100; 1≤b<r≤n, r+b=n).

n,r,b(3n100;1b<rn,r+b=n).

输出格式
满足条件的字符串。

输入样例:

3
7 4 3
6 5 1
19 13 6

输出样例:

RBRBRBR
RRRBRR
RRBRRBRRBRRBRRBRRBR

输入样例:

6
3 2 1
10 6 4
11 6 5
10 9 1
10 8 2
11 9 2

输出样例:

RBR
RRBRBRBRBR
RBRBRBRBRBR
RRRRRBRRRR
RRRBRRRBRR
RRRBRRRBRRR

题解

思路

想要直接确定字符串

s

s

s 是不行的,我们应该动态的输出。

由于题目保证了

r

>

b

r>b

r>b,因此我们应该把 RB 里插入,考虑初始情况一共有

b

+

1

b+1

b+1 个空隙,我们可以先插入

r

/

(

b

+

1

)

r/(b+1)

r/(b+1)R 和一个 B,此时更新下

r

=

r

r

/

(

b

+

1

)

r=r-r/(b+1)

r=rr/(b+1)

b

=

b

1

b=b-1

b=b1,重复上述过程即可。

注意边界。

代码

#include <bits/stdc++.h>

#define int long long

using namespace std;

constexpr int P = 998244353; 
using i64 = long long;

void out(char c, int cnt)
{
    while (cnt > 0) {
        cout << c;
        cnt -- ;
    }
}

void solve()
{
    int n, r, b;
    cin >> n >> r >> b;

    while (b) {
        int cnt = r / (b + 1);
        r = r - cnt;
        out('R', cnt);
        out('B', 1);
        b -- ;
    }
    out('R', r);
    cout << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T -- ) {
        solve();
    }

    return 0;
}

B. Bit Flipping

原题链接

B. Bit Flipping

题意

给定一个长度为

n

n

n 的字符串

s

s

s(只包含 01),每次操作可以选择一项保持不变,其他所有字符 0->11->0,问进行

k

k

k 次操作后字典序最大的

s

s

s

输入格式
第一行包含一个整数

t

(

1

t

1000

)

t (1≤t≤1000)

t(1t1000) ,表示有t组测试数据。
每个测试数据第一行包含两个整数

n

,

k

(

1

n

2

1

0

5

;

0

k

1

0

9

)

n,k (1≤n≤2⋅10^5; 0≤k≤10^9)

n,k(1n2105;0k109)
每个测试数据第二行包好一个字符串

s

s

s

输出格式
输出要求的字符串。

输入样例:

6
6 3
100001
6 4
100011
6 0
000000
6 1
111001
6 11
101100
6 12
001110

输出样例:

111110
1 0 0 2 0 0 
111110
0 1 1 1 0 1 
000000
0 0 0 0 0 0 
100110
1 0 0 0 0 0 
111111
1 2 1 3 0 4 
111110
1 1 4 2 0 4

题解

思路

由于每次反转只有一个位置不变且必须操作

k

k

k 次,因此我们可以先对字符串反转

k

k

k 次后再去确定不需要变换的位置即可。

细节见代码。

小技巧: 字符 01 的转换可以使用 ^ 运算来操作。

代码

#include <bits/stdc++.h>

// #define int long long

using namespace std;

using i64 = long long;

void solve()
{
    int n, k;
    cin >> n >> k;

    string s;
    cin >> s;

    vector<int> ans(n);

    if (k & 1) {
        for (int i = 0; i < n; i ++ ) {
            s[i] ^= 1; // 先反转k次
        }
    }

    for (int i = 0; i < n && k; i ++ ) {
        if (s[i] == '0') { // 对0的位置进行处理
            s[i] ^= 1;
            k -- ;
            ans[i] ++ ;
        }
    }

    if (k & 1) s[n - 1] ^= 1; // 因为必须要操作k次且要求字典序最大,因此剩余的操作数只能对最后一个字符操作
    ans[n - 1] += k;

    cout << s << "\n";
    for (int i = 0; i < n; i ++ ) cout << ans[i] << " \n"[i == n - 1];
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T -- ) {
        solve();
    }

    return 0;
}

C. Line Empire

原题链接

C. Line Empire

题意

给定一个序列

x

(

0

<

x

1

<

x

2

<

<

x

n

)

x(0<x_1<x_2<…<x_n)

x(0<x1<x2<<xn) 表示待征服地区的位置,以及整数

a

,

b

a,b

a,b,我们从

0

0

0 处开始,即我们的首都开始是

0

0

0,每次我们可以进行如下操作:

  1. 征服一个地方的代价为

    b

    ×

    x

    i

    c

    a

    p

    b×|x_i-cap|

    b×xicap

  2. 把一个被征服的地方变为首都

    a

    ×

    x

    i

    c

    a

    p

    a×|x_i-cap|

    a×xicap

求我们征服所有地方所需要的最小代价。

输入格式
第一行包含一个整数

t

(

1

t

1000

)

t (1≤t≤1000)

t(1t1000) ,表示有t组测试数据。
每个测试数据第一行包含三个整数

n

,

a

,

b

(

1

n

2

1

0

5

,

1

a

,

b

1

0

5

)

n, a, b (1≤n≤2⋅10^5,1≤a,b≤10^5)

n,a,b(1n2105,1a,b105)
每个测试数据第二行包含

n

n

n 个整数

x

1

,

x

2

,

,

x

n

(

1

x

1

<

x

2

<

<

x

n

1

0

8

)

.

x_1,x_2,…,x_n (1≤x_1<x_2<…<x_n≤10^8).

x1,x2,,xn(1x1<x2<<xn108).

n

n

n 的总和不超过

2

1

0

5

2⋅10^5

2105

输出格式
一个整数表示最小代价

输入样例:

4
5 2 7
3 5 12 13 21
5 6 3
1 5 6 21 30
2 9 3
10 15
11 27182 31415
16 18 33 98 874 989 4848 20458 34365 38117 72030

输出样例:

173
171
75
3298918744

题解

思路

首先给出结论,假设我们最后选择

x

i

x_i

xi 作为我们最后的首都,那么之前每一次操作都为先从

x

i

1

x_{i-1}

xi1 征服

x

i

x_i

xi,再把

x

i

x_i

xi 变为首都。

证明:首先把首都从

0

0

0 变到

x

i

x_i

xi 和中间过程无关,即代价均为

a

×

(

x

i

0

)

a×(x_i-0)

a×(xi0),由于

x

x

x 是单调上升的,因此从

x

i

1

x_{i-1}

xi1 征服

x

i

x_i

xi 的代价是一定小于从

x

1

,

x

2

,

.

.

.

,

x

i

2

x_1,x_2,...,x_{i-2}

x1,x2,...,xi2 征服

x

i

x_i

xi 的代价的,因此要一边征服一边改变首都。

因此我们只需要枚举我们最后以哪个坐标为首都即可,关于求距离可以采用前缀和优化,我们可以从小到大枚举

x

x

x 顺便记录之前的代价即可,细节见代码。

代码

#include <bits/stdc++.h>

#define int long long

using namespace std;

constexpr int P = 998244353;
using i64 = long long;

void solve()
{
    int n, A, B;
    cin >> n >> A >> B;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    int ans = 0; // 初始化ans显然是以0为首都的代价
    for (int i = 1; i <= n; i ++ ) ans += B * a[i];
    vector<int> b(n + 1); // 前缀和数组
    for (int i = 1; i <= n; i ++ ) b[i] = b[i - 1] + a[i];
    int cost = 0; // 表示征服到i并且把i变为首都的代价
    for (int i = 1; i <= n; i ++ ) {
        cost += (a[i] - a[i - 1]) * (A + B);
        ans = min(ans, cost + (b[n] - b[i] - (n - i) * a[i]) * B); // 注意此处以i为首都征服后面的城市时要减去首都的距离×城市的数量
    }

    cout << ans << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T -- ) {
        solve();
    }

    return 0;
}