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

Codeforces Round 899 (Div. 2)

时间：2023-09-27 11:14:33浏览次数：42  
标签：typedef now int 899 Codeforces long Div include define

Preface

好久没现场打CF了（玩CC玩的.jpg），但这场久违的打的还不错，把Kusanagi_Misuzu这个小号也打上橙了

虽然开场的时候状态不佳写的巨慢，但后面还是靠着ztc带我做出E1成功题数反超上大分

接下来要考虑启动第三个小号了，只敢打Div2的FW是这样的

A. Increasing Sequence

比赛时候降智了竟然想去写二分答案，后面写了一半发现我脑子可能有问题

直接从前往后依次检验贪心放是否合法即可

#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,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)
		{
			b[i]=b[i-1]+1;
			if (b[i]==a[i]) ++b[i];
		}
		printf("%d\n",b[n]);
	}
	return 0;
}

B. Sets and Union

刚开始拿到这个题还愣了一会，后面才反应过来是个傻逼题

考虑最后的\(S\)既然不能等于全集，那么至少存在一个和全集不同的元素

我们不妨大力枚举这个不同的元素是什么，那么贪心地把所有不包含这个元素的集合的并求出来更新答案即可

#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=55;
int t,n,k[N],x,vis[N][N],ext[N]; vector <int> num[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; memset(vis,0,sizeof(vis)); memset(ext,0,sizeof(ext));
		for (scanf("%d",&n),i=1;i<=n;++i)
		for (scanf("%d",&k[i]),num[i].clear(),j=1;j<=k[i];++j)
		scanf("%d",&x),num[i].push_back(x),vis[x][i]=ext[x]=1;
		int ans=0; for (i=1;i<=50;++i) if (ext[i])
		{
			unordered_set <int> s;
			for (j=1;j<=n;++j) if (!vis[i][j])
			for (auto x:num[j]) s.insert(x);
			ans=max(ans,(int)s.size());
		}
		printf("%d\n",ans);
	}
	return 0;
}

C. Card Game

本来想了个比较复杂的做法，后面ztc和我说了才发现是个傻逼题

考虑枚举我们要拿的牌中第一张的位置，显然它后面的所有权值为正的牌我们都可以拿，顺带更新答案即可

#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 int long long
#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,a[N],suf[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]);
		for (suf[n+1]=0,i=n;i>=1;--i) suf[i]=suf[i+1]+(a[i]>0?a[i]:0LL);
		int ans=0; for (i=1;i<=n;++i) ans=max(ans,(i&1?a[i]:0LL)+suf[i+1]);
		printf("%lld\n",ans);
	}
	return 0;
}

D. Tree XOR

经典换根DP

首先考虑有根树怎么做，很容易发现由于我们对根节点进行任何操作都是不优的，因此第一步肯定是把所有根节点的子节点异或上它们两点点权的异或值，以把这些子节点的权值变成和根节点一致

然后往下推，这些点的子节点也要异或上它们与父亲的权值的异或和，剩下的点亦然

因此写成式子，总代价就是\(\sum_{x\ne root} (a_x\oplus a_{fa_x})\times sz_x\)，可以很容易用一个DP来维护每个点子树内的答案

然后再考虑换根操作，稍微画一下图把每次变化的贡献搞清楚就很简单了

#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,a[N],x,y,sz[N]; LL f[N],g[N]; vector <int> v[N];
inline void DFS1(CI now=1,CI fa=0)
{
	sz[now]=1; f[now]=0;
	for (auto to:v[now]) if (to!=fa) DFS1(to,now),sz[now]+=sz[to],f[now]+=f[to];
	if (fa) f[now]+=1LL*(a[now]^a[fa])*sz[now];
}
inline void DFS2(CI now=1,CI fa=0)
{
	for (auto to:v[now]) if (to!=fa)
	g[to]=g[now]-1LL*(a[now]^a[to])*sz[to]+1LL*(a[now]^a[to])*(n-sz[to]),DFS2(to,now);
}
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]),v[i].clear();
		for (i=1;i<n;++i) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
		for (DFS1(),g[1]=f[1],DFS2(),i=1;i<=n;++i) printf("%lld%c",g[i]," \n"[i==n]);
	}
	return 0;
}

E1. Two Permutations (Easy Version)

好题，虽然有很多直觉猜想的成分，但只要能过就行

首先看到题目就感觉是先找到针对单个串的还原方案，然后合并两个串的答案

刚开始想的是由于我们可以通过重复操作\(1,|S|\)来使得一个串不发生改变，因此当且仅当两个串的答案长度的差值为偶数时才有解

但我们伟大的先驱者ztc写完交了一发发现挂了，因此后面随即发现另一个重要的corner case

当某个串长度为奇数时，对其进行串长次\(1\)操作即可在不改变它本身的情况下使得它的答案长度的奇偶性发生改变，从而把原来的无解情况变成有解情况

讨论完合并后我们考虑如何对于一个串求解，这里的思路比较自然，我们考虑依次把每个数接到一段已经恢复顺序的前缀后面

具体地，不妨设此时的序列形如\(x,\cdots,x,1,2,\cdots,i,x,\cdots,x,i+1,x,\cdots,x\)，我们想要把\(i+1\)接到\(i\)的后面而保证前面已经得到的\(1\sim i\)也依然有序

用\(pos(t)\)表示数\(t\)所在的位置，稍微手玩下会发现只要依次操作pivot(pos(i)+1)，pivot(pos(i+1))即可

不难发现这样对于单个串的操作上限为\(2n\)次，加上改变奇偶性需要的\(n\)次，总操作次数为\(3n=7500\le 10000\)，满足题意

#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=2505;
int n,m,x[N<<2],y[N<<2]; vector <int> a,b;
inline VI pivot(VI a,CI n,CI pos)
{
	VI b; RI i; for (i=pos+1;i<n;++i) b.push_back(a[i]);
	b.push_back(a[pos]);
	for (i=0;i<pos;++i) b.push_back(a[i]);
	return b;
}
inline VI solve(VI a,CI n)
{
	RI i,j; VI res; for (i=0;i<n-1;++i)
	{
		int pos; for (j=0;j<n;++j) if (a[j]==i) { pos=j; break; }
		if (pos!=n-1&&a[pos+1]==i+1) continue;
		if (pos!=n-1) a=pivot(a,n,pos+1),res.push_back(pos+1);
		for (j=0;j<n;++j) if (a[j]==i+1) { pos=j; break; }
		a=pivot(a,n,pos); res.push_back(pos);
	}
	return res;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; scanf("%d%d",&n,&m); a.resize(n); b.resize(m);
	for (i=0;i<n;++i) scanf("%d",&a[i]),--a[i];
	for (i=0;i<m;++i) scanf("%d",&b[i]),--b[i];
	VI A=solve(a,n),B=solve(b,m);
	if (A.size()%2!=B.size()%2)
	{
		if (n%2==0&&m%2==0) return puts("-1"),0;
		if (n%2==1)
		{
			VI tmp; for (i=0;i<n;++i) tmp.push_back(0);
			for (auto x:A) tmp.push_back(x); A=tmp;
		} else if (m%2==1)
		{
			VI tmp; for (i=0;i<m;++i) tmp.push_back(0);
			for (auto x:B) tmp.push_back(x); B=tmp;
		}
	}
	if (A.size()<=B.size())
	{
		for (i=0;i<A.size();++i) x[i+1]=A[i];
		for (i=1;i<=B.size()-A.size();i+=2) x[A.size()+i]=0,x[A.size()+i+1]=n-1;
		for (i=0;i<B.size();++i) y[i+1]=B[i];
	} else
	{
		for (i=0;i<B.size();++i) y[i+1]=B[i];
		for (i=1;i<=A.size()-B.size();i+=2) y[B.size()+i]=0,y[B.size()+i+1]=m-1;
		for (i=0;i<A.size();++i) x[i+1]=A[i];
	}
	int lim=max(A.size(),B.size()); printf("%d\n",lim);
	for (i=1;i<=lim;++i) printf("%d %d\n",x[i]+1,y[i]+1);
	return 0;
}

E2. Two Permutations (Hard Version)

E2其实和E1是完全不同的两个题了，看了Tutorial发现做法很巧妙完全想不到，但没太懂怎么实现就先坑了

Postscript

这场题还挺符合我胃口的属于是，久违的上一波大分了

标签：typedef,now,int,899,Codeforces,long,Div,include,define
From： https://www.cnblogs.com/cjjsb/p/17732188.html

相关文章

  • Codeforces Round 738 (Div. 2) A. Mocha and Math
    给一个数组\(a_1，a_2,\cdots,a_n\)。可以执行以下操作任意次：选择\(l,r(1\leql<r\leqn)\)，对于任意\(l\leqi\leqr\)，同时执行所有\(a_{l+i}=a_{l+i}\&a_{r-i}\)。希望经过若干次操作后，\(a\)的最小的最大值。性质：\(x\&y\leqmin(x,y)\)。......
  • Codeforces Round 898 (Div. 4)
    这是我的vp,不是正真的contest. A:不想多说，读者应该可以做到的！！！ B:让g=product(移除掉0的a)：如果有多过1个0答案肯定是0。如果只是有1个0答案就是g。没有0，答案就是max(g/a[i]*(a[i]+1))任何i。 C:没有仔细想那个profit的formula.手打表，sum就可以了。 D:就是双......
  • Codeforces Round 899 (Div. 2)
    赛后四题B题直接枚举不存在的元素即可C题的trick有点像之前abc的某道题，对于奇数位置它一定可以贡献，对于偶数位置，如果它有数选了，那么它就能够贡献。\(f[i]\)表示到前i个且至少选了一个的最大答案。#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#de......
  • Codeforces Round 738 (Div. 2) B. Mocha and Red and Blue
    给一个字符串，包含字符\(B\)，\(R\)，\(?\)。其中\(?\)可能为\(B\)或\(R\)。规定不完美数为字符串中相同字符连续出现的次数，询问一个字符串的最少可能不完美数。观察到\(BR\)或\(RB\)需要尽可能多，于是考虑尽可能让相邻字符不同。容易证明从左往右扫和从右往左扫贡献......
  • Codeforces Round 750 (Div. 2) B. Luntik and Subsequences
    给一个数组\(a_1,a_2,\cdots,a_n\)，定义\(s=\sum_{i=1}^{n}a_i\)。询问有多少个\(a\)的子序列满足\(\suma_{i_k}=s-1\)。显然要选出一个\(1\)不加入子序列，任意一个\(0\)可以加入或不加入子序列。于是\(ans=\binom{cnt1}{1}\cdot2^{cnt0}\)。vi......
  • CF1882 div.2 做题记录
    A题面扫一遍，令\(b_i\rightarrowb_{i-1}+1\)，若\(b_i=a_i\)，\(b_i\rightarrowb_i+1\)。点击查看代码#include<bits/stdc++.h>#defineullunsignedlonglong#definelllonglong#definepiipair<int,int>#definepdipair<double,int>#definepb......
  • Codeforces Round 899 (Div. 2)
    CodeforcesRound899(Div.2)A.IncreasingSequence解题思路：从左往右一个个看，从1开始，如果当前位相同\(+2\)，否则\(+1\)。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constintN=1e6+10;constintM=2*M;constintmod=1e9+......
  • 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......
  • 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......
  • 短视频app源码，自动滚动条挡住 div内容
    短视频app源码，自动滚动条挡住div内容<!DOCTYPEHTMLPUBLIC"-//W3C//DTDHTML4.01Transitional//EN""http://www.w3.org/TR/html4/loose.dtd"><html><head><metahttp-equiv="Content-Type"content="text/html;charset=utf......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99