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

Educational Codeforces Round 155 (Rated for Div. 2)

时间：2023-09-28 19:56:33浏览次数：43  
标签：Educational Rated 155 int typedef long include mx define

Preface

这天晚上这场因为不明原因（玩CCLCC中）就没有打，只能赛后补一下

这场的EF都不算难初看都有做法，但好家伙E写挂两发，F写个根号做法直接T到天上去了

A. Rigged!

签到题，对于所有的\(e_i\ge e_1\)的\(i\)，求出\(S=\max s_i\)，根据\(S+1\)和\(s_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>
#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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=105;
int t,n,s[N],e[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%d",&s[i],&e[i]);
		int mx=0; for (i=2;i<=n;++i) if (e[i]>=e[1]) mx=max(mx,s[i]);
		if (mx+1>s[1]) puts("-1"); else printf("%d\n",mx+1);
	}
	return 0;
}

B. Chips on the Board

还有这么生草的题的吗，周六刚在第二场网络赛考过，然后周日晚上的CF又出一遍

显然我们要么要在每行选一个，要么在每列选一个，因此答案就是\(\min(\sum a_i+n\times \min b_i,\sum b_i+n\times \min a_i)\)

#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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=300005;
int t,n,a[N],b[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]);
		for (i=1;i<=n;++i) scanf("%d",&b[i]); LL sa=0,sb=0;
		for (i=1;i<=n;++i) sa+=a[i],sb+=b[i];
		printf("%lld\n",min(sa+1LL*n*(*min_element(b+1,b+n+1)),sb+1LL*n*(*min_element(a+1,a+n+1))));
	}
	return 0;
}

C. Make it Alternating

不难发现对于每个连续段，设它的长度为\(len_i\)，则第一问的答案就是\(ans_1=\sum (len_i-1)\)

然后考虑方案数，显然每个连续段需要选一个数删去，因此\(ans_2=\prod len_i\)，当然由于删除的顺序可以不同所以还要乘上\((ans_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>
#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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005,mod=998244353;
int t,n; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; int lst=1,ans1=0,ans2=1;
		for (scanf("%s",s+1),n=strlen(s+1),i=1;i<=n;++i)
		if (s[i]!=s[lst]) ans1+=i-lst-1,ans2=1LL*ans2*(i-lst)%mod,lst=i;
		ans1+=n-lst; ans2=1LL*ans2*(n-lst+1)%mod;
		for (i=1;i<=ans1;++i) ans2=1LL*ans2*i%mod;
		printf("%d %d\n",ans1,ans2);
	}
	return 0;
}

D. Sum of XOR Functions

很一眼的题，这类题好像之前在哪里做到过类似的

考虑按位考虑，设此时每个位置的前缀异或和为\(pfx_i\)，对于某个区间\([l,r]\)，当且仅当\(pfx_r\oplus pfx_{l-1}=1\)时这个区间才能造成\((r-l+1)\times 2^k\)的贡献

很容易发现只要把前缀异或和为\(0/1\)的左端点的个数以及左端点的和统计下即可

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

#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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=300005,mod=998244353;
int n,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
	int ans=0; for (j=0;j<30;++j)
	{
		int c[2]={0,0},cur=0; LL s[2]={0,0},ret=0;
		for (c[0]=i=1;i<=n;++i)
		{
			if ((a[i]>>j)&1) cur^=1;
			ret+=1LL*c[cur^1]*i-s[cur^1];
			++c[cur]; s[cur]+=i;
		}
		(ans+=1LL*ret%mod*(1<<j)%mod)%=mod;
	}
	printf("%d\n",ans);
	return 0;
}

E. Interactive Game with Coloring

很有意思的一个题，需要想的比较清楚才行

首先样例很良心告诉我们答案至少有三种情况，而\(k=1\)的情况只有菊花图

同时不难发现\(k=3\)的做法就是分层循环染色，而这种方法总能得到答案，因此这题的难点在于\(k=2\)的情形的判断

考虑判断一个图是否可以被\(k=2\)判断，大致的思路也是分层染色，因为如果当某个点向上和向下的边同色的话就一定不能正确移动

思考一下会发现其实我们只关心那些向上和向下都只有一条边的点，因为如果一个点是叶子节点或者有多个儿子我们可以直接根据反馈的颜色情况来判断该选哪个颜色

而对于那些向上和向下都只有一条边的点，我们显然需要钦定它们都选择走某种颜色的边才行，否则一定会出现冲突

然后如果直接按这个思路去写的话会WA在第四个点，而我也是凭借着靠赛后补题时可以直接看数据这一点，发现对于根节点的每个儿子的颜色选择是需要枚举的，加上这个判断后就过了

#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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=105;
int n,fa[N],col[N],tp[2],c[5]; bool sign; vector <int> v[N];
inline void DFS1(CI now=1)
{
	for (auto to:v[now]) col[to]=col[now]^1,DFS1(to);
	if (now!=1&&v[now].size()==1)
	{
		if (col[now]==1) sign=0;
	}
}
inline void DFS2(CI now=1)
{
	for (auto to:v[now]) col[to]=(col[now]+1)%3,DFS2(to);
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; bool flag=1; for (scanf("%d",&n),i=2;i<=n;++i)
	if (scanf("%d",&fa[i]),v[fa[i]].push_back(i),fa[i]!=1) flag=0;
	if (flag)
	{
		for (printf("%d\n",1),i=2;i<=n;++i) printf("%d%c",1," \n"[i==n]);
		fflush(stdout); int x; for (i=1;i<=2;++i) scanf("%d",&x);
		printf("%d\n",1); fflush(stdout); scanf("%d",&x); return 0;
	}
	flag=1; for (auto x:v[1])
	{
		col[x]=0; sign=1; DFS1(x); if (sign) continue;
		col[x]=1; sign=1; DFS1(x); if (sign) continue;
		flag=0;
	}
	if (flag)
	{
		for (printf("%d\n",2),i=2;i<=n;++i) printf("%d%c",col[i]+1," \n"[i==n]);
		fflush(stdout); int x; scanf("%d",&x);
		while (x!=1)
		{
			for (i=1;i<=2;++i) scanf("%d",&c[i]);
			if (c[1]==0) printf("%d\n",2),fflush(stdout); else
			if (c[2]==0) printf("%d\n",1),fflush(stdout); else
			printf("%d\n",c[1]<=c[2]?1:2),fflush(stdout);
			scanf("%d",&x);
		}
		return 0;
	}
	for (DFS2(),printf("%d\n",3),i=2;i<=n;++i) printf("%d%c",col[i]+1," \n"[i==n]);
	fflush(stdout); int x; scanf("%d",&x);
	while (x!=1)
	{
		for (i=1;i<=3;++i) scanf("%d",&c[i]);
		if (c[1]&&c[2]==0&&c[3]==0) printf("%d\n",1),fflush(stdout); else
		if (c[2]&&c[1]==0&&c[3]==0) printf("%d\n",2),fflush(stdout); else
		if (c[3]&&c[1]==0&&c[2]==0) printf("%d\n",3),fflush(stdout); else
		if (c[1]==0) printf("%d\n",2),fflush(stdout); else
		if (c[2]==0) printf("%d\n",3),fflush(stdout); else
		if (c[3]==0) printf("%d\n",1),fflush(stdout);
		scanf("%d",&x);
	}
	return 0;
}

F. Last Man Standing

这题真的有2800吗……感觉如果能把根号做法放过去的话2000都没有

首先讲一下我的做法吧，不难发现对于某个\(x\)，一个人能撑的回合数为\(\lceil\frac{a_i}{x}\rceil\times h_i\)

而显然我们只要枚举\(x\in[1,2\times 10^5]\)中的每个数即可，而显然对于每个\(x\)我们只关心\(\lceil\frac{a_i}{x}\rceil\)发生改变的那些位置

刚开始还想着上取整有没有类似下取整的除法分块之类的东西，后面仔细一想其实\(\lceil\frac{a_i}{x}\rceil=\lfloor\frac{a_i-1}{x}\rfloor+1\)，因此直接套除法分块就行了

我们找出所有值改变点后，从大到小枚举\(x\)（因为这样可以使得每个点的贡献都是增加的），并记录此时的最大/次大值更新答案即可

总复杂度\(O((n+a_i)\times \sqrt {a_i})\)，可惜跑不过这题的时限的说

#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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,h[N],a[N],sz[N]; LL ans[N],val[N]; vector <int> 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)
		ans[i]=0,scanf("%d",&h[i]),val[i]=h[i];
		for (i=1;i<=200000;++i) vector<int>().swap(pos[i]),sz[i]=0;
		for (i=1;i<=n;++i)
		{
			scanf("%d",&a[i]); ++sz[a[i]]; --a[i];
			for (RI l=1,r;l<=a[i];l=r+1)
			r=a[i]/(a[i]/l),++sz[r];
		}
		for (i=1;i<=200000;++i) pos[i].reserve(sz[i]+1);
		for (i=1;i<=n;++i)
		{
			pos[a[i]+1].emplace_back(i);
			for (RI l=1,r;l<=a[i];l=r+1)
			r=a[i]/(a[i]/l),pos[r].emplace_back(i);
		}
		int mx=0,smx=0; for (i=1;i<=n;++i)
		if (val[i]>val[mx]) smx=mx,mx=i;
		else if (val[i]>val[smx]) smx=i;
		for (i=200000;i>=1;--i)
		{
			for (auto x:pos[i])
			{
				val[x]=1LL*h[x]*(a[x]/i+1);
				if (x==mx) continue; else
				if (x==smx)
				{
					if (val[smx]>val[mx]) swap(mx,smx);
				} else
				{
					if (val[x]>val[mx]) smx=mx,mx=x;
					else if (val[x]>val[smx]) smx=x;
				}
			}
			ans[mx]=max(ans[mx],val[mx]-val[smx]);
		}
		for (i=1;i<=n;++i) printf("%lld%c",ans[i]," \n"[i==n]);
	}
	return 0;
}

后面看了题解的做法才发现其实我们可以直接枚举\(x\)，考虑每次\(\lceil\frac{a_i}{x}\rceil\)取值不同的区间分别是\([1,x],[x+1,2x],\cdots\)

不难发现直接枚举的话复杂度是调和级数的，而对于每个区间内它们\(\lceil\frac{a_i}{x}\rceil\)的贡献都相同，因此只看\(h_i\)的大小，因此只要用类似于ST表的东西维护下区间最大值/次大值即可

但实际实现的时候其实可以不用写ST表，考虑我们直接记录每个值的后缀\(h_i\)的最大/次大值，每次枚举的时候更新一定不会把答案算少，因此还是正确的

当然不管怎么实现复杂度都是\(O((n+a_i)\log a_i)\)的

#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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,h[N],a[N],mx[N],smx[N]; LL ans[N]; vector <int> pos[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j,k; for (scanf("%d",&n),i=1;i<=n;++i)	ans[i]=0,scanf("%d",&h[i]);
		for (i=1;i<=200000;++i) pos[i].clear();
		for (i=1;i<=n;++i) scanf("%d",&a[i]),pos[a[i]].push_back(i);
		for (i=200000;i>=1;--i)
		{
			mx[i]=mx[i+1]; smx[i]=smx[i+1];
			for (auto x:pos[i])
			{
				if (h[x]>h[mx[i]]) smx[i]=mx[i],mx[i]=x;
				else if (h[x]>h[smx[i]]) smx[i]=x;
			}
		}
		for (i=1;i<=200000;++i)
		{
			auto calc=[&](CI x)
			{
				return 1LL*((a[x]+i-1)/i)*h[x];
			};
			int MX=0,SMX=0;
			for (j=1;j<=200000;j+=i)
			{
				if (mx[j]!=MX&&mx[j]!=SMX)
				{
					if (calc(mx[j])>calc(MX)) SMX=MX,MX=mx[j];
					else if (calc(mx[j])>calc(SMX)) SMX=mx[j];
				}
				if (smx[j]!=MX&&smx[j]!=SMX)
				{
					if (calc(smx[j])>calc(MX)) SMX=MX,MX=smx[j];
					else if (calc(smx[j])>calc(SMX)) SMX=smx[j];
				}
			}
			ans[MX]=max(ans[MX],calc(MX)-calc(SMX));
		}
		for (i=1;i<=n;++i) printf("%lld%c",ans[i]," \n"[i==n]);
	}
	return 0;
}

Postscript

明天开始国庆放假，前几天自己队里组织下训练，后面学校集训队有统一安排的训练，还是很充实的说

标签：Educational,Rated,155,int,typedef,long,include,mx,define
From： https://www.cnblogs.com/cjjsb/p/17736402.html

相关文章

  • 加训日记 Day4——挑战edu155，铭记巅峰的一集
    Day4，9.24edu155  ·打满六场新手保护赛之后的第一场（早知道暑假就不打那几场浪费保护了）  ·这场不出意外就是出意外了，库函数用的不熟练，奇奇怪怪的地方爆LL  ·C题赛后10分钟内看了看别人思路补出来了，进入思维误区了属于是  ·打完这场掉了25分捏，我觉得罚时得背大锅，越w......
  • CF957 Codeforces Round 472 (rated, Div. 2, based on VK Cup 2018 Round 2)
    CF957ATritonicIridescence如果原序列中有两个相同的字符，显然不合法。如果开头或者结尾为?，或者有两个连续的?，或者一个?两边的字符不同显然合法。否则一定不合法。#include<iostream>#include<cstdio>usingnamespacestd;constintN=105;intn;chars[N];intma......
  • CF1036 Educational Codeforces Round 50 (Rated for Div. 2)
    CF1036AFunctionHeight答案为\(\lceil\frac{k}{n}\rceil\)。#include<iostream>#include<cstdio>usingnamespacestd;longlongn,k;intmain(){ scanf("%lld%lld",&n,&k); printf("%lld",(k+n-1)/n); return0;}......
  • GENERATED_BODY()函数是什么？
    会发现它是一个宏定义//Includearedundantsemicolonattheendofthegeneratedcodeblock,sothatintellisenseparserscanstartparsing//anewdeclarationifthelinenumber/generatedcodeisoutofdate.#defineGENERATED_BODY_LEGACY(...)BODY_MACRO......
  • Educational Codeforces Round 155 D (CF1879_D)
    题目大意给一个长度为\(n\)的数组，求\(\Sigma_{i=1}^{n}\Sigma_{j=i}^{n}区间异或和\times(j-i+1)\)其中\(n\leq3e5,~a[i]\leq1e9\)分析首先注意到由\(l\)到\(r\)的区间异或和可以转化为\(sum_{l-1}~XOR~sum_r\)因此，对于每一个点\(x\)，无论它作为上述的\(sum......
  • # Tensorflow Federated (tff)
    TensorflowFederated(tff)1.安装pipinstalltensorflow-federated可通过以下方式检查已安装成功，importtensorflow_federatedastffprint(tff.federated_computation(lambda:'HelloWorld')())理想输出，2.数据tff.simulation.datasetstff.simulation下的一个模......
  • Educational Codeforces Round 155 (Rated for Div. 2)
    EducationalCodeforcesRound155(RatedforDiv.2)A.Rigged!解题思路:若存在\(s[i]>=s[1]\)并且\(e[i]>=e[i]\),那么答案为\(-1\).否则，答案为\(s[1]\).代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constintN=1e6+10;con......
  • CF_EduRound155小丑寄
    一句话总结：A题理解错了，数据又水，所以寄了。过程：22:35开题。22:40怎么还没加载出来？？急急急22:42哦，严格大于，但是主宾对调了，乐乐乐乐乐乐乐，cout<<ans;\(\rightarrow\)cout<<ans-1;22:45一发过。。。22:45-23:38啥事没有。23:38开E题23:50左右好像有点思路......
  • Educational Codeforces Round 155 (Rated for Div. 2)
    比赛链接A.Rigged!题目链接就是一个比较简单的模拟就可以解决，如何判断能不能第一只需要考虑比他力量大的耐力是不是也比他大就行，而只要比他大，他就不可能第一，否则输出他的力量作为标杆就行，这样也可以避免比他力量小的也可以举起来。#include<bits/stdc++.h>usingnamespaces......
  • Educational Codeforces Round 97 (Rated for Div 2) G. Death DBMS
    Problem-G-Codeforces题意给定n个字符串，每个字符串有一个值val，n次询问，每次给一个字符串，询问给定n个字符串中是询问字符串子串的值的最大值分析多模式匹配，从中找到给定串的子串，想到建立ac自动机，对于给定字符串，在自动机上面匹配时，沿fail指针向上跳并求最大值即可，由于n个字符......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99