Codeforces Round 951 (Div. 2) C、D（构造、线段树）

1979C - Earning on Bets 

构造题：观察到k范围很小，首先考虑最终硬币总数可以是多少，我们可以先假设最终的硬币总数为所有k取值的最小公倍数，这样只需要满足每个结果添加1枚硬币即可赚到硬币。

// Problem: C. Earning on Bets
// Contest: Codeforces - Codeforces Round 951 (Div. 2)
// URL: https://codeforces.com/contest/1979/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
#define int long long
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{int n;cin >> n;LL ans = 1;for(int i = 2 ; i <= 20 ; i ++){ans = lcm(ans , i);}int tot = 0;for(int i = 0 ; i < n ; i ++){cin >> a[i];tot += ans / a[i];}int res = ans - tot;if(res < n){cout << -1 << endl;}else{for(int i = 0 ; i < n - 1; i ++){cout << ans / a[i] + 1 << " ";res--;}cout << ans / a[n - 1] + res << endl;}
}            
signed main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

1979D - Fixing a Binary String  

        题意：

翻译有误，请看英文题面

        思路：典型的一个区间合并求数量问题，我们可以直接构造两颗线段树解决。

// Problem: D. Fixing a Binary String
// Contest: Codeforces - Codeforces Round 951 (Div. 2)
// URL: https://codeforces.com/contest/1979/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}template<class Info>
struct SegmentTree {int n;std::vector<Info> info;SegmentTree() : n(0) {}SegmentTree(int n_, Info v_ = Info()) {init(n_, v_);}template<class T>SegmentTree(std::vector<T> init_) {init(init_);}template<class T>void init(std::vector<T> init_) {n = init_.size();info.assign(4 << std::__lg(n), Info());std::function<void(int, int, int)> build = [&](int p, int l, int r) {if (r - l == 1) {info[p] = init_[l];return;}int m = (l + r) / 2;build(2 * p, l, m);build(2 * p + 1, m, r);pull(p);};build(1, 0, n);}void pull(int p) {info[p] = info[2 * p] + info[2 * p + 1];}void modify(int p, int l, int r, int x, const Info &v) {if (r - l == 1) {info[p] = info[p] + v;return;}int m = (l + r) / 2;if (x < m) {modify(2 * p, l, m, x, v);} else {modify(2 * p + 1, m, r, x, v);}pull(p);}void modify(int p, const Info &v) {modify(1, 0, n, p, v);}Info rangeQuery(int p, int l, int r, int x, int y) {if (l >= y || r <= x) {return Info();}if (l >= x && r <= y) {return info[p];}int m = (l + r) / 2;return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);}Info rangeQuery(int l, int r) {return rangeQuery(1, 0, n, l, r);}template<class F>int findFirst(int p, int l, int r, int x, int y, F pred) {if (l >= y || r <= x || !pred(info[p])) {return -1;}if (r - l == 1) {return l;}int m = (l + r) / 2;int res = findFirst(2 * p, l, m, x, y, pred);if (res == -1) {res = findFirst(2 * p + 1, m, r, x, y, pred);}return res;}template<class F>int findFirst(int l, int r, F pred) {return findFirst(1, 0, n, l, r, pred);}template<class F>int findLast(int p, int l, int r, int x, int y, F pred) {if (l >= y || r <= x || !pred(info[p])) {return -1;}if (r - l == 1) {return l;}int m = (l + r) / 2;int res = findLast(2 * p + 1, m, r, x, y, pred);if (res == -1) {res = findLast(2 * p, l, m, x, y, pred);}return res;}template<class F>int findLast(int l, int r, F pred) {return findLast(1, 0, n, l, r, pred);}
};struct Info {int left0 = 0, left1 = 0;int right0 = 0, right1 = 0;int cnt = 0;int act = 0;
};Info operator + (Info a, Info b) {if(a.act == 0){return b;}if(b.act == 0){return a;}Info c;c.left0 = a.left0;c.left1 = a.left1;c.right0 = b.right0;c.right1 = b.right1;c.act = a.act + b.act;c.cnt = a.cnt + b.cnt;if(a.right0 > 0 && b.left0 > 0){int tmp = a.right0 + b.left0;if(tmp > m){c.cnt = -1;}if(tmp == m){c.cnt++;}if(a.right0 == a.act){c.left0 = a.act + b.left0;}if(b.left0 == b.act){c.right0 = a.right0 + b.act;}if(a.right0 != a.act && b.left0 != b.act && tmp != m){c.cnt = -1;}}else if(a.right1 > 0 && b.left1 > 0){int tmp = a.right1 + b.left1;if(tmp > m){c.cnt = -1;}if(tmp == m){c.cnt++;}if(a.right1 == a.act){c.left1 = a.act + b.left1;}if(b.left1 == b.act){c.right1 = b.act + a.right1; }if(a.right1 != a.act && b.left1 != b.act && tmp != m){c.cnt = -1;}}else if(a.right0 > 0 && b.left1 > 0){int tmp1 = a.right0;int tmp2 = b.left1;if(b.left1 == b.act){c.right1 = b.act;}else if(b.left1 != m){c.cnt = -1;}if(a.right0 == a.act){c.left0 = a.act;}else if(a.right0 != m){c.cnt = -1;}}else if(a.right1 > 0 && b.left0 > 0){int tmp1 = a.right1;int tmp2 = b.left0;if(b.left0 == b.act){c.right0 = b.act;}else if(b.left0 != m){c.cnt = -1;}if(a.right1 == a.act){c.left1 = a.act;}else if(a.right1 != m){c.cnt = -1;}	}return c;
}void solve() 
{cin >> n >> m;string s;cin >> s;vector<Info>v;for(int i = 0 ; i < n ; i ++){Info tmp;if(s[i] == '1'){tmp.cnt = 0;tmp.act = 1;tmp.left1 = 1;tmp.right1 = 1;tmp.left0 = 0;tmp.right0 = 0;if(m == 1){tmp.cnt = 1;}}else{tmp.cnt = 0;tmp.act = 1;tmp.left1 = 0;tmp.right1 = 0;tmp.left0 = 1;tmp.right0 = 1;	if(m == 1){tmp.cnt = 1;}		}v.pb(tmp);}vector<Info>vv;for(int i = n - 1 ; i >= 0 ; i --){Info tmp;if(s[i] == '1'){tmp.cnt = 0;tmp.act = 1;tmp.left1 = 1;tmp.right1 = 1;tmp.left0 = 0;tmp.right0 = 0;if(m == 1){tmp.cnt = 1;}				}else{tmp.cnt = 0;tmp.act = 1;tmp.left1 = 0;tmp.right1 = 0;tmp.left0 = 1;tmp.right0 = 1;	if(m == 1){tmp.cnt = 1;}				}vv.pb(tmp);		}SegmentTree	<Info> seg(v);SegmentTree<Info>seg2(vv);for(int i = 1 ; i <= n ; i ++){Info tmp1 = seg.rangeQuery(i , n);Info tmp2 = seg2.rangeQuery(n - i , n);Info tmp3 = tmp1 + tmp2;if(tmp3.cnt == n / m){cout << i << endl;return;}}cout << -1 << endl;
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}