Codeforces Round #845 (Div. 2) and ByteRace 2023 A-D
A. Everybody Likes Good Arrays!
题意：对给定数组进行操作：删除相邻两项，替换为两项的乘积，使得该数组奇偶相间。
题解：从前向后遍历模拟
代码：
void solve(){
int n=read(),ans=0;
for(int i=1;i<=n;i++) a[i]=read()%2;
for(int i=1;i<n;i++){
if(a[i]&&a[i+1]) ans++;
else if(!a[i]&&!a[i+1]) ans++;
}
cout<<ans<<endl;
}
B. Emordnilap
题意：对n个数的每个全排列拼接上其逆序排列后的逆序对总数
题解：找规律 对于n个数 有如下性质：
1.有n!个排列
2.每个排列拼接上自己的逆序后 有n*(n-1)个逆序对
由此：逆序对总和即为n!*n*(n-1)个
代码：
void solve(){
int n=read(),ans=1;
for(int i=1;i<=n;i++){
ans*=i;
ans%=mod;
}
ans*=n;
ans%=mod;
ans*=(n-1);
ans%=mod;
}
C. Quiz Master
题意：在给定的数组中 选择其中几个使1~m的每个数是至少是一个选择的数字的因子 若选不出这样的几个数则输出-1 否则输出选择的最大数与最小值的差
题解：朴素的双指针思想 在对给定数组排序后 指向最大数与最小数的指针(分别记为R,L)有如下性质：
1.取上两个指针间所有数对最后答案无影响
2.对于目前不能构成选择区间的L,R指针，若L指针不动，只有R指针向后移动才可能重新构成满足题意的区间
所以采用双指针算法 R向后移动时记录新R的因子 L向后移动时去掉原L的因子 以此维护双指针区间
代码：
int a[N],cnt[N],n,m;
bool check(){
for(int i=1;i<=m;i++){
if(cnt[i]<=0) return false;
}
return true;
}
void solve(){
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=m;i++) cnt[i]=0;
sort(a+1,a+n+1);
int ans=inf;
for (int i = 1, j = 1; i <=n; i ++ ){
for(int h=1;h*h<=a[i];h++){
if(a[i]%h==0){
cnt[h]++;
cnt[a[i]/h]++;
}
}
while (j <= i && check()){
ans=min(ans,a[i]-a[j]);
j++;
for(int h=1;h*h<=a[j-1];h++){
if(a[j-1]%h==0){
cnt[h]--;
cnt[a[j-1]/h]--;
}
}
}
}
if(ans<inf)cout<<ans<<endl;
else cout<<-1<<endl;
}
D. Score of a Tree
题意：现有一棵根为1的树，其中初始点权是0或1。每一秒，一个点的点权变为其所有子节点的值的异或值。求在所有时间下，所有01配置的树节点的总值。
题解：对每一结点，有如下性质：
1.每个初始时刻值的期望为1/2
2.每个节点都存在一个时间点 tx ，在 tx 后该节点值始终为0。 且 tx 等于该节点的子树最大深度
3.每个节点在tx之前，其值的期望仍为1/2 （对于性质3，可采用数学归纳法证明这一点）
所以对于整颗树，要求的值即为每个节点的最大子树深度*2^(n-1).
标签：845,题意,int,题解,Codeforces,ByteRace,逆序,节点,指针 From： https://www.cnblogs.com/edgrass/p/17066135.html