C – Brutality

题如其名，相当暴力。直接暴力排序每一个连续段的值，然后计数统计即可。

// C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 2000;
int n, k, arr[MAX_N];
char str[MAX_N];
bool cmp(int a, int b)
{
    return a > b;
}
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    scanf("%s", str + 1);
    char previousVal = str[1];
    long long previousKey = 1;
    for (int i = 1; i <= n; i++)
    {
        if (str[i] != previousVal)
            sort(arr + previousKey, arr + i, cmp), previousKey = i;
        previousVal = str[i];
    }
    sort(arr + previousKey, arr + n + 1, cmp);
    long long tim = 0, ans = 0;
    char lastkey = str[1];
    for (int i = 1; i <= n; i++)
    {
        if (str[i] != lastkey)
            tim = 0, lastkey = str[i];
        if (tim < k)
            tim++, ans += arr[i];
    }
    printf("%lld", ans);
    return 0;
}

D – Compression

暴力题的又一典范。

枚举\(n\)的因数，然后在\((\frac{n}{i})^2\)的格子里进行前缀和验证即可：每一块的和要么是块长的平方要么就是 0.

// D.cpp
// Fuck codeforces.
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5300;
int n, mat[MAX_N][MAX_N], prefix[MAX_N][MAX_N], upb = 0x3f3f3f3f;
int getNum(char ch)
{
    if (ch <= '9' && ch >= '0')
        return ch - '0';
    return 10 + ch - 'A';
}
bool check(int blk)
{
    int tot = n / blk;
    for (int i = 1; i <= tot; i++)
        for (int j = 1; j <= tot; j++)
        {
            int x = blk * i, y = blk * j;
            int ans = prefix[x][y] - prefix[x - blk][y] - prefix[x][y - blk] + prefix[x - blk][y - blk];
            if (ans == blk * blk || ans == 0)
                continue;
            else
                return false;
        }
    return true;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n / 4; j++)
        {
            char ch = getchar();
            while (ch == '\n')
                ch = getchar();
            int num = getNum(ch);
            for (int k = 0; k < 4; k++)
                mat[i][(j - 1) * 4 + k + 1] = (num >> (3 - k)) & 1;
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + mat[i][j];
    // horizontial
    for (int i = 1; i <= n; i++)
    {
        int lst = 1;
        for (int j = 1; j <= n; j++)
            if (mat[i][j] != mat[i][lst])
                upb = min(upb, j - lst + 1), lst = j;
    }
    for (int i = 1; i <= n; i++)
    {
        int lst = 1;
        for (int j = 1; j <= n; j++)
            if (mat[j][i] != mat[lst][i])
                upb = min(upb, j - lst + 1), lst = j;
    }
    int ans = 1;
    for (int i = 2; i <= n; i++)
        if (n % i == 0 && check(i))
            ans = max(ans, i);
    printf("%d", ans);
    return 0;
}

E – Vasya and Binary String

考虑进行 DP。设状态 \(dp[st][ed][prefix]\) ，意义为串在\([st, ed]\)之间其中\(st\)已经连续到了\(prefix\)个了。枚举中间位\(i\)，考虑以下转移：

• 如果开始位的字符与此时的字符一致，即\(str[st] == str[i]\)，可以考虑将\(str[st+1, i-1]\)作为独立子问题进行递归，然后对于右边剩余的段\(str[i, ed]\)，相当于连续个数加一，所以继续递归下去：\(dp(i, ed, prefix+1)\)。
• 如果不一致瞎转移即可。

// E.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 110;
ll n, arr[MAX_N], dp[MAX_N][MAX_N][MAX_N];
char str[MAX_N];

ll dfs(int st, int ed, int pre)
{
    if (ed - st <= 0)
        return 0;
    if (ed - st == 1)
        return arr[pre];
    ll &ans = dp[st][ed][pre];
    if (ans != 0)
        return ans;
    ans = arr[pre] + dfs(st + 1, ed, 1);
    for (int i = st + 1; i < ed; i++)
        if (str[i] == str[st])
            ans = max(ans, dfs(st + 1, i, 1) + dfs(i, ed, pre + 1));
    return ans;
}

int main()
{
    scanf("%lld%s", &n, str);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]);
    printf("%lld", dfs(0, n, 1));
    return 0;
}

F – Vasya and Endless Credits

神仙题之一。注意到贷款顺序肯定优先贷\(b\)小的贷款项目，考虑进行 DP，设计状态\(dp[i][j]\)，意义为「考虑了前\(i\)个元素且打算还完\(j\)个贷款的最大获利」。所以可以考虑几种转移：

• 考虑换光或者不借，\(dp[i][0] = dp[i-1][0] + curt, curt = max(0, a_i – b_i*k_i)\)，取最大值可以直接决策。
• 考虑不换一部分，枚举\(j\)为打算还的项目。\(dp[i][j] = max(dp[i-1][j]+curt, dp[i-1][j-1]+a_i-b_i*(j_i-1))\)。

写代码吧。

// F.cpp
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int MAX_N = 550;
struct credit
{
    ll a, b, k;
    bool operator<(const credit &crd) const { return b > crd.b; }
} credits[MAX_N];
int n;
ll dp[MAX_N][MAX_N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld%lld", &credits[i].a, &credits[i].b, &credits[i].k);
    sort(credits + 1, credits + 1 + n);
    for (int i = 1; i <= n; i++)
        dp[0][i] = -1e9;
    for (int i = 1; i <= n; i++)
    {
        ll curt = max(0LL, credits[i].a - credits[i].b * credits[i].k);
        dp[i][0] = dp[i - 1][0] + curt;
        for (int j = 1; j <= i; j++)
            dp[i][j] = max(dp[i - 1][j] + curt, dp[i - 1][j - 1] + credits[i].a - credits[i].b * (j - 1));
    }
    ll ans = 0;
    for (int i = 0; i <= n; i++)
        ans = max(ans, dp[n][i]);
    printf("%lld", ans);
    return 0;
}