A.Almost Correct
题意：给定一个01串，要求构造一系列排序操作(xi,yi)，使得经过这些排序操作后可以使与给定01串等长的所有其他01串完全排好序，而给定的01串无法完全排好序
Solution
构造题
我们考虑到对0和1的位置进行统计，统计得出最左边的1的位置为l，最右边的0的位置为r
我们进行三次排序
第一次排序：对l和所有其他的1的位置进行排序，对r和所有其他的0的位置进行排序
第二次排序：对除了l和r以外的数进行排序
第三次排序：将l和r不断靠拢直到变为0000...0010111111..111的情况
如果l和r上有一个数是不对的话，那么最后经过一系列操作肯定可以排好序
如果l和r上都是对的话，考虑其他的0和1，如果当中出现了一个错误的0/1，那么经过第一次排序，将会使得l和r上面出现错误的数
void solve()
{
int n;cin>>n;
string s;cin>>s;
vector<int>s0,s1;
for(int i=0;i<s.length();i++)
{
if(s[i]=='0')s0.push_back(i+1);
else s1.push_back(i+1);
}
int r=s0.back(),l=*(s1.begin());
//cout<<l<<r<<"\n";
vector<pii>ans;
for(auto it:s0)if(it!=r)ans.push_back({min(it,r),max(it,r)});
for(auto it:s1)if(it!=l)ans.push_back({min(it,l),max(it,l)});
for(int i=1;i<=n;i++)
{
if(i==l||i==r)continue;
for(int j=i+1;j<=n;j++)
{
if(j==l||j==r)continue;
ans.push_back({i,j});
}
}
for(int i=s0.size()+1;i<r;i++)ans.push_back({i,r});
for(int i=n;i>r;i--)ans.push_back({r,i});
for(int i=s0.size();i>l;i--)ans.push_back({l,i});
for(int i=1;i<l;i++)ans.push_back({i,l});
cout<<ans.size()<<"\n";
for(auto &[x,y]:ans)
{
cout<<x<<" "<<y<<"\n";
}
}
D.Chocolate
题意：有一个矩阵巧克力，长n宽m，懵哥和Kelin轮流选一个点（i,j)，吃掉所有x<=i,y<=j的部分，吃掉最后一块巧克力的人输掉，Kelin先吃，问谁会赢
Solution
结论题
当n=1且m=1时懵哥获胜，否则Kelin获胜
证明也很好证
n=1,m=1的不用说
n=1,m!=1或者n!=1,m=1的也不用说
看n>1和m>1的情况
我们假设Kelin先吃(n-1,m-1)的部分，这时候懵哥为了获胜肯定只会选择某一边上的一部分，那么他吃的剩下多少，我们就使得另一边也剩多少，最后懵哥必定吃掉最后一块巧克力
void solve()
{
cin>>n>>m;
if(n==1&&m==1)cout<<"Walk Alone\n";
else cout<<"Kelin\n";
}
H.Matches
题意：给出两个数组a和b，令
可以进行最多一次交换操作，交换同数组内的两个数，问sum最小是多少
Solution
我们定义a[i]和b[i]与a[j]和b[j]两对数的大小关系相同的为正序，不相同的为反序
通过计算会使得答案变小的操作只有交换反序相交和反序包络的情况，即相互反序且有交集的
我们考虑把(a[i],b[i])都放到一个数组里排序，将它们按第一关键字左端点升序和第二关键字右端点升序排序
我们从头到尾开始遍历，并记录一下反序的最大的右端点mx
先以b[i]>a[i]为正序，如果当前的是正序，那么就与mx右端点比较，看是包络还是相交，并更新最大的变化值，如果是反序则更新mx
再以a[i]>b[i]为正序，重复上述操作即可
int a[N];
int b[N];
int n;
struct node
{
int x,y,z;
bool operator < (const node&t)const &{
if(x!=t.x)return x<t.x;
return y<t.y;
}
};
vector<node>v;
void solve()
{
cin>>n;
int sum=0;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++)
{
sum+=abs(a[i]-b[i]);
if(a[i]<b[i])v.push_back({a[i],b[i],0});
else if(a[i]>b[i])v.push_back({b[i],a[i],1});
}
int mx=-1e18;
int temp=0;
sort(v.begin(),v.end());
for(auto it:v)
{
if(it.z==1)mx=max(mx,it.y);
else if(mx>it.y)
{
temp=max(temp,2*(it.y-it.x));
}else
{
temp=max(temp,2*(mx-it.x));
}
//cout<<mx<<" "<<it.x<<" "<<it.y<<" "<<temp<<"\n";
}
//cout<<sum-temp<<"\n";
mx=-1e18;
for(auto it:v)
{
if(it.z==0)mx=max(mx,it.y);
else if(mx>it.y)
{
temp=max(temp,2*(it.y-it.x));
}else
{
temp=max(temp,2*(mx-it.x));
}
}
cout<<sum-temp<<"\n";
}
J.Roulette
题意：懵哥赌博，每次赌赢的概率都是0.5，他最开始有n元，想获得额外的m元，假设懵哥花了x块钱赌下一轮
如果懵哥赌赢了，他将获得2x元，并且下一次只会花1块钱
如果懵哥赌输了，他下次会花2x元
懵哥第一轮会花1元，并且会在获得n+m元时停止赌博
问懵哥额外获得n+m元的概率是多少
Solution
通过题意其实可以知道，无论输了多少次，如果当前赢了一把，其实就是在没输之前的情况下额外获得了一块钱而已
假设当前的钱数可以让他输x[i]次（即输了x[i]次后就无法赌了）
那么答案概率就是
对于x[i]相同的我们可以预处理一下，然后对分子分母进行计算即可
void solve()
{
a[0]=1;
for(int i=1;i<=31;i++)a[i]=a[i-1]*2;
cin>>n>>m;
int sum=0;
int cnt=0;
int now=1;
m=n+m;
while(sum+now<=n)
{
sum+=now;
now*=2;
cnt++;
}
int fz=1,fm=1;
while(n<m)
{
int pos=min(sum+now-1,m-1);
fz=(fz*ksm(a[cnt]-1,pos-n+1))%mod;
fm=(fm*ksm(a[cnt],pos-n+1))%mod;
cnt++;
sum+=now;
now*=2;
n=pos+1;
}
cout<<(fz*((ksm(fm,mod-2))%mod))%mod<<"\n";
}
K.Subdivision
题意：给出一个n个点m条边的无向图，每个边的长度为1，可以进行任意次以下操作
选择一个边(u,v)并删除，新加一个点w，新加两条边(u,w)和(w,v)，新加的边长度也为1
问最后与节点1距离不大于k的点有多少个
Solution
首先bfs遍历一遍图，这样保证每个点的距离是最小的，且是一颗树形的
我们把距离k以内的点的个数加入到答案的贡献内，现在考虑进行操作增加的贡献
现在我们看距离k以内的点相邻的边只有一条的，如果它的距离小于k，那么可以通过对它唯一相邻的边进行操作从而增加对答案的贡献
然后就是看其他的边了，因为我们最开始遍历呈现为一颗树形，且通过之前的操作已经使得整棵树不能在进行操作了，所以我们可以对除了树上以外的边进行操作
我们假设当前边连接的两个点的深度分别是dis[i]和dis[j]，那么其对应可以增加k-dis[i]和k-dis[j]个有效点
vector<int>e[N];
void add(int u,int v)
{
e[u].push_back(v);
e[v].push_back(u);
}
typedef pair<int,int> pii;
int d[N];
int vis[N];
struct node
{
int x,y,z;
};
void solve()
{
int n,m,k;cin>>n>>m>>k;
int ans=0;
set<pii>st;
for(int i=1;i<=m;i++)
{
int u,v;cin>>u>>v;
st.insert({min(u,v),max(u,v)});
add(u,v);
}
queue<node>q;
q.push({0,1,0});
while(q.size())
{
node t=q.front();
q.pop();
if(vis[t.y])continue;
vis[t.y]=1;
if(t.z!=0)
{
st.erase({min(t.y,t.z),max(t.y,t.z)});
}
d[t.y]=t.x;
for(auto it:e[t.y])
{
q.push({t.x+1,it,t.y});
}
}
for(int i=1;i<=n;i++)
{
if(d[i]>k)continue;
if(d[i]==0&&i!=1)continue;
ans++;
if(e[i].size()==1&&i!=1&&d[i]!=k)
{
ans+=k-d[i];
d[i]=k;
}
//cout<<ans<<"\n";
}
for(auto it:st)
{
//cout<<"1\n";
if(d[it.first]==0&&it.first!=1)continue;
ans+=max(0LL,k-d[it.first])+max(0LL,k-d[it.second]);
}
cout<<ans<<"\n";
}
L.Three Permutations
题意：有三个长为n的数组a,b,c，最开始有三个数x=1，y=1，z=1，每隔一秒这三个数会变成a[y],b[z],c[x]，进行q次询问，每一次查询最开始的x,y,z需要最少多少秒才能变成x',y',z'
Solution
中国剩余定理
解线性同余方程
考虑到x,y,z每一秒变成的数与其他数有关，我们来看每隔三秒的情况
如果当前是x,y,z，那么下一轮将会变成a[b[c[x]]],b[c[a[y]]],c[a[b[z]]]
这样我们可以预处理多少轮以后x,y,z会变回1,1,1，以及每个数最少需要多少轮，可以获得关于x,y,z的三个同余方程，通过中国剩余定理我们可以得到一个同余方程，这个同余方程即我们需要的答案
int a[N];
int b[N];
int c[N];
int ia[N];
int ib[N];
int ic[N];
int exgcd(int a, int b, int &x, int &y) {
if(!b)
{
x = 1;
y = 0;
return a;
}
int ans = exgcd(b, a%b, x, y);
int t = x;
x = y;
y = t - a / b * y;
return ans;
}
pii excrt(pii l,pii r)
{
int r1=l.first,m1=l.second;
int r2=r.first,m2=r.second;
if(r1==-1||r2==-1)return {-1,-1};
int x,y;
int g=exgcd(m1,m2,x,y);
if((r2-r1)%g)return {-1,-1};
int bg=m2/g;
x*=((r2-r1))/g;
x=(x%bg+bg)%bg;
int L=(m1/g*m2);
int R=r1+x*m1;
return {R,L};
}
struct node
{
int x,y,z;
};
int na[N];
int nb[N];
int nc[N];
int disa[N];
int disb[N];
int disc[N];
int lena=0,lenb=0,lenc=0;
const int inf=1e18;
int get(int x,int y,int z)
{
if(disa[x]==-1||disb[y]==-1||disc[z]==-1)return inf;
pii A={disa[x],lena};
pii B={disb[y],lenb};
pii C={disc[z],lenc};
/*cout<<A.first<<" "<<A.second<<"\n";
cout<<B.first<<" "<<B.second<<"\n";
cout<<C.first<<" "<<C.second<<"\n";*/
B=excrt(B,C);
A=excrt(A,B);
//cout<<A.first<<" "<<A.second<<"\n";
if(A.first==-1)return inf;
else return A.first;
//return 1;
}
void solve()
{
memset(disa,-1,sizeof(disa));
memset(disb,-1,sizeof(disb));
memset(disc,-1,sizeof(disc));
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++)cin>>c[i];
for(int i=1;i<=n;i++)ia[a[i]]=i;
for(int i=1;i<=n;i++)ib[b[i]]=i;
for(int i=1;i<=n;i++)ic[c[i]]=i;
for(int i=1;i<=n;i++)na[i]=a[b[c[i]]];
for(int i=1;i<=n;i++)nb[i]=b[c[a[i]]];
for(int i=1;i<=n;i++)nc[i]=c[a[b[i]]];
for(int i=1;disa[i]==-1;i=na[i],lena++)disa[i]=lena;
for(int i=1;disb[i]==-1;i=nb[i],lenb++)disb[i]=lenb;
for(int i=1;disc[i]==-1;i=nc[i],lenc++)disc[i]=lenc;
int q;cin>>q;
while(q--)
{
int x,y,z;cin>>x>>y>>z;
get(x,y,z);
int ans1=get(x,y,z);
int ans2=get(ic[z],ia[x],ib[y]); //先往前走再走一步
int ans3=get(ic[ib[y]],ia[ic[z]],ib[ia[x]]); //先往前走再走两步
int ans=min({ans1*3,ans2*3+1,ans3*3+2});
cout<<(ans>=inf?-1:ans)<<"\n";
}
}
M.Water
题意：有一个容积为A和B的容器，现在可以进行以下操作
1.使其中一个容器装满水
2.倒掉其中一个容器的所有水
3.喝光一个容器中的所有水
4.将一个容器中的水转移到另一个，直到其中一个容器的水空或者另一个容器装满
问最少要进行多少次操作，才能使得恰好喝下x单位的水
Solution
我们可以令x=rA+sB
我们可以发现有两种情况，一种是r和s都大于0的情况，这样我们只需进行2(r+s)次操作：A装r次水，A喝r次水，B装s次水，B喝s次水
另一种是r和s有一个小于0的，具体证明看https://zhuanlan.zhihu.com/p/644323896
大致意思：
令A>B，r>0，s<0
可以看成喝下(r+s)杯(A+B)和(-s)杯(A-B)的
A+B的贡献就是2(r+s)
A-B的进行以下操作：
1.装满A
2.A转移到B
3.喝光A中的（即A-B单位的水）
4.倒掉B中的
其实除了最后一个以外其他的都要进行(-s)次操作，最后一个只用进行(-s-1)次，因为最后一次可以不用倒掉，那么就有贡献3*(-s)+(-s-1)即-4s-1
将两者贡献相加即2r-2s-1即2|r|+2|s|-1
通过扩展欧几里得可以得到r和s的一个答案
通过一系列操作使得(r,s)为离原点最小的一个点，并且更新答案，然后再对其周围的点进行更新即可
int exgcd(int a, int b, int &x, int &y) {
if(!b)
{
x = 1;
y = 0;
return a;
}
int ans = exgcd(b, a%b, x, y);
int t = x;
x = y;
y = t - a / b * y;
return ans;
}
void solve()
{
int a,b,c,x,y;cin>>a>>b>>c;
int g=exgcd(a,b,x,y);
if(c%g)
{
cout<<"-1\n";
return;
}
a/=g;
b/=g;
c/=g;
x*=c;
x=(x%b+b)%b;
y=(c-x*a)/b;;
int ans=1e18;
for(int i=-10;i<=10;i++)
{
int r=x+i*b,s=y-i*a;
if(r>=0&&s>=0)ans=min(ans,2*(r+s));
else ans=min(ans,2*(abs(r)+abs(s))-1);
}
cout<<ans<<"\n";
}