csp-s模拟46 set read race

题面：https://www.cnblogs.com/Juve/articles/11556809.html

Set：

题干中说的M个数两两不同是说不能重复选同一个位置的数，而不是不能选数值相同的数，所以不用取重

题目中说是子集，其实连续的序列中就有答案

我们处理出mod N下的前缀和，如果有两个前缀和相同，那么选这两个前缀和中间的数即可，因为减完之后余数为0

这样一定能保证正确吗？或者一定存在两个前缀和相等的情况吗？

在mod N先前缀和最多有0～N-1这N种取值，但是一共有N+1个前缀和(sum[0]也算一种)，所以一定有答案

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#define MAXN 1000005

#define re register

using namespace std;

int n,sum[MAXN],a[MAXN],pos[MAXN];

inline int read(){

	re int x=0;re char ch=getchar();

	while(ch<'0'||ch>'9') ch=getchar();

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x;

}

signed main(){

	n=read();

	for(re int i=1;i<=n;++i){

		a[i]=read();

		sum[i]=(sum[i-1]+a[i]%n)%n;

		if(!pos[sum[i]]) pos[sum[i]]=i;

		else{

			re int j=pos[sum[i]];

			printf("%d\n",i-j);

			for(re int p=j+1;p<=i;++p){

				printf("%d ",p);

			}

			puts("");

			return 0;

		}

	}

	return 0;

}

Read：

一个显然的结论，设数量最多的书出现的次数为k，那么答案就是max(0,2×k-n-1)

但是题目卡空间，不能存下，所以我们要想顺序访问每一个元素就让它从新生成一遍

先扫第一遍，记录一个cnt和id，如果cnt=0，那么cnt=1，id=a[i]，

如果id=a[i]，cnt++，如果不等，cnt--，那么最终留下的id就是出现次数最多的

然后再扫一遍统计id出现次数即可

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define re register

using namespace std;

const int MAXN=1005;

int n,m,k,cnt[MAXN],x[MAXN],y[MAXN],z[MAXN],S,id=0,sum=0,ans;

signed main(){

	scanf("%d%d",&m,&k);

	for(int i=1;i<=m;++i) scanf("%d",&cnt[i]);

	for(int i=1;i<=m;++i) scanf("%d",&x[i]);

	for(int i=1;i<=m;++i) scanf("%d",&y[i]);

	for(int i=1;i<=m;++i) scanf("%d",&z[i]);

	S=(1<<k)-1;

	for(int i=1;i<=m;++i){

        if(sum==0) id=x[i],sum=1;

        else if(id==x[i]) ++sum;

        else --sum;

		long long last=x[i];

		for(int j=1;j<cnt[i];++j){

			last=(last*y[i]+z[i])&S;

            if(sum==0) id=last,sum=1;

            else if(id==last) ++sum;

            else --sum;

		}

	}

    sum=0;

    for(int i=1;i<=m;++i){

        n+=cnt[i];

        if(x[i]==id) ++sum;

		long long last=x[i];

		for(int j=1;j<cnt[i];++j){

			last=(last*y[i]+z[i])&S;

            if(last==id) ++sum;

		}

	}

	ans=max(0,sum*2-n-1);

    printf("%d\n",ans);

	return 0;

}

Race：

考虑怎么求出 x 的答案 . 平方相当于是枚举两个人 ( 可以相同 ), 把这两个人同时排在 x 前面的天数计入答案 . 那么对于 x, 如果我们求出 f[i] 也就是能力值的二进制中第 i+1 到 M-1 位都和他相等且第 i 位不同的人有多少个 , 那么这些人是否排在他前面只由第 i 位确定 , 一共有 2^(M-1) 天 , 而且不需要从这些人中枚举两个人了 , 因为直接平方即可 . 我们只要枚举 i 和 j, f[i] 这些人和 f[j] 这些人同时排在他前面的天数为2^(M-2), 所以把 2*f[i]*f[j]*2^(M-2) 计入答案 . 具体实现有很多方法 , 可以用 trie 树实现，记录trie上每一个节点被访问过的次数，在扫每一个a[i]时，它的f数组就是在当前二进制位上与他这一位相反的数被经过的次数，对于tr[root][p]和tr[root][p^1]，因为要xor从0到2^M-1，所以当前位xor出与他相反的次数是tr[root][p]，和它相同的是tr[root][p^1].

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

#include<algorithm>

#define int long long

#define re register

using namespace std;

const int MAXN=6000005;

const int mod=1e9+7;

int n,m,tot=1,ans=0,a[MAXN],f[MAXN];

int tr[MAXN][2],s[MAXN*2];

void insert(int val){

	int root=1;

	for(int i=m-1;i>=0;--i){

		int p=(val>>i)&1;

		if(!tr[root][p]) tr[root][p]=++tot;

		++s[tr[root][p]];

		root=tr[root][p];

	}

}

int query(int val){

	int res=0,root=1;

	for(int i=m-1;i>=0;--i){

		int p=(val>>i)&1;

		f[i]=s[tr[root][p^1]];

		for(int j=i;j<m;++j) (res+=(f[i]*f[j])%mod)%=mod;

		root=tr[root][p];

	}

	return (res<<(m-1))%mod;

}

signed main(){

	scanf("%lld%lld",&n,&m);

	for(re int i=1;i<=n;++i){

		scanf("%lld",&a[i]);

		insert(a[i]);

	}

	for(int i=1;i<=n;++i){

		ans^=query(a[i]);

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

csp-s模拟46 set read race

最新文章

热门文章