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

Codeforces Round 953 (Div. 2)

时间:2024-07-04 19:53:24浏览次数:15  
标签:typedef int 953 CI Codeforces long Div include define

Preface

经典30min写完前四题,然后E题大脑宕机想复杂,最后写了一坨很难调试的东西成功把自己送走

趁着 Div1 的训练还没开始赶紧找回点状态吧,不然到时候保准天天坑队友的说


A. Alice and Books

不难发现 \(a_n\) 一定会取,那么在剩下的里面找一个最大的自成一堆就行

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=105;
int t,n,a[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) scanf("%d",&a[i]);
		printf("%d\n",*max_element(a+1,a+n)+a[n]);
	}
	return 0;
}

B. New Bakery

把式子写出来不难发现是个二次函数,可以直接解析求出最值,也可以直接写三分求解

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
int t,n,a,b;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d%d",&n,&a,&b); int l=0,r=min(n,b);
		auto calc=[&](CI k)
		{
			return 1LL*(b+b-k+1)*k/2LL+1LL*a*(n-k);
		};
		while (r-l>2)
		{
			int lmid=l+(r-l)/3,rmid=r-(r-l)/3;
			if (calc(lmid)>=calc(rmid)) r=rmid; else l=lmid;
		}
		int pos=l; for (RI i=l+1;i<=r;++i)
		if (calc(i)>calc(pos)) pos=i;
		printf("%lld\n",calc(pos));
	}
	return 0;
}

C. Manhattan Permutations

首先不难发现 \(k\) 是奇数一定无解,否则我们考虑在 \([1,2,\dots,n]\) 的基础上进行若干交换

手玩一下不难发现每次换最远的没交换过的两个可以达到理论上界,而且可以构造出任意一个中间值

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,p[N]; LL k;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%lld",&n,&k);
		if (k%2==1) { puts("No"); continue; }
		RI i,j,l; for (i=1;i<=n;++i) p[i]=i;
		for (i=1,j=n;i<j&&k>0;++i,--j)
		{
			int tmp=(j-i)*2;
			if (k>=tmp) k-=tmp,swap(p[i],p[j]); else
			{
				for (l=i+1;l<=j;++l)
				if ((l-i)*2==k) { k=0,swap(p[i],p[l]); break; }
			}
		}
		if (k>0) puts("No"); else
		{
			for (puts("Yes"),i=1;i<=n;++i) printf("%d%c",p[i]," \n"[i==n]);
		}
	}
	return 0;
}

D. Elections

感觉被我写复杂了,摸了半天摸出来一坨,好在写完就过了没浪费多少时间

首先特判掉 \(1,n\) 两个人的情况,并直接把刚开始多出来的 \(c\) 个人加到 \(a_1\) 上

对于 \(i\in [2,n-1]\),我们先找出 \(mx=\max_\limits{i<j\le n} a_j\),随后进行讨论:

  • 若 \(mx>a_i\),此时无论如何 \([1,i-1]\) 的人都必须被干掉,否则 \(a_i\) 没法吃到闲散的票就不可能超过后面的人。算出此时 \(a_i\) 的值 \(a_i'\) 后再进行讨论:
    • 若 \(mx>a'_i\),则需要一次操作干掉 \(mx\) 对应的人,此时局面显然满足要求
    • 若 \(mx\le a'_i\),则不需要额外的操作
  • 若 \(mx\le a_i\),此时不需要考虑后面的人,考虑把所有 \(j\in[1,i-1]\and a_j\ge a_i\) 的人都干掉,之后又会出现两种情况:
    • 干掉的人对应的闲散票加到 \([1,i-1]\) 中第一个没被干掉的人上以后得到的值 \(< a_i\),此时不用进行额外的操作
    • 干掉的人对应的闲散票加到 \([1,i-1]\) 中第一个没被干掉的人上以后得到的值 \(\ge a_i\),此时 \([1,i-1]\) 中的所有人都必须被干掉

上述所有操作可以维护一个权值线段树解决,总复杂度 \(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,c,a[N],rst[N],tot,suf[N],ans[N]; LL pfx[N];
class Segment_Tree
{
	private:
		int cnt[N<<2],mnp[N<<2]; LL sum[N<<2];
	public:
		#define TN CI now=1,CI l=1,CI r=tot
		#define LS now<<1,l,mid
		#define RS now<<1|1,mid+1,r
		inline void build(TN)
		{
			mnp[now]=n+1; cnt[now]=sum[now]=0;
			if (l==r) return; int mid=l+r>>1;
			build(LS); build(RS);
		}
		inline void updata(CI val,CI pos,TN)
		{
			if (l==r)
			{
				++cnt[now]; sum[now]+=rst[val];
				mnp[now]=min(mnp[now],pos);	return;
			}
			int mid=l+r>>1;
			if (val<=mid) updata(val,pos,LS); else updata(val,pos,RS);
			cnt[now]=cnt[now<<1]+cnt[now<<1|1];
			sum[now]=sum[now<<1]+sum[now<<1|1];
			mnp[now]=min(mnp[now<<1],mnp[now<<1|1]);
		}
		inline int query_cnt(CI beg,CI end,TN)
		{
			if (beg<=l&&r<=end) return cnt[now]; int mid=l+r>>1,ret=0;
			if (beg<=mid) ret+=query_cnt(beg,end,LS);
			if (end>mid) ret+=query_cnt(beg,end,RS);
			return ret;
		}
		inline LL query_sum(CI beg,CI end,TN)
		{
			if (beg<=l&&r<=end) return sum[now]; int mid=l+r>>1; LL ret=0;
			if (beg<=mid) ret+=query_sum(beg,end,LS);
			if (end>mid) ret+=query_sum(beg,end,RS);
			return ret;
		}
		inline int query_pos(CI beg,CI end,TN)
		{
			if (beg<=l&&r<=end) return mnp[now]; int mid=l+r>>1,ret=n+1;
			if (beg<=mid) ret=min(ret,query_pos(beg,end,LS));
			if (end>mid) ret=min(ret,query_pos(beg,end,RS));
			return ret;
		}
		#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)
	{
		RI i; scanf("%d%d",&n,&c); tot=0;
		for (i=1;i<=n;++i) scanf("%d",&a[i]);
		for (a[1]+=c,i=1;i<=n;++i) rst[++tot]=a[i];
		if (n==1) { puts("0"); continue; }
		for (suf[n]=a[n],i=n-1;i>=1;--i) suf[i]=max(suf[i+1],a[i]);
		for (i=1;i<=n;++i) pfx[i]=pfx[i-1]+a[i];
		sort(rst+1,rst+tot+1); tot=unique(rst+1,rst+tot+1)-rst-1;
		for (i=1;i<=n;++i) a[i]=lower_bound(rst+1,rst+tot+1,a[i])-rst;
		if (rst[a[1]]>=suf[2]) ans[1]=0; else ans[1]=1;
		for (ans[n]=0,i=1;i<n;++i) if (a[i]>=a[n]) { ans[n]=n-1; break; }
		for (SEG.build(),SEG.updata(a[1],1),i=2;i<n;++i)
		{
			if (suf[i+1]>rst[a[i]])
			{
				ans[i]=i-1; LL cur=rst[a[i]]+pfx[i-1];
				if (cur<suf[i+1]) ++ans[i];
			} else
			{
				ans[i]=SEG.query_cnt(a[i],tot);
				if (ans[i]<i-1&&(a[i]>1?rst[a[SEG.query_pos(1,a[i]-1)]]:0)+SEG.query_sum(a[i],tot)>=rst[a[i]]) ans[i]=i-1;
			}
			SEG.updata(a[i],i);
		}
		for (i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]);
	}
	return 0;
}

E. Computing Machine

这题好像是个神秘的 \(O(n)\) ad hoc 题,但我完全没想到神秘奇妙性质只感觉可以莫队就直接冲了

首先不难发现先扫一遍序列 \(a\) 把 \(b\) 尽量多的位置涂成 \(1\);然后回头让 \(b\) 把 \(a\) 尽量多的位置涂成 \(1\);这个策略显然是最优的

因此我们发现加入一个位置 \(i\) 后至多影响其周围 \([i-3,i+3]\) 范围内的贡献,因此可以通过莫队来处理

但写的时候发现加入的情况还好说,删除的情况怎么写都感觉漏Case,无奈之下只好去写回滚莫队这种不用删除的科技

结构写完发现由于上面讲的一个位置的较大的影响范围,还不能像传统的回滚莫队一样直接滚回块尾后面的位置

但我最擅长的就是魔改经典算法了,后面发现我们手动放宽回滚莫队中做暴力的区间阈值,使得右端点可以推到较远的位置(代码里取了 \(10\))

然后手动把会因为左端点移动带来影响的前 \(3\) 个位置记录下来,每次回滚左端点的时候一并复原即可

总复杂度 \(O(m\sqrt n)\),胜在不用动脑子找性质

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int blk[N];
struct ques
{
	int l,r,id;
	friend inline bool operator < (const ques& A,const ques& B)
	{
		return blk[A.l]!=blk[B.l]?blk[A.l]<blk[B.l]:A.r<B.r;
	}
}q[N]; int t,n,m,sz,ta[N],tb[N],ans[N]; char a[N],b[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; scanf("%d%s%s",&n,a+1,b+1);
		for (sz=(int)sqrt(n),i=1;i<=n;++i) blk[i]=(i-1)/sz+1;
		for (scanf("%d",&m),i=1;i<=m;++i)
		scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
		RI l=1,r=0,p=1; sort(q+1,q+m+1);
		for (i=1;i<=blk[n];++i)
		{
			int ret=0,lim=min(n,i*sz); r=lim;
			int tmp_ta[3],tmp_tb[3]; tmp_ta[0]=-1;
			while (p<=m&&blk[q[p].l]==i)
			{
				auto chk=[&](int& x,CI y)
				{
					if (x==0&&y==1) ++ret;
					if (x==1&&y==0) --ret;
					x=y;
				};
				auto addr=[&](CI r)
				{
					ta[r]=a[r]-'0'; tb[r]=b[r]-'0'; ret+=ta[r];
					if (r-2>=l)
					{
						if (tb[r]&&tb[r-2]) chk(ta[r-1],1);
						if (a[r]=='0'&&a[r-2]=='0') tb[r-1]=1;
						if (r-3>=l&&tb[r-1]&&tb[r-3]) chk(ta[r-2],1);
					}
				};
				auto addl=[&](CI l)
				{
					ta[l]=a[l]-'0'; tb[l]=b[l]-'0'; ret+=ta[l];
					if (l+2<=r)
					{
						if (tb[l]&&tb[l+2]) chk(ta[l+1],1);
						if (a[l]=='0'&&a[l+2]=='0') tb[l+1]=1;
						if (l+3<=r&&tb[l+1]&&tb[l+3]) chk(ta[l+2],1);
					}
				};
				auto BF=[&](CI l,CI r)
				{
					RI i; static int ta[N],tb[N];
					for (i=l;i<=r;++i) ta[i]=a[i]-'0',tb[i]=b[i]-'0';
					for (i=l;i+2<=r;++i) if (a[i]=='0'&&a[i+2]=='0') tb[i+1]=1;
					for (i=l;i+2<=r;++i) if (tb[i]&&tb[i+2]) ta[i+1]=1;
					int cur=0; for (i=l;i<=r;++i) cur+=ta[i]; return cur;
				};
				l=lim+1;
				if (q[p].r-q[p].l+1<=sz+10)
				{
					ans[q[p].id]=BF(q[p].l,q[p].r);
					++p; continue;
				}
				while (r<q[p].r) addr(++r);
				if (tmp_ta[0]==-1)
				{
					for (j=0;j<3;++j) tmp_ta[j]=ta[lim+1+j];
					for (j=0;j<3;++j) tmp_tb[j]=tb[lim+1+j];
				}
				int tmp=ret;
				while (l>q[p].l) addl(--l);
				ans[q[p++].id]=ret; ret=tmp;
				for (j=0;j<3;++j) ta[lim+1+j]=tmp_ta[j];
				for (j=0;j<3;++j) tb[lim+1+j]=tmp_tb[j];
			}
		}
		for (i=1;i<=m;++i) printf("%d\n",ans[i]);
	}
	return 0;
}

F. Large Graph

本来感觉没啥突破口的,后面看到 \(k\ge 2\) 就知道是个傻逼题了

因为此时所有不为 \(1\) 的主对角线会直接连通在一起,因此原问题就转化为 \(2n-1\) 条主对角线直接的连通性问题了

同时主对角线还有个很好的性质,就是我们从左到右对其编号后,则编号为 \(i\) 和编号为 \(j\) 的两条对角线中任意选出两个元素,它们的曼哈顿距离都为 \(|i-j|\)

利用上面两个性质二维的问题就变成一维的情况了,看到 \(\gcd\) 就考虑分解质因数

对于某个质数 \(p\),不妨设其倍数对应的下标构成集合 \(pos_p\),则我们将 \(pos_p\) 中的元素排序后每次判断相邻的两个元素能否连边即可

用并查集暴力维护连通块,总复杂度 \(O(n\log n\times \alpha (n))\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=2e6+5;
int t,n,k,a[N],pri[N],cnt,mnp[N],fa[N]; bool vis[N]; vector <int> pos[N];
inline void init(CI n)
{
	for (RI i=2,j;i<=n;++i)
	{
		if (!vis[i]) pri[++cnt]=i,mnp[i]=i;
		for (j=1;j<=cnt&&i*pri[j]<=n;++j)
		{
			vis[i*pri[j]]=1; mnp[i*pri[j]]=pri[j];
			if (i%pri[j]==0) break;
		}
	}
}
inline int getfa(CI x)
{
	return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t),init(1e6);t;--t)
	{
		RI i; for (scanf("%d%d",&n,&k),i=1;i<=n;++i) scanf("%d",&a[n-1+i]);
		for (i=1;i<n;++i) a[i]=a[i+n]; vector <int> vec;
		for (i=1;i<=2*n-1;++i)
		{
			fa[i]=i; int x=a[i];
			while (x>1)
			{
				int p=mnp[x]; pos[p].push_back(i);
				vec.push_back(p); while (x%p==0) x/=p;
			}
		}
		sort(vec.begin(),vec.end());
		vec.erase(unique(vec.begin(),vec.end()),vec.end());
		for (auto p:vec)
		{
			for (i=0;i<pos[p].size()-1;++i)
			if (pos[p][i+1]-pos[p][i]<=k)
			fa[getfa(pos[p][i+1])]=getfa(pos[p][i]);
			pos[p].clear();
		}
		LL ans=0; for (i=1;i<=2*n-1;++i)
		{
			if (getfa(i)==i) ++ans;
			if (a[i]==1) ans+=(i<=n?i:2*n-i)-1;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

Postscript

因为昨天这场E题写的很唐再加上这两天在帮徐神写字符串的题面,因此今天就只能补个博客没时间新开一场VP了,明天继续坚持开一场吧

标签:typedef,int,953,CI,Codeforces,long,Div,include,define
From: https://www.cnblogs.com/cjjsb/p/18284556

相关文章

  • Codeforces 19xx 合集
    CF1974A.PhoneDesktop每个手机只能填两个大的,先把大的填完,然后剩下的地方用小的补上,最后小的不够用了再拿新的手机。B.SymmetricEncoding直接模拟吧。C.BeautifulTriplePairs一个比较好写的做法,是先不管那个不同的,把所有存在两个相同的都加上,最后减去三遍三个......
  • Codeforces Round 941 (Div. 2) cf 941 div2 A~D
    每题都有AC代码在伸缩代码框请留意!!A.CardExchange-------------------------------------------题解----------------------------------选择任意K张相同的牌替换成k-1张任意的牌,也就是说只要有一组牌相同的数量大于k就可以获得最大k-1相同的其他牌,按照这个策略便可以替换掉......
  • CF950Div3 G. Yasya and the Mysterious Tree(01Trie)
    Problem题目地址Solution设\(s[u]\)是根到\(u\)路径上的异或和,树上任意两点\(u,v\)的路径异或和可表示为\(s[u]\opluss[v]\)。考虑查询操作?vx即求\(\max\{s[v]\opluss[u]\oplusx|\\1\leu\len,u\not=v\}\),若把\(s[v]\oplusx\)看作一个整体......
  • Educational Codeforces Round 167 (Rated for Div. 2) A-D
    A.CatchtheCoin题意:在一个二维坐标系上有一个硬币每秒y轴坐标减一,而你每秒可以向旁边八个方向移动,问你有没有一个时刻你会和硬币重叠。思路:注意到在y小于-2时,我们无论如何都追不到硬币,而其他时候我们可以采取向左下或者右下的策略来保持和硬币y轴下落同步移动的时候接近......
  • EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2)
    Preface沟槽的又掉分了,难得凑齐了五个人打LOL结果只玩了两把就去打这场CF了,早知道继续玩了这场经典开局不顺,C想了一堆假做法到30min的时候才出,D题上来就莽一个贪心然后爆WA两发后还不知道错哪了,卡到90min的时候心态小崩滚去看了眼E马上秒了后回来发现D是个很一眼的DP,写完后就只......
  • Codeforces Round 918 G. Bicycles (二维最短路)
    G.Bicycles题意:在一个无向图里你要从1点到达n点,每条路的路径长度是该路的权值乘于你当前的慢度因子。而在每个点上我们都有一个慢度因子可以进行更换,问你到达n点所需要的最短时间。思路:我们很容易想到每次遇到更小的慢度因子我们就要更换,但因为存在你先去绕远路拿更小的慢......
  • Codeforces Round 894 (Div. 3) A-E cd 894 div3
    A.GiftCarpet每道题都是伸缩代码框有ac代码请不要漏掉--------------------------题解-----------------------------按先行便然后列再变循环设置jud每满足一个条件就让jud++只有jud==相应值的时候才让其++点击查看代码#include<bits/stdc++.h>usingnamespacestd;ch......
  • Codeforces Round 954 (Div. 3)
    A.XAxis题意:给3个x轴上的点xi,我们要放置一个点到x轴上,到这3个点的距离最短。(1<=xi<=10)思路:直接暴力破解即可inta,b,c;inlineintcal(intx){ returnabs(x-a)+abs(x-b)+abs(x-c);}voidsolve(){ cin>>a>>b>>c; intans=(int)1e9; for......
  • 创新实训 (九)CodeForces 数据和微调数据处理
    Codeforces数据获取Codeforces的题目中存在一些数学公式,所以处理的时候需要比较小心的对其进行处理。首先是题面数据,在CF当中标识一道题目的方式是problemSet与problemId。其中problemSet是一个数字,而problemId是一个字母。另外需要注意的是CF题面中存在许多数学......
  • [题解]AT_agc054_b [AGC054B] Greedy Division
    思路首先不难发现一个规律,当\(sum\)为奇数时不可能有解。定义\(dp_{i,j,k,0/1}\)表示A在前\(i\)个数中选出和为\(j\)的\(k\)个数,且第\(i\)个不选/选的方案数。那么,我们只需要对于第\(i\)个数的状态分类讨论就能得到状态转移方程:不选\(i\),\(dp_{i,j,k,0}=......