比赛链接：https://codeforces.com/contest/2140
A.Shift Sort
思路：要交换，我们可以想到第一个不合法的和最后一个不合法的位置进行交换，此时中间位置的值不会被改变。答案为排序后和原序列不同之处/2
#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include<iostream>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#include<functional>
#define ll long long
#define ull unsigned long long
#define lowbit(x) (x & -x)
#define endl "\n"// ???????
using namespace std;
mt19937 rnd(time(0));
const ll mod = 998244353;
// const ll N = 5e5 + 10;
// const ull p=1145161651561;
ll ksm(ll x, ll y)
{ll ans = 1;while (y){if (y & 1){ans = ans * x % mod;}x = x * x % mod;y >>= 1;}return ans % mod;
}
void fio()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
}
const ll N = 3e5 + 5;
struct s {ll l,r,id;friend bool operator<(const s& a, const s& b) {if(a.l!=b.l)return a.l<b.l;else return a.r<b.r;}
};
ll e[4] = { 0,1,0,-1 };
ll d[4] = { 1,0,-1,0 };
void solve() { ll n;cin>>n;string f;cin>>f;ll ans=0;ll cnt=0;for(ll i=0;i<f.size();i++){if(f[i]=='0')cnt++;}ll u=0;for(ll i=0;i<f.size();i++){if(cnt>0&&f[i]=='1')ans++;else if(cnt==0&&f[i]=='0')u++;cnt--;}ans=max(abs(u),abs(ans));cout<<ans<<endl;
}
int main() {fio();ll t = 1;cin>>t;while (t--)solve();return 0;
}
B. Another Divisibility Problem
思路：设len(y)为y的长度对应数值，例如28对应100.x#y%(x+y)=0是等价于\((x*len(y)+y)\%(x+y)=0\),显然y%（x+y）=y,x%(x+y)=x,又因为模意义下的乘积等于正常数乘积取模，故只要len(y)%(x+y)=1即可。那么枚举len(y),然后保证长度对应即可，由于x小于y一个数量级，所以必有答案（例如下面代码cc<=n全跳都可以，当然取消这个判断也对！）
#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include<iostream>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#include<functional>
#define ll long long
#define ull unsigned long long
#define lowbit(x) (x & -x)
#define endl "\n"// ???????
using namespace std;
mt19937 rnd(time(0));
const ll mod = 998244353;
// const ll N = 5e5 + 10;
// const ull p=1145161651561;
ll ksm(ll x, ll y)
{ll ans = 1;while (y){if (y & 1){ans = ans * x % mod;}x = x * x % mod;y >>= 1;}return ans % mod;
}
void fio()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
}
const ll N = 3e5 + 5;
struct s {ll l,r,id;friend bool operator<(const s& a, const s& b) {if(a.l!=b.l)return a.l<b.l;else return a.r<b.r;}
};
ll e[4] = { 0,1,0,-1 };
ll d[4] = { 1,0,-1,0 };
void solve() { ll n;cin>>n;ll cc=1;for(ll i=1;i<=9;i++){cc*=10;if(cc<=n)continue;else {ll dd=cc/10;dd=cc-1-n;ll kk=dd;ll cnt=0;while(kk){kk/=10;cnt++;}if(dd<1e9&&dd>0&&cnt==i){cout<<dd<<endl;return ;}}}
}
int main() {fio();ll t = 1;cin>>t;while (t--)solve();return 0;
}
C.Ultimate Value
思路：一旦后手肯定直接结束游戏了。只考虑变换一次，如果调换对应奇偶位，那么答案要么就是n-1或者n-2,；如果奇偶位互换，只需考虑枚举1-n,如果第i位为偶数位，那么换的是奇数位（设其为x），那么答案就是\(2*a[i]+r-2*a[x]-x\),那么我们只需维护奇数位\(-2*a[x]-x\)最大即可，同理奇数位换偶数位也是一样的道理（式子有所区别，但本质一样）。
#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include<iostream>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#include<functional>
#define ll long long
#define ull unsigned long long
#define lowbit(x) (x & -x)
#define endl "\n"// ???????
using namespace std;
mt19937 rnd(time(0));
const ll mod = 998244353;
// const ll N = 5e5 + 10;
// const ull p=1145161651561;
ll ksm(ll x, ll y)
{ll ans = 1;while (y){if (y & 1){ans = ans * x % mod;}x = x * x % mod;y >>= 1;}return ans % mod;
}
void fio()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
}
const ll N = 3e5 + 5;
struct s {ll l,r,id;friend bool operator<(const s& a, const s& b) {if(a.l!=b.l)return a.l<b.l;else return a.r<b.r;}
};
ll e[4] = { 0,1,0,-1 };
ll d[4] = { 1,0,-1,0 };
void solve() { ll n;cin>>n;vector<ll>a(n+2);for(ll i=1;i<=n;i++)cin>>a[i];ll ans=0;if(n&1)ans+=n-1;else ans+=n-2;ll cc=-3e9;ll yy=cc;ll cnt=0;for(ll i=1;i<=n;i++){if(i&1)cnt+=a[i];else cnt-=a[i];}ans+=cnt;for(ll i=1;i<=n;i++){if(i&1){ans=max(ans,cnt+yy-2*a[i]+i);}else ans=max(ans,cnt+cc+2*a[i]+i);if(i&1)cc=max(cc,-2*a[i]-i);else yy=max(yy,2*a[i]-i);}cout<<ans<<endl;
}
int main() {fio();ll t = 1;cin>>t;while (t--)solve();return 0;
}
D.A Cruel Segment's Thesis
思路：
\[基本思想：答案一定可以认为我先去n个线段的右端点，然后选则其中一半让其变为l后，所有r-所有l的值+每个线段r-l
\]
\[如果n为偶数，只需计算每个线段变换代价，-l-r，存起来排序后，选择其中最大的n/2个相加
\]
\[如果n为奇数，那么就枚举剔除一个线段后进行两两组合的答案，我们还是-l-r，存起来后排序，从大到小排序，可以发现答案要么就是前n/2个或者n/2+1个-剔除线段的（-l-r）,所有答案取max
\]
\[最后只需把所有线段的r-l加上即可
\]
#pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include<iostream>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#include<functional>
#define ll long long
#define ull unsigned long long
#define lowbit(x) (x & -x)
#define endl "\n"// ???????
using namespace std;
mt19937 rnd(time(0));
const ll mod = 998244353;
// const ll N = 5e5 + 10;
// const ull p=1145161651561;
ll ksm(ll x, ll y)
{ll ans = 1;while (y){if (y & 1){ans = ans * x % mod;}x = x * x % mod;y >>= 1;}return ans % mod;
}
void fio()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
}
const ll N = 3e5 + 5;
struct s {ll l,r,id;friend bool operator<(const s& a, const s& b) {if(a.l!=b.l)return a.l<b.l;else return a.r<b.r;}
};
ll e[4] = { 0,1,0,-1 };
ll d[4] = { 1,0,-1,0 };
void solve() { ll n;cin>>n;vector<pair<ll,ll>>a(n+5);ll sum=0;ll cnt=0;vector<ll>ls(n+2,0);for(ll i=1;i<=n;i++){auto &[l,r]=a[i];cin>>l>>r;sum+=r;cnt+=r-l;ls[i]=-l-r;}sort(ls.begin()+1,ls.begin()+1+n);reverse(ls.begin()+1,ls.begin()+1+n);if(!(n&1)){ll ans=cnt+sum;//cout<<ans<<endl;for(ll i=1;i<=n/2;i++){ans+=ls[i];//}cout<<ans<<endl;}else {ll ans=0;vector<ll>pre(n+4,0);for(ll i=1;i<=n;i++){pre[i]=pre[i-1]+ls[i];}for(ll i=1;i<=n;i++){ll uu=sum-a[i].second;//假设不需要ll xx=-a[i].first-a[i].second;ll zz=n/2;if(ls[zz+1]>=xx){ans=max(ans,uu+cnt+pre[zz]);}else {ans=max(ans,uu+cnt-xx+pre[zz+1]);}}cout<<ans<<endl;}}
int main() {fio();ll t = 1;cin>>t;while (t--)solve();return 0;
}