首页 > 其他分享 >Codeforces Round #842 (Div. 2)

Codeforces Round #842 (Div. 2)

时间：2023-01-06 22:01:08浏览次数：50  
标签：CI le const 842 int Codeforces Div include define

Preface

唉现在这是是做稍微难点的SB题（指Div2正常场的CD难度）总是要犯病

因此Rating上不去不说，比赛的时候连EF题面都没机会看一眼

这场先是C交上去忘记本机调试的时候把数组开小了挂了一发（本地IDE不能看很大的数组，辣鸡Dev）

然后一个D思路不顺畅，交上去WA了一发后思考了好久才发现原来的判断方法的问题，虽然在结束前两分钟改出来了但是分数已经惨不忍睹了

补题的这场的EF还行的说，顺手就都写掉了（唉又回想起以前OI全盛期的时候刷Div2都是倒着往前做的，现在菜成这个狗样）

A. Greatest Convex

因为\(x!+(x-1)!=(x+1)\times (x-1)!\)，因此直接输出\(k-1\)即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,k;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t) scanf("%d",&k),printf("%d\n",k-1);
	return 0;
}

B. Quick Sort

先直接上结论，找出以\(1\)开头的最长的按顺序出现的\(1,2,\cdots,len\)的长度\(len\)，则剩下的\(n-len\)个位置都必须被操作

证明的话很容易，首先所有在\(1\)之前的数都一定要操作，然后不在这个顺序里的数也必须要被拎出来

至于操作顺序总能找到一个次数最少的，最后答案就是\(\lceil \frac{n-len}{k} \rceil\)

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,k,a[N],pos[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d",&n,&k),i=1;i<=n;++i) scanf("%d",&a[i]),pos[a[i]]=i;
		int len=1; while (len<n&&pos[len]<pos[len+1]) ++len;
		printf("%d\n",(n-len+k-1)/k);
	}
	return 0;
}

C. Elemental Decompress

这种C题一般想到什么思路直接冲一发基本就没问题了，我还傻愣愣地去证做法的正确性，导致写完这题排名已经1000+了

首先判断掉一些显然无解的情况，比如某个数出现了\(3\)次及以上

然后考虑所有出现了两次的数，显然两个串在这对应的位置上必须要出现这个数，至于两个串里对应位置的分配对答案没有影响

那么剩下的就是只出现了一次的数了，我们不妨把它们全部扔到一个串里去，因为这些数之间肯定是能构成排列的（没有重复）

比如样例的第二个情况，在做完上面的两个操作后得到（用.代表不确定的位置）

5 3 4 2 .
. . . . 5

然后我们考虑怎么填上每个串里各自位置的空缺，以上面的例子填上第二个串的空缺为例

我们把第二个串所有没1出现过的数1 2 3 4，依次按对应的大小顺序填到第一个串对应的数的对应位置上

比如填完后第二个串就变成4 2 3 1 5，然后检查一下是否会出现有位置上的数大于第一个串的即可

对于第一个串的空位也是和上面一样的方法，如法炮制即可

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
struct element
{
	int val,id;
	friend inline bool operator < (const element& A,const element& B)
	{
		return  A.val<B.val;
	}
}p[N]; int T,n,cnt,c[N],tp[N],a[N],b[N]; bool va[N],vb[N]; vector <int> t[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&T);T;--T)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) a[i]=b[i]=va[i]=vb[i]=0,t[i].clear();
		for (i=1;i<=n;++i) scanf("%d",&c[i]),t[c[i]].push_back(i);
		bool flag=1; for (i=1;i<=n&&flag;++i) if (t[i].size()>2) flag=0;
		if (!flag) { puts("NO"); continue; }
		for (i=1;i<=n;++i) if (t[i].size()==2)
		a[t[i][0]]=i,b[t[i][1]]=i;
		else if (t[i].size()==1) a[t[i][0]]=i;
		for (i=1;i<=n;++i) va[a[i]]=vb[b[i]]=1,tp[i]=a[i];
		for (cnt=0,i=1;i<=n;++i) if (b[i]) p[++cnt]=(element){b[i],i};
		int lst=1; for (sort(p+1,p+cnt+1),i=1;i<=cnt&&flag;++i)
		{
			while (va[lst]) ++lst; if (lst>p[i].val) flag=0;
			else va[lst]=1,a[p[i].id]=lst;
		}
		for (cnt=0,i=1;i<=n;++i) if (tp[i]) p[++cnt]=(element){tp[i],i};
		lst=1; for (sort(p+1,p+cnt+1),i=1;i<=cnt&&flag;++i)
		{
			while (vb[lst]) ++lst; if (lst>p[i].val) flag=0;
			else vb[lst]=1,b[p[i].id]=lst;
		}
		if (!flag) { puts("NO"); continue; }
		for (puts("YES"),i=1;i<=n;++i)
		printf("%d%c",a[i]," \n"[i==n]);
		for (i=1;i<=n;++i)
		printf("%d%c",b[i]," \n"[i==n]);
	}
	return 0;
}

D. Lucky Permutation

首先考虑如果不是恰好一个逆序对这个限制，而是把整个序列复原有序，操作步数是多少

说到交换以及排列，很容易想到用置换环，具体地，我们把每个位置\(i\)和其上的值\(p_i\)连边，这样就可以得到若干个联通块，其中每个联通块一定是一个简单环

我们很容易发现，对于每一个简单环，需要用\(size-1\)次操作来复原环上的所有元素（每一次交换操作恢复一个位置，最后一次操作恢复两个）

有了这个结论之后我们考虑恰好一个逆序对的条件，不难发现恰有一个逆序对的排列就是把\(1,2,\cdots,n\)的排列的某两个相邻的数交换下得到的

那么我们枚举\(i,i+1\)，考虑交换它们两个之后带来的影响，不难发现其实就是断开原来图中\((i,a_i),(i+1,a_{i+1})\)的边，改连成\((i,a_{i+1}),(i+1,a_i)\)

首先我们发现如果\(i,i+1\)在原来的图中不再一个环内，那么这般操作后这两个环会合并，这样答案就是原来的答案\(+1\)

如果\(i,i+1\)在一个环内，就要视情况讨论，如果可以使得它们所在的环分成两个小的，那么答案就是原来的答案\(-1\)

考虑怎么判断这种情况，我的做法是把环上的点都找出来，按顺序排成一个序列

然后找到其中要删除的两条边，这两条边把原来的环分成了两个部分

考虑新加入的边是在这两部分内部连边还是在两部分之间连边即可，具体的实现当时脑子不清实现的可能有些复杂，不过大意是这样的没问题的说

#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,a[N],fa[N],sz[N],ans,ret,vis[N],num[N]; vector <int> v[N],pt[N];
inline int getfa(CI x)
{
	return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
inline void addedge(CI x,CI y)
{
	v[x].push_back(y); v[y].push_back(x);
}
inline void DFS(vector <int>& p,CI now,CI ct=1)
{
	p.push_back(now); vis[now]=1; num[now]=ct;
	for (int to:v[now]) if (!vis[to]) DFS(p,to,ct+1);
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) sz[i]=vis[i]=num[i]=0,fa[i]=i,v[i].clear();
		for (i=1;i<=n;++i) scanf("%d",&a[i]),fa[getfa(i)]=getfa(a[i]),addedge(i,a[i]);
		for (i=1;i<=n;++i) ++sz[fa[i]=getfa(i)];
		for (ans=1e9,ret=0,i=1;i<=n;++i) if (fa[i]==i) ret+=sz[i]-1,DFS(pt[i],i);
		for (i=1;i<n;++i)
		{
			int cur=ret; if (fa[i]==fa[i+1])
			{
				if (sz[fa[i]]==2) --cur; else
				{
					int S=sz[fa[i]],A=num[i],B=num[a[i]];
					if (A==S&&B!=S-1) B=S+1; if (B==S&&A!=S-1) A=S+1; if (A>B) swap(A,B);
					int C=num[i+1],D=num[a[i+1]];
					if (C==S&&D!=S-1) D=S+1; if (D==S&&C!=S-1) C=S+1; if (C>D) swap(C,D);
					if (A>C) swap(A,C),swap(B,D);
					if (B<=num[i]&&num[i]<=C&&B<=num[a[i+1]]&&num[a[i+1]]<=C) --cur; else
					if (B<=num[i+1]&&num[i+1]<=C&&B<=num[a[i]]&&num[a[i]]<=C) --cur; 
				}
			} else cur=ret+1;
			ans=min(ans,cur);
		}
		printf("%d\n",ans);
	}
	return 0;
}

E. Partial Sorting

知道思路就豁然开朗的数数题，感觉比赛的时候不写D开E可能会更好点

首先我们发现答案的上界为\(3\)，因为不管是怎样的排列，我们都可以通过依次进行操作\(1\)，操作\(2\)，操作\(1\)来使得它有序

证明也很简单，第一次执行操作\(1\)后所有大于\(2n\)的元素一定在\([n+1,3n]\)上了，这样在第二次执行操作\(2\)后所有大于\(2n\)的数都会归位，然后再执行一次操作\(3\)就都有序了

那么我们只要考虑统计出操作次数为\(0,1,2,3\)的排列的个数即可统计答案了

首先是操作次数为\(0\)的排列，其个数\(t0=1\)是显然的

然后是操作次数为\(1\)的排列，记其个数为\(t1\)，我们可以用容斥的思想，先分别考虑以下两种情况：

  • 前\(n\)个元素已经排列好了，只用考虑后面的\(2n\)个元素
  • 后\(n\)个元素已经排列好了，只用考虑前面的\(2n\)个元素

但这样得到的部分会有重复，因此要减去前\(n\)个元素已经排列好且后\(n\)个元素已经排列好的排列数目

而且这样得到的个数是操作次数小于等于\(1\)的排列个数，因此要减去\(t0\)

接下来考虑操作次数为\(2\)的排列个数\(t2\)，还是和上面类似，我们直接先考虑操作次数小于\(2\)的：

  • 所有小于等于\(n\)的元素已经在\([1,2n]\)中了，此时只要先给前\(2n\)个元素排序，这样前\(n\)个数归位后，再给后\(2n\)个数排序即可
  • 所有大于\(2n\)的元素已经在\([2n+1,3n]\)中了，理由同上

然后类似的我们也要容斥掉同时满是上面两种情况的排列的个数，不妨枚举\([n+1,2n]\)内有多少个小于等于\(n\)的数来计算

当然得到的结果要减去\(t0+t1\)才是操作次数等于\(2\)的方案数

最后操作次数等于\(3\)的方案数就直接\(t3=(3n)!-t0-t1-t2\)即可，总复杂度\(O(n)\)

#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=3000005;
int n,mod,fact[N],ifact[N],t0,t1,t2,t3;
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline int sum(CI x,CI y)
{
	return x+y>=mod?x+y-mod:x+y;
}
inline int sub(CI x,CI y)
{
	return x-y<0?x-y+mod:x-y;
}
inline void init(CI n)
{
	RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
	for (ifact[n]=quick_pow(fact[n]),i=n-1;~i;--i) ifact[i]=1LL*ifact[i+1]*(i+1)%mod;
}
inline int C(CI n,CI m)
{
	return 1LL*fact[n]*ifact[m]%mod*ifact[n-m]%mod;
}
int main()
{
	scanf("%d%d",&n,&mod); init(3*n); t0=1;
	t1=sub(sub(2LL*fact[2*n]%mod,fact[n]),t0);
	t2=2LL*C(2*n,n)*fact[n]%mod*fact[2*n]%mod;
	for (RI i=0;i<=n;++i)
	t2=sub(t2,1LL*C(n,i)*C(n,n-i)%mod*fact[n]%mod*C(2*n-i,n)%mod*fact[n]%mod*fact[n]%mod);
	t2=sub(t2,sum(t0,t1));
	t3=sub(fact[3*n],sum(sum(t0,t1),t2));
	return printf("%d",(1LL*t1+2LL*t2+3LL*t3)%mod),0;
}

F. Wonderful Jump

感觉很像那种经典的决策单调性优化DP的模型，但是之前是区间和乘上距离差的平方，这里改成了区间最小值一时不知所措

看了Tutorial才发现\(a_i\le n\)的深意所在，妙哉妙哉

考虑设\(f_i\)表示从\(1\)跳到\(i\)的最小代价，考虑\(i\)从\(j\)转移来，首先有两个关键结论要注意到：

  • \(\min_\limits{j\le k\le i} a_k\)等于\(a_i\)或\(a_j\)，否则我们可以找到\((j,i)\)中最小值的位置\(p\)，从\(j\)转移到\(p\)再从\(p\)转移到\(i\)一定可以使得答案更优
  • 当满足\(\min_\limits{j\le k\le i} a_k\times (i-j)^2>n\times (i-j)\)时，一定不可能从\(j\)转移到\(i\)，因为此时一步步转移的代价更小

考虑第二个结论的意义所在，我们化简以下会发现此时\(i-j\le \frac{n}{\min_\limits{j\le k\le i} a_k}\)，那么我们发现当\(\min_\limits{j\le k\le i} a_k\)较大的时候\(j\)的移动范围就很小了

因此很容易想到根号分治，我们考虑根据\(a_i\)和\(S=\sqrt n\)的大小情况来讨论：

  • 当\(a_i\ge S\)时，\(i-j\le S\)，因此可以直接\(O(S)\)暴力转移
  • 当\(a_i\le S\)时，分\(a_i\)为最小值和\(a_j\)为最小值的情况讨论：
    • 若\(a_j\)为最小值，我们可以直接用单调栈来维护前面的转移点，这样的转移点不会超过\(O(S)\)个
    • 若\(a_i\)为最小值，我们可以直接暴力往前枚举，一旦遇到\(a_j\le a_i\)就停下，这样的均摊复杂度是\(O(nS)\)的

关于均摊复杂度的计算其实也很简单，我们考虑每个位置和每个小于\(S\)的值，每个位置向同一个值最多转移一次

比如存在\(a_i,a_j,a_k\)，其中\(a_i<a_j=a_k\)，那么\(i\)只会向\(j\)转移而不会向\(k\)转移，因此复杂度均摊下来是对的

总复杂度就是\(O(nS)=O(n\sqrt n)\)

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=400005,S=650;
int n,a[N],stk[N],top; long long f[N];
int main()
{
	RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (stk[top=1]=1,i=2;i<=n;++i)
	{
		int mi=a[i]; for (f[i]=1e18,j=i-1;j>=1&&i-j<=S;--j)
		mi=min(mi,a[j]),f[i]=min(f[i],f[j]+1LL*mi*(i-j)*(i-j));
		for (j=1;j<=top;++j)
		f[i]=min(f[i],f[stk[j]]+1LL*a[stk[j]]*(i-stk[j])*(i-stk[j]));
		if (a[i]<=S)
		{
			for (j=i-1;j>=1;--j)
			if (f[i]=min(f[i],f[j]+1LL*a[i]*(i-j)*(i-j)),a[j]<=a[i]) break;
			while (top&&a[stk[top]]>=a[i]) --top; stk[++top]=i;
		}
	}
	for (i=1;i<=n;++i) printf("%lld ",f[i]);
	return 0;
}

Postscript

小掉了13pts，下场争取加把劲

标签：CI,le,const,842,int,Codeforces,Div,include,define
From： https://www.cnblogs.com/cjjsb/p/17031688.html

相关文章

  • Codeforces Round 842
    目录写在前面ABCDE写在最后写在前面仁王真好玩大太刀真好玩下辈子我还要玩大太刀[](https://pic.imgdb.cn/item/63b7fdb4be43e0d30ec2dccd.jpg)顺带吐槽一下，这什么排......
  • 《Quantifying the effects of environment and population diversity in multi-agent
    量化多智能体强化学习中环境和种群多样性的影响总结：在多种实验环境下评估多智能体强化学习受到环境多样性以及智能体多样性的影响，主要是泛化能力实验过程主要是通过改......
  • Codeforces Round #842 (Div. 2)
    题目链接A核心思路：样例模拟出答案。#define_CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstring>#include<algorithm>#include<vector>#include<bits/std......
  • Codeforces Round #842 (Div. 2) A-D
    比赛链接A题意给一个数\(k\)找到最大的\(x\)，满足\(1\leqx<k\)且\(x!+(x-1)!\)是\(k\)的倍数。题解知识点：数学。猜测\(x=k-1\)，证明\((k-1)!+(k-......
  • 1.6 vp Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!)
    A-AddPlusMinusSign题意：给出01字符串，可以在每两个字符中间任意添加‘+’，‘-’。最后要使表达式的绝对值最小思路：设表达式的值为\(cnt\)，若当前\(cnt\)大于\(0\)，不管......
  • Codeforces Round #842 (Div. 2) A-C, 补D
    A.GreatestConvex题意：给定一个k，求一个小于k的数x，使得x!+(x-1)!是k的倍数分析：题目已经给出提示：y!=y⋅(y−1)!，输出n-1cout<<n-1<<endl......
  • Codeforces Round #842 (Div. 2) A-D题解
    比赛链接A、GreatestConvex非常的简单。根据样例直接猜是输出\(n-1\).上一个\(Python\)代码。T=int(input())whileT>0:T-=1n=int(input())......
  • B. Quick Sort【Codeforces Round #842 (Div. 2)】
    B.QuickSortYouaregivenapermutation【排列】†\(p\)oflength\(n\)andapositiveinteger\(k≤n\).Inoneoperation,you:Choose\(k\)distinctelement......
  • Codeforces Contest 1616
    A.IntegerDiversity直接用个map贪心，如果有相同的就反向即可。B.MirrorintheString这道题洛谷的翻译锅了，所以建议去看原题。考虑这样一个字符串baacc，那么答案显......
  • 「Codeforces」寒假训练 2023 #2
    A.YetAnotherPalindromeProblem原题链接#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e5+10;intt;intn;inta[N];i......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99