B. Make Them Equal
https://codeforces.com/problemset/problem/1513/D
题解：显然每步操作不影响全局和，我们可以求和，若不被n整除则无解，否则我们得到最终状态。我们发现1位置很自由，故考虑把每一位都全部置于1上再全部重新放置，寻找一个位置，要么其可以交出元素给1，要么可以通过1给与其元素后把元素全部给1，若有解且所有数不全相等，则必然存在这样的位置。证明：
考虑最坏情况下1位置为1，而2位置至少为1，此时2即为该位置，而对于后续，即使每一位都为1，由于之前每一位我们都可以得到，故我们可以将其加到i位上从而>=i,故每一位都可以在至多3补内解决，故此题得解。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N];
struct node{
int x,y,c;
}ans[N];
void solve(){
int n;cin>>n;
int tot=0,p=0,s=0;
int ok=1;
for(int i=1;i<=n;i++){
cin>>a[i];
s+=a[i];
if(i>=2)
if(a[i]!=a[i-1]) ok=0;
}
if(ok){
cout<<0<<endl;
return;
}
if(s%n){
cout<<-1<<endl;
return;
}
s/=n;
for(int i=2;i<=n;i++){
int d=(a[i]%i),x=(a[i])/i;
if(d+a[1]>=i){
p=i;break;
}
if(x){
ans[++tot].x=i,ans[tot].y=1,ans[tot].c=x;
a[i]=a[i]%i;
p=i-1;
break;
}
}
if(p==0){
cout<<-1<<endl;
return;
}
for(int i=p;i>=2;i--){
int d=(i-(a[i]%i))%i,x=(a[i]+d)/i;
if(d!=0)
ans[++tot].x=1,ans[tot].y=i,ans[tot].c=d;
if(x!=0)
ans[++tot].x=i,ans[tot].y=1,ans[tot].c=x;
}
for(int i=p+1;i<=n;i++){
int d=(i-(a[i]%i))%i,x=(a[i]+d)/i;
if(d!=0)
ans[++tot].x=1,ans[tot].y=i,ans[tot].c=d;
if(x!=0)
ans[++tot].x=i,ans[tot].y=1,ans[tot].c=x;
}
for(int i=2;i<=n;i++){
ans[++tot].x=1,ans[tot].y=i,ans[tot].c=s;
}
cout<<tot<<endl;
for(int i=1;i<=tot;i++){
cout<<ans[i].x<<" "<<ans[i].y<<" "<<ans[i].c<<endl;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--) solve();
}
D. GCD and MST
https://codeforces.com/problemset/problem/1682/D
题解：
D. Binary String Sorting
https://codeforces.com/contest/1809/problem/D
题解：我的做法是贪心，对于0，我们认为到达最右端需要经过其的1为其cost，1则反之，我们每次应该删去cost最大的值，其只可能是最右端的0或最左端的1，而对于相同cost时，我们应该选择删去不会使得无法进行交换的那个位置（显然交换至多进行一次）故可以O（n）得到答案。
当我在网上看到了有一个更好的做法：由于至多进行一次交换操作，其余操作都为删除，故我们可以枚举i,i左边必须全为0，i右边包括i必须全为1，i从0->n，若这时ai=0而ai-1=1,则这两个位置进行交换，用此去更新答案，即为正解。
我的代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+100;
int a[N],s[N],ss[N],b[N];
void print(__int128 n){
if(n<0){
putchar('-');
n*=-1;
}
if(n>9) print(n/10);
putchar(n % 10 + '0');
}
void solve(){
string sss;cin>>sss;
int n=sss.length();
for(int i=1;i<=n;i++){
a[i]=sss[i-1]-'0';
b[i]=0;
}
for(int i=1;i<=n;i++){
s[i]=s[i-1]+a[i];
}
int p1=0,p2=n+1;
if(n==0){
cout<<0<<endl;
return;
}
ss[n+1]=0;
for(int i=n;i>=1;i--){
ss[i]=ss[i+1]+(1-a[i]);
}
int l=1,r=n;
while(l<=n&&a[l]==0) l++;
while(r>=1&&a[r]==1) r--;
for(int i=l;i<=n;i++){
if(a[i]==0){
p1=i;break;
}
}
for(int i=r;i>=1;i--){
if(a[i]==1){
p2=i;break;
}
}
p1=p1-l+1,p2=r-p2+1;
// if(l>=r){
// cout<<0<<endl;
// return;
// }
int cnt=0,ans=0;
int cnt1=0,cnt2=0;
while(l<r){
int x=ss[l]-cnt1,y=s[r]-cnt2;
// cout<<x<<" "<<y<<endl;
// cout<<l<<" "<<r<<endl;
if(x>y){
ans++;cnt++;
l++;
while(l<=n&&a[l]==0) l++;
cnt2++;
}
else if(x<y){
ans++;cnt++;
r--;
while(r>=1&&a[r]==1) r--;
cnt1++;
}
else if(x==y){
if(x>1){
if(a[l+1]==0){
r--;
while(r>=1&&a[r]==1) r--;
cnt1++;
}
else{
l++;
while(l<=n&&a[l]==0) l++;
cnt2++;
}
ans++;cnt++;
}
else if(x==1){
cnt++;
cnt1++,cnt2++;
l++,r--;
while(l<=n&&a[l]==0) l++;
while(r>=1&&a[r]==1) r--;
}
else if(x==0){
l++,r--;
while(l<=n&&a[l]==0) l++;
while(r>=1&&a[r]==1) r--;
}
}
}
__int128 xx=(__int128)cnt*1e12;
xx=xx+ans;
// ans=ans+cnt*1e12;
print(xx);
cout<<endl;
}
signed main(){
//ios::sync_with_stdio(false);
//cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--) solve();
}