『算法-ACM 竞赛-CodeForces』1323 div2 题解 ABC

A. Even Subset Sum Problem
签到题

#include <bits/stdc++.h>
using namespace std;
template <typename t>
void read(t &x)
{
    char ch = getchar();
    x = 0;
    t f = 1;
    while (ch < '0' || ch > '9')
        f = (ch == '-' ? -1 : f), ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    x *= f;
}

#define wi(n) printf("%d ", n)
#define wl(n) printf("%lld ", n)
#define P puts(" ")
typedef long long ll;
#define MOD 1000000007
#define mp(a, b) make_pair(a, b)
#define N 20005
#define rep(i, j, n) for (int i = j; i <= n; i++)
#define red(i, n, j) for (int i = n; i >= j; i--)
#define fil(a, n) rep(i, 0, n, ) read(a[i])

//---------------https://lunatic.blog.csdn.net/-------------------//

vector<int> a[2];
int main()
{

    int t, n, x;
    read(t);
    while (t--)
    {
        a[0].clear();
        a[1].clear();
        read(n);
        rep(i, 1, n + 1)
        {
            read(x);
            x %= 2;
            a[x].push_back(i);
        }
        if (!a[0].empty()){
            puts("1");
            wi(a[0][0]),P;
        }
        else if (a[1].size() > 1)
            puts("2");
                 wi(a[1][0]),wi(a[1][1] ),P;
        else
             puts("-1");
    }
    return 0;
}

B. Count Subrectangles
当时没做出来：
预处理：
首先统计 a 序列和 b 序列 的所有连续 1 区间长度， a 序列第 i 个连续 1 的区间 length 为 Ai ，b 序列第 i 个连续 1 的区间 length 为 Bi
考虑 k 的每一个约数 d。
则有， d×kd 这个矩形的个数就是 (Ai−d+1) *(Bi−kd+1) ，对 k 的每一个因子 d 计算后求和即可。
解答：
然后排序后二分输出。

#include <bits/stdc++.h>
using namespace std;
template <typename t>
void read(t &x)
{
    char ch = getchar();
    x = 0;
    t f = 1;
    while (ch < '0' || ch > '9')
        f = (ch == '-' ? -1 : f), ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    x *= f;
}

#define wi(n) printf("%d ", n)
#define wl(n) printf("%lld ", n)
#define P puts(" ")
typedef long long ll;
#define MOD 1000000007
#define mp(a, b) make_pair(a, b)
#define N 20005
#define rep(i, j, n) for (int i = j; i <= n; i++)
#define red(i, n, j) for (int i = n; i >= j; i--)
#define fil(a, n) rep(i, 0, n, ) read(a[i])

//---------------https://lunatic.blog.csdn.net/-------------------//

const int N = 4e4 + 100;
int a[N], b[N];
vector<pair<int, int>> node;
void init(int k)
{
    for (int i = 1; i * i <= k; i++)
    {
        if (k % i == 0)
        {
            node.push_back(make_pair(i, k / i));
            if (i != k / i)
                node.push_back(make_pair(k / i, i));
        }
    }
}
unordered_map<int, int> A, B;
void solve(int a[], int n, unordered_map<int, int> &mp)
{
    int pos = 1, cnt = 0;
    while (pos <= n)
    {
        while (a[pos])
        {
            pos++;
            cnt++;
        }
        if (cnt)
        {
            mp[cnt]++;
            cnt = 0;
        }
        pos++;
    }
}

int main()
{
    int n, m, k;
    read(n), read(m), read(k);
    init(k);
    rep(i, 1, n + 1)
        read(a[i]);
    rep(i, 1, m + 1)
        read(b[i]);
    solve(a, n, A);
    solve(b, m, B);
    LL ans = 0;
    rep(k, 0, node.size())
    {
        int x = node[k].first, y = node[k].second;
        LL xx = 0, yy = 0;
        for (auto it : A)
            if (it.first >= x)
                xx += it.second * (it.first - x + 1);
        for (auto it : B)
            if (it.first >= y)
                yy += it.second * (it.first - y + 1);
        ans += xx * yy;
    }
    wi(ans), P;
    return 0;
}

C. Unusual Competitions
我觉得这个题应该和 B 换一换
这个题把左括号看成-1，右括号看成 1，如果前缀和小于 0 即存在单独的右括号，需要重排。
然后找到所有前缀和为负的连续段包括最后一个 0，计算长度和就行。

#include <bits/stdc++.h>
using namespace std;
template <typename t>
void read(t &x)
{
    char ch = getchar();
    x = 0;
    t f = 1;
    while (ch < '0' || ch > '9')
        f = (ch == '-' ? -1 : f), ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    x *= f;
}

#define wi(n) printf("%d ", n)
#define wl(n) printf("%lld ", n)
#define P puts(" ")
typedef long long ll;
#define MOD 1000000007
#define mp(a, b) make_pair(a, b)
#define N 20000005
#define rep(i, j, n) for (int i = j; i <= n; i++)
#define red(i, n, j) for (int i = n; i >= j; i--)
#define fil(a, n) rep(i, 0, n, ) read(a[i])

//---------------https://lunatic.blog.csdn.net/-------------------//

string s;
int a[N], n, ans = 0;
int main()
{
    read(n);
    cin >> s;
    rep(i, 0, n)
    {
        a[i] = a[i - 1] + (s[i] == '(' ? -1 : 1);
    }
    if (a[n - 1] != 0)
        puts("-1");
    else
    {
        rep(i, 0, n) ans += (a[i] < 0) + (a[i] < 0 && a[i - 1] >= 0);
        wi(ans),P;
    }
    return 0;
}