【题目全解】ACGO挑战赛#8-数字星空

前言：本次挑战赛的难度相较于前面几期有所提升，主要还是因为集训的关系，出题组的成员们没有充裕的时间想原创题目（so，只能原模原样搬运某一场 ABC 的考试了。）Anyway，AK 了就行。

备注：由于 Python 的常数过大，本题解暂不同步更新 Python 版本的题解。

第一题 - Intersection

题目跳转：交集。

这道题可以用暴力的方法，也可以稍微动点脑筋。看在数据量小，直接打暴力就行了，没必要花时间去找两个线段之间的关系。

注意到 \(0 \le L_1 R_1, L_2, R_2 \le 100\)，可以新建一个标记数组：如果某个坐标属于某一条线段，那么就将对应索引的标记增加一。最后再遍历一边标记数组，如果存在一个坐标被标记了两遍，那么就证明该坐标被两条线段同时覆盖住了。

最后注意输出的时候要 \(-1\)，表示区间的长度。（如果没有任何重合的区间，即 ans == 0 时，特判直接输出 \(0\) 就可以了。

代码时间复杂度：\(O(N)\)。

本题的 AC 代码如下：

#include <iostream>
using namespace std;

int a, b, c, d;
int arr[1005], ans;

int main(){
    cin >> a >> b >> c >> d;
    for (int i=a; i<=b; i++) 
        arr[i]++;
    for (int i=c; i<=d; i++) 
        arr[i]++;
    for (int i=0; i<=100; i++)
        ans += (arr[i] == 2);
    cout << max(0, ans-1) << endl;
	return 0;
}

第二题 - Tournament Result

题目跳转：比赛结果。

第二题也是一道纯暴力的模拟题目，双层 for 循环依照题目题干的要求判断点 \((i, j)\) 和点 \((j, i)\) 所存的值是否存在冲突就行了。这边我用了一个 check 函数来检查是否存在冲突。如果存在冲突直接返回结果即可。

这边判断冲突的 check 函数我觉得值得讲一下，分类讨论：

如果双方胜负状态相同且不是平局，则返回 false。
如果一方是平局二另一方不是平局，则返回 false。
可以证明其余的情况一定是合法的，直接返回 true 即可，不需要跟其他题解一样大费周章来写条件分支语句。

代码时间复杂度：\(O(N^2)\)。

本题的 AC 代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

int n;
char arr[1005][1005];

bool check(char a, char b){
    if (a == b && a != 'D') 
        return false;
    if (a == 'D' && b != a)
        return false;
    return true;
}

int main(){
    cin >> n;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            cin >> arr[i][j];
    for (int i=1; i<=n; i++){
        for (int j=1; j<=n; j++){
            // 当 i == j 的时候，跳过枚举。
            if (i == j) continue;
            if (!check(arr[i][j], arr[j][i])){
                cout << "incorrect" << endl;
                return 0;
            }
        }
    }
    cout << "correct" << endl;
    return 0;
}

第三题 - NewFolder(1)

题目跳转：新建文件夹(1)。

也是一道水题，用 STL 的 unordered_map/ map 存一下某一个字符串出现的次数就可以了。由于 \(N\) 比较大，因此如果直接用双层循环遍历的话绝对会超时。

但需要注意的是，map 的单次插入/查询的时间复杂度约为 \(O(\log_2 N)\)。因此本题的综合时间复杂度约为 \(O(N \log_2 N)\)。

本题的 AC 代码如下：

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

int n;
string str[200005];
unordered_map<string, int> map;

int main(){
    cin >> n;
    for (int i=1; i<=n; i++){
        cin >> str[i];
        map[str[i]] += 1;
        int cnt = map[str[i]];
        if (cnt == 1)
            cout << str[i] << endl;
        else 
            cout << str[i] << "(" << cnt-1 << ")" << endl;
    }
    return 0;
}

第四题 - Flipping and Bonus

题目跳转：投硬币。

接下来来到了本次比赛的重头戏，题目难度也在此有了一个质的飞跃（我也不清楚这次 ABC 的难度为什么这么跳跃）。

考虑使用动态规划，定义状态 \(dp_i\) 表示第 \(i\) 次掷硬币可以获得的最大金额。（其实这道题的状态定义有很多种，用二维的 dp 也可以通过本题，本题解暂是只提供前缀和动态规划的解法）

我们可以枚举在第 \(j\) 次抛置硬币时选择正面和反面的价值并取最大值。所以，对于每一次投掷硬币有两种可能的决策，分别是：

硬币最终的状态时正面，得到第 \(i\) 次投掷硬币的钱，计数器自增。因此结果就是得到 \(x_1 + x_2 + x_3 + \cdots + x_{i-1} + x_i\) 元钱和 \(y_1 + y_2 + y_3 + \cdots + y_{k-1} + y_k\ (c[k] \le i)\) 的奖金。
硬币最终的状态是反面，那么计数器就从头开始计数。因此最终可以获得的结果就为从第 \(j\) 次投硬币时可以获得的最大金额 \(dp_j\) 加上在区间 \([j+2, i]\) 投币全是正面所获的的金额（因为第 \(j+1\) 次投币不会获得任何的奖励）\((x_1 + x_2 + x_3 + \dots + x_{i-1} + x_i) - (x_1 + x_2 + x_3 + \cdots + x_j + x_{j+1})\) 再加上前 \(i-j-1\) 次计数器的奖励金额 \((y_1 + y_2 + y_3 + \cdots + y_{k-1} + y_k\ (c[k] \le i-j-1)\) 。

可以发现，我们可以通过开设两个前缀和数组来优化算法，分别约定 \(\mathtt{suma, sumb}\) 分别表示前 \(i\) 次投币全都是正面所获的的金额和计数器的奖励金额。因此最后的状态转移方程时可以写成：

\[dp_i = \max(dp_i, dp_j + suma_i - suma_{j+1} + sumb_{i-j-1}) \]

备注：十年 OI 一场空，不开 long long 见祖宗。请大家务必开 long long。本题的时间复杂度为 \(\Theta(\dfrac{N+N^2}{2})\)。

周后，本题的 AC 代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
long long dp[5005],x[5005],c[5005],y[5005],suma[5005],sumb[5005],m,n,cnt;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>x[i];
        suma[i]=suma[i-1]+x[i];
    }
    for(int i=1;i<=m;i++){
        int a, b;
        cin >> a >> b;
        c[a] = b;
    }
    for (int i=1; i<=5000; i++){
        sumb[i]=sumb[i-1]+c[i];
    }
    for(int i=1;i<=n;i++){
        dp[i]=suma[i]+sumb[i];
        for(int j=1;j<i;j++){
            // 状态转移方程的推导见原文。
        	dp[i]=max(dp[i],dp[j]+suma[i]-suma[j+1]+sumb[i-j-1]);
        }
    }
    cout<<dp[n];
	return 0;
}

第五题 - Many Operations

题目跳转：宏量运算。

一道位运算的恶心题目，跟上一题一样，可以用前缀和动态规划的思想来解决。因为每一位都是相互独立的，所以只需要按位进行 \(\mathtt{dp}\) 预处理就可以了。定义状态 \(dp_{i, j(0/1), k}\) 表示对于第 \(i\) 位来说，一开始的值为 \(j(0/1)\)，经过前 \(k\) 次操作后这一位的值。而状态转移方程就是 \(dp_{i, j, k} = dp_{i, j, k-1}\)。之后不断迭代就可以求出最后的解。

本题的主要难点是位运算的一些操作，有些同学对位运算的操作不太熟悉，这里提供一些常见的位运算操作：

获取一个数字的第 \(j\) 位：(x >> j) & 1。
判断数字是否是奇数：x & 1。
将一个数字乘上 \(2^j\)：(1 << j) * x。

本题的时间复杂度约为 \(\Theta(60N)\)。

因此，本题的 AC 代码如下：

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 2e5 + 5;
int n, c;
int dp[50][5][N];
int t[N], a[N];

signed main(){
    cin >> n >> c;
    for (int i=1; i<=n; i++)
        cin >> t[i] >> a[i];
    // cout << log2(1e9) << endl; 
    for (int i=0; i<30; i++){
        for (int j=0; j<2; j++){
            dp[i][j][0] = j;
            for (int k=1; k<=n; k++){
                // 三种状态，分别判断一下就可以了了。
                bool x = a[k] & (1 << i);
                if (t[k] == 1) dp[i][j][k] = dp[i][j][k-1] & x;
                else if (t[k] == 2) dp[i][j][k] = dp[i][j][k-1] | x;
                else dp[i][j][k] = dp[i][j][k-1] ^ x;
            }
        }
    }
    for (int i=1; i<=n; i++){
        int ans = 0, k = c;
        for (int j=0; j<30; j++) {
            // 基础位运算操作。
            ans += dp[j][k & 1][i] * (1 << j);
            k >>= 1;
        }
        cout << ans << endl;
        c = ans;
    }
    return 0;
}

第六题 - Sorting Color Balls

题目跳转：彩球排序。

一道逆序对的题目，因为我懒的使用归并排序来做，所以我用了 树状数组 + map 的方式，荣获运行时长 44.9s 的好成绩。其实这道题应该比第五题简单，Based on my opinion。

一道普普通通的逆序对的题目，在计算逆序对的时候去除相同颜色的逆序对就可以了，类似一道模板题。我用了两个树状数组分别来计算每个数字出现的次数和每个颜色出现的次数。

本题的 AC 代码如下，时间复杂度约为 \(O(N \log_2 N)\)：

#include <iostream>
#include <vector>
#include <unordered_map>
#define int long long
using namespace std;

const int N = 3e5 + 5;
int n, c[N], x[N];
int cnt[N], tot[N];
unordered_map<int, int> cnt2[N];

// 记录某一个数字出现的次数。
void add_n(int x){
    while(x <= n){
        cnt[x] += 1;
        x += x & (-x);
    }
}

// 记录某一个颜色出现的次数。
void add_c(int x, int c){
    while(x <= n){
        cnt2[x][c] += 1;
        x += x & (-x);
    }
}

// 查询某一个数字出现的次数。
int query_n(int x){
    int ans = 0;
    while(x){
        ans += cnt[x];
        x -= x & (-x);
    }
    return ans;
}

// 查询某一个颜色出现的次数。
int query_c(int x, int c){
    int ans = 0;
    while(x){
        ans += cnt2[x][c];
        x -= x & (-x);
    }
    return ans;
}

signed main(){
    cin >> n;
    for (int i=1; i<=n; i++) cin >> c[i];
    for (int j=1; j<=n; j++) cin >> x[j];
    int result = 0;
    for (int i=1; i<=n; i++){
        // 减去相同颜色出现的次数即可。
        result += (i - 1) - tot[c[i]] - query_n(x[i]) + query_c(x[i], c[i]);
        tot[c[i]] += 1;
        add_c(x[i], c[i]); add_n(x[i]);
    }
    cout << result << endl;
	return 0;
}