集合之和
Attachments - 2022 CCPC Henan Provincial Collegiate Programming Contest - Codeforces
题意
构造一个集合，使得集合中每两个数相加，得到的数再组成的一个集合，使得新集合的大小为\(n\)。
思路
当\(n\)为奇数时，构造集合{1,2,……(n + 1) / 2}，得到的新集合中的数为2~n+1。如果\(n\)为偶数，把第一个数改为0即可。注意当\(n\le4\)且\(n\)为偶时是无法构造的。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
if(n & 1) {
cout << (n + 1) / 2 << "\n";
for(int i = 1; i <= (n + 1) / 2; i++) {
cout << i << " ";
}
} else {
if(n <= 4) {
cout << -1 << "\n";
} else {
cout << n / 2 << "\n" << 0 << " ";
for(int i = 2; i <= n / 2; i++) {
cout << i << " ";
}
}
}
return 0;
}
龙语魔法
Attachments - The 7-th BIT Campus Programming Contest for Junior Grade Group - Codeforces
题意
给定一个序列，找到所有子区间中区间和第\(k\)大的区间，输出其区间和。
思路
二分答案+双指针
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 n, k;
cin >> n >> k;
vector<int> a(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
}
i64 lo = 1, hi = 1e18;
while(lo < hi) {
i64 mid = lo + hi >> 1;
i64 i = 0, j = 0, sum = 0, cnt = 0;
while(j < n) {
sum += a[j++];
while(j < n && sum <= mid) {
sum += a[j++];
}
cnt += n - j + 1;
while(sum - a[i] > mid) {
sum -= a[i++];
cnt += n - j + 1;
}
sum -= a[i++];
}
if(n * (n + 1) / 2 >= k + cnt) {
hi = mid;
} else {
lo = mid + 1;
}
}
cout << hi << "\n";
return 0;
}
Xenia and Bit Operations
题意
有\(2^n\)个数和\(m\)个操作，每次修改一个数，然后你要输出 ( (a1|a2)xor(a3|a4) )|( (a5|a6)xor(a7|a8) )....
即 or 与 xor 交替计算。
思路
建一棵二叉树，每次修改只要\(\log\)的时间，根据二叉树的层数的奇偶确定是xor操作还是or操作。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(2 << n);
for(int i = 0; i < (1 << n); i++) {
cin >> a[1 << n | i];
}
for(int i = (1 << n) - 1; i > 0; i--) {
if((n - __lg(i)) % 2) {
a[i] = a[i * 2] | a[i * 2 + 1];
} else {
a[i] = a[i * 2] ^ a[i * 2 + 1];
}
}
for(int i = 0; i < m; i++) {
int p, b;
cin >> p >> b;
p += 1 << n;
a[--p] = b;
while(p /= 2) {
if((n - __lg(p)) % 2) {
a[p] = a[p * 2] | a[p * 2 + 1];
} else {
a[p] = a[p * 2] ^ a[p * 2 + 1];
}
}
cout << a[1] << "\n";
}
return 0;
}
Good Subarrays
题意
定义区间和等于区间长度的区间为好区间，求给出序列的好区间的数量。
思路
设\(f_i\)为\(i\)的前缀和，则好区间满足\(f_r-f_l=r-l\)，变化一下可得\(f_r-r=f_l-l\)。用map记录每个右端点前面满足条件的左端点数。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n;
string s;
cin >> n >> s;
vector<int> pre(n + 1);
for(int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + (s[i - 1] - '0');
}
map<int, int> cnt;
cnt[0] = 1;
i64 ans = 0;
for(int i = 1; i <= n; i++) {
ans += cnt[pre[i] - i]++;
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--) {
solve();
}
return 0;
}
Number of Ways
题意
给定一个序列，求有多少种方式把该序列分为三个部分，使得三个部分的和相等。
思路
遍历前缀和，如果有前缀和等于序列总和的1/3，则该点可作为一个分割第一二部分的点。如果有点的前缀和等于总和的2/3，那么该点可作为分割第二三部分的点。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<i64> pre(n + 1);
i64 sum = 0;
for(int i = 1, x; i <= n; i++) {
cin >> x;
sum += x;
pre[i] = pre[i - 1] + x;
}
i64 ans = 0, cnt = 0;
for(int i = 1; i <= n; i++) {
if(i >= 2 && i <= n - 1 && pre[i] * 3 == sum * 2) {
ans += cnt;
}
if(i <= n - 2 && pre[i] * 3 == sum) {
cnt += 1;
}
}
cout << ans << "\n";
return 0;
}