首页 > 其他分享 >CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)

CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)

时间：2023-09-21 20:57:55浏览次数：52  
标签：typedef Rated int long Prizes pair Div include define

Preface

这场因为晚上去做大物实验了，到寝室洗完澡都11点了，就没现场打了的说

后面补题发现前5题都很一眼，虽然补题的时候E题FST了（T在了42个点，如果放在比赛就FST了），F题还是很有意思的一个题目的说

A. MEXanized Array

简单讨论一下即可

#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;
int t,n,k,x;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d%d",&n,&k,&x);
		if (k>n||k>x+1) { puts("-1"); continue; }
		printf("%d\n",k*(k-1)/2+(n-k)*(k==x?k-1:x));
	}
	return 0;
}

B. Friendly Arrays

稍加思索会发现当\(n\)是偶数时，每或上一个数都不会让答案变大，同理当\(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<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,m,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%d",&n,&m),i=1;i<=n;++i) scanf("%d",&a[i]);
		int all=0; for (i=1;i<=m;++i) scanf("%d",&b[i]),all|=b[i];
		int ans1=0,ans2=0; for (i=1;i<=n;++i) ans1^=a[i],ans2^=a[i]|all;
		if (ans1>ans2) swap(ans1,ans2); printf("%d %d\n",ans1,ans2);
	}
	return 0;
}

C. Colorful Table

稍微手玩一下会发现对于每个数，所有大于等于它的数所在的位置的下标，在矩阵中对应的行列都会有这个数

因此从大到小加入每个数，统计此时下标的最大最小值即可

#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=100005;
int t,n,k,x,l,r,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; for (scanf("%d%d",&n,&k),i=1;i<=k;++i) pos[i].clear();
		for (i=1;i<=n;++i) scanf("%d",&x),pos[x].push_back(i);
		for (l=n+1,r=0,i=k;i>=1;--i)
		{
			if (pos[i].empty()) { ans[i]=0; continue; }
			for (auto x:pos[i]) l=min(l,x),r=max(r,x);
			ans[i]=2*(r-l+1);
		}
		for (i=1;i<=k;++i) printf("%d%c",ans[i]," \n"[i==k]);
	}
	return 0;
}

D. Prefix Purchase

首先可以对输入的序列做一个单调栈的处理，剔除掉那些绝对无用的元素

那么剩下的元素的\(c_i\)一定单调增，由于要让字典序最大，因此我们要从前往后依次保证每个数的取值时最大的

可以用如下的贪心策略，首先先假设取了\(\lfloor \frac{k}{c_1}\rfloor\)个\(c_1\)，这一定是最后\(a_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;
int t,n,k,c[N],stk[N],top,d[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) d[i]=0,scanf("%d",&c[i]);
		for (top=0,i=1;i<=n;++i)
		{
			while (top&&c[stk[top]]>=c[i]) --top;
			stk[++top]=i;
		}
		scanf("%d",&k); d[stk[1]]+=k/c[stk[1]]; int left=k%c[stk[1]];
		for (i=1;i<top;++i)
		{
			if (!d[stk[i]]) break; int tmp=min(d[stk[i]],left/(c[stk[i+1]]-c[stk[i]]));
			d[stk[i+1]]+=tmp; d[stk[i]]-=tmp; left-=tmp*(c[stk[i+1]]-c[stk[i]]);
		}
		for (i=n-1;i>=1;--i) d[i]+=d[i+1];
		for (i=1;i<=n;++i) printf("%d%c",d[i]," \n"[i==n]);
	}
	return 0;
}

E. Another MEX Problem

这题上来有一个很trivial的\(O(n^3)\)做法，考虑设\(f_i\)作为集合存储所有以\(i\)为右端点结尾，能得到的数的异或和，转移就是枚举每个区间进行转移

但如果只是这样做的话就没有利用到题目中\(\operatorname{MEX}\)的性质了，因此我们考虑利用一下

首先有个很直观的想法就是当固定左端点时，随着右端点的移动，只有那些\(\operatorname{MEX}\)发生了改变的位置才有意义

而直觉告诉我们对于所有的左端点，其有效的右端点的数量之和不会很大，因此可以预处理出来再转移，然后交一发就会喜提TLE on 42

但我们还可以加一个同质的优化，即固定右端点时，向左移动左端点，只允许\(\operatorname{MEX}\)发生改变的位置进行转移，这样就可以通过此题了

#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=5005;
int t,n,a[N]; bool g[N][N],vis[N<<1],ext[N][N<<1]; vector <pi> pos[N]; vector <int> f[N],S;
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),S.clear(),i=1;i<=n;++i)
		scanf("%d",&a[i]),pos[i].clear(),f[i].clear();
		for (i=1;i<=n;++i)
		{
			for (j=0;j<=n;++j) vis[j]=g[i][j]=0; int mex=0,lst=0;
			for (j=i;j<=n;++j)
			{
				vis[a[j]]=1; while (vis[mex]) ++mex; if (mex==0) continue;
				if (mex!=lst) g[i][j]=1; lst=mex;
			}
			for (j=0;j<=n*2;++j) ext[i][j]=0;
		}
		for (i=n;i>=1;--i)
		{
			for (j=0;j<=n;++j) vis[j]=0; int mex=0,lst=0;
			for (j=i;j>=1;--j)
			{
				vis[a[j]]=1; while (vis[mex]) ++mex; if (mex==0) continue;
				if (mex!=lst&&g[j][i]) pos[j].push_back(pi(i,mex)); lst=mex;
			}
		}
		for (i=0;i<=2*n;++i) vis[i]=0;
		for (S.push_back(0),vis[0]=1,i=1;i<=n;++i)
		{
			for (auto pre:S) for (auto [end,val]:pos[i])
			if (!ext[end][pre^val]) ext[end][pre^val]=1,f[end].push_back(pre^val);
			for (auto val:f[i]) if (!vis[val]) vis[val]=1,S.push_back(val);
		}
		printf("%d\n",*max_element(S.begin(),S.end()));
	}
	return 0;
}

F. Lazy Numbers

好神的题

首先发现如果我们建出一个\(n\)个点的Trie，其中每个点有\(k\)个分支

那么某个点原来的编号相当于是它在Trie上的BFS序，而排序过后的编号相当于是DFS序，而我们要求的就是这两者相同的点的个数

注意到一个重要的性质，在同一层的相邻两点之间，BFS序的增量始终为\(1\)，而DFS序的增量始终\(\ge 1\)

换句话说，DFS序减去BFS序的值在同一层中是单调不减的，因此我们可以用二分快速地找到差值为\(0\)的那一段

剩下的部分就是考虑给定\(x\)，如何求\([1,n]\)中字典序小于等于\(x\)的数的个数，当然可以用数位DP来实现，但这里讲一种更简便的方法

我们如果从低位到高位依次删去\(x\)末尾的数，把现在的数记为\(x'\)，那么所有剩下位数和\(x'\)位数一致的数中，小于等于\(x'\)的数的个数都有贡献

同理还可以在\(x'\)后面依次添上\(0\)得到\(x''\)，则所有剩下位数和\(x''\)位数一致的数中，小于\(x''\)的数的个数都有贡献

这样这题就做完了，单组数据复杂度\(O(\log^3 n)\)（枚举层数，二分，计算排名都是单\(\log\)的）

#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;
int t,n,k,a[70],len,pw[70],l[70],r[70];
inline int calc(int x)
{
	static int b[70]; int cur=0,ret=0; RI i;
	while (x) b[++cur]=x%k,x/=k; reverse(b+1,b+cur+1);
	i128 pre=0; for (i=1;i<=cur;++i)
	pre=pre*k+b[i],ret+=min((int)pre,r[i])-l[i]+1;
	for (i=cur+1;i<=len;++i)
	pre=pre*k,ret+=(int)min(pre-1,(i128)r[i])-l[i]+1;
	return ret;
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		scanf("%lld%lld",&n,&k); int tmp=n; len=0;
		while (tmp) a[++len]=tmp%k,tmp/=k;
		RI i; i128 pw=1; int ans=0;
		for (i=1;i<=len;++i)
		{
			l[i]=pw; r[i]=(int)min((i128)n,pw*k-1);
			pw*=k; if (pw>n) break;
		}
		for (i=1;i<=len;++i)
		{
			int L=l[i],R=r[i],mid,lb=-1,rb=-1;
			while (L<=R)
			{
				mid=L+(R-L)/2; tmp=calc(mid)-mid;
				if (tmp==0) lb=mid;
				if (tmp<0) L=mid+1; else R=mid-1;
			}
			if (!~lb) continue; L=l[i]; R=r[i];
			while (L<=R)
			{
				mid=L+(R-L)/2; tmp=calc(mid)-mid;
				if (tmp==0) rb=mid;
				if (tmp>0) R=mid-1; else L=mid+1;
			}
			ans+=rb-lb+1;
		}
		printf("%lld\n",ans);
	}
}

Postscript

这场补完还有周日的ARC要补，不过幸好明天运动会放假，可以用来补一下

标签：typedef,Rated,int,long,Prizes,pair,Div,include,define
From： https://www.cnblogs.com/cjjsb/p/17720915.html

相关文章

  • 题解 ARC141D【Non-divisible Set】
    这个题不是网络流。problem我们说一个集合\(D\)是一个好的集合，当不存在集合中的两个不同元素\(a,b\)使得\(a\)是\(b\)的约数。给定\(N\)个整数的一个集合\(S\)，值域均落在\([1,2*M]\)内。对\(S\)中的每个元素\(A_i\)询问：是否存在一个恰好包含\(A_i\)的\(......
  • selenium 报错 element not interactable: [object HTMLDivElement] has no size and
    selenium自动化识别验证码x,y坐标 命令move_to_element_with_offset报错：elementnotinteractable:[objectHTMLDivElement]hasnosizeandlocation由于>4.0是以中心点偏移，4.0是左上角偏移。卸载掉最新的seleniuim：pipuninstallselenium安装selenium4.0：pipinstalls......
  • CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) 更新ing
    A.MEXanizedArray题意给你三个数\(n\)、\(k\)、\(x\)，让你求出能否构造出mex为\(k\)，且所有数字都不超过\(x\)，大小为\(n\)的数组。线索1如果有存在-1情况，先想啥时候不可能，如果能一下子找到-1的情况，这个题会很简单，因为可以的情况反推过去很容易，如果特判复杂就想想是不是诈骗规......
  • 在开启contenteditable可编辑div光标处插入图片
     $("#Content").focus();//创建img元素varimg=document.createElement('img');img.src='xxxx';img.style.display='block';//插入img元素if(window.getSelection){vareditableDiv=document.getEle......
  • <div>标签
    1.盒子模型(上右下左顺时针顺序设置属性值)1.1外边距margin1.2内边距padding1.3边框bordersoliddashed例如：（border:1pxdashedblack）意思就是设置1个像素的黑色虚线边框1.4阴影box-shadow:h-shadow水平阴影的位置  v-shadow垂直阴影的位置  blur模糊距离  sprea......
  • div 拖动例子
    第一个是简单的例子：<!DOCTYPEHTMLPUBLIC"-//W3C//DTDHTML4.01Transitional//EN"><html> <head> <title>dragTest</title> <metahttp-equiv="content-type"content="text/html;charset=UTF-8"> <......
  • Educational Codeforces Round 154 (Rated for Div. 2) A-D
    传送门：edu154/div2A.PrimeDeletion题意：给定一个0-9的排列，要求一个长度>=2的子序列，使得该子序列是质数做法：考虑31或者13即可。不过当时没有立刻想到，感觉1000以内的质数必有答案，打了暴力。用时就多了点。Code#include<bits/stdc++.h>usingnamespacestd;intpri[10......
  • CF1870 div1+div2做题记录
    A题面挺蠢的，无解条件为\(n<k\)或\(x<k-1\)，即\(\mathop{\mathrm{mex}}\not=k\)。先选\(0\simk-1\)，再选能选的最大值，当\(x=k\)，选\(x-1\)，否则选\(x\)。点击查看代码#include<bits/stdc++.h>#defineullunsignedlonglong#definelllonglong#definepiipai......
  • CodeTON Round 6 (Div. 1 + Div. 2)( A-D )
    A.MEXanizedArray下次还得得签快一点，嘉心糖4分就过了思路一个简单的讨论nkx之间关系就行完整代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglonginlineintread(){ints=0,w=1;charg=getchar();while(g>'9'||g<'0'){if(g=......
  • CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)(A-D)
    CodeTONRound6(Div.1+Div.2,Rated,Prizes!)A.让你找mex为k的n个数，这n个数从0-x，问n个数的和最大值是多少先判断不行的。然后行的肯定有0-k-1，剩下还有就选x就行。查看代码#include<iostream>usingnamespacestd;typedeflonglongll;voidsolve(){ intn,k,x;......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99