A. 找摆杆

题解

两个相同的数进行异或运算结果为0，0和任意数异或都是那个数，只需要将所有数进行异或，得到的就是落单的数。

标准程序代码

#include<bits/stdc++.h>
using namespace std;
int ans,x;
int main() {
    int n;
    cin>>n;
    while(n--){
        cin>>x;
        ans^=x;
    }
    cout<<ans;
}

B. 开火车

题解

可以发现，如果yangCA出的第一张牌是Pear没有的牌，那么Pear无论如何都无法阻止yangCA用这张牌得1分。除了这一可能性外，Pear总能阻止yangCA得分。

标准程序代码

#include<bits/stdc++.h>
using namespace std;

int main() {
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        int ini,x;
        int p=0;
        cin>>ini;
        for(int i=1;i<n;i++){
            cin>>x;
            if(x==ini)p=1;
        }
        cout<<p<<endl;
    }
}

C. 交通枢纽

题解

本题可贪心但逻辑不严谨，正解是DP

贪心

看为连续可通过的联通块，每次选择走最长段

程序代码

#include<bits/stdc++.h>
using namespace std;
#define range(x) x.begin(), x.end()
#define fixd(x) fixed << setprecision(x)
typedef long long ll;
typedef unsigned long long ull;
ll n;
ll ans = 1, pos;

int main() {
    cin >> n;
    vector<vector<int>> a(n + 5, vector<int>(3, 0)), b(n + 5, vector<int>(3, 0)); // b储存联通长度
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 3; j++) cin >> a[i][j];
    }

    for (int i = n; i >= 1; i--) {
        for (int j = 0; j < 3; j++) {
            if (a[i][j] == 0) continue;
            b[i][j] += b[i + 1][j] + 1;
        }
    }
    int mx = 0;
    for (int j = 0; j < 3; j++) {
        if (a[1][j] && b[1][j] > mx) {
            mx = b[1][j];
            pos = j;
        }
    }
    for (int i = 1; i <= n;) {
        if (!a[i][pos]) {
            ans++;
            mx = 0;
            for (int j = 0; j < 3; j++) {
                if (a[i][j] && b[i][j] > mx) {
                    mx = b[i][j];
                    pos = j;
                }
            }
        }
        i += mx;
    }
    cout << ans;
}

DP

dp[i][j] 表示通过第 i 个关卡时，当前车型为 j的最小总调度经费，初始状态：dp[0][j] = 1 对第 i 个关卡，若车型 j 可通行： 保持车型：dp[i][j] = dp[i-1][j]（无切换代价）； 切换车型：dp[i][j] = min(dp[i-1][k] + 1)（k≠j，切换代价 1）； 取两者最小值（若不可通行则 dp[i][j] = INF）。 最终答案：min(dp[n][0], dp[n][1], dp[n][2])。

程序代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF = 1e18;

int main() {
    ll n;
    cin >> n;
    vector<vector<int>> a(n + 1, vector<int>(3));
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> a[i][j];
        }
    }

    
    vector<vector<ll>> dp(n + 1, vector<ll>(3, INF));
    for (int j = 0; j < 3; j++) {
        dp[0][j] = 1;
    }

   
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 3; j++) {
            if (a[i][j] == 0) continue; 

            // 情况1：
            if (dp[i-1][j] != INF) {
                dp[i][j] = min(dp[i][j], dp[i-1][j]);
            }

            // 情况2：
            for (int k = 0; k < 3; k++) {
                if (k == j) continue;
                if (dp[i-1][k] != INF) {
                    dp[i][j] = min(dp[i][j], dp[i-1][k] + 1);
                }
            }
        }
    }

 
    ll ans = min({dp[n][0], dp[n][1], dp[n][2]});
    cout << ans << endl;

}

D. 团队激励值

题解

利用归并排序的分治思想,对数组中每个元素 $arr[j]$，求其左侧所有 $≤ arr[j]$ 的元素之和，最后将所有结果累加。

标准程序代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int, int> PII;
// #define int long long
#define i128 __int128
#define i64 long long
const int mod = 1e9 + 7;
const int MOD = 998244353;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
ll ksm(ll a, ll b, ll p)
{
    ll sum = 1;
    a %= p;
    while (b)
    {
        if (b & 1)
            sum = (sum * a) % p;
        b >>= 1;
        a = (a * a) % p;
    }
    return sum % p;
}
const int N = 100010;
int help[N], arr[N];
ll merge(int l, int m, int r)
{
    ll ans = 0;
    for (int j = m + 1, i = l, sum = 0; j <= r; j++)
    {
        while (i <= m && arr[i] <= arr[j])
        {
            sum += arr[i++];
        }
        ans += sum;
    }
    int i = l;
    int a = l;
    int b = m + 1;
    while (a <= m && b <= r)
    {
        help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
    }
    while (a <= m)
    {
        help[i++] = arr[a++];
    }
    while (b <= r)
    {
        help[i++] = arr[b++];
    }
    for (i = l; i <= r; i++)
    {
        arr[i] = help[i];
    }
    return ans;
}
ll smallSum(int l, int r)
{
    if (l == r)
    {
        return 0;
    }
    int m = (l + r) >> 1;
    return smallSum(l, m) + smallSum(m + 1, r) + merge(l, m, r);
}
void Hint()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    cout << smallSum(0, n - 1) << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // cin >> _;
    while (_--)
    {
        Hint();
    }
    return 0;
}

E. 业绩管理

题解

如果我们决定保留索引 $i$，其值仍为$a_{i}$。因此，保留的索引必须构成 $a$ 的一个非递减子序列。 我们的目标是最小化总成本。等价地，我们可以最大化保留索引中$c_{i}$的总和，因为 $cast=\sum{c_{i}}-\sum\limits_{kept}{c_{i}}$ 因此，问题简化为找到一个非递减的子序列，最大化相应的$c_{i}$之和。 设 $dp[i]$是在索引 $i$ 结束的非递减子序列中$c_{i}$的最大和。 对于每一个$i$，我们都可以将$a_{i}$追加到以$a_{j}\leqslant a_{i}$结束于某个$j < i$的有效子序列中: $dp[i]=c_{i}+max dp[j](j<i,a_{j}\leqslant a_{i})$ 如果没有这样的$j$，我们就直接取 $dp[i]=c_{i}$。 计算完所有$dp[i]$后，可保留元素的最大和为 $max_{i} dp[i]$。 因此，最终答案是 $\sum\limits_{i=1}^{n}{c_{i}}-max_{i} dp[i]$

标准程序代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int, int> PII;
//#define int long long
#define i128 __int128
#define i64 long long
const int mod = 1e9 + 7;
const int MOD = 998244353;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
ll ksm(ll a, ll b, ll p)
{
    ll sum = 1;
    a %= p;
    while (b)
    {
        if (b & 1)
            sum = (sum * a) % p;
        b >>= 1;
        a = (a * a) % p;
    }
    return sum % p;
}
const int N = 8005;
ll a[N],c[N],dp[N];
void Hint()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    ll sum = 0;
    for(int i = 1; i <= n; i++) {
        cin >> c[i];
        dp[i] = 0;
        sum += c[i];
    }
    ll mx = 0;
    for(int i = 1; i <= n; i++) {
        dp[i] = c[i];
        for(int j = 1; j < i; j++) {
            if(a[i] >= a[j]) {
                dp[i] = max(dp[i], dp[j] + c[i]);
            }
        }
        mx = max(mx,dp[i]);
    }
    cout << sum - mx << endl;

}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    cin >> _;
    while (_--)
    {
        Hint();
    }
    return 0;
}