Educational Codeforces Round 96 (Rated for Div. 2)_综合

传送门

Educational Codeforces Round 96 (Rated for Div. 2)

A

多重部分和问题， $d p [i] [j]$ 代表使用 $0 ? i$ 种数字是否能组合为 $j$
$dp[i-1][j]\ |\ dp[i][j-N[i]]$ 动态规划的同时记录任一可行解。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 1005
int N[3] = {
    3, 5, 7};
int dp[maxn], rec[maxn][3];int main()
{
    int sz = sizeof(int) * 3;dp[0] = 1;for (int i = 0; i < 3; i++){
    for (int j = 0; j < maxn - N[i]; j++){
    if (dp[j]){
    dp[j + N[i]] = 1;memcpy(rec[j + N[i]], rec[j], sz);++rec[j + N[i]][i];}}}int t, n;scanf("%d", &t);while (t--){
    scanf("%d", &n);if (dp[n]){
    printf("%d %d %d\n", rec[n][0], rec[n][1], rec[n][2]);}else{
    puts("-1");}}
}

B

贪心地从 $[1, k]$ 多的水瓶向最多的水平倒水。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 200005
typedef long long ll;
int a[maxn];int main()
{
    int t, n, k;scanf("%d", &t);while (t--){
    scanf("%d%d", &n, &k);for (int i = 0; i < n; i++){
    scanf("%d", a + i);}sort(a, a + n);int lb = max(0, n - k - 1);ll res = 0;for (int i = lb; i < n; i++){
    res += a[i];}printf("%lld\n", res);}
}

C

最终答案大于 $1$ ，那么最优解为 $2$ 。贪心地取最大的两个数进行合并，最后一步为 $3$ 与 $1$ 合并。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define maxn 200005
int rec[maxn][2];int main()
{
    int t, n;scanf("%d", &t);while (t--){
    scanf("%d", &n);priority_queue<int> q;for (int i = 1; i <= n; ++i){
    q.push(i);}int k = 0;while (q.size() >= 2){
    int a = q.top();q.pop();int b = q.top();q.pop();rec[k][0] = a, rec[k++][1] = b;q.push((a + b + 1) >> 1);}printf("%d\n", q.top());for (int i = 0; i < k; ++i){
    printf("%d %d\n", rec[i][0], rec[i][1]);}}
}

D

贪心地取最早被操作二删除的（即最靠串首）的连续 $0$ 或 $1$ 其中一个进行操作一；若串中不存在连续的 $0$ 或 $1$ ，那么每一轮操作一可以从串首或串尾进行删除，然后进行操作二，每轮删除 $2$ 个字符。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
#define maxn 200005
int cnt[maxn];
char s[maxn];int main()
{
    int t, n;scanf("%d", &t);while (t--){
    scanf("%d", &n);scanf(" %s", s);set<int> st;int k = 0, pre = -1, cur = 0;while (cur < n){
    while (cur + 1 < n && s[cur] == s[cur + 1])++cur;cnt[k] = cur - pre;if (cnt[k] > 1)st.insert(k);++k;pre = cur, cur = pre + 1;}int step = 0, l = 0, r = k;while (l < r){
    while (!st.empty() && *st.begin() < l){
    st.erase(st.begin());}if (st.empty()){
    step += (r - l + 1) >> 1;break;}else{
    if (cnt[l] > 1){
    }else{
    if (--cnt[*st.begin()] == 1){
    st.erase(st.begin());}}++l;}++step;}printf("%d\n", step);}
}

E

记录字符集各自出现的位置，将字符串反转，从后向前遍历，每次取原串离当前反串位置最近的字符向后进行交换；用 $B I T$ 维护原串字符交换后各字符的相对索引值。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 200005
#define base 26
int n, pos[base][maxn], ptr[base];
int bit[maxn];
char s[maxn];void add(int i, int x)
{
    while (i <= n){
    bit[i] += x;i += i & -i;}
}int sum(int i)
{
    int s = 0;while (i > 0){
    s += bit[i];i -= i & -i;}return s;
}int main()
{
    scanf("%d %s", &n, s);for (int i = 0; i < n; i++){
    int c = s[i] - 'a';pos[c][ptr[c]++] = i;}for (int i = 1; i <= n; i++){
    add(i, 1);}reverse(s, s + n);long long res = 0;for (int i = n - 1; i >= 0; i--){
    int c = s[i] - 'a', j = pos[c][--ptr[c]];res += sum(n) - sum(j + 1);add(j + 1, -1);}printf("%lld\n", res);
}

F 补题

$∑a[i]\sum a[i]$ 是一定要消耗的子弹数量，目标是最小化丢弃的子弹数。 $d p [i] [j]$ 代表第 $i$ 轮开始剩余 $j$ 颗子弹，设 $r$ 为第 $i$ 轮结束剩余的子弹，则有重新填充与保留子弹两种选择
${dp[i+1][k]=min{dp[i][j]+j}dp[i+1][r]=min{dp[i][j]}\begin{cases}dp[i+1][k] = min\{dp[i][j] + j\}\\ dp[i+1][r] = min\{dp[i][j]\}\\ \end{cases}$ 每一轮剩余各种子弹数的情况都对应了一种子弹剩余的情况，且可能进行重新填充弹药，那么第 $i$ 状态总数不超过 $i + 1$ ，那么总状态数 $O(n^2)$ ，用 $m a p$ 维护。

考虑到第 $i + 1$ 轮前可以填充弹药,需要满足 $l_{i+1}>r_i$ 或者弹药消灭怪兽的时间 $t<r_i$ ，那么按每一轮进行 $D P$ 时需要额外记录是否能够填充弹药的信息。

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
#define maxn 2005
typedef long long ll;
struct node
{
    ll n;bool f;
};
typedef map<int, node> mp;
typedef mp::iterator ite;
int N, K, L[maxn], R[maxn], A[maxn];
mp dp[maxn];inline void rem(int a, int j, int &r, int &d)
{
    if (a <= j){
    r = j - a, d = 0;}else{
    d = (a - j + K - 1) / K, r = d * K - (a - j);}
}inline bool judge(int i, int r, bool f, bool c)
{
    int n = R[i] - L[i];if (f){
    n += (c || L[i] > R[i - 1]) ? 1 : 0;return A[i] <= 1LL * n * K;}return A[i] <= 1LL * n * K + r;
}int main()
{
    scanf("%d%d", &N, &K);ll s = 0;for (int i = 0; i < N; i++){
    scanf("%d%d%d", L + i, R + i, A + i);s += A[i];}dp[0][K] = node{
    0, 0};for (int i = 0; i < N; i++){
    for (ite it = dp[i].begin(); it != dp[i].end(); ++it){
    int j = it->first, r, d;node &cur = it->second;if (judge(i, j, 0, cur.f)){
    rem(A[i], j, r, d);node &nxt = dp[i + 1][r];if (!nxt.n || cur.n < nxt.n){
    nxt.n = cur.n, nxt.f = d < R[i] - L[i];}}if (j < K){
    if (judge(i, 0, 1, cur.f)){
    rem(A[i], (cur.f || L[i] > R[i - 1]) ? K : 0, r, d);node &nxt = dp[i + 1][r];if (!nxt.n || cur.n + j < nxt.n || (cur.n + j == nxt.n && !nxt.f)){
    nxt.n = cur.n + j, nxt.f = d < R[i] - L[i];}}}}}ll res = LLONG_MAX;for (ite it = dp[N].begin(); it != dp[N].end(); ++it){
    res = min(res, it->second.n);}printf("%lld\n", res == LLONG_MAX ? -1 : res + s);return 0;
}

考虑 $m a p$ 以及记录额外信息的开销，修改动态规划的定义， $d p [i]$ 代表到达第 $i$ 轮开始弹药满匣的最小花费，那么枚举 $i$ 迭代更新 $d p [j], j > i$ 。

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 2005
typedef long long ll;
ll N, K, L[maxn], R[maxn], A[maxn], dp[maxn];inline void rem(int i, ll &r, ll &d)
{
    if (A[i] <= r){
    r -= A[i], d = 0;}else{
    d = (A[i] - r + K - 1) / K, r = d * K - (A[i] - r);}
}inline bool judge(int i, ll r)
{
    return A[i] <= (R[i] - L[i]) * K + r;
}int main()
{
    scanf("%lld%lld", &N, &K);ll s = 0;for (int i = 0; i < N; i++){
    scanf("%lld%lld%lld", L + i, R + i, A + i);s += A[i];}fill(dp, dp + N, LLONG_MAX);dp[0] = 0;ll res = LLONG_MAX;for (int i = 0; i < N; i++){
    ll r = K, d, tmp = dp[i];for (int j = i; j < N; j++){
    if (tmp == LLONG_MAX || !judge(j, r)){
    break;}else{
    rem(j, r, d);if (j + 1 < N){
    if (d < R[j] - L[j] || R[j] < L[j + 1]){
    dp[j + 1] = min(dp[j + 1], tmp + r);}}else{
    res = min(res, tmp);}}}}printf("%lld\n", res == LLONG_MAX ? -1 : res + s);return 0;
}

Educational Codeforces Round 96 (Rated for Div. 2)

传送门

A

B

C

D

E

F 补题

G 补题