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

这篇具有很好参考价值的文章主要介绍了VP记录:Codeforces Round 873 (Div. 2) A~D1。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

传送门:CF

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

A题:A. Divisible Array

一道构造题.因为需要被下标整除,所以我们不妨直接将每一位的数字赋值成该下标,但是我们发现这样子的总和将会是 ( n + 1 ) ∗ n / 2 (n+1)*n/2 (n+1)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 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] 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 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 ] 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 pos1.我们继续找 a [ i + 1 ] a[i+1] a[i+1]的可放位置数,记为 p o s 2 pos2 pos2.我们会发现存在这样的一个性质,就是a[i]可以放的位置显然a[i+1]也是可以放的,并且a[i]会占用a[i+1]的一个可行位置.所以此时的总贡献就是:
∏ i = 1 n p o s i − ( i − 1 ) \prod\limits_{i=1}^n {pos_i-(i-1)} i=1nposi(i1)
至此本题也就不难解决了

#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 r-l rl

然后我们发现对于一个位置的数字进行排序的花费是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 rl,所以我们没分出一个新的块,我们的贡献就是当前的长度-1.我们将其累加一下就会发现区间的总贡献就是总区间的长度减去块的个数.

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

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

假设当前枚举到的数字比之前的最大值要大,那么此时这个数字比之前的所有数字都要大,这就意味着当前数字目前来说并不需要进行排序,所以我们将其独立作为一个块文章来源地址https://www.toymoban.com/news/detail-449433.html

#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;
}

到了这里,关于VP记录:Codeforces Round 873 (Div. 2) A~D1的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Codeforces Round 882 (Div. 2)

    目录 A. The Man who became a God  题目分析: B. Hamon Odyssey 题目分析: C. Vampiric Powers, anyone? 题目分析:  n个人分成k组,每一组的力量都是 这样的,那么如果分成k组那么就会有k-1个力量不被统计,将力量总和减去前k-1个最大的力量就是最小的结果   将数组分组,每个组内进行按位与

    2024年02月05日
    浏览(51)
  • Codeforces Round 920 (Div. 3)

    Codeforces Round 920 (Div. 3) 题意:随机给出正方形在平面坐标系上的四个顶点的坐标,求正方形的面积,正方形边与xy轴平行。 思路:因为正方形与坐标轴平行,所以找出相同的两x或y坐标即可找到一条边的长度,平方就是面积,注意结果返回整型。 AC code: 题意:给出两个01字符

    2024年01月17日
    浏览(68)
  • Codeforces Round 912 (Div. 2)

    大等于2依据冒泡排序即可排序,因此判断下1即可 对每一个数字找哪一位肯定为0填0其他的填1 从后往前考虑加到当前集合或新立一个集合 从最高位开始考虑能否为1,计算能否时每个数当前位为1

    2024年02月04日
    浏览(45)
  • Codeforces Round 881 (Div. 3)

    给定一个数组,给每个元素涂色。求最大的代价。 代价为每个颜色的代价和。 每个颜色的代价为涂了该颜色的元素的极差。 因为是极差,每个元素要么对答案有正的贡献,要么有负的贡献,要么无贡献。且正负贡献的个数要相同。 因为要最大值,自然就是想有正贡献的是最

    2024年02月09日
    浏览(44)
  • Codeforces Round 867 (Div. 3)

    从所有a[i]+i-1=t的选择种取个max即可 实际上就是取同符号乘积的最大值 找规律,发现结果与边长n的关系是:res = n * (n + 3) - (n - 2) ①当n为奇数时,除了1其他均无解 ②当n为偶数时,我们可以构造一个形如n,1,n - 2,3,...的数列 首先我们可以发现n必定出现在起始位置。如果n不在起

    2024年02月02日
    浏览(49)
  • Codeforces Round 874 (Div. 3)

    用最少的长度为2的字符串按一定规则拼出s。规则是:前一个字符串的尾与后一个字符串的首相同。 统计s中长度为2的不同字符串数量。 给定数组a[n]和b[n],重排b后,令任意|ai−bi|≤k成立(1≤k≤n)数据保证一定有解。 将a和b分别按从小到大的顺序匹配便是最优的,一定能满足

    2024年02月05日
    浏览(38)
  • Codeforces Round 894 (Div. 3)

    签到题 a数组里,大于等于前一个值的a[i]会被写到b里。直接遍历b,如果b[i]比前一个小就在它前面插一个相等的值 计算反过来的长度,判断是否相等就行 对于没有重复口味的集合,能选出的方案是n*(n-1)/2 (从n个里面选2个的组合数)。二分找出需要多少不同口味的冰淇淋,

    2024年02月11日
    浏览(45)
  • Codeforces Round 926 (Div. 2)

    类似于倍投法,就是在一赔一的情况下,第一次压一块钱,每输一次就押注上一次两倍的金额. 假如资金无限的话,这种方法赢的期望为无穷大.原理类似于二进制,不论你输再多次,只要赢一次总额就增加了1.比如 15 二进制1111,前3把一直输,但是只要第4把赢,就一定可以增加 1

    2024年02月20日
    浏览(45)
  • Codeforces Round 868 Div 2

    要求构造一个仅包含 (1) 和 (-1) 的长度为 (n) 的数组 (a) ,使得存在 (k) 个下标对 ((i, j), i j) 满足 (a_i times a_j = 1) 。 当有 (x) 个 (1) , (y) 个 (-1) 时,其满足条件的下标对数量为 (frac{x (x - 1)}{2} + frac{y (y - 1)}{2}) 。 由于 (n) 只有 (100) ,直接枚举 (x) 即可。

    2024年02月01日
    浏览(45)
  • Codeforces Round 866 (Div. 2)

    给出一个仅由_或^组成的字符串,你可以在任意位置添加_或^字符,使得字符串满足: 任意字符要么属于^_^的一部分,要么属于^^的一部分。求最少添加的字符数量。 对于_我们只需处理没有组成^_^的_: ①如果_在首位置且左边没有^则添加^ ②如果_在尾位置且右边没有^则添加

    2023年04月25日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包