1941(div3)

A. Rudolf and the Ticket

从两个数组中各选择一个数字，求使得两个数字和不超过 $k$ 的个数

暴力即可

for (int i = 0;i < n;i++) {
	for (int j = 0;j < m;j++) {
		if (b[i] + c[j] <= k) {
			cnt++;
		}
	}
}

B. Rudolf and 121

现在有一个操作：$a[i]-=2,a[i-1]-=1,a[i+1]+=1$

问能否只通过这个操作使得数组变为 0

贪心即可

void solve() {
    int n;cin >> n;vector<int>a(n);
    for (int i = 0;i < n;i++)cin >> a[i];
    for (int i = 0;i < n;i++) {
        if (a[i] >= 1) {
            a[i + 1] -= 2 * a[i];a[i + 2] -= a[i];a[i] = 0;
        }
    }
    for (int i = 0;i < n;i++) {
        if (a[i]) {
            cout << "No\n";return;
        }
    }
    cout << "Yes\n";
}

C. Rudolf and the Ugly String

鲁道夫有一个长度为 $n$ 的字符串 $s$ 。如果字符串 $s$ 包含子串 ${}^{†}$ "pie "或子串 "map"，鲁道夫就会认为这个字符串 $s$ 很丑。派 "或子串 "map"，否则字符串 $s$ 将被视为优美。

Rudolf 希望通过删除一些字符来缩短字符串 $s$ 使其美观。

主角不喜欢吃力，所以他要求你删除最少的字符，使字符串变得漂亮。他可以删除字符串中任何***位置的字符（不仅仅是字符串的开头或结尾）。

主要是注意 mapie

void solve() {
    int n;cin >> n;string s;cin >> s;
    int cnt = 0;
    for (int i = 0;i < n;i++) {
        if (i + 2 < n) {
            if (s.substr(i, 3) == "map") {
                cnt++;
            } else if (s.substr(i, 3) == "pie") {
                cnt++;
            }
        }
        if (i + 4 < n) {
            if (s.substr(i, 5) == "mapie") {
                cnt--;
            }
        }
    }
    cout << cnt << '\n';
}

D. Rudolf and the Ball Game

鲁道夫和伯纳德决定和朋友们玩一个游戏。 $n$ 人站成一圈，开始互相扔球。他们按顺时针顺序从 $1$ 到 $n$ 依次编号。

让我们把球从一个人向他的邻居移动称为一次过渡。转换可以顺时针或逆时针进行。

初始时，球在编号为 $x$ 的棋手处（棋手按顺时针方向编号）。在第 $i$ 步时，持球人将球抛向 $r_i$ （ $1\le r_i\le n-1$ ）顺时针或 $7$ （ $2$ ）逆时针的距离。( $1\le r_i\le n-1$ ) 的距离顺时针或逆时针抛出。例如，如果有 $7$ 名球员，第 $2$ 名球员在接球后将球投掷到 $5$ 处，那么球将被第 $7$ 名球员（顺时针投掷）或第 $4$ 名球员（逆时针投掷）接住。该示例的图示如下。

由于下雨，比赛在 $m$ 次投掷后中断。雨停后，大家又聚在一起继续比赛。但是，没有人记得球在谁手里。结果，伯纳德记住了每次投掷的距离和**次投掷的方向（顺时针或逆时针）。

鲁道夫请你帮助他，根据伯纳德提供的信息，计算出 $m$ 次抛球后可能拿到球的球员人数。

Solution

DP/思维

虽然这题并没有用到 dp，但是DP 需要专项练习了！

这题 Jiangly 的思路很棒，将每次能走到的地方更新到 d 数组中去，每次再将 d 数组中能走到的全部赋值给 dp 数组，这样，dp 数组中就有最后一次能走到的全部位置了。

void solve() {
    int n, m, x;cin >> n >> m >> x;x--;
    vector<int> dp(n);dp[x] = 1;
    for (int i = 0;i < m;i++) {
        int d;char ch;cin >> d >> ch;
        vector<int> g(n);
        for (int j = 0;j < n;j++) {
            if (dp[j]) {
                if (ch != '1') {
                    g[(j + d) % n] = 1;
                }
                if (ch != '0') {
                    g[(j - d + n) % n] = 1;
                }
            }
        }
        dp = g;
    }
    cout << count(dp.begin(), dp.end(), 1) << '\n';
    for (int i = 0;i < n;i++) {
        if (dp[i])cout << i + 1 << ' ';
    }
    cout << '\n';
}

E. Rudolf and k Bridges

给出一条河，两边全为 0 的是岸边，每次可以选择一个 $i$，在这一行的河里搭桥，在这行的岸边必须要搭上支架，每两个支架之间的距离不得大于 $\mid j_1-j_2\mid -1$，现在要在这条河连续行建造 $k$ 座桥，求最小的总支架成本。

Solution

DP+单调队列

先算出每行最小的代价。到最后拿来枚举比较即可。

需要整理单调队列的模板。

需要详细了解单调队列的特性

void solve() {
    int n, m, k, d;
    std::cin >> n >> m >> k >> d;
    d++;
    
    std::vector<i64> cost(n);
    for (int i = 0; i < n; i++) {
        std::vector<int> a(m);
        for (int j = 0; j < m; j++) {
            std::cin >> a[j];
            a[j]++;
        }
        std::vector<i64> dp(m, inf);
        dp[0] = 1;
        std::deque<int> q;
        for (int j = 1; j < m; j++) {
	        //新入的数字下标是再原来的右边的，且还比前面的数小，则前面的数字就没用了
            while (!q.empty() && dp[j - 1] < dp[q.back()]) {
                q.pop_back();
            }
            q.push_back(j - 1);
            while (q.front() < j - d) {//j-d<->j-1-d+1( (j_2 - j_1)<=d )
                q.pop_front();
            }
            dp[j] = a[j] + dp[q.front()];
        }
        cost[i] = dp[m - 1];
    }
    
    i64 ans = inf;
    for (int i = 0; i + k <= n; i++) {
        i64 sum = 0;
        for (int j = 0; j < k; j++) {
            sum += cost[i + j];
        }
        ans = std::min(ans, sum);
    }
    std::cout << ans << "\n";
}

F. Rudolf and Imbalance

给出长度分别为 $n,m,k$ 的数组 $a,d,f$，$a$ 是升序的，现在可以在 $d,f$ 数组中各抽取一个数字放入 $a$ 数组，并按照升序排列。

求 $max(a_i-a_{i-1})$ 的最大值是多少？

Solution

二分+双指针

由于只能操作一次，所以肯定是对 $a_i-a_{i-1}$ 差距最大的位置进行操作，对第二大的一定不操作，所以操作后的答案一定不小于原来序列的第二大 $(a_i-a_{i-1})$

先找到序列中 $max(a_i-a_{i-1})$ 的 $i$

对于 $max(a_i-a_{i-1})$,我们总是要想办法去“中和”这个最大值，最好的情况就是，从 $d,f$ 序列选出的数字恰好是 $\lfloor \frac{a_{i-1}+a_i}{2}\rfloor$ ,就算到不了这个值，也要尽可能的接近这个值。

先找出最大值和第二大的值备用，再进行二分，二分出口会有 $l,r$ 两个值，分别比较取最小即可。

#define int long long
void solve() {
    int n, m, k;cin >> n >> m >> k;
    vector<int> a(n), b(m), c(k);
    for (int i = 0;i < n;i++)cin >> a[i];
    for (int i = 0;i < m;i++)cin >> b[i];
    for (int i = 0;i < k;i++)cin >> c[i];
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    int ma = 0, p = -1;
    for (int i = 1;i < n;i++) {
        if (a[i] - a[i - 1] > ma) {
            ma = a[i] - a[i - 1];
            p = i;
        }
    }
    int ans = ma;
    ma = 0;
    for (int i = 1;i < n;i++) {
        if (i != p && a[i] - a[i - 1] > ma) {
            ma = a[i] - a[i - 1];
        }
    }

    int t = a[p] + a[p - 1] >> 1;
    for (int i = 0;i < m;i++) {
        int l = 0, r = k - 1;
        while (l + 1 < r) {
            int mid = l + r >> 1;
            if (b[i] + c[mid] <= t) {
                l = mid;
            } else {
                r = mid;
            }
        }
        ans = min(ans, max({ma,abs(b[i] + c[l] - a[p - 1]),abs(b[i] + c[l] - a[p])}));
        ans = min(ans, max({ma,abs(b[i] + c[r] - a[p - 1]),abs(b[i] + c[r] - a[p])}));
    }
    cout << ans << '\n';
}

G. Rudolf and Subway

(待更 $\dots$)