Codeforces Round #807 (Div. 2)

A.Mark the Photographer

题目大意

要给$2n$个人拍照。把他们排成两排，每排$n$个人，要求是第二排的人要比他前面这个人高至少$x$。给定所有人身高，问能不能让他们站成符合要求的队形。

解题思路

贪心。先上结论：
能站成符合要求的队形 <==> 将身高从小到大排序后，对于从$1$到$n$的$i$，都有$h_{n+i}-x\geq h_i$
可以这样证明：
1.假设现在有一个合法的队形如图所示，那么有$a-b\geq x$和$c-d \geq x$

2.倘若$b\geq c$，不妨交换$b$，$c$位置

3.得到了一个新的队形，而这个新队形是一定合法的。因为$a-c\geq a-b \geq x$，且$b-d\geq c-d\geq x$。

上面的三步说明了一件事：即使有不是按我们这种贪心策略站的合法队形，这个合法队形也一定能转换成按贪心策略站的队形。(因为可以重复以上步骤，直到第二排的所有人都比第一排高)。然后结论就显然了。

具体代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, x;
int h[N];
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n >> x;
        for (int i = 1; i <= n << 1; i++)
            cin >> h[i];
        sort(h + 1, h + n * 2 + 1);
        bool flag = true;
        for (int i = 1; i <= n; i++)
        {
            if (h[i + n] - x < h[i])
            {
                cout << "NO" << '\n';
                flag = false;
                break;
            }
        }
        if (flag)
            cout << "YES" << '\n';
    }
    return 0;
}

B.Mark the Dust Sweeper

题目大意

有$n$个房间要清理，编号$1$到$n$，每个房间有$a_i$的垃圾，每次清扫可以选择$i,j$($i\leq j$且要求$a_i,a_{i+1}$……$a_{j-1}$都大于零)，使得$a_i$减一，$a_j$加一。问至少清理几次能使得除了最后一个房间外的别的房间都没有垃圾。

解题思路

要把垃圾都扫到最后一个房间，如果不考虑(要求$a_i,a_{i+1}$……$a_{j-1}$都大于零)这个要求，那么$ans=\sum_{i=1}^{n-1} {a_i}$。然后再思考这个要求，其实就是多了填充$0$的步数，每填充一个$0$需要消耗一步,所以$ans+=\sum_{i=l}^{n-1} {(a_i==0)}$。$l$是第一个$a_i$大于$0$的位置。

具体代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL; //记得开LL
const int N = 2e5 + 10;
int n;
int a[N];
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        LL ans = 0;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        int l = 1;
        while (a[l] == 0)
            l++;
        for (int i = 1; i <= n - 1; i++)
            ans += (LL)a[i];
        for (int i = l; i <= n - 1; i++)
            ans += (LL)(a[i] == 0);
        cout << ans << '\n';
    }
    return 0;
}

C.Mark and His Unfinished Essay

题目大意

给一个字符串$s$，可以进行若干次复制粘贴操作。每次复制粘贴操作可以选中$s[l,r]$，把它粘贴到字符串末尾。所有复制粘贴操作结束后会给若干询问，给一个$k$，问$s[k]$是什么字符

解题思路

数据范围很大，说明题意不是要真的模拟去把最后的字符串求出来。那么题目考察的应该是怎么对询问优化。

为了清晰可以看看如图这种情况，是复制粘贴了三次。现在要查询$s[k]$，先跳到蓝串本来的位置，发现这里正好也在绿串上，那么再跳回绿串本来的位置上，发现这里已经是黑串(即原串)上，那么就找到答案了。想到这里代码实现就不难了。

具体代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, c, q;
string s;
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n >> c >> q >> s;
        vector<LL> l(c + 1), r(c + 1), d(c + 1);
        l[0] = 0;
        r[0] = n;
        for (int i = 1; i <= c; i++)
        {
            LL a, b;
            cin >> a >> b;
            a--, b--;
            l[i] = r[i - 1];
            r[i] = l[i] + (b - a + 1);
            d[i] = l[i] - a;
        }
        while (q--)
        {
            LL k;
            cin >> k;
            k--;
            for (int i = c; i >= 1; i--)
            {
                if (k < l[i])
                    continue;
                else
                    k -= d[i];
            }
            cout << s[k] << '\n';
        }
    }
    return 0;
}