VP记录:Codeforces Round 873 (Div. 2) A~D1

传送门:CF

前题提要:因为本场比赛的D题让我十分难受.刚开始以为$r-l+1$与$r-l$应该没什么不同.但是做的时候发现假设是$r-l+1$的话我们可以使用线段树来维护,但是$r-l$就让线段树维护的难度大大增加,这导致我十分烦躁,所以就不想做本场比赛的D2了

A题:A. Divisible Array

一道构造题.因为需要被下标整除,所以我们不妨直接将每一位的数字赋值成该下标,但是我们发现这样子的总和将会是$(n+1)\ast n/2$这样不一定被$n$整除,但是此时我们只要将整体乘一个$2$就可以了.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int main() {int T=read();while(T--) {int n=read();for(int i=1;i<=n;i++) {cout<<2*i<<" ";}cout<<endl;}return 0;
}

B题:B. Permutation Swap

把玩一下题意之后不难发现.我们的$a[i]$最终是要移动到下标为$a[i]$的位置.那么我们需要移动的总距离就是$abs(a[i]-i)$.诶,此时我们想一下有多少种$k$将会满足此次移动,我们会发现$k$需要满足是$abs(a[i]-i)$的因子才行.
所以此时我们只要对所有的$abs(a[i]-i)$取一个$gcd$就行了.
但是有一个细节需要注意,就是当我们的$a[i]$就处于$a[i]$的位置的时候,此时任意的$k$对于该数字都是满足的,所以此时我们不需要管这个数字即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int gcd(int a,int b) {if(a%b==0) return b;else return gcd(b,a%b);
}
int a[maxn];
int main() {int T=read();while(T--) {int n=read();for(int i=1;i<=n;i++) a[i]=read();vector<int>b;for(int i=1;i<=n;i++) {int num=abs(a[i]-i);if(num==0) continue;else b.push_back(num);}int ans=b[0];for(int i=1;i<b.size();i++) {ans=gcd(ans,b[i]);}cout<<ans<<endl;}return 0;
}

C. Counting Orders

考虑对两个数组进行一个排序(从小到大).然后此时我们的两个数组应该满足所有的$a[i]<b[i]$.不然我们的答案就是0.下面简单证明一下这个结论:
假设此时我们的答案不为0.那么我们将需要处理一下$a[i]>b[i]$的那一个数字.我们发现想要处理这个数字,我们就需要将后面的$i$后面的数字换到$i$位置.那么也就是将$i$换到后面去才能满足题意.但是我们发现两个数组都是单调增的.此时我们的$a[i]$已经偏小了,换到后面去不是更为偏小,所以是不可能满足题意的(还有一种情况是先与i前面的换,再将前面的换到后面,这种情况显然也是不行的)
那么此时我们考虑在这个的基础上算出最后的答案.考虑对于每一位的$a[i]$,我们先算出他能放在哪些位置,不难发现可以在b数组中用二分找到第一个大于$a[i]$的位置,不妨记为$pos1$(注意,b数组是单调的).那么此时我们可以放的位置显然就是$pos-1$.我们继续找$a[i+1]$的可放位置数,记为$pos2$.我们会发现存在这样的一个性质,就是a[i]可以放的位置显然a[i+1]也是可以放的,并且a[i]会占用a[i+1]的一个可行位置.所以此时的总贡献就是:
$$\prod _{i=1}^{n}po{s}_i-(i-1)$$
至此本题也就不难解决了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
#define int long long
const int mod=1e9+7;
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int n;vector<int>a,b;
signed main() {int T=read();while(T--) {n=read();a.clear();b.clear();for(int i=1;i<=n;i++) {int num=read();a.push_back(num);}for(int i=1;i<=n;i++) {int num=read();b.push_back(num);}sort(a.begin(),a.end());sort(b.begin(),b.end());int flag=0;for(int i=0;i<n;i++) {if(a[i]<=b[i]) {flag=1;break;} }if(flag) {cout<<0<<endl;continue;}int ans=1;for(int i=0;i<n;i++) {int pos=lower_bound(b.begin(),b.end(),a[i])-b.begin();ans=ans*(pos-i)%mod;}cout<<ans<<endl;}	return 0;
}

D1:Range Sorting (Easy Version)

首先需要注意的是对于一个区间的花费是$r-l$

然后我们发现对于一个位置的数字进行排序的花费是0.这就意味对于不需要排序的所有数字,我们也可以将其看做为对单个位置的数字进行排序!!.
然后我们考虑对于一个区间$[l,r]$,我们将其按照排序的区间来将其分块,举一个栗子:
$1,2,4,3$这样的区间,我们就将其分块为$124,3$这三个区间,此时我们发现这样做的总贡献就是区间的长度减去块的个数!!,这个很好证明.因为我们的花费是$r-l$,所以我们没分出一个新的块,我们的贡献就是当前的长度-1.我们将其累加一下就会发现区间的总贡献就是总区间的长度减去块的个数.

当然对于上述的结论,我们需要一个前题,“就是对于每一个排序区间,它们都不是相交的,也就是进行不相交的进行排序才是最优的”,这个不难证明,限于篇幅,此处就不在赘述了

所以我们现在的问题就变成了计算一个区间中的块的个数.我们发现每一个块内的数字显然是单调递减的(这个很重要).考虑使用单调栈来维护每一个块的最大值(维护的栈是单调增的,这个也很重要).假设当前枚举到了区间中的$a[i]$,我们此时的值小于前面的数字,我们就需要将$a[i]$换到之前的位置,那么此时需要换到哪一个位置呢.我们发现当前数字假设比块的最大值要小,并且因为我们块中的数字是呈单调减排列的,所以此时我们的该数字应该是放在这个块前面才行,也就是说此时的排序区间的左端点要管到最大值的那一个位置.所以此时这个数字很显然就可以合并到之前的那一个块中.我们对此进行合并即可.

假设当前枚举到的数字比之前的最大值要大,那么此时这个数字比之前的所有数字都要大,这就意味着当前数字目前来说并不需要进行排序,所以我们将其独立作为一个块

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
#define int long long
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int a[maxn];
signed main() {int T=read();while(T--) {int n=read();for(int i=1;i<=n;i++) a[i]=read();int ans=0;for(int l=1;l<=n;l++) {stack<int>s;for(int len=1;l+len-1<=n;len++) {int r=l+len-1;int flag=1;int maxx=a[r];while(!s.empty()&&a[r]<s.top()) {if(flag==1){maxx=s.top();flag=0;}s.pop();}if(flag==0) s.push(maxx);else s.push(a[r]);ans+=len-s.size();}}cout<<ans<<endl;}return 0;
}