题目A

题目大意

给定一个长度为n的二进制数，构造一个排序网络，使除了给定二进制数不能达到非递减排序外其它长度为n的二进制数情况都能达到。

解题思路

若有多个1，那么找到第一个1的位置pos，构造以pos为i，其它1为j的排序网络，这样原二进制数就会因为此产生无效交换实现达不到非递减排序的目的。

其它情况相同合并处理，对除了pos位置的其它位置进行排序，此时排序后（对于长度为n的非给定的二进制数）可能出现pos为0，pos左边出现1的情况，那么我们就要把左边的1都往右移动一个位置；还有可能排序后pos为1，后面的数为0，此时要对pos位置的1进行调整后移，但不能移到最后否则给定的要求不能达到排序效果的原二进制数也被成功排序了。

复杂度分析

时间复杂度：Ｏ（ｎ＾２）

参考代码

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
/*====================*/
typedef long long LL;
typedef pair<int,int> PII;
/*====================*/
const double eps=1e-8;
/*====================*/
bool multi=1;

void solve(){
    vector<pair<int,int>> res;
    int n;
    cin>>n;
    string s;
    cin>>s;
    s=' '+s;
    int pos=1,cnt=0;
    while(s[pos]!='1'){
        pos++;
    }

    for(int i=1;i<=n;i++){
        cnt+=s[i]=='1';
    }

    for(int i=pos+1;i<=n;i++){
        if(s[i]=='1') res.push_back({pos,i});
    }

    for(int i=n;i>=1;i--){
        if(i==pos) continue;
        for(int j=1;j<i;j++){
            if(j==pos) continue;
            res.push_back({j,i});
        }
    }
    for(int i=pos-1;i>=1;i--) res.push_back({i,i+1});
    for(int i=pos;i<=n-cnt-1;i++){
        res.push_back({i,i+1});
    }

    cout<<res.size()<<endl;
    for(int i=0;i<res.size();i++){
        cout<<res[i].first<<' '<<res[i].second<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

题目D

题目大意

有一个 $n*m$ 的方格，每格上都有一块巧克力。Kelin(K)和Walk Alone(W)两人轮流吃巧克力，Kelin先手。每人每次选择一对数x,y，吃掉以 $(1,1)$ 为左下角， $(x,y)$ 为右上角的矩形的巧克力且每次必须至少吃到 $1$ 个。吃到 $(n,m)$ 的玩家败，问谁获胜。

解题思路

分情况讨论：

①当n=1且m=1时，显然W胜

②当n=1且m≠1时，K第一次取走(1,1)到(1,m-1)，W只能取(n,m)，显然K胜；当n≠1且m=1时同理。

③当n≠1且m≠1时，K第一次取走(1,1)，接下来W取走后有两种情况：剩下完整矩形；剩下缺角的矩形。前者情况下若剩下的完整矩形只剩一列或一行，则与②情况相同，否则继续取剩下矩形的左下角的一块方格；后者情况下，取走最下边若干行或最左边若干列，可使得矩形仍然变成缺左下一块角的矩形，最终会剩下2*2大小缺左下一个角的矩形，此时W只能取左上块或右下块，K取对应得另一块，显然K取胜。

复杂度分析

时间复杂度：O(1)

空间复杂度：O(1)

参考代码

void solve(){
    int a,b;
    cin>>a>>b;
    if(a==1&&b==1)  cout<<"Walk Alone"<<endl;
    else cout<<"Kelin"<<endl;
}

题目H

题目大意

给定两个长度为n的数组a,b，可以选择其中一个数组交换其中的两个数字，问经过至多一次操作后最小的 $\sum_{i=1}^n \lvert a_i-b_i \rvert$ .

$1\le n\le 2*10^5,0\le \lvert a_i\rvert,\lvert b_i \rvert\le 10^{12}$

解题思路

由于选择 $a,b$ 数组的效果相同，我们规定只选 $a$ 数组。

我们可以用原来的 $\sum_{i=1}^n \lvert a_i-b_i \rvert$ 减去交换这一操作的贡献来得到答案。

那么如何算交换这一操作带来的贡献？
首先，每一个 $a[i],b[i]$ 都可以用一维坐标轴上的一条线段表示，线段的长度即 $\lvert a_i-b_i \rvert$

而一次交换操作，则是相当于将 $i,j$ 对应两条线段的 $a[i],a[j]$ 两点交换。

（1）（正序）当 $a[i]\le b[i]$ 且 $a[j]\le b[j]$$$$(a[i]>b[i]且a[j]>b[j])情况原此类似，这里也一一画图解释)$

①如下图所示为 $a[j]\le b[i]$ 时和交换 $a[i],a[j]$ 后的图，两线段和交换前后不变

② $a[j]>b[i]$ 情况下画图同理可得，两线段和交换前后不变。

（2）（反序）当 $a[i]>b[i]$ 且 $a[j]<b[j]$ （ $a[i]\le b[i]且a[j]\ge b[j]$ )

（重叠情况）如下图情况下，线段和减少了 $2*\lvert a[i]-a[j]\rvert$ ，即两倍的重叠面积

因为情况略多，画图不便，这里只讨论重叠情况下这一种情况，其它情况同理

（不重叠情况）如下图，观察到交换前后，线段和增加了 $2*\lvert a[i]-a[j]\rvert$

同样情况略多，我们只演示了一种情况。

多次情况模拟后可总结：反序 $(a[i]-b[i])*(a[j]-b[j])<0$ 下的有重叠情况会使答案在原来情况下减小 $2*重叠部分的长度$

因此我们只需找到反序重叠情况下最大的重叠部分的长度即可。

那么如何找：

我们先按照每个线段的左端点排序，再从左往右遍历每个线段。初始使cur为c[0],i从1开始遍历到n-1

①如果 $c[i].r<=cur[i].r$ 且 $flag$ 不相等又左端点递增即 $c[i].l>=cur.l$ （i线段被cur线段包含，且反序），此时被包含的线段的长度即为重叠部分长度 $c[i].r-c[i].l$ ，维护最大重叠部分长度overlap

②反之， $c[i].r>cur[i].r$ ，若 $c[i].l<cur.r$ ，则有重叠部分 $cur.r-c[i].l$ ，否则没有重叠部分，但也可以合并在 $cur.r-c[i].l$ 中，因为此时 $cur.r-c[i].l<0$ 不会更新overlap，对结果无影响。

那么什么时候更新cur？

情况①中不需要更新cur，因为cur包含了c[i]，c[i+1]与cur的重叠部分只会比c[i]大。

情况②中需要更新cur，因为左端点递增，而c[i].r>cur，接下来与c[i]的重叠部分只会比cur大。

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

参考代码

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
/*====================*/
typedef long long ll;
typedef pair<int,int> pii;
/*====================*/
const double eps=1e-8;
/*====================*/
bool multi=0;

struct Node{
    int l,r;//线段的左右端点
    bool flag;//记录a[i]<b[i]还是a[i]>b[i]
//当两个线段的flag不同是即为反序，在此情况下找到两线段重叠部分长度
    bool operator<(const Node &w) const{
        if(l!=w.l) return l<w.l;
        else return r<w.r;
    }
};

void solve(){
    int n;
    cin>>n;
    vector<int> a(n+1),b(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    int sum=0;//求不交换情况下的结果
    vector<Node> c(n);
    for(int i=1;i<=n;i++){
        sum+=abs(a[i]-b[i]);
        c[i-1]={min(a[i],b[i]),max(a[i],b[i]),a[i]<b[i]};
    }
    sort(c.begin(),c.end());
    int overlap=0;//最大重叠部分的长度
    Node cur=c[0];
    for(int i=1;i<n;i++){
        if(c[i].r<=cur.r){
            if(cur.flag!=c[i].flag) overlap=max(overlap,c[i].r-c[i].l);//反序情况下更新最大重叠部分长度
        }else{
            if(cur.flag!=c[i].flag) overlap=max(overlap,cur.r-c[i].l);//反序情况下更新最大重叠部分长度
            cur=c[i];
        }
    }
    cout<<sum-2*overlap<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

题目J

题目大意

Walk Alone 初始有 $n$ 块钱，如果每次投 $x$ 元，有一半的概率输掉这 $x$ 元，另一半概率赢得 $2x$ 元。现在

Walk Alone 采取下述策略投注：

如果上一把赢了，这一把投 $x_i = 1$ 元
如果上一把输了，这一把投 $x_i = 2x_{i-1}$ 元

问 Walk Alone 有多大概率拿到 n + m 元离开。 $1 ≤ n, m ≤ 10^9$ 。

解题思路

观察与模拟样例可知，令一个周期为“输输输 $\dots$ 赢”，此时相当于在最开始的基础上赢了1元

（假设输了k次后赢，相当于 $-1,-2,-4,-8,-16,\dots,-2^{k-1},+2^{k}$ ，最终赚1元）

而我们要从n元赢到n+m元，即需要m个周期。

那么我们只需要求 $n\sim n+m-1$ 每个周期都赢的概率，即 $\prod_{i=n}^{n+m-1}P(i)$

而每个i的P(i)怎么算呢？即从i赢到n+m的概率如何计算？

我们可以考虑i什么情况下不能赢到n+m：

可以发现，有本金才能投入，一个周期内输的次数是有限的

当输了一个周期内能输掉的最大次数k时候，则失败：

$1+2+4+\dots+2^{k-1}\le i\Rightarrow 2^{k}-1\le i$$(注意：输一次是$$2^0$$，所以输k次是$$2^{k-1}$$) 要求最大整数k，且k满足$$2^{k}-1\le i\Rightarrow 2^k\le i+1\Rightarrow k= \lfloor\log_2(i+1)\rfloor$$① 输的概率：$$\frac{1}{2^k}$$ 赢的概率：$$1-\frac{1}{2^k}$

而每个k对应的一块区间 $[2^k-1,2^{k+1}-2]$ 的概率都是相同的，即 $2^k-1\le x(x∈[2^k-1,2^{k+1}-2])$ 对应的最大k都相同

所以我们只需要对 $[n,n+m-1]$ 分块，进行逐块求解即可。

那么找到k的左端点和右端点分别是 $l=\lfloor\log_2(n+1)\rfloor$ 和 $r=\lfloor\log_2(n+m)\rfloor$ （由①式可知）

然后用i遍历 $[l,r]$ ，每次对i对应的块整体用快速幂累乘块中数量length次赢的概率 $p_i=1-\frac{1}{2^i}$ （注意l和r出块间数量从l开始r结束）

复杂度分析

时间复杂度：遍历套快速幂

$logn(\log(n+m)-\log(n+1))$

参考代码

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
/*====================*/
typedef long long ll;
typedef pair<int,int> pii;
/*====================*/
const double eps=1e-8;
const int mod=998244353;
/*====================*/
bool multi=0;

//a ^ b mod p
int qpow(int a,int b,int p){
    ll res=1%p;
    while(b){
        if(b&1) res=res*a%p;
        a=(long long)a*a%p;
        b>>=1;
    }
    return res;
}

void solve(){
    int n,m;
    cin>>n>>m;
    int l=log2(n+1),r=log2(n+m);
    int res=1;
    int inv2=qpow(2,mod-2,mod);//费马小定理预处理2^{-1}%mod的值
    for(int i=l;i<=r;i++){
        int length=min(n+m-1,(1ll<<(i+1))-2)-max(n,(ll)(1ll<<i)-1)+1;//块间数量
        //l对应块的左端点需大于等于n+m-1，r对应块的右端点需小于等于n，我这里直接整体都取min和max了
        res=res*qpow(((1-qpow(inv2,i,mod))%mod+mod)%mod,length,mod)%mod;
        //用到了两次快速幂：1-1/2^k,累乘块长度个概率
    }
    cout<<res<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

题目K

题目大意

给定一个无向图 $G(n, m)$ ，可以将其中任意一条边用两条边替换，每条边的长度都为 $1$ ，可以操作任意多次（也可以不操作）。问经过这
样处理之后，从 1 号节点出发，至多走 k 步最多可以到多少个节点。
数据范围： $1 ≤ n ≤ 10^5， 1 ≤ m ≤ 2 × 10^5， 1 ≤ k ≤ 10^9$ 。

解题思路

首先，我们要知道bfs树的概念，bfs树就是通过bfs从一个指定为树根开始遍历一个图得到的树形结构，既然是树形结构，就没有环。

那么如何构建bfs树？（因为本题求距离1小于等于k的结点数，所以我这里就以1为根节点构建距离1小于等于k的所有结点形成的树）

从树根开始做bfs，每一个u通过一条边edge连向v，如果v第一次被更新则这条边为bfs树边，这个点也被加到bfs树结点中，不满足树需要的条件是结束。

显然，我们要探究的是分裂哪些边？如何选择？

假设k=1e9,如果我们选择分裂与1相邻的边，那么原来结点1连向的点如果有多个边连向其它点，那么这些贡献就会损失，由此可推出应该尽可能保留原有的距离1小于等于k的点。——①

结论：

通过分析发现，我们应该保留原来可以在k步内能到达的点，而去分裂这些点之间多余的边，即删去这些边仍能到达这些点，这些边即bfs树结点之间的非bfs树边。

如下图，假设最上面的顶点为1，红色即为无用边，删去后所有点与根节点的最短距离不变且最短距离所在路径仍存在。

情况2，bfs树的叶子结点如果没有连向bfs树其它结点的非bfs树边，则在这个点与它的父节点之间分裂边

（上面①处分析了损失贡献的分裂边损失贡献的原因，而叶子结点与它的父节点之间分裂边不会损失贡献）

总而言之：bfs树直接解决了分裂哪些边的问题。①所有bfs树结点之间的非bfs树边②bfs树的叶子节点与它的父节点之间的边且该叶子节点不能有一条连向bfs树结点的非bfs树边

复杂度分析

时间复杂度：O(mlogm)（遍历所有边m，标记bfs树边使用了map，每次操作logm）

参考代码

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
/*====================*/
typedef long long ll;
typedef pair<int,int> pii;
/*====================*/
const double eps=1e-8;
/*====================*/
bool multi=0;

void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    vector<vector<int>> edge(n+1);//bool用来标记是否是bfs树边
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    map<pair<int,int>,bool> mp;//边是否是bfs树边
    vector<int> dist(n+1,-1),bfsver,pre(n+1);
    //dist存结点到根节点1的距离，bfsver存储bfs树结点，pre存储每个bfs树点的父节点
    vector<bool> st(n+1);//标记是否是bfs树上的点
    st[1]=true;
    bfsver.push_back(1);//1是bfs树点
    dist[1]=0;
    queue<int> q;
    q.push(1);
    while(q.size()){
        int u=q.front();
        q.pop();
        if(dist[u]==k) break;//只求距离根节点小于等于k部分的树
        for(auto v:edge[u]){
            if(dist[v]!=-1) continue;
            q.push(v);
            mp[{min(u,v),max(u,v)}]=true;
            //为了降低时间复杂度，所以我直接用{min(u,v),max(u,v)}来同时表示双向边都是bfs树边
            dist[v]=dist[u]+1;
            pre[v]=u;
            st[v]=true;
            bfsver.push_back(v);//将bfs树点加入遇到bfsver中
        }
    }
    int res=(int)bfsver.size();//bfs树上的点都保留，这些点都会是答案的一部分
    
    for(int i=0;i<bfsver.size();i++){
        int u=bfsver[i];
        bool is_cal=0;
        bool is_leaf=1;
        for(auto v:edge[u]){
            bool flag=mp[{min(u,v),max(u,v)}];
            if(st[v]&&!flag){//如果这个bfs树点通过非bfs树边连向了bfs树点，那么这条边可以分裂
                res+=k-dist[u];
                is_cal=1;
            }
            if(pre[v]==u){
                is_leaf=0;
            }
        }
        if(!is_cal&&is_leaf&&u!=1){
            //如果这个点是叶子结点且没有通过非bfs树边连向其它bfs树点，则这个点和它的父节点之间的边可以分裂
            res+=k-dist[u];
        }
    }
    cout<<res<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

题目M

题目大意

给定两个杯子的容积a,b，你可以进行这四种操作：

将其中一个杯子装满水
倒走其中一个杯子中的所有水
喝掉其中一个杯子的所有水
将尽可能多的水从其中一个杯子转移到另一个杯子，保证不溢出

问能喝到c单位水的体积需要的最少操作次数。

解题思路

设喝a水杯和b水杯的次数分别为x,y，得： $ax+by=c$

根据裴蜀定理，若 $gcd(a,b)|c$ ，那么有解，否则无解输出-1

若有解，讨论x,y的正负性与操作次数的关系。

当x≥0且y≥0，每次喝水即倒入和喝水两次操作，结果为2*(x+y)
令a0一种情况,每次喝水先倒入b，再倒入倒出多次a，再喝掉b中的水，但最后一次不需要倒走a中的水，所以结果为2*|x-y|-1

讨论x,y的绝对值最小的四种情况即可。

复杂度分析

时间复杂度: $O(Tlogx)$

参考代码

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
/*====================*/
typedef long long LL;
typedef pair<int,int> PII;
/*====================*/
const double eps=1e-8;
/*====================*/
bool multi=1;

//返回gcd(a,b)
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

void solve(){
    int a,b,c;
    cin>>a>>b>>c;
    int x0,y0;
    int d=exgcd(a,b,x0,y0);
    if(c%d!=0){//裴蜀定理，不能整除表示无解
        cout<<-1<<endl;
        return;
    }
    int x1=x0*c/d,y1=y0*c/d;
    int t1=abs(b/d),t2=a/d;
    //枚举x，y的绝对值最小的四种情况。
    //x为最小非负数
    int x=(x1%t1+t1)%t1;
    int y=(c-a*x)/b;
    int res=(x>=0&&y>=0)?2*(x+y):2*abs(x-y)-1;
    //x为最大负数
    x=(x1%t1+t1)%t1-t1;
    y=(c-a*x)/b;
    res=min(res,(x>=0&&y>=0)?2*(x+y):2*abs(x-y)-1);
    //y为最小非负数
    y=(y1%t2+t2)%t2;
    x=(c-b*y)/a;
    res=min(res,(x>=0&&y>=0)?2*(x+y):2*abs(x-y)-1);
    //y为最大负数
    y=(y1%t2+t2)%t2-t2;
    x=(c-b*y)/a;
    res=min(res,(x>=0&&y>=0)?2*(x+y):2*abs(x-y)-1);

    cout<<res<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}