A.Even Subset Sum Problem
题意：
给定一个数字序列，寻找一个子序列使得序列中和为偶数，输出子序列的元素个数和对应下标，找不到则输出-1
题解：
贪心找一个偶数或者找两个奇数即可
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int a[maxn];
void solve()
{
int n;
scanf("%d", &n);
int id = -1;
int f = 0;
for (int i = 1, x; i <= n; i++)
{
scanf("%d", &x);
if (f)
continue;
if (x % 2 == 0)
{
printf("1\n%d\n", i);
f = 1;
}
else
{
if (id == -1)
id = i;
else
{
printf("2\n%d %d\n", id, i);
f = 1;
}
}
}
if (!f)
puts("-1");
}
int main()
{
int t;
for (scanf("%d", &t); t >= 1; t--)
solve();
}B.Count Subrectangles
题意：
给两个数组a,b。矩阵c满足 。问c中有多少个子区域全为1且1的个数恰好为k。
题解：
子区域的长宽一定为k的因子，因此暴力枚举一遍分别在a,b数组里面扫描一下所有的组合即可。同样也可以用dp预处理出所有连续的长度。
暴力枚举：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 4e4 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[maxn], b[maxn], n, m, k;
ll solve(int x)
{
ll res = 0;
int cnt1 = 0, cnt2 = 0, cnt = 0, y = k / x;
for (int i = 1; i <= n; i++)
{
if (a[i] == 1)
cnt1++;
else
cnt1 = 0;
if (cnt1 >= x)
cnt++;
}
for (int i = 1; i <= m; i++)
{
if (b[i] == 1)
cnt2++;
else
cnt2 = 0;
if (cnt2 >= y)
res += cnt;
}
return res;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= m; i++)
scanf("%d", &b[i]);
ll ans = 0;
for (int i = 1; i * i <= k; i++)
{
if (k % i == 0)
{
ans += solve(i);
if (i != k / i)
ans += solve(k / i);
}
}
printf("%lld\n", ans);
return 0;
}dp预处理：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 4e4 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int dpn[maxn], dpm[maxn];
int main()
{
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for (int i = 1, x; i <= n; i++)
{
scanf("%d", &x);
dpn[i] = (x == 1) ? dpn[i - 1] + 1 : 0;
}
for (int i = 1, x; i <= m; i++)
{
scanf("%d", &x);
dpm[i] = (x == 1) ? dpm[i - 1] + 1 : 0;
}
sort(dpn + 1, dpn + n + 1);
sort(dpm + 1, dpm + m + 1);
ll sum = 0;
for (int i = 1; i <= n; i++)
{
if (k % i == 0 && k / i <= m)
{
int pos1 = lower_bound(dpn + 1, dpn + n + 1, i) - dpn;
int pos2 = lower_bound(dpm + 1, dpm + m + 1, k / i) - dpm;
sum += (n - pos1 + 1) * (m - pos2 + 1);
}
}
printf("%lld\n", sum);
return 0;
}C.Unusual Competitions
题意：
给定一个左右圆括号序列。每次可以花费x以选择长度为x的字串进行任意排序。问最少花费多少使得括号匹配。
题解：
经典的括号匹配思路，首先可以把左括号看成1，右括号看成-1，遍历序列，如果一段序列的和为0则这段序列的括号匹配。从左往右遍历，吗，每次更新每个状态为0的位置l，如果前一个点的状态为-1说明这一段序列肯定至少有一个右括号在左括号前面需要重新排序，ans+=i-l
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[maxn];
int main()
{
int n;
scanf("%d", &n);
string s;
cin >> s;
int cnt1 = 0, cnt2 = 0;
for (auto i : s)
{
if (i == '(')
cnt1++;
else
cnt2++;
}
if (cnt1 != cnt2)
{
puts("-1");
return 0;
}
int ans = 0, cnt = 0, l = 0;
for (int i = 1; i <= s.length(); i++)
{
if (s[i - 1] == '(')
a[i] = a[i - 1] + 1;
else
a[i] = a[i - 1] - 1;
if (a[i] == 0)
{
if (a[i - 1] == -1)
ans += i - l;
l = i;
}
}
printf("%d\n", ans);
return 0;
}D.Present
题意：
给定数组a，求
题解：
考虑最后答案的每一位。排除低位对高位的影响后，对于所有数字a，对第k位的贡献等同于a% 对第k位的贡献。对于pos=a%
而言，只有位于区间
内的数才能改变第k位的状态。所以，我们可以对于每一位开一个树状数组维护区间状态。枚举最多25位即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 4e5 + 5;
const int MAXN = (1 << 25) + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[maxn], n, v;
bool c[MAXN];
inline int lowbit(int x) { return x & (-x); }
void add(int x)
{
for (; x < v; x += lowbit(x))
c[x] ^= 1;
}
bool query(int x)
{
bool res = 0;
for (; x; x -= lowbit(x))
res ^= c[x];
return res;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int ans = 0;
for (int p = 0; p < 25; p++)
{
memset(c, 0, sizeof(c));
v = 1 << p;
int res = 0;
for (int i = 1; i <= n; i++)
if (a[i] >> p & 1)
res++;
res = (res & 1) & ((n - res) & 1);
for (int i = 1; i <= n; i++)
{
int pos = a[i] % v;
if (pos)
{
res ^= query(v - 1) ^ query(v - pos - 1);
add(pos);
}
}
if (res)
ans = ans | v;
}
printf("%d\n", ans);
return 0;
}E.
题意：
给定共2n个点，m条边的二分图。右部的每个点都有一个权值，现规定S为左部点的任意子集，N(S)为与S中的点直接相连的右部点集。f(S)为S中所有点权值之和。要求所有f(N(S))的gcd。
题解：
首先可以思考一下对于(1,1),(1,2),(2,1),(2,2)的话，不论选择左边节点1、节点2还是节点1和节点2，右边节点1和2会被同时选择，相当于是他们是捆绑在一起的，那么就可以将这些点缩点缩成一个点。对于缩点我们从右节点映射到左节点只需要扫描一遍即可。对于相同的映射结果我们可以将这些点合并为一个权值等于这些点权值之和的新节点，并将其映射到左节点的子集。
再考虑到任意子集的问题。先给出一个结论gcd(a+b,a,b)=gcd(gcd(a+b,a),b)=gcd(a,b)。
证明：gcd(a+b,a)=gcd(a,b)
设gcd(a,b)=c
a=mc,b=nc,其中n和m互质
a+b=(n+m)c。
因为n和m互质
所以gcd(n+m,n)=1
所以gcd(a+b,a)=gcd((n+m)c,c)=c=gcd(a,b)
同理可以推广到gcd(a,b,c,(a+b),(a+c),(b+c),(a+b+c))=gcd(a,b,c)
所以最终答案就是gcd(缩点后的各个节点权值)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
ll c[maxn];
vector<int> G[maxn];
map<vector<int>, ll> mp;
void solve()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%lld", &c[i]);
G[i].clear();
}
for (int i = 1; i <= m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
G[v].push_back(u);
}
mp.clear();
for (int i = 1; i <= n; i++)
{
if (G[i].size() == 0)
continue;
sort(G[i].begin(), G[i].end());
mp[G[i]] += c[i];
}
ll ans = 0;
for (auto i : mp)
ans = __gcd(ans, i.second);
printf("%lld\n", ans);
}
int main()
{
int t;
for (scanf("%d", &t); t >= 1; t--)
solve();
}
京公网安备 11010502036488号