A

思路：

当$n$为奇数时，答案为$x$，否则为$0$

B

思路：

显然每条线段都要经过，答案为$n+m$

C

题意：

现有$2$侧：$0$侧和$1$侧，$0$分钟一开始在$0$侧，尽可能地在两侧之间来回跑 给定$n$个约束 每个约束给定$ai,bi$，要求在第$ai$分钟，需要在$bi$侧 求经过$m$分钟后，最大来回次数

思路：

模拟+分类讨论

对于样例1：2个约束，跑4分钟 最好的方式: 0 1 1 0 0 1 2 3 4 5 跑2次

样例3：2个约束，跑7分钟 最好的方式： 0 1 0 1 0 1 0 1 0 1 2 3 4 5 6 7 跑7次

观察得到：

当约束时间差$dif=a[i]-a[i-1]$为偶数时 如果$b[i]!=b[i-1]$,那么这段时间对答案的贡献是$dif-1$ 反之,贡献是$dif$

当$dif$为奇数时， 如果$b[i]!=b[i-1]$，那么这段时间对答案的贡献是$dif$ 反之贡献是$dif$

一开始时间戳为$0$，在$0$侧，模拟即可

D

题意：

有一台收割机，一开始是关闭的。 给定一个数组$a$，按任意顺序访问每个数组元素一次。 当访问元素为奇数时，收割机开关一次，否则无视 当收割机开启时，会使访问到的元素添加到答案之和中 求答案之和的最大值

思路：

贪心 当数组$a$没有奇数时，显然收割机无法开启，答案为0

否则，可以取到所有的偶数元素之和 将奇数元素从大到小排列，先取当前最大的元素 再去取最小的元素，使收割机下一次遇到奇数时是开启的状态

E

题意：

给定一个长度为$n$的数组$a$

有$k$个$multiset$多重集 现在规定一个区间$[l,r]$为好区间，当且仅当: 对于整个数组$a$区间$[l,r]$，都必须放入第一个多重集中 其他剩下来的元素，可以放入任意一个多重集中 要求可以通过操作使得这$k$个多重集完全相同

现在求出数组$a$的好区间数量

思路：

双指针

要将数组$a$的一个元素$x$分到$k$个多重集中 要求$x$的数量$Cnt[x]$为$k$的倍数

对于一个好区间$[l,r]$，其中所有的元素$x$的数量不能多于$Cnt[x]/k$个

发现区间窗口往右扩展时，元素数量是单调增的 因此用双指针$O(n)$地统计区间数量：= 满足条件的最大的$r$ -当前的$l$

F

题意：

给定$n$个长度不一定相等的数组$ai$ 按照一定顺序从高到低排列，当一个数组元素下面是空的，会下落 求最低层数组元素 最小的字典序排列

思路：

时间复杂度+模拟

可以通过对vector<vector<int>>vec这样的数组进行sort操作 此时会按照数组字典序顺序排列

那么每次取出第一个数组（字典序最小），然后将其他数组与该数组长度相等的地方进行暴力删除，再重新放入vec排序，不断重复即可

void solve(){
    int n;cin>>n;
    vector<vector<int>>vec;
    int cnt=0;

    rep(i,1,n){
        int k;cin>>k;
        cnt=max(cnt,k);
        vector<int>s;
        rep(j,1,k){
            int x;cin>>x;s.pb(x);
        }
        vec.pb(s);
    }
    int p=0;
    while(p!=cnt){
        sort(vec.begin(),vec.end());
        int siz=vec[0].size();
        p+=siz;
        for(auto ele:vec[0]){
            cout<<ele<<' ';
        }
        vector<vector<int>>vs;
        for(auto v:vec){
            if(v.size()==siz)continue;
            vector<int>x;
            for(int j=siz;j<v.size();j++){
                x.pb(v[j]);
            }
            vs.pb(x);
        }
        vec=vs;
    }
    cout<<endl;
}

G

题意：

给定一个长度为$n$的数组$a$ 设$f(a)$为经过重新排序后，使得前缀$gcd$降低的最右边的数组下标 现在对$a$的每一个前缀$pre$数组都求一边$f(pre)$

思路：

观察样例1： 8 2 4 3 6 5 7 8 6

0 1 2 3 3 3 4 5

对于2 4 3 6这个前缀数组 像2 4 6 3这样排列是最优的 因此启发我们将某个数的倍数放在靠前的位置，这样答案是最优的

但考虑样例3： 9 8 4 2 6 3 9 5 7 8

对于8 4 2 6这个前缀数组： 像4 8 2 6这样排列是最优的 这4个数都是$2$的倍数，但是答案不是$4$ 因此我们知道当前前缀数组$[1,i]$的答案一定比$i$小

那么我们去找 其他数的倍数 个数小于i 的极大值，就是当前最优的答案

由于当 前缀数组$[1,i]$ 某个数$x$的倍数个数是 $i$ ，但是到前缀数组$[1,i+1]$ 时，$a[i+1]$不是$x$的倍数，此时最优的答案就要考虑把$x$的倍数放在靠前的位置，也就是$i$

const int M=2e5+5;
vector<int>divor[M];
void pre(){//题解的预处理方式
    for(int i=2;i<M;i++){
        for(int j=i;j<M;j+=i){
            divor[j].pb(i);
        }
    }
}
void solve(){
    int n;cin>>n;
    vector<int>a(n+1);
    rep(i,1,n)cin>>a[i];

    vector<int>tot(n+1);
    vector<int>max_nums;

    int ans=0;
    rep(i,1,n){

        vector<int>nxt;
        for(auto ele:divor[a[i]]){
            tot[ele]++;
            if(tot[ele]!=i)ans=max(ans,tot[ele]);
            else {
                nxt.pb(ele);
            }
        }

        for(auto ele:max_nums){
            if(tot[ele]!=i){
                ans=max(ans,tot[ele]);
            }
        }

        cout<<ans<<' ';
        max_nums = nxt;
    }
    cout<<endl;
}

signed main()
{
  ios::sync_with_stdio(false),cin.tie(0);
  int T=1;
cin>>T;
pre();
  while(T--){
  solve();
  }

  return 0;
}