A. Even Subset Sum Problem 签到题
代码语言：javascript复制#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计算后求和即可。 解答： 然后排序后二分输出。
代码语言：javascript复制#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，计算长度和就行。
代码语言：javascript复制#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;
}
