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

Codeforces Round 893 (Div. 2)

时间：2023-08-17 20:56:45浏览次数：37  
标签：typedef 893 int Codeforces long -- Div include define

Preface

最战俘的一场，B题写挂一发后整个人脑子就不清醒了，放着D不写去写E1，然后忘了可持久化栈有一个经典的倍增写法，最主要当时暑假前集训我还上去讲了这个东西然后比赛的时候还没想起来

后面目送徐神爆切5题成功完成两场从蓝上橙，狠狠地把我这个在紫卡了半年的废物羞辱了一波

不过确实说实话我们队比赛后期我也基本全程划水，真大腿还得看徐神的说

A. Buttons

签到题，每个人肯定优先按公用的按钮然后再按自己的

#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<functional>
#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;
int t,a,b,c;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d%d",&a,&b,&c);
		int sa=a+(c+1)/2,sb=b+c/2;
		puts(sa>sb?"First":"Second");
	}
	return 0;
}

B. The Walkway

最难读懂题目的一题，最后这题过的人比C少到不知道哪里去了

其实就是枚举删掉哪个点，每两个点之间的贡献也很好预处理出来，只不过细节比较多容易写挂

#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<functional>
#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=100005;
int t,n,m,d,a[N],pfx[N],sfx[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%d",&n,&m,&d),i=1;i<=m;++i) scanf("%d",&a[i]);
		for (a[0]=1,pfx[0]=1,i=1;i<=m;++i)
		{
			if (a[i]==1) { pfx[i]=1; continue; }
			pfx[i]=pfx[i-1]+(a[i]-a[i-1]-1)/d+1;
		}
		for (a[m+1]=n+1,sfx[m+1]=0,i=m;i>=1;--i) sfx[i]=sfx[i+1]+(a[i+1]-a[i]-1)/d+1;
		int mi=2e9,num; for (i=1;i<=m;++i)
		{
			int tmp=pfx[i-1]+sfx[i+1]+(a[i+1]-a[i-1]-1)/d;
			if (tmp<mi) mi=tmp,num=1; else if (tmp==mi) ++num;
		}
		printf("%d %d\n",mi,num);
	}
	return 0;
}

C. Yet Another Permutation Problem

纯签到题，看一眼就会了的C还有什么出的必要吗

对于每个质数\(p_i\)，将范围内的\(2p_i,4p_i,8p_i\cdots\)都依次放在它后面即可

#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<functional>
#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=100005;
int t,n; bool vis[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) vis[i]=0;
		vector <int> ans; ans.push_back(1); vis[1]=1;
		for (i=2;i<=n;++i) if (!vis[i])
		for (j=i;j<=n;j<<=1) if (!vis[j]) ans.push_back(j),vis[j]=1;
		for (int x:ans) printf("%d ",x); putchar('\n');
	}
	return 0;
}

D. Trees and Segments

比赛的时候心态崩了完全想不进去，其实不是很难的一个题

考虑我们可以枚举一段区间\([l,r]\)，将它全部变成\(0\)，然后以此作为我们最后的最长连续\(0\)的区间

然后对于\([1,l-1],[r+1,n]\)可以分别预处理出在分配了若干次修改后，可以得到的最长连续\(1\)的长度

可以用上面的信息求出当最长连续\(0\)的区间长为\(i\)时，最长连续\(1\)的区间长为\(len_i\)，最后我们枚举系数\(a\)更新答案即可

具体实现看代码，不难发现所有东西的处理都是\(O(n^2)\)的

#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<functional>
#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=3005;
int t,n,k,a[N],pfx[N][2],pre[N][N],suf[N][N],len[N],ans[N]; char s[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%d%s",&n,&k,s+1),i=1;i<=n;++i)
		pfx[i][1]=pfx[i-1][1]+(s[i]=='1'),pfx[i][0]=pfx[i-1][0]+(s[i]=='0');
		auto calc=[&](CI l,CI r,CI tar)
		{
			return pfx[r][tar^1]-pfx[l-1][tar^1];
		};
		for (i=0;i<=n+1;++i) for (j=0;j<=n+1;++j) pre[i][j]=suf[i][j]=0;
		for (i=0;i<=n;++i) len[i]=ans[i]=-1;
		for (i=1;i<=n;++i) for (j=i;j<=n;++j)
		pre[j][calc(i,j,1)]=max(pre[j][calc(i,j,1)],j-i+1),
		suf[i][calc(i,j,1)]=max(suf[i][calc(i,j,1)],j-i+1);
		for (i=1;i<=n;++i) for (j=0;j<=n;++j) if (j) pre[i][j]=max(pre[i][j],pre[i][j-1]);
		for (j=0;j<=n;++j) for (i=1;i<=n;++i) pre[i][j]=max(pre[i][j],pre[i-1][j]);
		for (i=n;i>=1;--i) for (j=0;j<=n;++j) if (j) suf[i][j]=max(suf[i][j],suf[i][j-1]);
		for (j=0;j<=n;++j) for (i=n;i>=1;--i) suf[i][j]=max(suf[i][j],suf[i+1][j]);
		for (len[0]=pre[n][k],i=1;i<=n;++i) for (j=i;j<=n;++j)
		if (calc(i,j,0)<=k) len[j-i+1]=max(len[j-i+1],max(pre[i-1][k-calc(i,j,0)],suf[j+1][k-calc(i,j,0)]));
		for (i=1;i<=n;++i) for (j=0;j<=n;++j) if (~len[j]) ans[i]=max(ans[i],i*j+len[j]);
		for (i=0;i<=n+1;++i) for (j=0;j<=n+1;++j) pre[i][j]=suf[i][j]=0;
		for (i=0;i<=n;++i) len[i]=-1;
		for (i=1;i<=n;++i) for (j=i;j<=n;++j)
		pre[j][calc(i,j,0)]=max(pre[j][calc(i,j,0)],j-i+1),
		suf[i][calc(i,j,0)]=max(suf[i][calc(i,j,0)],j-i+1);
		for (i=1;i<=n;++i) for (j=0;j<=n;++j) if (j) pre[i][j]=max(pre[i][j],pre[i][j-1]);
		for (j=0;j<=n;++j) for (i=1;i<=n;++i) pre[i][j]=max(pre[i][j],pre[i-1][j]);
		for (i=n;i>=1;--i) for (j=0;j<=n;++j) if (j) suf[i][j]=max(suf[i][j],suf[i][j-1]);
		for (j=0;j<=n;++j) for (i=n;i>=1;--i) suf[i][j]=max(suf[i][j],suf[i+1][j]);
		for (len[0]=pre[n][k],i=1;i<=n;++i) for (j=i;j<=n;++j)
		if (calc(i,j,1)<=k) len[j-i+1]=max(len[j-i+1],max(pre[i-1][k-calc(i,j,1)],suf[j+1][k-calc(i,j,1)]));
		for (i=1;i<=n;++i) for (j=0;j<=n;++j) if (~len[j]) ans[i]=max(ans[i],j+i*len[j]);
		for (i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]);
	}
	return 0;
}

E1. Rollbacks (Easy Version)

想这种有回溯操作的题可以用经典套路在操作间连边建成一棵DFS树，每次在树上完成插入和撤销操作即可

但这题由于要实现弹出栈中元素的功能，直接暴力做肯定会T飞，因此需要用可持久化栈的思路

就是对于每个点倍增维护出向前弹出\(2^k\)个数的状态，然后遇到弹出操作直接把它接在对应的下面即可

总复杂度\(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<functional>
#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=1e6+5;
int q,x[N],tot,ans[N],stk[N],top,bkt[N],cur,anc[N][21]; char opt[10]; vector <int> v[N],ques[N];
inline void add(CI x)
{
	if (++bkt[x]==1) ++cur;
}
inline void del(CI x)
{
	if (--bkt[x]==0) --cur;
}
inline void DFS(CI now)
{
	if (now) add(x[now]); for (int id:ques[now]) ans[id]=cur;
	for (int to:v[now]) DFS(to); if (now) del(x[now]);
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d",&q),i=1;i<=q;++i)
	{
		scanf("%s",opt); ans[i]=-1;
		switch (opt[0])
		{
			case '+':
			{
				int now=++tot; scanf("%d",&x[now]); anc[now][0]=stk[top]; v[stk[top]].push_back(now);
				for (j=0;j<20;++j) anc[now][j+1]=anc[anc[now][j]][j]; stk[++top]=now; break;
			}
			case '-':
			{
				int now=stk[top],k; scanf("%d",&k);
				for (j=0;j<21;++j) if ((k>>j)&1) now=anc[now][j]; stk[++top]=now; break;
			}
			case '!':
				--top; break;
			case '?':
				ques[stk[top]].push_back(i); break;
		}
	}
	//for (i=0;i<=q;++i) for (int x:v[i]) printf("%d -> %d\n",i,x);
	for (DFS(0),i=1;i<=q;++i) if (~ans[i]) printf("%d\n",ans[i]);
	return 0;
}

E2. Rollbacks (Hard Version)

听zzh说好像就是维护每种数第一次出现的位置即可，没太仔细想就先坑着了

Postscript

今晚还有CF，又要被虐杀了……

标签：typedef,893,int,Codeforces,long,--,Div,include,define
From： https://www.cnblogs.com/cjjsb/p/17638815.html

相关文章

  • Educational Codeforces Round 109 (Rated for Div. 2)
    EducationalCodeforcesRound109(RatedforDiv.2)A-Potion-making思路：求最小操作数即药水最简比#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong//#defineint__int128#definedoublelongdoubletypedefpair<int,int>PII;typedefpair......
  • Codeforces Round 883 (Div. 3)
    比赛链接：https://codeforces.com/contest/1846A.RudolphandCuttheRope题意：给n条绳子，知道一端所在高度坐标和各自绳长，他们另一端都连到一个糖果上，问至少剪掉多少绳子糖果能碰到地面思路：显然只有坐标小于绳长的才能让糖果触地，去掉其他的即可B.RudolphandTic-Tac-Toe题......
  • Codeforces Round 892 (Div. 2)
    CodeforcesRound892(Div.2)目录CodeforcesRound892(Div.2)AUnitedWeStandBOlyaandGamewithArraysCAnotherPermutationProblemDAndreyandEscapefromCapygradEMaximumMonogonosityAUnitedWeStand给定长度为\(n\)的数组a，可以将a中元素添加到空数组b......
  • 2023.08.12 codeforces round 893 div2
    年轻人的第四场div2rank:8217solved:2ratingchange:+31newrating:1354A.Buttons题意：给定a,b,c三种按钮的数量，a按钮只能被Anna按，b按钮只能被Katie按，两个人都可以按c按钮，最后没有按钮可以按的人输，Anna先手，问谁是赢家；两个人肯定优先按c按钮，且Anna是先手，只需比较两人能按的按......
  • Codeforces Round 891 (Div. 3)
    比赛链接：https://codeforces.com/contest/1857A.ArrayColoring题意：一个数列，问能否分成两个和的奇偶性相同的集合思路：因为偶数不改变奇偶性，咱们就统计奇数的个数，能平分成两组就行B.MaximumRounding题意：给一个数，每次可以找一位数不四舍可五入，然后把这个位及后面的数都变成......
  • IE中div被视频遮住的解决方法
    使用embed来内嵌视频，因为视频是windowsmediaplayer，上面想用div浮动一些内容，之前尝试了一些方法，比如1.通过设定不同组件的z-index值2.通过设定wmode值结果都没有效果。最后设定了windowlessVideo=1，终于解决问题。 具体说明一下：“windowlessVideo”属性如为true，则设置成无窗......
  • Educational Codeforces Round 107 (Rated for Div. 2)
    EducationalCodeforcesRound107(RatedforDiv.2)A-ReviewSite思路：数1和3的个数#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong//#defineint__int128#definedoublelongdoubletypedefpair<int,int>PII;typedefpair&l......
  • Codeforces Round 765 (Div. 2) A-E
    A.AncientCivilization好像就是对每个二进制位看一下0多还是1多，选择多的那个数就好了。vp的时候直接猜的，交了一发直接过了voidsolve(){intn=read(),m=read();vector<int>cnt0(m+1),cnt1(m+1);for(inti=1;i<=n;i++){intx=read();for(int......
  • Codeforces Round 893（div2）
    CodeforcesRound893（div2）[A题传送门](Problem-A-Codeforces)A题意：我们有a+b+c个瓶盖，选手1可以拿指定的a个或者c个里面的一个，选手2可以拿指定的b个或者c个里面的一个，可以拿完最后一个的即为获胜者，每个人都有最优策略。A思路：这个题一开始想错了，主要是没有读懂题意，理解清楚......
  • AGC064C Erase and Divide Game
    题面传送门首先考虑你只插入若干个数怎么做：按位从低到高插入一棵Trie，问题就变成：在Trie上每次可以往左儿子走或者往右儿子走，如果当某个人操作的时候为空节点那么这个人就输了。如果我们可以将这棵树建出来那么这个问题就是好解决的，可惜建不出来。仿照从高到低建Trie的方法，将......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99