首页 > 其他分享 >Educational Codeforces Round 152 (Rated for Div. 2)

Educational Codeforces Round 152 (Rated for Div. 2)

时间：2023-08-01 22:25:51浏览次数：50  
标签：Educational Rated int Codeforces long typedef fi include define

Preface

经典秒完SB题然后开始坐牢1h，写了个E的假算法T在24个点就不管了打lol去了

妈的怎么稍微难点的题就是想不到呢

A. Morning Sandwich

签到

#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>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=100005;
int t,b,c,h;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d%d",&b,&c,&h); int t=b-1;
		if (c+h>=t) printf("%d\n",b+t); else printf("%d\n",(c+h)*2+1);
	}
	return 0;
}

B. Monsters

令\(b_i=a_i\bmod k\)，将数按照二元组\((b_i,i)\)排序后输出即可，其中第一维从大到小，第二维从小到大

注意\(b_i=0\)时要转化成\(b_i=k\)

#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>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=300005;
int t,n,k,a[N],b[N],id[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)
		if (scanf("%d",&a[i]),b[i]=a[i]%k,id[i]=i,!b[i]) b[i]=k;
		auto cmp=[&](CI x,CI y)
		{
			return b[x]!=b[y]?b[x]>b[y]:x<y;
		};
		for (sort(id+1,id+n+1,cmp),i=1;i<=n;++i) printf("%d%c",id[i]," \n"[i==n]);
	}
	return 0;
}

C. Binary String Copying

刚开始一眼没思路就直接跳，后面冷静下来感觉可以写个Hash试一波

然后就直接过了，也没啥好说的

#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>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=200005;
const int mod1=998244353,mod2=19260817;
struct Hasher
{
	int x,y;
	inline Hasher(CI X=0,CI Y=0)
	{
		x=X; y=Y;
	}
	inline LL val(void)
	{
		return ((1LL*x)<<31LL)|(1LL*y);
	}
	friend inline bool operator == (const Hasher& A,const Hasher& B)
	{
		return A.x==B.x&&A.y==B.y;
	}
	friend inline Hasher operator + (const Hasher& A,const Hasher& B)
	{
		return Hasher((A.x+B.x)%mod1,(A.y+B.y)%mod2);
	}
	friend inline Hasher operator - (const Hasher& A,const Hasher& B)
	{
		return Hasher((A.x-B.x+mod1)%mod1,(A.y-B.y+mod2)%mod2);
	}
	friend inline Hasher operator * (const Hasher& A,const Hasher& B)
	{
		return Hasher(1LL*A.x*B.x%mod1,1LL*A.y*B.y%mod2);
	}
}h[N],pw[N],one[N];
const Hasher seed=Hasher(31,131);
int t,n,m,l,r,pfx[N]; char s[N]; set <LL> rst;
inline Hasher get(Hasher *h,CI l,CI r)
{
	if (l>r) return Hasher();
	return h[r]-h[l-1]*pw[r-l+1];
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d%s",&n,&m,s+1),pw[0]=Hasher(1,1),i=1;i<=n;++i)
		pw[i]=pw[i-1]*seed,one[i]=one[i-1]*seed+Hasher(1,1),h[i]=h[i-1]*seed+Hasher(s[i]-'0',s[i]-'0'),pfx[i]=pfx[i-1]+s[i]-'0';
		int num=0; for (rst.clear(),i=1;i<=m;++i)
		{
			scanf("%d%d",&l,&r); int c1=pfx[r]-pfx[l-1];
			Hasher tmp=get(h,1,l-1)*pw[n-l+1]+one[c1]*pw[n-r]+get(h,r+1,n);
			if (!rst.count(tmp.val())) ++num,rst.insert(tmp.val());
		}
		printf("%d\n",num);
	}
	return 0;
}

D. Array Painting

考虑把所有非\(0\)的连续段找出来，显然如果某个段\([l,r]\)内有\(2\)的话那么它一定可以把\([l-1,r+1]\)都涂色

否则如果该段都为\(1\)那么就只能涂\([l-1,r]\)或者\([l,r+1]\)

很容易想到贪心，先把有\(2\)的段全涂了，然后全\(1\)的段优先涂左边那个格，如果已经涂了就涂右边

#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>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=200005;
int n,a[N],c[N],ret;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (i=1;i<=n;++i) if (a[i])
	{
		for (j=i;j<=n&&a[j];++j); ++ret;
		bool flag=0; for (k=i;k<j;++k) if (a[k]==2) flag=1;
		for (k=i;k<j;++k) c[k]=1;
		if (flag==1) c[i-1]=c[j]=1; else
		{
			if (i>1&&!c[i-1]) c[i-1]=1; else c[j]=1;
		}
		i=j-1;
	}
	for (i=1;i<=n;++i) if (!c[i]) ++ret;
	return printf("%d\n",ret),0;
}

E. Max to the Right of Min

比赛的时候一直想着枚举中间的某个点，发现难算的一比

其实考虑枚举右端点，考虑移动左端点对答案造成的影响

由于要统计区间最大最小，很容易想到开两个单调栈，这样我们可以对每个右端点\(r\)维护出若干个事件\((l,tp=0/1)\)，表示当左端点\(l\)是区间\([l,r]\)最小值（\(tp=0\)），或区间\([l,r]\)最大值（\(tp=1\)）

考虑如何统计答案，将所有事件按照第一维从小到大排序，不难发现对于两个相邻的事件\((l_i,tp_i),(l_{i+1},tp_{i+1})\)，若\(tp_{i+1}=0\)，则左端点为\([l_i+1,l_{i+1}]\)时都是合法的

那么我们就直接维护一个对应的事件集合，由于贡献的添加与删除都是和相邻的元素间产生，因此很好维护

总复杂度\(O(n\log n)\)，据说有用双端队列实现的\(O(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>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=1e6+5;
int n,a[N],stkmi[N],topmi,stkmx[N],topmx,cur; LL ans; set <pi> s;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (s.insert(pi(0,0)),s.insert(pi(0,1)),i=1;i<=n;++i)
	{
		while (topmi&&a[stkmi[topmi]]>a[i])
		{
			auto it=s.lower_bound(pi(stkmi[topmi],0)),pre=it,nxt=it;
			--pre; ++nxt; cur-=it->fi-pre->fi;
			if (nxt!=s.end()&&nxt->se==0) cur+=nxt->fi-pre->fi;
			s.erase(it); --topmi;
		}
		cur+=i-s.rbegin()->fi; s.insert(pi(i,0)); stkmi[++topmi]=i;
		while (topmx&&a[stkmx[topmx]]<a[i])
		{
			auto it=s.lower_bound(pi(stkmx[topmx],1)),pre=it,nxt=it;
			--pre; ++nxt;
			if (nxt!=s.end()&&nxt->se==0) cur+=it->fi-pre->fi;
			s.erase(it); --topmx;
		}
		s.insert(pi(i,1)); stkmx[++topmx]=i; ans+=cur;
	}
	return printf("%lld",ans-n),0;
}

F. XOR Partition

据说是经典老题，反正我没见过的说

考虑有一个\(n\)个点的图，图中两个点\(x,y\)之间的边权就是\(a_x\oplus a_y\)

由于最大值最小，很容易想到用类似克鲁斯卡尔求MST的思想，每次考虑当前最小的异或对\((x,y)\)，显然我们需要把它们放进不同的集合中才能让答案变优

因此不难发现当我们给这个图跑一遍最小异或生成树后答案就确定了，只要对生成树跑一个黑白染色即可

而这个是一个经典问题了，大致做法就是分治，从高位到低位考虑

很显然高位相同的数一定要在一组内，同时根据抽屉原理如果当前位分组如果数的个数大过\(2\)，那么无论你怎么分这一位在最终答案都是\(0\)

那么这题只要求输出方案的话其实代码就很好写了，每次递归到不能划分的时候暴力处理即可

但如果要求最小异或生成树的边权和的话，就考虑每次将两个集合内部的联通块先连起来，然后考虑要在两个集合中间连一条边

可以把某一个集合的所有数扔进0/1Trie里，然后在另一边查询即可

#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<limits.h>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
const int N=200005;
int n,ans[N]; pi a[N];
inline void solve(CI l,CI r,CI d)
{
	if (d<0||l>r) return; int mid=l-1;
	while (mid+1<=r&&((a[mid+1].fi>>d)&1)==0) ++mid;
	if (mid-l+1>=3||r-mid>=3) return solve(l,mid,d-1),solve(mid+1,r,d-1);
	int tot=r-l+1,mx=0,res=0; RI i,j,k;
	for (i=0;i<(1<<tot);++i)
	{
		int cur=INT_MAX; for (j=0;j<tot;++j) for (k=j+1;k<tot;++k)
		if (((i>>j)&1)==((i>>k)&1)) cur=min(cur,a[l+j].fi^a[l+k].fi);
		if (cur>mx) mx=cur,res=i;
	}
	for (i=0;i<tot;++i) if ((res>>i)&1) ans[a[l+i].se]=1;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i].fi),a[i].se=i;
	for (sort(a+1,a+n+1),solve(1,n,30),i=1;i<=n;++i) putchar(ans[i]?'1':'0');
	return 0;
}

Postscript

so Weak……

标签：Educational,Rated,int,Codeforces,long,typedef,fi,include,define
From： https://www.cnblogs.com/cjjsb/p/17599257.html

相关文章

  • Codeforces Round 889 (Div. 2)
    CodeforcesRound889(Div.2)T1​ 思路：我们将\(i\nep_i\)的数量记下来，再判断这个数的奇偶性，如果为偶，那么答案就为这个数/2，如果为奇，那么就是这个数/2+1。T2​ 思路：我们枚举\(1\simn\)，我们记录连续是\(n\)的因数的个数，如果不连续了就\(break\)，答案就是个数......
  • Codeforces Round 885 (Div. 2)
    CodeforcesRound885(Div.2)A.VikaandHerFriends题目大意太长了click思路可以手动模拟一下，可以发现当两个人的\(x+y\)值就行相同的就能抓到了#include<bits/stdc++.h>usingnamespacestd;intmain(){intT;cin>>T;while(T--){......
  • Codeforces Round 887 (Div. 2)
    CodeforcesRound887(Div.2)A.Desorting题目大意给出一个长度为\(n\)的数组\(a\),可以执行这个操作任意次。选择一下标\(i\),使得\(a_{1...i}\)加上\(1\)，\(a_{i+1...n}\)减少\(1\)。问最少几次操作使得数组\(a\)无序。思路首先如果\(a\)原本就无序的......
  • Codeforces Round 885 (Div. 2) 题解
    A.VikaandHerFriends看一下样例就可以发现，Vika以及她的朋友都不能走对角线，在这种情况下Vika和朋友的距离为偶数，且朋友一定追不上Vika所以直接判断Vika和朋友的距离是否都为偶数即可B.VikaandtheBridge显然贪心，枚举颜色，找到相邻距离最大的两块木板，记该距离为\(......
  • Practice on Codeforces and Atcoder in May
    CF补题题解2023.5说明：CF题直接去luogu看翻译，AT题会附上简要题意CF1821E先考虑如何高速计算权值一个显而易见的贪心是尽量在右边取括号消除，设右括号为1，左括号为-1那么我们每一次消除的括号\(i,i+1\)都满足了\(i+1\)的右边剩下的全部是右括号，代价就是往右数的个数更进一......
  • Practice on Codeforces and Atcoder in June
    \(Practice\)\(on\)\(codeforces\)\(in\)\(June\)wk，误删了4个题，但我不想补了\(CF1839D\)题意：给一个正整数序列\(a\)，给定\(k\)个0，将其放进序列的任意位置里，可以进行无限次操作，每次将一个挨着0的数移动到序列的任意位置，最后删掉所有的0，求使得序列变成递增序列的最小操作......
  • Practice on Codeforces and Atcoder in July
    \(1844E\)题意：定义一个矩形\(a\)是好的，当且仅当其满足以下条件：矩形中每一个元素\(x\)都为\(A,B,C\)其中之一每一个\(2\times2\)的子矩形都必须包含三个不同的字符共用一条边的两个元素不相等给定\(k\)个限制条件，限制条件分为两类：\((x,x+1,y,y+1)\)，限制\(a[x......
  • Codeforces Round 887 (Div. 2) 题解
    A.Desorting题目的核心操作就是选定一个位置\(i\)，使得：对于所有\(j\lei\)，\(a_j\leftarrowa_j+1\)对于所有\(j>i\)，\(a_j\leftarrowa_j-1\)这样一来，操作后\(a_{i+1}-a_i\)的值就会\(-2\)因为\(a_{i+1}-a_i<0\)时，也意味着\(a_i>a_{i+1}\)，所以就达到了要求那么题......
  • Educational Codeforces Round 152 (Rated for Div. 2) D. Array Painting
    初始所有点都是蓝色的，给定一个数组，每个元素为0，1，2等值，两种操作，选定一个点花1元变红，或者选定一个为1或者2的红色点，减去一个价值，让周围的点变红，最后所有点都要变红思路：贪心，对于一个数组来说我们找寻连续的不等于0的一段，判断每一段最多所能变红的存在两种情况010，这种情况花1可以最......
  • Educational Codeforces Round 152 (Rated for Div. 2) C. Binary String Copying
    题目大意为给定一个01字符串，给定m个区间，对于每个区间进行一次局部排序，求能得到的字符串种类数解法：因为字符串只包含0，1两个字符，我们观察可以得到，对于不同的区间来说如果排序后一样则说明肯定是某些位置在排序过程中无贡献，因此我们只需找出有贡献的位置即可对于一个区间[l,r],来说......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99