Codeforces Round #825 (Div. 2) A-C1 D
A. Make A Equal to B
题目大意: 给定两个$01$序列$a$,$b$长度为$n(1\leq n\leq 1e2)$，现在有两种操作，第一种操作是选择一个位置进行反转，第二个操作是任意排序$a$序列，问最少需要几次操作能让序列$a$等于序列$b$
解题思路: 首先我们先思考一下，我们刚开始一定要让序列$a$和$b$中的$01$个数相同，然后在这个前提下，如果两个序列在增加$1$的过程中相同了，就不进行二操作，否则就进行二操作。如何判断两个序列是否在过程中就相同了呢？我们可以考虑将序列中的$0$变成$1$，然后看哪个序列中原本的$1$多，如果$b$中多就变$a$，$a$中多实际上就是变$b$
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--)
{
int na,nb;
na = nb = 0;
cin >> n;
for(int i = 1;i <= n;++i)
{
cin >> a[i];
if(a[i]) na++;
}
for(int i = 1;i <= n;++i)
{
cin >> b[i];
if(b[i]) nb++;
}
int f = 1;
int ck = 0;
if(na > nb) ck = 1;
if(na < nb)
{
for(int i = 1;i <= n;++i)
{
if(!a[i]) continue;
if(a[i] != b[i]) f = 0;
}
}
else
{
for(int i = 1;i <= n;++i)
{
if(!b[i]) continue;
if(a[i] != b[i]) f = 0;
}
}
cout << abs(na - nb) + (1 - f) << "\n";
}
}B. Playing with GCD
题目大意: 给定一个长度为$n(1\leq n \leq 2e5)$的序列，问是否存在一个长度为$n + 1$的序列$b$，满足$a_i = gcd(b_i,b_{i + 1})$
解题思路: 观察样例可得我们可以对原序列中的$a_{i - 1}$,$a_i$和$a_{i + 1}$进行分析，这三个数字分别由$b_{i - 1}$,$b_i$,$b_{i + 1}$,$b_{i + 2}$
考虑$b_i$和$b_{i + 1}$实际上还在$a_{i - 1}$和$a_{i + 1}$中，我们考虑$gcd$的性质实际上是去求若干个数字的质因子取$min$
那么我们可以对$a_{i- 1}$和$a_{i + 1}$取$gcd$，如果$a_i$不能和他们的$gcd$取余获得$0$的话，那么实际上就是不可以的，说明还有其他的质因子存在
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--)
{
cin >> n;
for(int i = 1;i <= n;++i) cin >> a[i];
int f = 1;
for(int i = 2;i <= n - 1;++i)
{
int gd = __gcd(a[i - 1],a[i + 1]);
if(a[i] % gd) f = 0;
}
if(f) cout << "YES\n";
else cout << "NO\n";
}
}C1. Good Subarrays (Easy Version)
题目大意: 给定一个长度为$n(1\leq n \leq 2e5)$的序列，找出这个序列中有多少个序列满足好序列，好序列的要求是对于一段序列第$i$个元素大于等于$i$
解题思路: 固定左端点取计算右端点在哪里。我们可以发现这样一件事情，如果我在当前这个位置$i$右端点到达$j$,那么我到$i + 1$的话，我可以继续从$j$往右边移动，满足双指针的性质，直接写就可以。
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--)
{
cin >> n;
for(int i = 1;i <= n;++i) cin >> a[i];
int ans = 0;
int j = 1;
int now = 1;
for(int i = 1;i <= n;++i)
{
if(j < i)
{
j = i;
now = 1;
}
while(a[j] >= now && j <= n)
{
// cout << "i -> "<< i << " " << j << " " << now<< "\n";
j++;
now++;
}
j--,now--;
int num = j - i + 1;
ans += num;
now--;
// cout << i << " " << j << "\n";
}
cout << ans << "\n";
}
}
D. Equal Binary Subsequences
题目大意: 给定一个长度为$2n(1\leq n \leq 1e5)$的$01$串，可以进行以下的操作一次，选择一个子序列，并且把这个子序列中的数字往前移动一个，如果是第一个就移动到最后一个，问是否能够将这个$01$串分割成两个子序列，使得这两个子序列相同
解题思路: 首先我们先考虑无法构成的情况，如果$0$的个数或者$1$的个数是奇数，那么这个序列肯定就无法构成
做一个大胆的猜想，假设目前剩下的情况下所有情况都是有解的，那么剩下的串可能是由若干个$00$ $01$ $10$ $11$组成的
我们从前往后对于一个子序列来说$00$和$11$肯定是可以直接放进去的，那么对于$01$和$10$呢？
我们可以考虑把他们放到操作里面去变换，那么实际上我们只需要把奇数位置上面的$1$放到偶数位置上去，把偶数位置上面的$1$放到奇数位置上去
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--)
{
cin >> n;
cin >> str;
str = " " + str;
int num = 0;
n <<= 1;
for(int i = 1;i <= n;++i)
{
num += (str[i] == '1');
}
if(num & 1)
{
cout << -1 << "\n";
continue;
}
vector<int> pos;
for(int i = 1;i <= n;i += 2)
{
if(str[i] == str[i + 1]) continue;
pos.push_back(i);
}
vector<int> ans;
for(int i = 0;i < pos.size();++i)
{
int now = pos[i];
if((i & 1) == str[now] - '0')
{
ans.push_back(now);
}
else ans.push_back(now + 1);
}
cout << ans.size() << "\n";
for(auto to:ans)
{
cout << to << " ";
}
cout << "\n";
for(int i = 1;i <= n;i += 2) cout << i << " \n"[i == n - 1];
}
}
