「BZOJ3687」「FJ2014集训」简单题

2014年9月14日6,2832

「题目描述」
小呆开始研究集合论了，他提出了关于一个数集四个问题：
1. 子集的异或和的算术和。
2. 子集的异或和的异或和。
3. 子集的算术和的算术和。
4. 子集的算术和的异或和。
目前为止，小呆已经解决了前三个问题，还剩下最后一个问题还没有解决，他决定把
这个问题交给你，未来的集训队队员来实现。
「输入格式」
从 xor.in 中输入数据
第一行，一个整数 n。
第二行，n 个正整数，表示 a1, a2, …, an
「输出格式」
输出到 xor.out 中
一行，包含一个整数，表示所有子集和的异或和。
「样例输入」
2
1 3
「样例输出」
6
「样例解释」
6 = 1 ⊗ 3 ⊗ (1 + 3)
「数据规模与约定」
数据分为 A,B,C 三类。
A 类数据 (20%) 保证：ai > 0，1 ≤ n ≤ 10。
B 类数据 (40%) 保证：ai > 0，1 ≤ n ≤ 1000，
∑ ai ≤ 10000。
C 类数据 (40%) 保证：ai > 0，1 ≤ n ≤ 1000，
∑ ai ≤ 2000000。
另外，不保证集合中的数满足互异性，即有可能出现 ai = aj 且 i ̸= j。

「题解」

蒟蒻比赛的时候只会60直接背包。。。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
inline ll read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int ans,n,a[1005],b[1005],f[10005],bin[25];
void getans(int x)
{
	int tot=0;
	for(int i=1;i<=x;i++)
	    tot+=b[i];
	ans^=tot;
}
void dfs(int k,int last)
{
	if(k==n)return;
	for(int i=last+1;i<=n;i++)
	{
		b[k+1]=a[i];
		getans(k+1);
		dfs(k+1,i);
	}
}
void solve1()
{ans=0;dfs(0,0);printf("%d\n",ans);}
void solve2()
{
    ans=0;f[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=10000;j>=a[i];j--)
            f[j]+=f[j-a[i]];
    for(int i=1;i<=10000;i++)
        if(f[i]%2)ans^=i; 
	printf("%d\n",ans);
}
int main()
{
	bin[1]=1;for(int i=2;i<=24;i++)bin[i]=bin[i-1]*2;
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    if(n<=10)solve1();
    else solve2();
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

inline ll read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

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

return x*f;

}

int ans,n,a[1005],b[1005],f[10005],bin[25];

void getans(int x)

{

int tot=0;

for(int i=1;i<=x;i++)

tot+=b[i];

ans^=tot;

}

void dfs(int k,int last)

{

if(k==n)return;

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

{

b[k+1]=a[i];

getans(k+1);

dfs(k+1,i);

}

void solve1()

{ans=0;dfs(0,0);printf("%d\n",ans);}

void solve2()

{

ans=0;f[0]=1;

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

for(int j=10000;j>=a[i];j--)

f[j]+=f[j-a[i]];

for(int i=1;i<=10000;i++)

if(f[i]%2)ans^=i;

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

}

int main()

{

bin[1]=1;for(int i=2;i<=24;i++)bin[i]=bin[i-1]*2;

n=read();

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

a[i]=read();

if(n<=10)solve1();

else solve2();

return 0;

}

学了下bitset好像很优越

不过这题数据似乎有问题。。不满n位，用快速读入会跪

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<bitset>
using namespace std;
int n,x,sum,ans;
bitset<2000000> a;
int main()
{
	scanf("%d",&n);
	a[0]=1;
	while(n--)
	{
		scanf("%d",&x);
		sum+=x;
		a^=(a<<x);
	}
	for(int i=1;i<=sum;i++)
		if(a[i])ans^=i;
	printf("%d",ans);
	return 0;
}