UIC-ACM 月赛·February

比赛链接

A

[UIC 1030] 选择题.cpp >folded

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using std::cin, std::cout, std::string;
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 1e4 + 5;
const int INF = 1 << 30;
// const long long INF = 1LL << 60;
int n;
string inp[N];
int buk[4], ans;
void solve()
{
    string s, t;
    cin >> s >> t;
    buk[0] = buk[1] = buk[2] = buk[3] = 0;
    for (auto ch : t) buk[ch - 'A'] = 1;
    int cnt = 0;
    for (auto ch : s)
    {
        if (buk[ch - 'A'] != 1)
        {
            cnt = 5;
            break;
        }
        else cnt++;
    }
    if (cnt == 5) return;
    else if (cnt == t.size() and t.size() == 1) ans += 3;
    else if (cnt == t.size()) ans += 5;
    else ans += 2;
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    cout << ans;
    return 0;
}

B

[UIC 1031] 统计.cpp >folded

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using std::cin, std::cout, std::string;
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 2e5 + 5;
const int INF = 1 << 30;
// const long long INF = 1LL << 60;
int n, q, a[N], lft[N], rgt[N], bel[N];
void solve()
{
    n = read(), q = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) lft[i] = a[i] == a[i - 1] ? lft[i - 1] : i;
    for (int i = n; i >= 1; i--) rgt[i] = a[i] == a[i + 1] ? rgt[i + 1] : i;
    int nodecnt = 0;
    for (int i = 1; i <= n; i++) bel[i] = nodecnt, nodecnt += (rgt[i] == i);
    // for (int i = 1; i <= n; i++) cout << bel[i] << ' ';
    // puts("-------");
    // for (int i = 1; i <= n; i++)
    for (int l, r; q; q--)
    {
        l = read(), r = read();
        cout << bel[r] - bel[l] + 1 << '\n';
        // cout << q << '\n';
    }
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("B.in", "r", stdin);
#endif
    for (int T = 1; T--; solve());
    return 0;
}

C

[UIC 1032] 删除字符.cpp >folded

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using std::cin, std::cout, std::string;
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 1e6 + 5;
const int INF = 1 << 30;
// const long long INF = 1LL << 60;
int n, buk[27];
void solve()
{
    string s;
    cin >> n >> s;
    for (int i = 0; i < 26; i++) buk[i] = 0;
    int ans = 0, cnt = 0;
    for (auto ch : s)
    {
        if (!buk[ch - 'a']) cnt++;
        buk[ch - 'a']++;
        ans += cnt;
    }
    cout << ans << '\n';
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("C.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    return 0;
}

D

贴下 sol，讲的很清晰了

不难发现，对于每一列，一定是从最大的开始选择。而且不同列之间的选择是独立的，
所以可以先给每一列单独从大到小排序，然后再进行后续分析。
选择的这个过程实际上可以看作是一个大小为 N × K 的窗口从左往右滑动，并且这个 窗口是一个上三角的，即对于窗口的第 i 列，最多只能选择前 i 个物品。并且如果一次 性选择了 j 个，那么这个窗口还会向右一次性滑动 j 个单位。
设 f[i,j] 表示当前窗口左端点在第 i 列，且当前考虑到的是整个序列的第 j 列时收获的最大电子币之和。转移的话，只需要枚举第 j 列选择了多少个就行

[UIC 1033] 电子钱包.cpp >folded

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using std::cin, std::cout, std::string;
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int M = 1e5 + 5;
const int N = 10 + 5;
int n, m, k, a[N][M], sum[N][M], f[N][M];

void solve()
{
    n = read(), m = read(), k = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = read();
    for (int j = 1; j <= m; j++)
    {
        std::vector<int> b(n);
        for (int i = 1; i <= n; i++) b[i - 1] = a[i][j];
        std::sort(b.rbegin(), b.rend());
        for (int i = 1; i <= n; i++) a[i][j] = b[i - 1];
        for (int i = 1; i <= n; i++) a[i][j] += a[i - 1][j];
    }
    for (int i = 1; i + k - 1 <= m; i++)
        for (int j = i; j <= i + k - 1; j++)
        {
            int len = j - i + 1;
            for (int c = 0; c <= len and i + k - 1 + c <= m + 1; c++)
                f[len - c + 1][i + c] = std::max(f[len - c + 1][i + c], f[len][i] + a[c][j]);
        }
    int ans = 0;
    for (int i = 1; i <= k; i++)
        for (int j = 0; j <= m + 1; j++)
            ans = std::max(ans, f[i][j]);
    cout << ans;
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("D.in", "r", stdin);
#endif
    for (int T = 1; T--; solve());
    return 0;
}

E

看成数轴上的若干条线段，sum 是这 n 条线段长度的和

手玩一下交换一条线段，发现只有两条线段不交的时候才会使答案变大

[UIC 1034] 绝对值.cpp >folded

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using std::cin, std::cout, std::string;
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 1e6 + 5;
// const long long INF = 1LL << 60;
int n, a[N], b[N];
void solve()
{
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) b[i] = read();
    int ans = 0;
    for (int i = 1; i <= n; i++) ans += abs(a[i] - b[i]);
    int sum = ans, p = 1, q = 1;
    for (int i = 1; i <= n; i++)
    {
        if (std::max(a[i], b[i]) < std::max(a[p], b[p])) p = i;
        if (std::min(a[i], b[i]) > std::min(a[q], b[q])) q = i;
    }
    for (int i = 1; i <= n; i++)
        ans = std::max(ans, sum - abs(a[i] - b[i]) - abs(a[p] - b[p]) + abs(a[i] - b[p]) + abs(a[p] - b[i])),
        ans = std::max(ans, sum - abs(a[i] - b[i]) - abs(a[q] - b[q]) + abs(a[i] - b[q]) + abs(a[q] - b[i]));
    cout << ans << '\n';
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("E.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    return 0;
}