|
|
赛时搞出了D,C2赛时有一处输出忘记换行了,惨...
A Make A Equal to B
代码实现
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
using LL = long long;
const int maxn = 105;
int a[maxn], b[maxn];
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a;
for(int i = 1; i <= n; i++) cin >> b;
int cnta = count(a + 1, a + n + 1, 1);
int cntb = count(b + 1, b + n + 1, 1);
int c = 0;
for(int i = 1; i <= n; i++) c += (a != b);
cout << min(c, abs(cnta - cntb) + 1) << &#39;\n&#39;;
}
}
B Playing with GCD
代码实现
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
using LL = long long;
const int maxn = 1e5 + 5;
int a[maxn];
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a;
bool success = 1;
for(int i = 2; i <= n - 1; i++){
if (a % __gcd(a[i - 1], a[i + 1])){
success = 0;
break;
}
}
cout << (success ? &#34;YES&#34; : &#34;NO&#34;) << &#39;\n&#39;;
}
}
C1 Good Subarrays (Easy Version)
分析
思路是固定左端点,求能到达的右端点.
把位置按照a_i - i排序,然后双指针搞一下即可.从左到右遍历,利用双指针把满足当前位置要求的元素填进去,每次右端点就是往右第一个还没填的位置,这个位置也是单调的可以用双指针暴力计算.
代码实现
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
using LL = long long;
const int maxn = 2e5 + 5;
int a[maxn], id[maxn];
bool v[maxn];
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a, id = i, v = 0;
v[n + 1] = 0;
sort(id + 1, id + n + 1, [&](int x, int y){
return a[x] - x > a[y] - y;
});
LL ans = 0;
for(int i = 1, j = 0, r = 1; i <= n; i++){
while(j + 1 <= n && a[id[j + 1]] - id[j + 1] + i - 1 >= 0){
j++;
v[id[j]] = 1;
}
while(v[r]) r++;
ans += r - i;
}
cout << ans << &#39;\n&#39;;
}
}
C2 Good Subarrays (Hard Version)
分析
这道题赛时没过,然后赛后一看错误样例居然是因为输出答案没有换行......吐血
首先我们把答案算出来,对于每次修改我们计算增量.
首先我们预处理出对于每个左端点,右端点最远可以到哪里,因为这个位置可能可以被修改,所以我们还需要在处理以下如果这个位置能满足要求的话右端点最远能到什么位置,但是这样就无法使用双指针(因为势能均摊失效)去做了,我们可以用线段树二分去做,线段树二分找序列中第一个0出现的位置是经典操作,有模板的话套个模板就行了.
对于每次修改
- 当x > a[p],显然这种情况最后答案会增加,我们可以通过右端点二分出受影响的左右边界,然后通过预处理出的数组前缀和(即假设不满足要求的第一个位置满足要求后右端点最远能到达什么位置)就可以快速计算增量.
- 当x < a[p],这种情况答案会减少,我们同样可以二分出影响的区间左右边界,然后利用右端点数组的前缀和可以快速求解(受影响的区间r之和减去区间长度乘位置p,可以理解为所有右端点本来大于p的位置右端点都变成了p).
代码实现
#include<iostream>
#include<cstring>
#include<vector>
#include<numeric>
#include<functional>
#include<algorithm>
using namespace std;
using LL = long long;
const int maxn = 2e5 + 5;
int a[maxn], id[maxn];
int R[maxn];
LL s[maxn], sr[maxn];
struct Info {
int v;
Info() : v(1) {}
Info(int v) : v(v) {}
};
Info operator+(const Info &a, const Info &b){
return min({a.v, b.v});
}
template<class Info, class Merge = plus<Info>>
struct SegmentTree{
const int n;
const Merge merge;
vector<Info> info;
SegmentTree(int n) : n(n), merge(Merge()), info((n << 2) + 1){}
SegmentTree(vector<Info> init) : SegmentTree((int)init.size()){
function<void(int, int, int)> build = [&](int p, int l, int r){
if (l == r){
info[p] = init[l - 1];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m + 1, r);
pull(p);
};
build(1, 1, n);
}
void pull(int p){
info[p] = merge(info[2 * p], info[2 * p + 1]);
}
void modify(int p, int l, int r, int x, const Info &v){
if (l == r){
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 + 1, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v){
modify(1, 1, n, p, v);
}
Info query(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 merge(query(2 * p, l, m, x, y), query(2 * p + 1, m + 1, r, x, y));
}
Info query(int l, int r){
return query(1, 1, n, l, r);
}
int find_first(int p, int l, int r, int L, int R, const function<bool(const Info&)> &f, Info &pre){
if (l >= L && r <= R){
if (!f(merge(pre, info[p]))){
pre = merge(pre, info[p]);
return r + 1;
}
if (l == r) return r;
int m = (l + r) / 2;
int res;
if (f(merge(pre, info[2 * p]))){
res = find_first(2 * p, l, m, L, R, f, pre);
}
else{
pre = merge(pre, info[2 * p]);
res = find_first(2 * p + 1, m + 1, r, L, R, f, pre);
}
return res;
}
int m = (l + r) / 2;
int res = m + 1;
if (L <= m){
res = find_first(2 * p, l, m, L, R, f, pre);
}
if (R > m && res == m + 1){
res = find_first(2 * p + 1, m + 1, r, L, R, f, pre);
}
return res;
}
int find_first(int l, int r, const function<bool(const Info&)> &f){
Info pre = Info();
return find_first(1, 1, n, l, r, f, pre);
}
};
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n, m;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a, id = i;
sort(id + 1, id + n + 1, [&](int x, int y){
return a[x] - x > a[y] - y;
});
const function<bool(const Info&)> f = [&](const Info &info){
return info.v == 0;
};
SegmentTree<Info> seg(vector<Info>(n, Info(0)));
LL ans = 0;
for(int i = 1, j = 0; i <= n; i++){
while(j + 1 <= n && a[id[j + 1]] - id[j + 1] + i - 1 >= 0){
j++;
seg.modify(id[j], {1});
}
int r = seg.find_first(i, n, f);
R = r;
ans += r - i;
if (r <= n){
seg.modify(r, {1});
s = seg.find_first(i, n, f) - r;
seg.modify(r, {0});
}
}
for(int i = 1; i <= n; i++) s += s[i - 1];
for(int i = 1; i <= n; i++) sr = sr[i - 1] + R;
cin >> m;
while(m--){
int p, x;
cin >> p >> x;
if (x == a[p]){
cout << ans << &#39;\n&#39;;
}
else if (x > a[p]){
int Ri = upper_bound(R + 1, R + p, p) - R - 1;
int Le = lower_bound(R + 1, R + p, p) - R;
Le = max(Le, max(1, p - x + 1));
if (Le > Ri) cout << ans << &#39;\n&#39;;
else cout << ans + s[Ri] - s[Le - 1] << &#39;\n&#39;;
}
else{
int Le = upper_bound(R + 1, R + p, p) - R;
int Ri = max(0, p - x);
if (Le > Ri) cout << ans << &#39;\n&#39;;
else cout << ans - (sr[Ri] - sr[Le - 1] - 1LL * (Ri - Le + 1) * p) << &#39;\n&#39;;
}
}
}
D Equal Binary Subsequences
分析
首先如果0或者1出现了奇数次肯定是无解的.
其他情况都是有解的,我们可以考虑把原串变成a_{2k - 1} = a_{2k}的形式,例如0011001111,这样只要交替取就能轻松构造出答案.
首先先找到所有a_{2k - 1} \ne a_{2k}的位置记录下来我们只操作这些位置,很显然这些位置要么是01要么10,并且总数肯定是偶数个,我们要做的是把这些位置变为11或者00,假设这些位置为p_1, p_2, p_3, p_4 \cdots(p_i = 01/10)所以其实我们只需要把奇数位置的的1换到偶数位置去,偶数位置的0换到奇数位置去即可.比如01, 10,我们就把10的1换到前面去,变成11, 00,更长的序列也一样,实现方法见代码.
这个题目的解法其实非常简单,主要难度在于思维,在场上我第一感觉也是先想办法check一个序列能否满足题目的要求,但是发现不带修都很难做,不太符合Div.2D的难度,然后才转变思路去做构造,只要能想到构造出的最终串是什么样子这个问题就迎刃而解了.
做这类题目的话我们可以发现其实题目最终的解法没有任何价值,思考这个题目的过程才有价值.
代码实现
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
using LL = long long;
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--){
int n; string s;
cin >> n >> s;
int cnt = count(s.begin(), s.end(), &#39;1&#39;);
if (cnt % 2){
cout << -1 << &#39;\n&#39;;
continue;
}
s = &#34; &#34; + s;
vector<int> v, ans;
for(int i = 1; i <= 2 * n; i += 2)
if (s != s[i + 1]) v.push_back(i);
for(int i = 0; i < v.size(); i++){
int pos = v;
if ((i & 1) == s[pos] - &#39;0&#39;) ans.push_back(pos);
else ans.push_back(pos + 1);
}
cout << ans.size();
for(auto x : ans) cout << &#39; &#39; << x;
cout << &#39;\n&#39;;
for(int i = 1; i <= 2 * n; i += 2)
cout << i << &#39; &#39;;
cout << &#39;\n&#39;;
}
}
本文使用 Zhihu On VSCode 创作并发布
|
|
发表于 2022-11-27 14:33:20