A. Red Versus Blue

题目大意

红队和蓝队进行了$n$次比赛。用一个长度为$n$的字符串表示每场的胜负情况。
R代表红队获胜,B代表蓝队获胜,蓝队获胜的次数严格小于红队。
给你三个整数n, b, r请你构造一个长度为n的字符串,表示$n$场比赛的胜负情况,满足R的个数为r,B的个数为b,
并且使得每个队伍连续获胜的最大次数尽可能小。

解题思路

如果要使连续字符数量最小,肯定是要进行平均分配。
对于字符串,rB可以把它分为b + 1段。
所以我们只需要对每段平均分配r / (b + 1)R
因为r / (b + 1)不一定是整数, 所以不一定能够每段都一样的数量。
还剩余 r % (b + 1)R要逐个分配1个到每段里直至剩余数量为0

Code

void solve()
{
    int n, r, b;	cin >> n >> r >> b;
    int avg = r / (b + 1), remain = r % (b + 1);
    
    for (int i = 1; i <= b + 1; i++)	a[i] = avg;  // 除数平均分配
    for (int i = 1; i <= remain; i++)	a[i]++;  // 余数逐个分配
    
    for (int i = 1; i <= b + 1; i++)
    {
    	for (int j = 1; j <= a[i]; j++)	cout << "R";
    	if (i != b + 1)	cout << "B";
    }
    cout << '\n';
}

B. Bit Flipping

题目大意

给定一个长度为$n$的二进制字符串和操作次数$k$,你可以进行$k$次这样的操作:选定字符串的任意一位,除了选定位置外,其他位置的状态都被翻转(0变1,1变0)。求进行$k$次操作之后,能获得的字典序最大的字符串,以及每一位的反转次数。

解题思路

看了看官方题解,觉得思路更清晰些!

让我们看看给定的位会被翻转多少次。
显然,只要在操作中未选择某个位,它就会被翻转。因此,第$i$位被翻转$k-f_i$次。 我们希望尽可能少地选择某一位。现在我们可以处理一些情况。
$k$是偶数,第$i$位是1 ⇒ $f_i = 0$(偶数翻转不改变位)
$k$是偶数,第$i$位是0 ⇒ $f_i = 1$(奇数次翻转将位从 0 切换到 1)
$k$是奇数,第$i$位是1 ⇒ $f_i= 1$(偶数翻转不改变位)
$k$是奇数,第$i$位是0 ⇒ $f_i= 0$(奇数翻转将位从 0 切换到 1)
从左到右处理字符串,直到不能再处理为止。 如果最后还有一些剩余的$k$,可以把它们全部放在最后一位。
然后可以通过检查$k - f_i$的奇偶性来构造最终的字符串。

Code

void solve()
{
    cin >> n >> k >> s;
    vector<int> f(n, 0);

    int t = k;
    for (int i = 0; i < n && t > 0; i++)
        if (k % 2 == s[i] - '0')    f[i] = 1, t--;

    f[n - 1] += t;
    
    for (int i = 0; i < n; i++)
        if ((k - f[i]) % 2 == 1)    s[i] = '1' - (s[i] - '0'); // 翻转
    
    cout << s << endl;
    for (auto x : f) cout << x << ' ';
    cout << endl;
}

C. Line Empire(贪心)

题目大意

假设你是一个国王,你的首都的初始位置是$0$。
地图上有$n$个未征服的国家位置分别为$0 < x_1 < x_2 < x_3 < ... < x_n$,你想征服所有国家。
你有两种操作:
1.更换首都:将当前的首都$c1$更换为其他任意被征服的国家(位置为$c2$)所需要花费的代价为 $a * |c1 - c2|$
2.征服国家:可以从当前的首都征服任意一个未征服的国家,所需要花费的代价为$b * |c1 - c2|$
注意:如果在$c1$和$c2$之间存在未征服的国家,那么就不能执行这个征服操作 。给定$n$,$a$和$b$,以及未征服国家的位置,求征服所有国家的最小代价。

解题思路

先上图!
avatar
未迁都的情况下:前面部分 = $b * (pos2 - pos1) * (n - i)$ => n-i表示剩余没有征服的领地数量
迁都的情况下:前面部分 = 迁都费用 = $a * (pos2 - pos1)$
化简式子,两式同除$(pos2 - pos1)$
所以只需比较$b * (n - i)$和$a$的大小即可
如果后者小于前者就迁都, 这种情况下总是满足最优解

Code

void solve()
{
	int n, a, b;	cin >> n >> a >> b;
	
	for (int i = 1; i <= n; i++)	cin >> pos[i];
	pos[0] = 0;  // 初始为0
	
	int res = 0, now = pos[0];  
	for (int i = 1; i <= n; i++)
	{
		res += b * (pos[i] - pos[now]);  // 加上征服的费用
		if (b * (n - i) >= a)	res += a * (pos[i] - pos[now]), now = i;  // 符合条件则迁都,满足最优
	}
	
	cout << res << endl;
}

D. Reverse Sort Sum(树状数组)

题目大意

定义数组$A$是一个由$0$和$1$构成的数组,函数 $f(k, A) $ 表示对数组$A$ 的前$k$个元素排序后得到的新数组$C$。
如果给定$A$有$n$个元素,那么数组$C=f(1,A) + f(2,A) + ... + f(k,A)$
现在给出数组$C$,求数组$A$。

解题思路

比赛时真的两点性质都想到了,原本想用线段树,但是没想到树状数组也可以做到
题解可以参考严格鸽

TIPS:树状数组区间修改,单点查询等操作可以看这里

Code

int n, a[N], tr[N], res[N];
int lowbit(int x){return x & -x;}
void add(int x, int v)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}

int query(int x)  // 单点查询即差分求和
{
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) res += tr[i];
    return res;
}

void solve()
{
    memset(res, 0, sizeof res);
	memset(tr, 0, sizeof tr);  // 每次都别忘记初始化
    int sum = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i], sum += a[i];
    for (int i = 1; i <= n; i++)    add(i, a[i] - a[i - 1]);  

    int num1 = sum / n;

    for (int i = n; i >= 1; i--)
        if (query(i) >= i)    
        {
            res[i] = 1;
            add(i - num1 + 1, -1), add(i + 1, 1);  // 区间修改要通过差分补值
            num1--;
        }

    for (int i = 1; i <= n; i++)    cout << res[i] << " ";
    cout << '\n';
}

TIPS: 如果WA了,那一定是精度问题,本人代码头文件不同

下一篇