A:AC

方法：可反悔贪心
这个方法我也是第一次学到，当时在赛场上想到的是dp，然后看到数据量直接劝退了。
首先为了理解什么是可反悔贪心，我们先偏离一下题目，看一道另外的一个可反悔贪心题目。
种树
我们很容易想到一个dp写法，dp[i][j]表示前i个树坑中种了j棵树的收获，但是数据量直接就劝退，于是我们先尝试着模拟一遍过程。
容易想到一种贪心的方法， 每次都取获利最高的树坑种树，然后做一个标记，表示该坑两边都不种树，最后得到的获利我们就作为最大获利值。用一个优先队列维护即可。但是我们也不难得出，这个方法肯定不是正确解法，因为可能最大值的两边加起来是大于它本身的，比如8，9，8，1这种就是，选9，1肯定不如8，8。于是我们需要对贪心做一个优化。
那么如何优化呢？很明显，就拿8，9，8，1这个举例子，如果需要选2个的话，我们就要给自己选了最大值之后后悔的余地。
我们这样操作，每次取出a[i]时候，我们同时加入a[i - 1] + a[i + 1] - a[i]这个数字，举个例子
在8，9，8，1这四个数中选择2个数。我们先选择9，然后加入8 + 8 - 9 = 7，然后再选择7（因为8被标记不能选了）于是就得到了9 + 7 = 16的收获。但是我们实际上选的是8 + 8，只不过形式换成了9 + 8 + 8 - 9，相当于我虽然一开始选了9，但是我一看好像另外两个更优，于是就去掉9选择8 + 8
具体我们用一个双向链表维护，选择一个数a[i]之后，将其左右两边的数删除并加入一个a[i - 1] + a[i + 1] - a[i]

#include <bits/stdc++.h>
#define PLI pair<LL, int>
#define LL long long
using namespace std;
const int N = 5e5 + 10;
LL a[N];
int pre[N], nex[N];
bool v[N];//标记是否已经出队
priority_queue<PLI> q;
inline void del(int u) {
    nex[pre[u]] = nex[u];
    pre[nex[u]] = pre[u];
}
int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i], q.push({a[i], i});
        pre[i] = i - 1, nex[i] = i + 1;
    }
    LL ans = 0, res = 0;
    while (m -- ) {
        auto t = q.top();
        q.pop();
        while (v[t.second]) {
            t = q.top();
            q.pop();
        }
        int u = t.second;
        v[nex[u]] = v[pre[u]] = true;
        ans += a[u];
        if (res >= ans) break;
        else res = ans;
        a[u] = a[nex[u]] + a[pre[u]] - a[u];
        del(nex[u]), del(pre[u]);
        q.push({a[u], u});
    }
    cout << res << endl;
    return 0;
}

回到原题，我们来看题目。
首先乍一看还是看不出来我们到底如何贪心。于是我们可以构造一个数组从出来
c[i]表示让s[i]与s[i + 1]构成ac的代价，于是题目就变成了在一定代价内，选择不相邻的两个c使得总ac数最多，这就是我们刚刚看到的原题，但是这题有一个难点，就是需要输出方案具体的内容，这里主要讲如何输出方案数
这里的重点就是，我们如何记录到底是选了i还是选择后悔选i，我们这里参考三个顶俩队伍的代码，用一个另外的h来替代我们当前选到的点，于是也需要一个新的L和R数组，具体看代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;//由于我们新造了结点来代替选择到的结点，于是开2倍的空间
int c[N];
char s[N];
int l[N], r[N], R[N], L[N];//这里l[]r[]都表示原始的双向链表，R[]L[]表示新的结点构成的链表
bool v[N];//这里表示是否被标记过
bool tr[N];//这里表示被标记过的多次叠加的结果
int n, k;
priority_queue<PII, vector<PII>, greater<>> q;
inline void del(int u) {
    l[r[u]] = l[u];
    r[l[u]] = r[u];
}
inline void doit(int u, int h) {
    v[l[u]] = v[r[u]] = true;
    tr[L[u] - 1] ^= 1;//如果是原始的结点(就是n以内的)，就直接取上一个和本身，否则就说明我们之前取过这个，就要往外扩展一层。
    tr[R[u]] ^= 1;
    //接下来都是更新链表的操作
    if (l[u] != 0 && r[u] != n) {//注意两边边界，如果选到边界上说明没有可能会后悔，直接删除结点即可
        L[h] = L[l[u]];
        R[h] = R[r[u]];
        c[h] = c[l[u]] + c[r[u]] - c[u];
        del(l[u]), del(r[u]);
        r[l[u]] = l[r[u]] = h;
        l[h] = l[u], r[h] = r[u];
        q.push({c[h], h});
    } else if (l[u] == 0 && r[u] != n) {
        del(u), del(r[u]);
    } else if (l[u] != 0 && r[u] == n) {
        del(u), del(l[u]);
    }
}
int main() {
    cin >> n >> k;
    scanf("%s", s + 1);
    for (int i = 1; i < n; i ++ ) {
        c[i] = (s[i] != 'a') + (s[i + 1] != 'c');//构造c数组
        l[i] = i - 1, r[i] = i + 1;
        L[i] = i, R[i] = i;
        q.push({c[i], i});
    }
    int ans = 0;
    int h = n + 2;//新结点的位置
    while (ans < n / 2) {
        auto t = q.top();
        q.pop();
        if (v[t.second]) continue;
        int u = t.second;
        k -= c[u];
        if (k < 0) break;
        ans ++ ;
        h ++ ;
        doit(u, h);
    }
    cout << ans << endl;
    for (int i = n - 1; i; i -- ) {//倒序枚举，计算后缀异或和，当为真时，说明当前已经被改变，否则说明还没改变。这里可以自己画一遍模拟一下，以更好理解。
        tr[i] ^= tr[i + 1];
        if (tr[i]) s[i + 1] = 'c', s[i] = 'a';
    }
    printf("%s", s + 1);
    return 0;
}

C-Cities

考点：区间dp
比赛的时候竟然每看出来是区间dp，还一直往差分方向想，是我太菜了
其实不难赛后过题的人不配说这句话，状态转移和状态表达还是很(chao)好(ji)想(nan)的，大概就是
状态表达：dp[i][j]表示合并从i到j的代价最小值
状态转移：
1、当a[i] == a[j]时dp[i][j] = dp[i + 1][j - 1] + 1
2、当a[k] == a[j]时\(min_{i < k < j}(dp[i][k - 1] + dp[k + 1][j] + 1)\)
3、当a[k] == a[i] == a[j]时\(min_{i < k < j}(dp[i][k - 1] + dp[k + 1][j])\)
4、一般情况dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1)
有一点需要注意的dp[i][j]的最大值应该是j - i，因为最坏情况就是全部点都不同色
我们用记忆化搜索来写
注意，为了枚举k，我们采用一个预处理，即用pre[i]表示颜色为a[i] 的上一个位置出现在哪

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N = 6060;
int dp[N][N];
int a[N], pre[N];
int dfs(int l, int r) {
    if (l == r) return 0;
    if (dp[l][r] != INF) return dp[l][r];
    int ans = r - l;
   ans = min(ans, dfs(l + 1, r) + 1);
   ans = min(ans, dfs(l, r - 1) + 1);
    if (a[l] == a[r]) ans = min(ans, dfs(l + 1, r - 1) + 1);
    for (int k = pre[r]; k > l; k = pre[k]) {
        ans = min(ans, dfs(l, k - 1) + dfs(k + 1, r) + 1);
        if (a[k] == a[l] && a[k] == a[r])
            ans = min(ans, dfs(l, k - 1) + dfs(k + 1, r));
    }
    return dp[l][r] = ans;
}
inline void solve() {
    memset(dp, 0x3f, sizeof dp);
    int n; cin >> n;
    map<int, int> f;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        if (a[i] == a[i - 1]) {
            i --, n --;
            continue;
        }
        pre[i] = f[a[i]];
        f[a[i]] = i;
    }
    int ans = dfs(1, n);
    cout << ans << endl;
}
int main() {
    int t; cin >> t;
    while (t -- ) solve();
    return 0;
}

G-Gift

打比赛的时候乍一看是个大模拟，后来读完题后就秒看出来是个dp，但是无奈当时被L题卡着了，所以没开这题就很难受
方法：背包dp
感觉就是普通的背包dp，但是需要注意的点比较多，我们先写出状态表达和状态转移
状态表达：dp[i][j][k]表示在前k天中，只给前i个人做蛋糕，其中前i个人中还有j个人没做的最大获利
状态转移：状态转移:
1、不给i做蛋糕，就是dp[i - 1][j - 1][k]
2、给i做蛋糕，就是dp[i - 1][j][k - c[i]] + v[i]
算出不收到蛋糕的人数，剩下的都用礼物给就行。用f[j]表示规定钱数内买j件礼物的最大获利
这样就可以写了

#include <bits/stdc++.h>
using namespace std;
const int N = 550, M = 17;
int n, m, w;
int dp[N][M][370];//dp[i][j][k]表示前k天中，只对前i个人考虑是否做蛋糕，并且在前i个人中还有j个人没有做的情况下的最大获利值
int f[M];//f[j]表示在规定钱数内买j件礼物的最大获利值
int a[M], b[M];
int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int s[M];
struct node {
    int c, v;
    int day;//表示是2021年的第day天
    bool operator < (const node &B) const {
        return day < B.day;
    }
} d[N];
inline void solve() {
    cin >> n >> m >> w;
    for (int i = 1; i <= n; i ++ ) {
        int yy, mm, dd;
        scanf("%d-%d-%d", &yy, &mm, &dd);
        cin >> d[i].c >> d[i].v;
        d[i].day = s[mm - 1] + dd;
        if (mm == 2 && dd == 29) i --, n --;
    }
    for (int i = 1; i <= m; i ++ ) cin >> a[i] >> b[i];
    sort(d + 1, d + 1 + n);
    memset(f, 0, sizeof f);
    for (int i = 0; i < (1 << m); i ++ ) {
        int cnt = 0, sum = 0, val = 0;
        for (int j = 0; j < m; j ++ ) {
            if (i >> j & 1) {
                cnt ++ ;
                sum += a[j + 1];
                val += b[j + 1];
            }
        }
        if (sum <= w) f[cnt] = max(f[cnt], val);
    }
    for (int i = 0; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; k <= 365; k ++ ) dp[i][j][k] = -1e9;
    dp[0][0][0] = 0;
    /*
     * 状态转移:
     * 1、不给i做蛋糕，就是dp[i - 1][j - 1][k];
     * 2、给i做蛋糕，就是dp[i - 1][j][k - c[i]] + v[i];
     */
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 0; j <= min(i, m); j ++ ) {
            for (int k = 0; k <= 365; k ++ ) {
                dp[i][j][k] = dp[i - 1][max(j - 1, 0)][k];//不给i做蛋糕
                if (k >= d[i].c && k <= d[i].day)//只有这样才可以给i做蛋糕
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - d[i].c] + d[i].v);
            }
        }
    }
    int ans = 0;
    for (int j = 0; j <= m; j ++ ) {
        for (int k = 0; k <= 365; k ++ ) ans = max(ans, dp[n][j][k] + f[j]);
    }
    cout << ans << endl;
}
int main() {
    for (int i = 1; i <= 12; i ++ ) s[i] = s[i - 1] + mon[i];
    int t; cin >> t;
    while (t -- ) solve();
    return 0;
}

L-Simone and graph coloring

这里先给出队友的线段树做法
接下来给出我们队在比赛时候的写法（比较容易写一些）
方法：二分
具体就是，先暴力，后优化
首先写一个暴力写法

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int col[N];
inline void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    col[1] = 1;
    for (int i = 2; i <= n; i ++ ) {
        int j = 1;
        for (; j < i; j ++ ) {
            if (a[i] > a[j]) {
                col[i] = col[j];
                break;
            }
        }
        if (!col[i]) col[i] = col[i - 1] + 1;
    }
    int ans = 0;
    for (int i = 1; i <= n; i ++ ) ans = max(ans, col[i]);
    cout << ans << endl;
    for (int i = 1; i <= n; i ++ ) cout << col[i] << ' ';
    cout << endl;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while (t -- ) solve();
    return 0;
}

当然这个肯定是不行的，我们想办法优化，我们发现，每次我们要填色时，都是从前往后找，找到一个比自己小的数字，然后和他填一样的颜色即可，而这个的时间是O(n)的，我们可以从这里下手
我们定义一个数组c，c[i]表示颜色为i的最大数字为多少，我们注意到，由于数字大的染上颜色要尽量小，所以c数组是具有单调性的，我们二分查找即可

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], c[N], ans[N];
int main() {
    int t;
    scanf("%d", &t);
    while (t -- ) {
        int n; scanf("%d", &n);
        for (int i = 0; i <= n + 1; i ++ ) c[i] = 0;
        for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
        int cnt = 0;
        for (int i = 1; i <= n; i ++ ) {
            int l = 1, r = n;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (c[mid] > a[i]) l = mid + 1;
                else r = mid;
            }
            if (c[l] == 0) cnt ++ ;
            c[l] = a[i];
            ans[i] = l;
        }
        printf("%d\n", cnt);
        for (int i = 1; i <= n; i ++ ) printf("%d ", ans[i]);
        puts("");
    }
    return 0;
}