A. Subsequence Permutation

题意

有一个字符串，可以选择任意个字符任意调换他们的位置，求选择最少数量的字符调换他们的位置使得调换后字符串按字典序排列。

分析

先按字典序sort一遍字符串，与原字符串比较，只要不同的都需要重新调整位置。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
vector<char> temp;
char s[111];
int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while(t--) {
        int ans = 0;
        temp.clear();
        int n;
        cin >> n;
        cin >> s;
        for(int i = 0; i < n; i++) temp.push_back(s[i]);
        sort(temp.begin(),temp.end());
        for(int i = 0; i < n; i++) {
            if(s[i] != temp[i]) ans++;
        }
        //puts("----------");
        cout << ans << endl;
    }
    return 0;
}

B. Running for Gold

题意

有五场马拉松比赛，有n名运动员，已知每个运动员在每场比赛的排名，如果运动员 A 至少有三场比赛排名比运动员 B 高，那么运动员A就比B厉害，让你找到最厉害的运动员（即比每个运动员都至少有三场比赛排名高），如果不存在则输出-1。

分析

就是按照一定的规则去找最大值，“打擂台”的方式逐一比较一次找到最大值，然后再从头扫描一次确保找到的运动员比其余所有都厉害。因为可能会存在A>B>C>D>A这种可能，所以需要再次扫描确定是最大值。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 5e4 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
int rank1[maxn][5];
int temp[maxn];

bool judge(int x, int y) {
    int cnt = 0;
    for (int i = 0; i < 5; i++) {
        if (rank1[x][i] < rank1[y][i]) cnt++;
    }
    if (cnt >= 3) return 1;
    return 0;
}


int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            temp[i] = i;
            for (int j = 0; j < 5; j++) scanf("%d", &rank1[i][j]);
        }
        int ans = 0;
        for(int i = 1; i < n; i++) {
            if(judge(ans,i) == 0) ans = i;
        }
        int f = 0;
        for(int i = n-1; i >= 0; i --) {
            if(i == ans) continue;
            if(judge(ans,i) == 0) {
                f = 1;
                break;
            }
        }
        if (f == 1) {
            puts("-1");
        } else {
            cout << ans+1 << endl;
        }
    }
    return 0;
}

C. Maximize the Intersections(贪心+构造)

题意

有2n个不相同的点在一个圆上，且满足这样一个性质：任意连接3对不同的点，形成三条弦，保证三条弦不会相交于同个点。初始已经连接好k条弦（k条弦都不共用某个点），剩下2n-2k个点，让你连出n-k条弦，这些弦不能共用端点，要求交点尽可能的多。

分析

从某个未使用的点开始，沿顺时针或逆时针将所有未使用的点从1开始编号一直到2(n-k)，将 1 和 1+n-k 连，2 和 2+n-k 连，i 和 i+n-k 连，这样的交点最多。比赛的时候是猜出来的，看了题解学了严谨证明，为了表述方便，我们将题目给出的已经存在的弦称为黑弦，让我们进行连接的弦称为红弦。一共分两步证明：

• 第一部分： 证明如果有两条红弦不相交，则将它们相交后，交点数是一定增加的。

• 第二部分： 证明按照上述的连接方法，可以使得任意两条红弦都相交。

第一部分：

第一种情况是两条红弦都没有和黑弦有交点，则将它们相交后，交点数+1。

第二种情况是某一条红弦与黑弦相交，可以发现，让红弦相交后，交点数还是+1，如下图所示。

第三种情况是两条红弦都和黑弦相交，同样，交点数还是+1，如下图所示。

综上所述，只要有两条红弦没有相交，那么将它们相交就可以使得总交点数+1，那么只要构造一种连接方法使得相交的红弦尽可能的多，交点数就会尽可能的多，这就涉及到第二部分的证明。

第二部分：

反证法，假设有条弦 a----b (a<b)，且 b != a+n-k，那么整个圆上的点就被割裂成两个点集，a-----b左边的点和右边的点，由于 b != a+n-k，那么这两个点集是不一样多的，由于弦之间不能有共用点，所以一定会存在某条弦在a-----b的左边或者右边，那么就和a-----b没有交点，所以只有当 a 和 a+n-k 相连的时候，任意两条红弦都相交。下面有个更一般的例子便于理解：

1本来应该和4相连，但是和5连了，那么6只能和234其中一个点相连，剩下的两个点相连构成一条弦，这条弦和1-----5这条弦不相交。

通过上述证明我们可以得出结论：按照 i 和 i+n-k 相连的策略可以使得交点最多，那么如何计算交点？由于题目保证任意三条弦不会相交于一个点，那么对于弦a-----b我们只要统计一下有几条弦的一个端点在a----b的左侧同时另外一个端点在a----b的右侧，那么a----b就贡献了几个交点，注意重复计算的问题。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 5e4 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
int mp[1111];
int vis[1111];
int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while (t--) {
        memset(vis, 0, sizeof vis);
        memset(mp, 0, sizeof mp);
        int n, k;
        cin >> n >> k;
        vector<PII> d;
        for(int i = 0; i < k; i++) {
            int a, b;
            cin >> a >> b;
            mp[a] = b;
            mp[b] = a;
            d.push_back({a,b});
        }
        vector<int> temp;
        n *= 2;
        for(int i = 1; i <= n; i++) if(mp[i] == 0) temp.push_back(i);
        int nn = temp.size() / 2;
        for(int i = 0; i < nn; i++) {
            mp[temp[i]] = temp[nn+i];
            mp[temp[nn+i]] = temp[i];
            d.push_back({temp[i],temp[nn+i]});
        }
        LL ans = 0;
        for(int i = 0; i < d.size(); i++) {
            int x = d[i].first, y = d[i].second;
            if(x > y) swap(x,y);
            vis[x] = 1, vis[y] = 1;
            for(int j = x+1; j < y; j++) {
                if(vis[j] == 1) continue;
                if(mp[j] < x || mp[j] > y) ans ++;
            }
        }
        //puts("0----------");
        cout << ans << endl;
    }
    return 0;
}

D. Array Differentiation(构造)

题意

给你n个数字构成的数组a，问你是否可以构造一个数组b，满足对于任意一个a，都存在 $a_i = b_j – b_k,(1\leq j,k \leq n)$，其中 j 和 k 可以相等。

分析

我们先假设有n+1个b，满足：$b_1 – b_2 = a_1, b_2 – b_3 = a_2, b_3 – b_4 = a_3, b_n – b_{n+1} = a_n$,那么如果存在 k ，满足 $a_1 + a_2 + … + a_k = a_{k+1}$,那么$a_{k+1}$ 就不用$b_{k+1} – b_{k+2}$ 来表示了，就会少用一个b，只要n个b就可以构造出来。由于题目中j和k的位置没有要求，所以可以随意调换顺序，那么其实正负没有什么关系，所以我们维护一个set，初始先将 $a_1$ 的正负都放入set，从 $a_2$ 开始，先在set查找是否有 $a_i$ 或 $-a_i$ ,如果有则直接退出，输出YES。否则将set中的所有值逐一与$a_i$做加减运算，将结果放入set，同时将 $a_i$ 和 $-a_i$也放入set ，然后找$a_{i+1}$是否在set中，依次进行。如果全部a都找完也不存在，则输出NO。注意，如果a中存在0，则直接输出YES即可，因为0可以用任意一个b来表示（$b_i – b_i = 0$），这样就空出一个位置了。

代码

#include <bits/stdc++.h>

using namespace std;
int a[111];
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int f = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if(a[i] == 0) f = 1;
        }
        if (f == 1) {
            puts("YES");
            continue;
        }
        set<int> all;
        all.insert(a[0]);
        all.insert(-a[0]);
        for (int i = 1; i < n; i++) {
            if (all.find(a[i]) != all.end() || all.find(-a[i]) != all.end()) {
                f = 1;
            }
            set<int> temp;
            for (int val : all)
                temp.insert(val + a[i]), temp.insert(val - a[i]);
            for (int val : temp) all.insert(val);
            all.insert(a[i]), all.insert(-a[i]);
        }
        if (f == 1)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

E. Colors and Intervals（构造）

题意

给你一个由n * k个数字组成的数组col，每个数字的取值为1到n，让你在a数组中找到n个区间 [a,b] ，对于第 i 个区间，满足$col[a_i] = col[b_i] = i$，同时要保证每个数字最多出现在 $\lceil \frac{n} {k-1} \rceil$ 个区间中。

分析

又是一个构造题，构造方法如下：由于题目要求，对于第 i 个区间，满足$col[a_i] = col[b_i] = i$，所有可知每个数字仅会作为一次区间的端点。将这n个数字按照第 i + 1次出现的顺序进行排序，取前$\lceil \frac{n} {k-1} \rceil$ 个还没当过区间端点的数，将他们与第 i 次出现的位置相连，依次进行，直到连完n和区间，输出即可。画一画就能发现，这样构造可以很好满足题目要求。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e4 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
int a[maxn], vis[maxn];
vector<int> lo[111];
int main(int argc, char const *argv[]) {
    int n, k;
    cin >> n >> k;
    vector<PII> temp;
    PII ans[111];
    int m = (n - 1 + k - 1) / (k - 1);
    for (int i = 1; i <= n; i++) lo[i].push_back(-1);
    for (int i = 1; i <= n * k; i++) {
        scanf("%d", a + i);
        lo[a[i]].push_back(i);
    }
    int now = 2;
    int tot = 0;
    while (tot < n) {
        temp.clear();
        for (int i = 1; i <= n; i++) temp.push_back({lo[i][now], i});
        sort(temp.begin(), temp.end());
        int t = 0, i = 0;
        while (t < m && i < temp.size()) {
            if (vis[temp[i].second] == 1) {
                i++;
                continue;
            }
            ans[temp[i].second] = {lo[temp[i].second][now - 1], temp[i].first};
            tot++;
            vis[temp[i].second] = 1;
            t++;
            i++;
        }
        now++;
    }
    for (int i = 1; i <= n; i++) {
        printf("%d %d\n", ans[i].first, ans[i].second);
    }
    return 0;
}

F. Telepanting(推式子)

题意

有一只蚂蚁开始在0位置，每秒向右行进一格，有n个传送门，每个传送门有两种状态：有效和无效，初始时传送门状态不定，由题目给出。当蚂蚁遇到传送门时，如果传送门无效，则蚂蚁继续向右走，且该传送门状态变为有效。如果传输门状态为有效，设传输门位于x，则将蚂蚁传输到 y (y<x)，x和y题目都给出，然后传送门失效，蚂蚁从y继续保持向右移动。问蚂蚁需要移动多少路程才能从0走到x[n]+1的位置，其中x[n] 表示最后一个传输门的位置。

分析

有一个重要的结论：如果蚂蚁位于某个传送门 i 且为有效状态，则所有在i之前的传送门都有效。

证明：

蚂蚁遇到传送门只有两种可能：传送门有效或传送门无效。设蚂蚁遇到的传送门位于x，如果传送门无效，则蚂蚁移动到x+1的位置，位于x的传送门有效。由此可知，处于蚂蚁当前位置之前的所有传送门都有效。那么当蚂蚁位于某个有效传送门时，其前面的所有传送门都有效。

我们假设初始时所有的传送门都有效，设 $q_i$ 表示蚂蚁被第 i 个传送门传送到 y[i] 后再次走到 传送门i所在的位置 x[i] 所需的距离。我们从最开始推：

$q_1 = x_1 – y_1$ ,因为第一个传送门之前没传送门了，所以经过的距离就是传送门到被传送到的坐标之间的距离。

我们再令 b[i] 表示位于 y[i] 右边最近的传送门的下标，即蚂蚁被第i个传送门传送到y[i]后将遇到的第一个传送门的下标。由于我们证明过了，第i个传送门如果为有效的，那么第i个传送门之前的传送门都有效。所以 b[i] 到 i-1 之间的传送门也都效，蚂蚁从y[i]走到x[b[i]]后遇到第b[i]个传送门，然后被传送到某个位置，再次回到x[b[i]]所需的距离为q[b[i]]，依次往下推我们可以得到 $q_i = x_i – y_i + sum[i-1] – sum[b[i] – 1]$，其中$sum[i]$ 表示$q_1 + q_2 + … + q_i$。对于最终答案，我们可以得到 $ans = x_n + 1 + \sum q_i$，其中$i$ 的取值为所有初始状态未有效状态的传送门的下标。实现上，我们可以先用二分查找求出所有的b[i]，然后维护q的前缀和sum[i]，同时计算出所有的q，然后再遍历一遍全部的传送门找到初始有效的传送门，加上相应的q值即可。注意取模的一些易错点。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 2e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;

LL to[maxn], x[maxn], y[maxn], s[maxn];
int n;
LL sum[maxn], q[maxn];

int cal(int k) {
    int l = 1, r = n;
    while(l < r) {
        int mid = l + r >> 1;
        if(x[mid] >= k) 
            r = mid;
        else l = mid + 1;
    }
    return l;
}

int main(int argc, char const *argv[]) {
    cin >> n;
    for(int i = 1; i <= n; i++) scanf("%lld %lld %lld",x + i, y + i, s + i);
    for(int i = 1; i <= n; i++) {
        to[i] = cal(y[i]);
    }    
    for(int i = 1; i <= n; i++) {
        q[i] = (x[i] - y[i] + mod + sum[i-1] - sum[to[i] - 1] + mod) % mod;
        sum[i] = (sum[i-1] + q[i]) % mod;
    }
    LL ans = (x[n] +1) % mod;
    for(int i = 1; i <= n; i++) {
        if(s[i] == 1) ans = (ans + q[i]) % mod;
    }
    cout << ans << endl;
    return 0;
}