Post 51

Veröffentlicht am

良时不再，思乐难常。

今天又回到SLYZ ， zky学长来讲课！

（我怎么莫名其妙被奶Au了？？我和ljs这么像吗？？？

睿智luogu又不能用了，zky学长又给了我们两年权限号，所以

冲呀，BZOJ！！

不过是公共账号所以以后BZOJ做的题记个数（前面不算了233

[Poi2010]Intelligence test

Description

霸中智力测试机构的一项工作就是按照一定的规则删除一个序列的数字，得到一个确定的数列。Lyx很渴望成为霸中智力测试机构的主管，但是他在这个工作上做的并不好，俗话说熟能生巧，他打算做很多练习，所以他希望你写一个程序来快速判断他的答案是否正确。

Input

第一行为一个整数m（1<=m<=1000000）第二行包括m个用空格分开的整数ai（1<=ai<=1000000），组成了最初的序列，第三行为一个整数n（1<=n<=1000000），表示n个Lyx经过一系列删除得到的序列，每个序列两行，第一行给出长度L（1<=L<=m），然后下一行为L个由空格分开的整数bi（1<=bi<=1000000）。

Output

共n行，如果Lyx的序列确实是由最初的序列删除一些数得到，就输出TAK，否则输出NIE。

Sample Input

7

1 5 4 5 7 8 6

4

5

1 5 5 8 6

3

2 2 2

3

5 7 8

4

1 5 7 4

Sample Output

TAK

NIE

TAK

NIE

Hint

Source

题解

bzoj t1

秒切的大水题（略有问题，不过也对

把原序列每个数存位置序列，贪心地让新每个数出现的位置尽量靠前且比上个数位置靠后（直接二分就可以啦）找一个位置单增的序列即可。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#define maxn 1000005
std::vector<int> p[maxn];
int a[maxn] , b[maxn] , l , n , num;
int find(int x , std::vector<int>& ar)
{
	int l = 0 , r = (int)ar.size() - 1 , ans = -1;
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(ar[mid] > x) ans = ar[mid] , r = mid - 1;
		else l = mid + 1;
	}
	return ans;
}

bool solve()
{
	if(!(int)p[b[1]].size()) return false;
	int las = p[b[1]][0];
	for(int i = 2 ; i <= l ; ++i)
	{
		int k = find(las , p[b[i]]);
//		printf("%d " , k);
		if(k == -1) return false;
		else las = k;
	}
	return true;
//	puts("A QUERY!!!!!");
}

int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&a[i]);
	for(int i = 1;  i <= n ; ++i)
		p[a[i]].push_back(i);
	scanf("%d",&num);
	for(int i = 1 ; i <= num ; ++i)
	{
		scanf("%d",&l);
		for(int j = 1 ; j <= l ; ++j)
			scanf("%d",&b[j]);
		if(solve()) puts("TAK");
		else puts("NIE");
	}
}

3687: 简单题

Description

小呆开始研究集合论了，他提出了关于一个数集四个问题：
1．子集的异或和的算术和。
2．子集的异或和的异或和。
3．子集的算术和的算术和。
4．子集的算术和的异或和。
​ 目前为止，小呆已经解决了前三个问题，还剩下最后一个问题还没有解决，他决定把
这个问题交给你，未来的集训队队员来实现。

Input

第一行，一个整数n。
第二行，n个正整数，表示01，a2…．，。

Output

一行，包含一个整数，表示所有子集和的异或和。

Sample Input

2
1 3

Sample Output

6

HINT

【样例解释】

6=1 异或 3 异或 (1+3)

【数据规模与约定】

ai >0，1<n<1000，∑ai≤2000000。

另外，不保证集合中的数满足互异性，即有可能出现Ai= Aj且i不等于J

题解

bzoj t2!

又是一道大水题！

我们只需要知道每个和出现了奇数次还是偶数次就可以了。

然后每次多一个数我们就把当前所有的子集和都加上这个值，就是右移，原先的可能多加一次就没了，所以是异或。

所以说就是bitset维护每个和出现次数的奇偶，由于值域小可过。

复杂度$O(n\sum_{a_i}/w)$

$w$一般取32.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <bitset>
#define maxn 2000005
std::bitset<2000005> s;
int ans , mx = -0x7ffffff , n;

int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
	{
		int x ;
		scanf("%d",&x);
		s[0] = 1;
		s ^= (s << x);
	}
	for(int i = 1 ; i <= 2000000 ; ++i)
		if(s[i]) ans ^= i;
	printf("%d",ans);
}

然后就很水了，回家来发现虚拟机拷了忘了拷VMware…..

所以晚上早点开溜。

数学作业就写了半张，毕竟没料到讲课。。。不过下午是自己做题，以后干脆留在家做作业得了。

zky居然600充了两年bzoj权限号。

卸载了chrome，每次打不开网站以为是我的网的事，用edge吧。

也卸载了搜狗，感觉舒服多了。

发现以前有些Latex出了问题，也不知道为啥，感觉写的挺正确。。

吃饭。