windows7PHP网站建设,西安直播网站开发,电商网站开发公司杭州,网站建设费预付定金什么科目传送门:CF
前题提要:因为本场比赛的D题让我十分难受.刚开始以为 r − l 1 r-l1 r−l1与 r − l r-l r−l应该没什么不同.但是做的时候发现假设是 r − l 1 r-l1 r−l1的话我们可以使用线段树来维护,但是 r − l r-l r−l就让线段树维护的难度大大增加,这导致我十分烦躁,所以…传送门:CF
前题提要:因为本场比赛的D题让我十分难受.刚开始以为 r − l 1 r-l1 r−l1与 r − l r-l r−l应该没什么不同.但是做的时候发现假设是 r − l 1 r-l1 r−l1的话我们可以使用线段树来维护,但是 r − l r-l r−l就让线段树维护的难度大大增加,这导致我十分烦躁,所以就不想做本场比赛的D2了
A题:A. Divisible Array
一道构造题.因为需要被下标整除,所以我们不妨直接将每一位的数字赋值成该下标,但是我们发现这样子的总和将会是 ( n 1 ) ∗ n / 2 (n1)*n/2 (n1)∗n/2这样不一定被 n n n整除,但是此时我们只要将整体乘一个 2 2 2就可以了.
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define maxn 1000000
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int main() {int Tread();while(T--) {int nread();for(int i1;in;i) {cout2*i ;}coutendl;}return 0;
}B题:B. Permutation Swap
把玩一下题意之后不难发现.我们的 a [ i ] a[i] a[i]最终是要移动到下标为 a [ i ] a[i] a[i]的位置.那么我们需要移动的总距离就是 a b s ( a [ i ] − i ) abs(a[i]-i) abs(a[i]−i).诶,此时我们想一下有多少种 k k k将会满足此次移动,我们会发现 k k k需要满足是 a b s ( a [ i ] − i ) abs(a[i]-i) abs(a[i]−i)的因子才行. 所以此时我们只要对所有的 a b s ( a [ i ] − i ) abs(a[i]-i) abs(a[i]−i)取一个 g c d gcd gcd就行了. 但是有一个细节需要注意,就是当我们的 a [ i ] a[i] a[i]就处于 a [ i ] a[i] a[i]的位置的时候,此时任意的 k k k对于该数字都是满足的,所以此时我们不需要管这个数字即可
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define maxn 1000000
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int gcd(int a,int b) {if(a%b0) return b;else return gcd(b,a%b);
}
int a[maxn];
int main() {int Tread();while(T--) {int nread();for(int i1;in;i) a[i]read();vectorintb;for(int i1;in;i) {int numabs(a[i]-i);if(num0) continue;else b.push_back(num);}int ansb[0];for(int i1;ib.size();i) {ansgcd(ans,b[i]);}coutansendl;}return 0;
}C. Counting Orders
考虑对两个数组进行一个排序(从小到大).然后此时我们的两个数组应该满足所有的 a [ i ] b [ i ] a[i]b[i] a[i]b[i].不然我们的答案就是0.下面简单证明一下这个结论: 假设此时我们的答案不为0.那么我们将需要处理一下 a [ i ] b [ i ] a[i]b[i] a[i]b[i]的那一个数字.我们发现想要处理这个数字,我们就需要将后面的 i i i后面的数字换到 i i i位置.那么也就是将 i i i换到后面去才能满足题意.但是我们发现两个数组都是单调增的.此时我们的 a [ i ] a[i] a[i]已经偏小了,换到后面去不是更为偏小,所以是不可能满足题意的(还有一种情况是先与i前面的换,再将前面的换到后面,这种情况显然也是不行的) 那么此时我们考虑在这个的基础上算出最后的答案.考虑对于每一位的 a [ i ] a[i] a[i],我们先算出他能放在哪些位置,不难发现可以在b数组中用二分找到第一个大于 a [ i ] a[i] a[i]的位置,不妨记为 p o s 1 pos1 pos1(注意,b数组是单调的).那么此时我们可以放的位置显然就是 p o s − 1 pos-1 pos−1.我们继续找 a [ i 1 ] a[i1] a[i1]的可放位置数,记为 p o s 2 pos2 pos2.我们会发现存在这样的一个性质,就是a[i]可以放的位置显然a[i1]也是可以放的,并且a[i]会占用a[i1]的一个可行位置.所以此时的总贡献就是: ∏ i 1 n p o s i − ( i − 1 ) \prod\limits_{i1}^n {pos_i-(i-1)} i1∏nposi−(i−1) 至此本题也就不难解决了
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define maxn 1000000
#define int long long
const int mod1e97;
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int n;vectorinta,b;
signed main() {int Tread();while(T--) {nread();a.clear();b.clear();for(int i1;in;i) {int numread();a.push_back(num);}for(int i1;in;i) {int numread();b.push_back(num);}sort(a.begin(),a.end());sort(b.begin(),b.end());int flag0;for(int i0;in;i) {if(a[i]b[i]) {flag1;break;} }if(flag) {cout0endl;continue;}int ans1;for(int i0;in;i) {int poslower_bound(b.begin(),b.end(),a[i])-b.begin();ansans*(pos-i)%mod;}coutansendl;} return 0;
}D1:Range Sorting (Easy Version)
首先需要注意的是对于一个区间的花费是 r − l r-l r−l
然后我们发现对于一个位置的数字进行排序的花费是0.这就意味对于不需要排序的所有数字,我们也可以将其看做为对单个位置的数字进行排序!!. 然后我们考虑对于一个区间 [ l , r ] [l,r] [l,r],我们将其按照排序的区间来将其分块,举一个栗子: 1 , 2 , 4 , 3 1,2,4,3 1,2,4,3这样的区间,我们就将其分块为 1 2 4 , 3 1\;\;2\;\;4,3 124,3这三个区间,此时我们发现这样做的总贡献就是区间的长度减去块的个数!!,这个很好证明.因为我们的花费是 r − l r-l r−l,所以我们没分出一个新的块,我们的贡献就是当前的长度-1.我们将其累加一下就会发现区间的总贡献就是总区间的长度减去块的个数.
当然对于上述的结论,我们需要一个前题,“就是对于每一个排序区间,它们都不是相交的,也就是进行不相交的进行排序才是最优的”,这个不难证明,限于篇幅,此处就不在赘述了
所以我们现在的问题就变成了计算一个区间中的块的个数.我们发现每一个块内的数字显然是单调递减的(这个很重要).考虑使用单调栈来维护每一个块的最大值(维护的栈是单调增的,这个也很重要).假设当前枚举到了区间中的 a [ i ] a[i] a[i],我们此时的值小于前面的数字,我们就需要将 a [ i ] a[i] a[i]换到之前的位置,那么此时需要换到哪一个位置呢.我们发现当前数字假设比块的最大值要小,并且因为我们块中的数字是呈单调减排列的,所以此时我们的该数字应该是放在这个块前面才行,也就是说此时的排序区间的左端点要管到最大值的那一个位置.所以此时这个数字很显然就可以合并到之前的那一个块中.我们对此进行合并即可.
假设当前枚举到的数字比之前的最大值要大,那么此时这个数字比之前的所有数字都要大,这就意味着当前数字目前来说并不需要进行排序,所以我们将其独立作为一个块
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define maxn 1000000
#define int long long
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int a[maxn];
signed main() {int Tread();while(T--) {int nread();for(int i1;in;i) a[i]read();int ans0;for(int l1;ln;l) {stackints;for(int len1;llen-1n;len) {int rllen-1;int flag1;int maxxa[r];while(!s.empty()a[r]s.top()) {if(flag1){maxxs.top();flag0;}s.pop();}if(flag0) s.push(maxx);else s.push(a[r]);anslen-s.size();}}coutansendl;}return 0;
}
