526互联

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

发布时间 2023-09-21 20:46:41作者: 空気力学の詩

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要补，不过幸好明天运动会放假，可以用来补一下