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

Codeforces Round 873 (Div. 2)

时间：2023-05-18 19:01:08浏览次数：33  
标签：CI const int 873 Codeforces -- Div include define

Preface

补题，这场本来周日晚上打算现场打的

但一来第二天要上课怕熬太晚影响早上的微积分和电分，二来那天晚上开了DP专题然后就在手速抢一血

过程中被两道DFS搞红温了，本来打CF的计划也咕咕咕了

今天差不多想起来好久没做CF了赶紧补一场

看了下自己补题的时候2h也才堪堪做完D1，虽然后面上大物课的时候想出了E的做法，不过真到比赛时估计也是一眼都不会看的说

感觉现在切2000左右的题的速度还是太慢太慢，而且经常有想法但是容易写假就很难受

A. Divisible Array

SB题，令\(a_i=2i\)，总和为\(n\times(n+1)\)显然为\(n\)的倍数

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=205;
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) printf("%d%c",2*i," \n"[i==n]);
	}
	return 0;
}

B. Permutation Swap

这题好像就最近的某一场出过思想基本一样的东西的说

考虑令\(t_i=|i-p_i|\)，不难发现如果可以把\(i\)换到对应的位置则一定有\(k|t_i\)

因此答案就是所有\(t_i\)的\(\gcd\)，当时写的时候闹抽了还写了暴力对每个\(t_i\)分解质因数，属实智障了

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,a[N],c[N],tot;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),tot=0,i=1;i<=n;++i) c[i]=0;
		auto resolve=[&](CI x)
		{
			for (RI i=1;i*i<=x;++i) if (x%i==0)
			if (++c[i],i!=x/i) ++c[x/i];
		};
		for (i=1;i<=n;++i) scanf("%d",&a[i]),tot+=abs(a[i]-i)!=0,resolve(abs(a[i]-i));
		for (i=n;i>=1;--i) if (c[i]==tot) { printf("%d\n",i); break; }
	}
	return 0;
}

C. Counting Orders

这场的ABC水的一逼啊，10min就全切了

显然我们从大到小考虑\(b_i\)，求出大于\(b_i\)且未被使用的\(a_j\)的个数，然后累乘起来即可

把\(a,b\)都排序后，two pointers即可

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,mod=1e9+7;
int t,n,a[N],b[N],ans;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d",&n),ans=1,i=1;i<=n;++i) scanf("%d",&a[i]);
		for (i=1;i<=n;++i) scanf("%d",&b[i]); sort(a+1,a+n+1); sort(b+1,b+n+1);
		for (i=j=n;i>=1;--i)
		{
			while (j>=1&&a[j]>b[i]) --j; ans=1LL*ans*(n-j-(n-i))%mod;
		}
		printf("%d\n",ans);
	}
	return 0;
}

D1. Range Sorting (Easy Version)

刚开始从区间DP入手然后其实已经想出针对D2的关键转化了，结果还是拘泥于DP的形式没有看到本质的东西

首先很容易想到设\(f_{l,r}\)表示\([l,r]\)的答案，转移的话就是枚举一个\(k\)，满足\(\max_\limits{l\le i\le k} a_i<\min_\limits{k<j\le r} a_j\)，则有\(f_{l,r}=\max(f_{l,k}+f_{k+1,r})\)

然后对着样例手玩一下就会发现我们只要找到某个分界点然后直接转移一定不会更劣，因为能划分区间就尽量划分即可

因此现在问题就是怎么对每个区间求出符合上面式子的分界点\(k\)

可以先枚举\(a_k\)，然后双指针统计合法的左右区间的取法即可，但是这里我傻逼了还是以为一定要具体的求出所有的转移点信息，写了个\(O(n^2\log n)\)的东西结果爆内存了

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=5005;
struct Data
{
	int l,r,v;
	inline Data(CI L=0,CI R=0,CI V=0)
	{
		l=L; r=R; v=V;
	}
	friend inline bool operator < (const Data& A,const Data& B)
	{
		return A.l<B.l;
	}
}; vector <Data> s[N]; int t,n,a[N],f[N][N],pos[N][N],mx[N],mi[N];
inline int DP(CI l,CI r)
{
	if (l>=r) return 0; if (~f[l][r]) return f[l][r];
	return f[l][r]=~pos[l][r]?DP(l,pos[l][r])+DP(pos[l][r]+1,r):r-l;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		for (i=1;i<=n;++i) for (s[i].clear(),j=1;j<=n;++j) f[i][j]=pos[i][j]=-1;
		for (i=1;i<n;++i)
		{
			for (mx[i]=a[i],j=i-1;j>=1;--j) mx[j]=max(mx[j+1],a[j]);
			for (mi[i+1]=a[i+1],j=i+2;j<=n;++j) mi[j]=min(mi[j-1],a[j]);
			RI l=i,r=n; for (;l>=1;--l)
			{
				while (r>=i+1&&mx[l]>mi[r]) --r;
				if (r>=i+1) s[l].push_back(Data(i+1,r,i));
			}
		}
		for (i=1;i<n;++i)
		{
			sort(s[i].begin(),s[i].end()); int lst=0;
			for (auto [l,r,v]:s[i])
			{
				for (j=max(l,lst+1);j<=r;++j) pos[i][j]=v; lst=max(lst,r);
			}
		}
		//for (i=1;i<=n;++i) for (j=i;j<=n;++j) printf("l=%d r=%d : %d\n",i,j,pos[i][j]);
		long long ret=0; for (i=1;i<=n;++i) for (j=i;j<=n;++j) ret+=DP(i,j);
		printf("%lld\n",ret);
	}
	return 0;
}

后面仔细一想DP个狗屁东西，显然只要有一对三元组\((l,r,k)\)满足上面的限制，答案就可以减\(1\)，因此直接算贡献即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=5005;
int t,n,a[N],mx[N],mi[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		long long ret=0; for (i=1;i<=n;++i) for (j=i;j<=n;++j) ret+=j-i;
		for (i=1;i<n;++i)
		{
			for (mx[i]=a[i],j=i-1;j>=1;--j) mx[j]=max(mx[j+1],a[j]);
			for (mi[i+1]=a[i+1],j=i+2;j<=n;++j) mi[j]=min(mi[j-1],a[j]);
			RI l=i,r=n; for (;l>=1;--l)
			{
				while (r>=i+1&&mx[l]>mi[r]) --r;
				if (r>=i+1) ret-=r-(i+1)+1;
			}
		}
		printf("%lld\n",ret);
	}
	return 0;
}

当然其实D1还有另一种思路的单调栈做法，就是枚举左端点，然后考虑在右边加入元素的过程中

如果新加入的数比之前都大，那么它就自成一段，否则找到它前面大于它的位置合并贡献即可

可以用一个单调栈来维护这个过程，不过这个反而不好优化到正解的说

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=5005;
int t,n,a[N],stk[N],top;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		long long ret=0; for (i=1;i<=n;++i)	for (top=0,j=i;j<=n;++j)
		{
			int cur=a[j]; while (top&&stk[top]>a[j]) cur=max(cur,stk[top--]);
			stk[++top]=cur; ret+=j-i+1-top;
		}
		printf("%lld\n",ret);
	}
	return 0;
}

D2. Range Sorting (Hard Version)

考虑上面的三元组的个数如何统计，这里看了Tutorial才知道可以这样搞，感觉有点玄妙的说

考虑枚举\(\min_\limits{k<j\le r} a_j\)的值\(a_i\)，然后可以用单调栈求出它左右第一个小于它的位置，记为\(x,y\)，这样右端点的取法就确定了

然后考虑此时左端点的取值范围，设\(a_t\)为\(x\)之前的第一个大于\(a_i\)的数，显然此时\(l\)不能取\(\le t\)的值

那么对答案的贡献就是\((x-t)\times (y-i)\)，而找\(t\)的过程可以写一个类似于ST表的倍增

总复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=300005;
int t,n,a[N],mx[N][20],stk[N],top,L[N],R[N]; long long ans;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d",&n),ans=0,i=1;i<=n;++i)
		scanf("%d",&a[i]),mx[i][0]=a[i],ans+=1LL*i*(i-1)/2LL;
		for (j=1;(1<<j)<=n;++j) for (i=n;i-(1<<j)+1>=1;--i)
		mx[i][j]=max(mx[i][j-1],mx[i-(1<<j-1)][j-1]);
		for (stk[top=0]=0,i=1;i<=n;++i)
		{
			while (top&&a[stk[top]]>a[i]) --top;
			L[i]=stk[top]; stk[++top]=i;
		}
		for (stk[top=0]=n+1,i=n;i>=1;--i)
		{
			while (top&&a[stk[top]]>a[i]) --top;
			R[i]=stk[top]; stk[++top]=i;
		}
		for (i=1;i<=n;++i)
		{
			int pos=L[i]; for (j=19;~j;--j)
			if (pos-(1<<j)+1>=1&&mx[pos][j]<a[i]) pos-=(1<<j);
			ans-=1LL*(L[i]-pos)*(R[i]-i);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

E. Palindrome Partition

不是这题的思路怎么和D题一个模子里出来的，都是只有一个转移点的区间DP

首先还是很容易想到设\(f_{l,r}\)表示\([l,r]\)的答案，但是这题有一个很显然的贪心性质，我们找到最小的\(k\in[l,r]\)满足\([l,k]\)是even palindrome的，则可以直接转移\(f_{l,r}=f_{k,r}+1\)

因此可以直接改写状态，\(f_i\)表示以\(i\)开头的子串中even palindrome的个数，设它的转移点为\(pos_i\)，则\(f_i=f_{pos_i}+1\)

那么现在的问题就是怎么对每个位置求出其转移点，不难想到先用Manacher求出以\(i\)为中心的最大回文半径\(r_i\)

显然\(i\)能影响的就是\([i-r_i+1,i]\)这段区间的\(pos\)，只要把区间内的\(pos\)向\(i\)取\(\min\)即可

当然实现起来我们不需要写类似于吉司机线段树这样的东西，直接从大到小枚举\(i\)，这样相当于每次做区间赋值即可，直接用线段树即可解决

总复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=500005;
int t,n,f[N]; char s[N];
namespace Manacher
{
	char ns[N<<1]; int r[N<<1],len,pos,mx;
	inline void expand(char *s)
	{
		ns[0]='#'; ns[len=1]='$'; pos=mx=0;
		for (RI i=1;i<=n;++i) ns[++len]=s[i],ns[++len]='$'; ns[len+1]='%';
	}
	inline void solve(char *s)
	{
		expand(s); for (RI i=1;i<=len;++i)
		{
			if (i<mx) r[i]=min(r[2*pos-i],mx-i); else r[i]=1;
			while (ns[i-r[i]]==ns[i+r[i]]) ++r[i];
			if (i+r[i]>mx) mx=i+r[i],pos=i;
		}
	}
};
using namespace Manacher;
class Segment_Tree
{
	private:
		struct segment
		{
			int val,tag;
		}node[N<<2];	
		#define V(x) node[x].val
		#define T(x) node[x].tag
		#define TN CI now=1,CI l=1,CI r=n
		#define LS now<<1,l,mid
		#define RS now<<1|1,mid+1,r
		inline void apply(CI now,CI mv)
		{
			V(now)=mv; T(now)=mv;
		}
		inline void pushdown(CI now)
		{
			if (T(now)) apply(now<<1,T(now)),apply(now<<1|1,T(now)),T(now)=0;
		}
	public:
		inline void build(TN)
		{
			V(now)=-1; T(now)=0; if (l==r) return; int mid=l+r>>1; build(LS); build(RS);
		}
		inline void modify(CI beg,CI end,CI mv,TN)
		{
			if (beg<=l&&r<=end) return apply(now,mv); int mid=l+r>>1; pushdown(now);
			if (beg<=mid) modify(beg,end,mv,LS); if (end>mid) modify(beg,end,mv,RS);
		}
		inline int query(CI pos,TN)
		{
			if (l==r) return V(now); int mid=l+r>>1; pushdown(now);
			if (pos<=mid) return query(pos,LS); else return query(pos,RS);
		}
		#undef V
		#undef T
		#undef TN
		#undef LS
		#undef RS
}SEG;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%s",&n,s+1); solve(s);
		RI i; for (SEG.build(),i=n-1;i>=1;--i)
		if (r[2*i+1]=(r[2*i+1]-1)/2) SEG.modify(i-r[2*i+1]+1,i,i);
		long long ans=0; for (f[n+1]=0,i=n;i>=1;--i)
		{
			int pos=SEG.query(i); if (!~pos) f[i]=0;
			else f[i]=f[2*pos-i+2]+1; ans+=f[i];
		}
		printf("%lld\n",ans);
	}
	return 0;
}

Postscript

补场CF放松下，滚回去写DP专题了qwq

标签：CI,const,int,873,Codeforces,--,Div,include,define
From： https://www.cnblogs.com/cjjsb/p/17413031.html

相关文章

  • Codeforces Round 703 (Div. 2) A-D
    CodeforcesRound703(Div.2) A.ShiftingStacksinta[N];voidsolve(){intn=read(),ans=1;for(inti=1;i<=n;i++)a[i]=read();intrest=0,last=-1;for(inti=1;i<=n;i++){a[i]+=rest;rest=a[i]-last-1;last++......
  • Codeforces Round 868 (Div. 2) A-D
    CodeforcesRound868(Div.2) A.A-characteristicintfac[N];map<int,int>mp;voidinit(){fac[1]=0;mp[0]=1;for(inti=2;i<N;i++){fac[i]=fac[i-1]+(i-1);mp[fac[i]]=i;}}voidsolve(){intn=read(),k=rea......
  • Codeforces Round 873 (Div. 2)
    CodeforcesRound873(Div.2)链接CodeforcesRound873(Div.2)A题打印2-n并且计算总和,然后找到严格大于sum的n的倍数记为x,然后用这个x减去sum得到a.然后先打印a然后再打印2-n#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include......
  • Codeforces Round 767 (Div. 1) E. Groceries in Meteor Town (Kruskal重构树 + 线段
    传送门  出现最大路径权值就应该联想到克鲁斯卡尔重构树，我们对于克鲁斯卡尔重构树求一遍dfs序，维护所有白色点的最大最小dfn（包括出发点），求出最大最小dfn的最近公共祖先既是答案。注意需要特判一下除了本身以外没有白色点情况。#include<bits/stdc++.h>intn,m;constintN......
  • Codeforces Round 873 A~E
    CodeforcesRound873(Div.1）A.CountingOrders对于每个\(a_i\)，可以计算出\(c_i\)表示有多少个\(b_j\lta_i\)。那么第\(i\)个人就有\(c_i\)种可能的位置。注意到如果将\(a\)升序排序，则能放的位置集合从前往后是包含的关系。所以将\(a\)排序（等价于将\(c\)排序......
  • DIV 随着滚动条 移动
    <!DOCTYPEhtmlPUBLIC"-//W3C//DTDXHTML1.0Transitional//EN""http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><htmlxmlns="http://www.w3.org/1999/xhtml"><HEAD><TITLE>codeby：haiw......
  • Educational Codeforces Round 148 (Rated for Div. 2) A-D2
    EducationalCodeforcesRound148(RatedforDiv.2) A.NewPalindromemap<int,int>mp;voidsolve(){strings;mp.clear();cin>>s;for(inti=0;i<s.size()/2;i++){mp[s[i]]++;}puts(mp.size()>=2?"YES......
  • CodeForces 1827 D Two Centroids
    洛谷传送门CF传送门考虑固定一个重心，设\(k\)为重心最大子树大小，答案为\(n-2k\)。构造方法是往最大的子树塞叶子。树的重心有一个很好的性质，就是加一个叶子，重心最多移动一条边的距离。简单证一下，设重心为\(x\)，往儿子\(u\)的子树中加叶子。如果\(sz_u>\left\lfloor......
  • CodeForces 1827 B Range Sorting
    洛谷传送门CF传送门考虑拆贡献\(i-1\simi\)，发现当\([1,i-1]\)的最大值大于\([i,n]\)的最小值时\(i-1\simi\)产生\(1\)的贡献。考虑枚举左端点\(j\)，设\(x=\max\limits_{k=j}^{i-1}a_k\)。设\(i\)及\(i\)以后第一个\(<x\)的数位置是\(p\)，那么......
  • Codeforces 1158E - Strange device（交互）
    一个有点烦的\(8\logn\)的做法。大致想法大家都一样：以\(1\)为根，然后先问出每个点深度，再问出每个点的父亲。首先先用一个log的做法问出树高，具体做法是直接令根节点的\(f\)为二分出的\(mid\)，看能否覆盖所有点即可，记最大深度为\(mxdep\)。可以在二分过程中顺带着求出深......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99