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;
}