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

Codeforces Round 877 (Div. 2)

时间:2023-06-11 18:12:08浏览次数:42  
标签:CI const int 877 Codeforces mid Div include define

Preface

补题

这场补题的时候直接成腐乳了,A题挂两发,B题挂两发,C题挂一发是真的抽象

虽然D是个套路题看一眼就秒了,但如果真的比赛时候打真要罚时爆炸了的说

后面的EF还是做不来啊岂可修,不过都很有启发性让人感觉神清气爽,不像傻逼蓝桥杯花钱买罪受


A. Blackboard List

刚开始想错方向了,签到题写挂真没理由的

首先考虑求出\(a_i\)的最小值\(mi\),显然如果\(mi<0\)则它一定是初始的某个数之一,因为不可能生成负数

否则求出\(a_i\)的最大值\(mx\),则\(mx\)此时一定是初始的某个数之一,因为此时所有数都大于等于\(0\),那么其差的绝对值只会越来越小

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int t,n,x,mi,mx;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),mi=1e9,mx=-1e9,i=1;i<=n;++i)
		scanf("%d",&x),mi=min(mi,x),mx=max(mx,x);
		printf("%d\n",mi<0?mi:mx);
	}
	return 0;
}

B. Minimize Permutation Subarrays

这题感觉比A题要简单点的说,不过我还是写挂了

其实很简单,只要把\(n\)插到\(1,2\)的中间即可保证没有除了\(\{1\}\)和整个序列之外的其它排列了

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,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",&n),i=1;i<=n;++i) scanf("%d",&a[i]),pos[a[i]]=i;
		int x=min(pos[1],pos[2]),y=max(pos[1],pos[2]);
		if (pos[n]<x) printf("%d %d\n",pos[n],x); else
		if (pos[n]>y) printf("%d %d\n",pos[n],y); else puts("1 1");
	}
	return 0;
}

C. No Prime Differences

一般Div2的构造还是很trivial的,刚开始想复杂了还好后面悬崖勒马

首先如果\(m\)不是质数的话就有个很trivial的构造方案,即形如这样的填法(\(n=4,m=4\)):

1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16

此时所有相邻数的差都是\(1\)或者\(m\),显然符合要求

否则此时\(m\)为质数,考虑\(m+1\)一定是合数,因此我们可以如下构造(\(n=5,m=5\)):

1  2  3  4  5
7  8  9  10 6
13 14 15 11 12
19 20 16 17 18
25 21 22 23 24

即如果我们把每行最小的数每次向右有一个\(m-1\)的循环移位,确定下它的位置之后按顺序填入其它数即可

代码就非常好写了

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int t,n,m,a[N][N]; bool ispri[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (i=2;i<=1000;++i) for (ispri[i]=1,j=2;j*j<=i;++j) if (i%j==0) ispri[i]=0;
	for (scanf("%d",&t);t;--t)
	{
		if (scanf("%d%d",&n,&m),!ispri[m])
		{
			for (i=1;i<=n;++i) for (j=1;j<=m;++j) a[i][j]=(i-1)*m+j;
		} else
		{
			for (i=1;i<=m;++i) a[1][i]=i; int dlt=m-1,pos=1,num=m;
			for (i=2;i<=n;++i)
			{
				pos+=dlt; if (pos>m) pos-=m;
				for (j=pos;j<=m;++j) a[i][j]=++num;
				for (j=1;j<pos;++j) a[i][j]=++num;
			}
		}
		for (i=1;i<=n;++i) for (j=1;j<=m;++j) printf("%d%c",a[i][j]," \n"[j==m]);
	}
	return 0;
}

D. Bracket Walk

经典套路题,感觉最近括号序列相关的题见的有点太多了,所以思路就很容易了

首先当整个序列长度为奇数时一定无解,因为不管怎么刷括号也不会改变两个括号差值的奇偶性

否则考虑套路地把左括号看成\(1\),右括号看成\(-1\),考虑什么时候我们需要刷左括号

很显然就是当存在某个位置的前缀和\(<0\)时就会有不合法的情况,我们把最左边的这个位置记为\(pos\)

那么我们现在要判断的就是在\(pos\)之前有没有连续两个左括号的出现,如果有的话我们直接在这里刷够左括号的数目使得后面不会出现前缀和\(<0\)的情形

对于右括号的讨论也是同理,我们也可以用经典套路,把整个括号序列reverse之后并把所有括号取反,就把刷右括号转化成和刷左括号一样的操作了

(不然的话要写两种线段树上二分代码量有点大的说)

然后维护这些信息显然直接用线段树维护前缀和序列的值即可,查询第一个小于\(0\)的位置只要维护区间最小值然后线段树上二分即可

至于那个连续的左括号的位置直接用set存一下即可,每次拿出其中最左的位置和\(pos\)比较一下即可

#include<cstdio>
#include<iostream>
#include<set>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,q,x,a[N],b[N],pfx_a[N],pfx_b[N]; char s[N]; set <int> sa,sb;
class Segment_Tree
{
	private:
		struct segment
		{
			int mi,tag;
		}node[N<<2];
		#define MI(x) node[x].mi
		#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 pushup(CI now)
		{
			MI(now)=min(MI(now<<1),MI(now<<1|1));
		}
		inline void apply(CI now,CI mv)
		{
			MI(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(int *pfx,TN)
		{
			T(now)=0; if (l==r) return (void)(MI(now)=pfx[l]);
			int mid=l+r>>1; build(pfx,LS); build(pfx,RS); pushup(now);
		}
		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); pushup(now);
		}
		inline int query(TN)
		{
			if (MI(now)>=0) return n+1; if (l==r) return l; int mid=l+r>>1; pushdown(now);
			if (MI(now<<1)<0) return query(LS); return query(RS);
		}
		#undef M
		#undef T
		#undef TN
		#undef LS
		#undef RS
}A,B;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d%s",&n,&q,s+1),i=1;i<=n;++i)
	a[i]=s[i]=='('?1:-1,b[n-i+1]=-a[i];
	for (sa.clear(),sb.clear(),i=1;i<n;++i)
	{
		if (a[i]==1&&a[i+1]==1) sa.insert(i);
		if (b[i]==1&&b[i+1]==1) sb.insert(i);
	}
	for (i=1;i<=n;++i) pfx_a[i]=pfx_a[i-1]+a[i],pfx_b[i]=pfx_b[i-1]+b[i];
	for (A.build(pfx_a),B.build(pfx_b),i=1;i<=q;++i)
	{
		if (n&1) { puts("NO"); continue; }
		scanf("%d",&x); A.modify(x,n,-2*a[x]); B.modify(n-x+1,n,-2*b[n-x+1]);
		if (x<n&&a[x]==1&&a[x+1]==1) sa.erase(x);
		if (x>1&&a[x-1]==1&&a[x]==1) sa.erase(x-1);
		a[x]*=-1; if (x<n&&a[x]==1&&a[x+1]==1) sa.insert(x);
		if (x>1&&a[x-1]==1&&a[x]==1) sa.insert(x-1);
		x=n-x+1; if (x<n&&b[x]==1&&b[x+1]==1) sb.erase(x);
		if (x>1&&b[x-1]==1&&b[x]==1) sb.erase(x-1);
		b[x]*=-1; if (x<n&&b[x]==1&&b[x+1]==1) sb.insert(x);
		if (x>1&&b[x-1]==1&&b[x]==1) sb.insert(x-1);
		int pa1=sa.empty()?n+1:*sa.begin(),pa2=A.query();
		int pb1=sb.empty()?n+1:*sb.begin(),pb2=B.query();
		if (pa1<=pa2&&pb1<=pb2) puts("YES"); else puts("NO");	
	}
	return 0;
}

E. Count Supersequences

龟龟原来答案和序列的形态无关,真是太巧妙了的说

首先我们可以尝试先写个暴力DP,设\(f_{i,j}\)表示填了序列\(b\)的前\(i\)位,匹配序列\(a\)的最长前缀的长度为\(j\)的方案数

转移的话考虑这一位填的是否和\(a\)中下一个位置匹配来转移,而且要注意如果\(j\)是\(a\)的最后一个位置(即之前以及全部匹配了)就可以随便填,因为前面的已经合法了

写成转移方程就是这样:

\[f_{i,j} = \begin{cases} f_{i-1, j-1} + (k-1)\times f_{i-1, j} & j < n \\ f_{i-1, j-1} + k\times f_{i-1, j} & j = n \end{cases} \]

然后我们可以很惊喜地发现这个DP和\(a_i\)的具体形态无关,那么就意味着我们可以任意地修改\(a_i\)的取值来简化问题

比如此时我们可以令所有的\(a_i\)都为\(1\),此时题目转化为,求\(b\)的方案数使得序列中至少有\(n\)个\(1\)

考虑到\(m\)较大而\(n\)较小,因此可以容斥计算答案,即枚举不合法的只放了\(i\)个\(1\)的方案,则:

\[Ans=k^m - \sum_{i=0}^{n-1} C_m^i\times (k-1)^{m-i} \]

现在还有一个问题就是\(m\)很大时组合数\(C_m^i\)的值应该怎么快速计算,考虑因为要求的所有组合数的下标其实都一样,因此可以用递推求解:

\[C_m^i = \frac{m(m-1)\ldots(m-i+1)}{i(i-1)\ldots 1} = \frac{m - i + 1}{i}\times C_m^{i-1} \]

因此总复杂度\(O(n\log m)\)

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,mod=1e9+7;
int t,n,m,k,x,coef,ans;
inline void dec(int& x,CI y)
{
	if ((x-=y)<0) x+=mod;
}
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;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d%d",&n,&m,&k),i=1;i<=n;++i) scanf("%d",&x);
		for (ans=quick_pow(k,m),coef=1,i=0;i<n;++i)
		dec(ans,1LL*coef*quick_pow(k-1,m-i)%mod),coef=1LL*coef*(m-i)%mod*quick_pow(i+1)%mod;
		printf("%d\n",ans);
	}
	return 0;
}

F. Stuck Conveyor

妙题,其实前面有一个差不多的做法但感觉写起来很麻烦,看了Tutorial只能说是醍醐灌顶

本题最核心的思想就是构建两种蛇形的方案,即:

不难发现这两种方案都经过了所有格子各一次,并且第二种方案就是第一种方案路径的反向

考虑按照第一种方案的顺序给格子赋上\(1\sim n^2\)的编号,则第一种方案总是从编号小的走到编号大的,第二章方案则恰好相反

现在考虑我们分别以编号为\(1\)的格子为初始位置,并用方案一来询问得到一组反馈\(x_1,y_1\),同时以编号为\(n^2\)的格子为初始位置,并用方案二来询问得到一组反馈\(x_2,y_2\)

考虑现在如果\(x_1=x_2,y_1=y_2\)且都不是循环,则说明一定是某个边界上的格子坏了,并且我们此时很容易判断出坏掉的格子的方向

否则出现的一定是某个方案有循环而另一个方案不成循环

因为考虑坏掉的格子的方向是从编号大的指向编号小的,那么其在方案二的填法中一定不会成循环,反之则在方案一中一定会成环

下面我们就以这种情况为例,考虑此时如何确定方案一中坏掉的格子的编号\(j\)

不难发现如果此时我们改变初始位置\(i\)的编号,如果\(i\le j\)则此时会返回循环,否则就可以跳出循环

答案显然具有二分性,因此很容易确定出\(j\)的值,这个在方案二中也是同理,只不过是\(i\ge j\)会循环

那么现在我们已经知道了坏掉的格子的具体位置了,要确定它的方向也很容易,直接向下图一样再询问一次即可(非红色的格子的填法任意,中间那个就是坏掉的格子位置):

此时根据反馈的跳出位置可以很容易地判断方向了,而此法的询问总次数为\(2+\lceil \log(n^2)\rceil +1=17\),足以通过此题

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int n,cnt,rx[N*N],ry[N*N],x_1,y_1,x_2,y_2; char A[N][N],B[N][N];
inline void ask(char c[N][N],CI sx,CI sy,int& x,int& y)
{
	printf("? %d %d\n",sx,sy);
	for (RI i=1,j;i<=n;++i,putchar('\n'))
	for (j=1;j<=n;++j) putchar(c[i][j]);
	fflush(stdout); scanf("%d%d",&x,&y);
}
inline void answer(CI x,CI y,const char& ch)
{
	printf("! %d %d %c\n",x,y,ch); fflush(stdout);
}
int main()
{
	RI i; scanf("%d",&n); int x=1,y=1,dy=1,ret; bool flag=0;
	while (x<=n)
	{
		rx[++cnt]=x; ry[cnt]=y;
		if (flag&&(y==1||y==n)) A[x][y]='v'; else
		if (dy==1) A[x][y]='>'; else A[x][y]='<';
		if (flag&&(y==1||y==n)) ++x,dy*=-1,flag=0; else y+=dy,flag=1;
	}
	ask(A,1,1,x_1,y_1);
	x=rx[cnt]; y=ry[cnt]; dy=y==1?1:-1; flag=0;
	while (x>=1)
	{
		if (flag&&(y==1||y==n)) B[x][y]='^'; else
		if (dy==1) B[x][y]='>'; else B[x][y]='<';
		if (flag&&(y==1||y==n)) --x,dy*=-1,flag=0; else y+=dy,flag=1;
	}
	ask(B,rx[cnt],ry[cnt],x_2,y_2);
	if (x_1==x_2&&y_1==y_2)
	{
		if (x_1==0) answer(1,y_1,'^'); else
		if (x_1==n+1) answer(n,y_1,'v'); else
		if (y_1==0) answer(x_1,1,'<'); else answer(x_1,n,'>');
		return 0;
	}
	if (x_1==-1)
	{
		int l=1,r=cnt,mid; while (l<=r)
		{
			mid=l+r>>1; ask(A,rx[mid],ry[mid],x_1,y_1);
			if (x_1==-1) ret=mid,l=mid+1; else r=mid-1;
		}
	} else
	{
		int l=1,r=cnt,mid; while (l<=r)
		{
			mid=l+r>>1; ask(B,rx[mid],ry[mid],x_2,y_2);
			if (x_2==-1) ret=mid,r=mid-1; else l=mid+1;
		}
	}
	x=rx[ret]; y=ry[ret];
	for (i=1;i<x;++i) A[i][y]='^';
	for (i=x+1;i<=n;++i) A[i][y]='v';
	for (i=1;i<y;++i) A[x][i]='<';
	for (i=y+1;i<=n;++i) A[x][i]='>';
	ask(A,x,y,x_1,y_1);
	if (x_1==0) answer(x,y,'^'); else
	if (x_1==n+1) answer(x,y,'v'); else
	if (y_1==0) answer(x,y,'<'); else answer(x,y,'>');
	return 0;
}

Postscript

唉突然发现还有两周就要期末考了,接下来得好好复习下了

不过考完之后就是爽训时间,暑假开始可能要开始做Gym的真题来训练了,到时候可能也要拉上队友一起,训练下默契度啥的

总而言之还是加油吧,争取明年能打出些成绩的说

标签:CI,const,int,877,Codeforces,mid,Div,include,define
From: https://www.cnblogs.com/cjjsb/p/17473307.html

相关文章

  • Codeforces Round 876 Div2 A-D题解
    CodeforcesRound876Div2A-D题解A.TheGoodArray这个题就是问你对于\(i\leqn\),要求前面后面至少\(ceil(\frac{i}{k})\)个1那我们就贪心的每k个放一个1,或者直接用数学算一下就好了AC代码#include<bits/stdc++.h>usingnamespacestd;constexprintlimit=(......
  • [Codeforces Round 876 (Div. 2)][Codeforces 1839D. Ball Sorting]
    题目链接:D-BallSorting题目大意:需要对一个排列按照指定操作进行排序。操作一:在数字间插入一个特殊点,可执行不超过\(k\)次;操作二:将在特殊点旁的数移动到任意位置。所有操作结束后特殊点会消失,要求对所有\(k\in[1,n]\),求出操作二的最少操作次数。分析题意可以得出,操作一放......
  • Codeforces 1188D Make Equal
    设最终所有数变为的值为\(u\),\(\operatorname{bitcount}(x)\)为\(x\)二进制上为\(1\)的位数,由题可得答案即为\(\sum\limits_{i=1}^n\operatorname{bitcount}(u-a_i)\)。此时让\(a_i\)从小到大排序,答案即为\(\sum\limits_{i=1}^n\operatorname{bitcount}(u-a_......
  • 【若归】 【LGR-142-Div.4】洛谷入门赛 #13赛后反思
    比赛链接:【LGR-142-Div.4】洛谷入门赛#13rk288,比前几次差(可能是因为rated?)A十年OI一场空,不开longlong见祖宗#include<bits/stdc++.h>usingnamespacestd;intmain(){ longlongintn; cin>>n; cout<<"8"<<12*(n-2)<<""<<6*(n-......
  • Codeforces 1626 C
    1626C题意抽象出题意:给出n个区间的结尾以及它的区间长度,然后每一段连续区间的贡献为\(\sum_{i=1}^{len}i\),求总贡献。思路处理出每个区间的开头结尾,排序后处理每个连续区间就行了。代码voidsolve(){ cin>>n; for(inti=1;i<=n;i++)cin>>p[i].second; for(inti=1,......
  • Codeforces 1514 C
    1514C题意给出一个数n,求[1,2,3...n-1]的某个最长子序列,这个子序列的元素乘积模n余1。思路这是个思维题,一个数学公式\[x\equiv1(modn)\rightarrowkx\equivk(mod kn)\]所以子序列中的元素与\(n\)互质,累乘结果模\(n\)后如果不是1,那么将序列中等于结果的元素去......
  • Codeforces 1515 B
    1515B题意有n只袜子(n为偶数),但左袜子有L只,右袜子有R只,每只袜子的颜色为\(C_i\),可以进行以下操作:换袜子的方向、或者将袜子变色,问进行多少次操作后变成(n/2)对袜子思路很曲折,想了很久后终于想清楚,排除配对的袜子后,对于某类袜子\(i\),剩下\(c\geq2\)(假设剩下的是右边)只,它的配对......
  • CF1338 Div.1 做题记录
    ACF题面假定用到的最大的数是\(x\),那么一个数最大可以增大\(2^x-1\)。题目只要求不降,所以求出将\(a_i<a_{i-1}\)变成\(a_i=a_{i-1}\)时需要增大的最大值。求出这个数的二进制位数即可。点击查看代码#include<bits/stdc++.h>#defineullunsignedlonglong#definell......
  • CodeForces - 658A Bear and Reverse Radewoosh (模拟)水
    TimeLimit: 2000MS MemoryLimit: 262144KB 64bitIOFormat: %I64d&%I64uCodeForces-658ABearandReverseRadewooshSubmit StatusDescriptionLimakandRadewoosharegoingtocompeteagainsteachotherintheupcomingalgorithmiccontest.Theyareequ......
  • CodeForces - 616B Dinner with Emma (模拟)水
    TimeLimit: 1000MS MemoryLimit: 262144KB 64bitIOFormat: %I64d&%I64uCodeForces-616BDinnerwithEmmaSubmit StatusDescriptionJackdecidestoinviteEmmaoutforadinner.Jackisamodeststudent,hedoesn'twanttogotoanexpensiveres......