. Make A Equal to B
给出两个由0和1组成的数组a，b，有两种操作，一个是将a中任意元素换成1-a[i]，一是将a数组重新排序，问使得a等于b的最少操作。
思路：首先0和1的数量差是必须解决的，然后就是判断重新排序或者在改变01数量差的时候就完成所有操作哪种操作数更少。
AC Code：
#include <bits/stdc++.h>
typedef long long ll;
const int N=1e5+5;
int t,n;
int a[N],b[N];
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin>>t;
while(t--){
std::cin>>n;
int cnta=0,cntb=0;
for(int i=1;i<=n;i++){
std::cin>>a[i];
cnta+=(a[i]==1);
}
for(int i=1;i<=n;i++){
std::cin>>b[i];
cntb+=(b[i]==1);
}
bool flag=true;
int cnt=0;
for(int i=1;i<=n;i++){
if(a[i]!=b[i]){
flag=false;
cnt++;
}
}
if(flag){
std::cout<<0<<'\n';
continue;
}
std::cout<<std::min(abs(cnta-cntb)+1,cnt)<<'\n';
}
return 0;
}B. Playing with GCD
给出一个数组a，判断能否构造一个数列b，使得相邻两个元素的gcd为对应a数组中的元素。
思路：对于相邻的a中元素a[i-1]和a[i]，a[i-1]为b[i-1]和b[i]的gcd，a[i]为b[i]和b[i+1]的gcd，可以得知，b[i]同时为a[i-1]和a[i]的倍数，而满足此情况的最小b[i]即a[i-1]和a[i]的LCM。于是对于b数组中间部分，我们可以构造a数组相邻元素的lcm作为b数组的元素，而开头和结尾的两个元素则可以分别取a[1]和a[n]，这样构造完之后再返回去判断一下即可。
AC Code：
#include <bits/stdc++.h>
typedef long long ll;
const int N=1e5+5;
int t,n;
ll a[N];
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin>>t;
while(t--){
std::cin>>n;
for(int i=1;i<=n;i++){
std::cin>>a[i];
}
std::vector<ll>vec;
vec.push_back(a[1]);
for(int i=1;i<n;i++){
vec.push_back(a[i]*a[i+1]/std::__gcd(a[i],a[i+1]));
}
vec.push_back(a[n]);
bool flag=true;
int len=vec.size();
for(int i=0;i<len-1;i++){
ll gcd=std::__gcd(vec[i],vec[i+1]);
if(gcd!=a[i+1]){
flag=false;
break;
}
}
std::cout<<(flag?"YES":"NO")<<'\n';
}
return 0;
}os：感觉思路很清奇
C1. Good Subarrays (Easy Version)
给出数组a，计算满足条件的子序列个数。
思路：一眼双指针，不解释。
AC Code：
#include <bits/stdc++.h>
typedef long long ll;
#define int long long
const int N = 2e5 + 5;
int t, n;
int a[N];
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> t;
while (t --) {
std::cin >> n;
for(int i = 1; i <= n; i ++) {
std::cin >> a[i];
}
int j = 1;
int ans = 0;
for(int i = 1; i <= n; i ++) {
while (a[j] >= j - i + 1 && j <= n) {
j ++;
}
ans += (j - i);
}
std::cout << ans << '\n';
}
return 0;
}D. Equal Binary Subsequences
给出一个01字符串，可以任意选择一个子序列，旋转交换位置，即1~n-1向后移动一位，n到第一位，这样操作一次之后能否满足条件：选择一个长度为n的子序列，使得选出的子序列和剩下的两个串相等。
思路：首先我们可以知道，0和1的个数若存在为奇数的，则一定无法满足要求，直接输出-1即可；不妨两位两位分析，若是00,11这样的，直接选择0或1即可，但是对于01,10这样的，就需要我们的旋转操作了，如果对于一个相邻两位不同的，我们如果在第一组01中选择了1，则后面会多一个0，那么我们需要在后面再插入一个0，以此类推，我们要构造的是001100这样的01偶数串，这样随意选择即可。
AC Code：
#include <bits/stdc++.h>
typedef long long ll;
const int N = 2e5 + 5;
int t, n;
std::string s;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> t;
while (t --) {
std::cin >> n >> s;
s = ' ' + s;
int cnt0 = 0, cnt1 = 0;
for(int i = 1; i <= 2*n; i ++) {
if(s[i] == '0') cnt0 ++;
else cnt1 ++;
}
if(cnt1 % 2 || cnt0 % 2) {
std::cout << -1 << '\n';
continue;
}
int cur = 0;
std::vector<int> vec;
for(int i = 1; i <= 2*n; i += 2) {
if(s[i] != s[i + 1]) {
if(s[i] - '0' == cur) {
vec.push_back(i);
}
else vec.push_back(i + 1);
cur ^= 1;
}
}
std::cout << vec.size() << ' ';
for(auto u : vec) {
std::cout << u << ' ';
}
std::cout << '\n';
for(int i = 1; i <= 2*n; i += 2) {
std::cout << i << ' ';
}
std::cout << '\n';
}
return 0;
}abc1都还好，但是我做的像shit一样，，WA麻了
竟然没掉分？！怪事