同步更新，但是现在网站的latex还没渲染好
https://happycoding.me/posts/codeforces-round-1050-div4/
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;
}
——Xml序列化、反序列化、IXmlSerializable接口)
)
)
