题目

收集卡片

De ion

Star 计划订购一本将要发行的周刊杂志，但他可不是为了读书，而是——集卡。已知杂志将要发行 N 周（也就是 N 期），每期都会附赠一张卡片。Star通过种种途径，了解到 N 期杂志附赠的卡片种类。Star 只想订购连续的若干期，并在这些期内收集所有可能出现的种类的卡片。现在他想知道，他最少需要订购多少期。

Input

第一行一个整数 N；
第二行一个长度为 N 的字符串，由大写或小写字母组成，第 i 个字符表示 第 i 期附赠的卡片种类，每种字符（区分大小写）表示一种卡片。

Output

输出一行一个整数，表示 Star 最少订购的期数。

Sample Input

8
acbbbcca

Sample Output

3

Data Constraint

对于 30%的数据，N ≤ 300；
对于 40%的数据，N ≤ 2000；
对于 60%的数据，N ≤ 5000；
对于 80%的数据，N ≤ 100000；
对于 100%的数据，N ≤ 500000。

基因变异

De ion

21 世纪是生物学的世纪，以遗传与进化为代表的现代生物理论越来越多的 进入了我们的视野。 如同大家所熟知的，基因是遗传因子，它记录了生命的基本构造和性能。 因此生物进化与基因的变异息息相关，考察基因变异的途径对研究生物学有着 至关重要的作用。现在，让我们来看这样一个模型：
1、所有的基因都可以看作一个整数或该整数对应的二进制码；
2、在 1 单位时间内，基因 x 可能会在其某一个二进制位上发生反转；
3、在 1 单位时间内，基因 x 可能会遭到可感染基因库内任一基因 y 的影响 而突变为 x XOR y。
现在给出可感染基因库，Q 组询问，每组给出初始基因与终止基因，请你 分别计算出每种变异最少要花费多少个单位时间。

Input

第 1 行两个整数 N, Q； 第 2 行 N 个用空格隔开的整数分别表示可感染基因库内的基因； 接下来 Q 行每行两个整数 S、T，分别表示初始基因与终止基因。

Output

输出 Q 行，依次表示每组初始基因到终止基因间最少所花时间。

Sample Input

3 3
1 2 3
3 4
1 2
3 9

Sample Output

2
1
2

Data Constraint

对于 20%的数据，N = 0；
对于额外 40%的数据，1 ≤ Q ≤ 100，所有基因表示为不超过 104 的非负整 数；
对于 100%的数据，0 ≤ N ≤ 20，1 ≤ Q ≤ 105，所有基因表示为不超过 106 的 非负整数。

abcd

De ion

有4个长度为N的数组a,b,c,d。现在需要你选择N个数构成数组e，数组e满足ai​≤ei​≤bi​以及i=1∑N​ei​∗ci​=0并且使得i=1∑N​ei​∗di​最大。

Input

输入文件名为abcd. in。
输入文件共 N+1 行。
第 1 行包含1个正整数N。
第 i+1 行包含4个整数a[i],b[i],c[i],d[i]。

Output

输出文件名为abcd.out。
输出共1行，包含1个整数，表示所给出公式的最大值。输入数据保证一定有解。

Sample Input

Sample1:
5
-1 1 2 5
-2 2 1 2
0 1 1 3
-2 -1 3 10
-2 2 3 9
Sample2:
10
1 10 1 7
-10 10 2 0
-10 10 2 2
-10 10 2 0
1 10 1 0
-10 10 2 0
10 10 2 0
1 10 1 0
-10 10 2 0
1 10 1 0
Sample3:
10
1 10 1 0
-10 10 2 2
-10 10 2 2
-10 10 2 2
1 10 1 0
-10 10 2 2
-10 10 2 2
1 10 1 0
-10 10 2 2
1 10 1 0

Sample Output

Sample1:
2
Sample2:
90
Sample3:
-4

Data Constraint

对于20%的数据，N≤10，-2≤a[i]<b[i]≤2；
对于60%的数据，N≤50, -20≤a[i]<b[i]≤20；
对于100%的数据，N≤200，-25≤a[i]<b[i]≤25，1≤c[i]≤20，0≤d[i] ≤100000。

总结

今天犯了一个错误，坑了100分，只有100分了。

第一题：
我先想到了二分答案、前缀和等高深的算法。好不容易才回过神来，发现这是一道很水很水的双向指针。在想完第二题后打代码，考场AC。

第二题：
一开始觉得很神仙，就去看第三题，结果发现第三题更神仙o(╥﹏╥)o
于是决定模拟一下样例。由于我理解错了题意，把

在 1 单位时间内，基因 x 可能会在其某一个二进制位上发生反转；

理解成了可以在1单位时间内翻转基因 x 的所有二进制位，因此怎么算也算不出来；等我算完样例后，惊奇地发现了一个神奇的东西：

把基因 x 变成基因 y 等价于把 0 变成 x^y（即 x 和 y 有多少个不同的位）

于是我欣欣然打了一个DP：设fi​表示把基因 i 变成0的最少步数。⎩⎪⎨⎪⎧​f0​=0fi⨁2j​=max(fi⨁2j​,fi​+1)fi⨁aj​​=max(fi⨁aj​​,fi​+1)​i>0i>0​其中⨁表示xor。
结果发现这个DP有后效性，遂改成记忆化搜索（DFS），结果时间复杂度似乎不太理想。

正常人这个时候都会把DFS改成BFS，然而我却脑残了一般，输出 f 数组，然后在代码的开头直接给 f 数组赋初值。

其实这样是会出错的，因为每一个输入的 a 都不一样，那么 f 的值就自然不同了；然而我却没有意识到这一点，直接交到OJ上。
注意码量！
是不是很惊人？我TMD给220那么大的DP数组赋初值，结果直接编译错误了（OJ能容忍的最长码量似乎是105byte）
不过话说回来，这样的实验似乎是挺有趣的。

正解

T1

双指针搜索就可以了。
下面就来解释什么是双指针搜索。
首先申明一下，这里的指针并非指数据结构中的那个指针，而是两个指向数组中位置的变量。我们要两个指针 l 和 r，分别指向子区间的开头和结尾。

这个算法常用来解决在大区间中找满足要求的最长或最短的子区间。它的步骤常是这样：

若当前区间不满足要求（有时也可以是满足要求），且若是该区间向右扩张后可能满足，即向右扩张可接近要求，则把 r 指针向右移动1个单位，并加上该元素的值；
若当前区间已经超出要求（有时是满足要求），且该区间向右扩张会不断远离要求，则把 l 指针向右移动1个单位。
注意：在所有这些过程中，l 和 r指针永远向右移动

在这题中，我们先把两个指针指针指向第一个元素，再执行上面的过程。如果当前区间不包含所有字符，则 r 向右移动；包含所有字符，就把 l 向右移动（因为我们这道题目是要求最短序列的）。
最后，请注意边界条件！

T2

这题其实也不难（然而我却爆0了）
首先，我们可以发现一个显而易见的规律（不要问我为什么想了20分钟才发现）

把基因 x 变成基因 y 等价于把 0 变成 x^y（即 x 和 y 有多少个不同的位）

因此，我们可以先预处理出所有数变成0的最少步数（很容易发现把x变成y等价于把y变成x嘛）
可以从0出发，搜索所有它可以变成的数，若可以更新，就更新它并从它出发进行搜索。
显然DFS会TLE，我们就要加上记忆化；然而记忆化DFS还是会爆炸，于是我就想到了打表（不要问我为什么想不到BFS！！！）
其实用BFS就可以了。。。

T3

这题不少人用水法过了。
其实我们可以把它转化成一道多重背包问题：

给出n个物品，每一件可以选ai​到bi​个，体积为ci​，价值为di​，恰好填满一个容量为0的背包

对于这个问题，我们可以把范围转换成0~b[i]-a[i]，那么选的件数就成了e[i]-a[i]，那么背包的体积就成了-a[i]*c[i]（因为a[i]几乎总是小于0），价值是(ei​−ai​)∗di​+Σai​∗di​。
但是这样DP显然时超，因此我们要用优化。有两种：单调队列和二进制。
这里说一下二进制优化：

设物品的体积为x，我们就把它分解成体积为1,2,4,8,…2k−1,n−2k−1的物品。
可以证明，这些物品可以组成0~x中的任意体积。

这样做就可以了。

代码

T1

#include<cstdio>
#include<algorithm>
using namespace std;
#define N 500005
struct node
{char ch;int id;}s[N];
int a[N],num[N];
inline bool cmp(node x,node y)
{return x.ch<y.ch;}
int main()
{
	int n,m=1,i,j,l,r,ans=N;
	bool bk;
	scanf(\"%d\\n\",&n);
	for(i=1;i<=n;i++) scanf(\"%c\",&s[i].ch),s[i].id=i;
	sort(s+1,s+n+1,cmp);
	a[s[1].id]=1;
	for(i=2;i<=n;i++)
	{
		if(s[i].ch>s[i-1].ch) m++;
		a[s[i].id]=m;
	}
	for(l=r=1,num[a[1]]=1;l<=n;--num[a[l++]])
	{
		bk=1;
		for(;bk&&r<=n;num[a[++r]]++)
		{
			for(j=1;j<=m;j++)
				if(!num[j])
					break;
			if(j>m){bk=0;break;}
		}
		if(bk) break;
		if(r-l+1<ans) ans=r-l+1;
	}
	printf(\"%d\\n\",ans);
	return 0;
}

T2

#include<cstdio>
using namespace std;
#define M 1048576
#define N 25
int n,a[N],f[M],data[5110000];
int main()
{
	int m,i,j,x,y,head=0,tail=1;
	scanf(\"%d%d\",&n,&m);
	for(i=1;i<=n;i++) scanf(\"%d\",&a[i]);
	for(i=1;i<M;i++) f[i]=N;
	while(head<tail)
	{
		x=data[++head];
		for(i=1;i<=n;i++)
		{
			if(f[x^a[i]]>f[x]