又是一周一度的周考

T1：permut

1.1 题目描述

求由 1 到 n 一共 n 个数字组成的所有排列中，逆序对个数为 k 的有多少个

1.2 输入格式

第一行为一个整数 T，为数据组数。

以下 T 行，每行两个整数 n， k，意义如题目所述。

1.3 输出格式

对每组数据输出答案对 10000 取模后的结果

1.4 Sample Input

1
4 1

1.5 Sample Output

3

1.6 数据范围及约定

对于 30% 的数据，满足 n ≤ 12。

对于所有数据，满足 n ≤ 1000, k ≤ 1000， T ≤ 10。

解题思路：

第一眼咋一看，逆序对？归并！！然而并不是。

接着仔细一读，排列中的逆序对……排序是有顺序的，想想排列中的交换某些位置后逆序对数的变化，of course是有规律的。

设f[i][j]为由1到i组成的序列中，逆序对数最多为j的有多少。

当多加一个数后，逆序对最多增加i，最少为0。

得到转移方程：

if(j<i) f[i][j]=(f[i][j-1]+f[i-1][j]);

else f[i][j]=(f[i][j-1]+f[i-1][j]-f[i-1][j-i]);

最后输出为f[n][k]-f[n][k-1].

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1e3+2,mod=1e4;
int f[maxn][maxn]={0};
int main()
{
	freopen("permut.in","r",stdin);
	freopen("permut.out","w",stdout);
	int t=0,n,k;
	scanf("%d",&t);
	f[0][0]=1;
	for(int i=1;i<=1001;i++)
	{
		f[i][0]=f[0][i]=1;
	}
	for(int i=1;i<=1001;i++)
	{
		for(int j=1;j<=1001;j++)
		{
			if(j<i) f[i][j]=(f[i][j-1]+f[i-1][j])%mod;
			else f[i][j]=(f[i][j-1]+mod+f[i-1][j]-f[i-1][j-i])%mod;//mod时记得先加mod,还有i不要写成1了，虽然经常int i=1，然而i!=1;
		}
	}
	for(int i=1;i<=t;i++)
	{
		scanf("%d%d",&n,&k);
		cout<<(f[n][k]+mod-f[n][k-1])%mod<<endl;
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

T2: beautiful

2.1题目描述

一个长度为 n 的序列，对于每个位置 i 的数 ai 都有一个优美值，其定义是：找到序列中最长的一段 [l, r]，满足 l ≤ i ≤ r，且 [l, r] 中位数为 ai（我们比较序列中两个位置的数的大小时，以数值为第一关键字，下标为第二关键字比较。这样的话 [l, r] 的长度只有可能是奇数）， r - l+ 1 就是 i 的优美值。接下来有 Q 个询问，每个询问 [l, r] 表示查询区间 [l, r] 内优美值的最大值。

2.2输入格式

第一行输入 n 接下来 n 个整数，代表 ai 接下来 Q，代表有 Q 个区间接下来 Q 行，每行
两个整数 l, r(l ≤ r)，表示区间的左右端点

2.3 输出格式

对于每个区间的询问，输出答案

2.4 Sample Input

8
16 19 7 8 9 11 20 16
8
3 8
1 4
2 3
1 1
5 5
1 2
2 8
7 8

2.5 Sample Output

7 3 1 3 5 3 7 3
3

2.6数据范围及约定

对于 30% 的数据，满足 n， Q ≤ 50

对于 70% 的数据，满足 n， Q ≤ 2000

对于所有数据，满足 n ≤ 2000, Q ≤ 100000,ai ≤ 200

解题思路：

仔细看看这道题，中位数？——》有序奇数互异序列左右数字个数相等，优美值？——》符合题意的区间大小。

理解题意就简单了，对于每个数，分别向左右扫描一遍，遇到大于的就++，else —，

然后分别记录下来，再对于这些状态求max，找出每个点的优美值。

最后将l - > r扫一遍，ans=max，得出答案。

Code：

#include<iostream>
#include<cstdio>
#include<cstring>
#define max(a,b) ((a)>(b)?(a):(b))
#define clsm(a) memset(a,255,sizeof(a))
using namespace std;
const int maxn=2010;
int l[maxn*2],r[maxn*2],a[maxn],w[maxn];
int main()
{
	int n,q;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		clsm(l),clsm(r);
		l[n]=r[n]=0;
		int cnt=0;
		for(int j=i-1;j>=1;j--)
		{
			if(a[i]<a[j]) cnt++;
			else cnt--;
			l[n+cnt]=i-j;
		}
		cnt=0;
		for(int j=i+1;j<=n;j++)
		{
			if(a[i]<=a[j]) cnt++;
			else cnt--;
			r[n+cnt]=j-i;
		}
		for(int j=1-i;j<=i-1;j++)
		{
			if(l[n+j]>=0&&r[n-j]>=0)
			{
				w[i]=max(w[i],l[n+j]+r[n-j]+1);
			}
		}
	}
	scanf("%d",&q);
	while(q--)
	{
		int L,R;
		scanf("%d%d",&L,&R);
		int ans=0;
		for(int i=L;i<=R;i++)
		{
			ans=max(ans,w[i]);
		}
		cout<<ans<<endl;
	}
	return 0;
}

T3：subset

3.1题目描述

一开始你有一个空集，集合可以出现重复元素，然后有 Q 个操作

1. add s

在集合中加入数字 s。

1. del s

在集合中删除数字 s。保证 s 存在

1. cnt s

查询满足 a&s = a 条件的 a 的个数

3.2 输入格式

第一行一个整数 Q 接下来 Q 行，每一行都是 3 个操作中的一个

3.3 输出格式

对于每个 cnt 操作输出答案

3.4 Sample Input

7
add 11
cnt 15
add 4
add 0
cnt 6
del 4
cnt 15

3.5 Sample Output

1 2 2

3.6 数据范围及约定

对于 30% 的数据满足： 1 ≤ n ≤ 1000

对于 100% 的数据满足， 1 ≤ n ≤ 200000 , 0 < s < 216

解题思路：

先开始并没有像出来，216用set绝对会炸，看了看题解，听了听lifel讲，大概知道了题解之意。

分块计算。 a[pre][suf]，其中 pre < 28， suf < 28，表示前面 8 位是 pre，后面 8 位是 suf 的子集的数字的个数。

那么对于每个 add 和 del 操作都可以最多 28 时间枚举 suf 更新 a 数组。

对于 cnt 操作，最多 28 枚举 pre，计算答案即可。

Code：

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=301;
int a[maxn][maxn];
int main()
{
	int q=0,x=0;
	char str[5];
	scanf("%d",&q);
	for(int t=1;t<=q;t++)
	{
		int w=1;
		scanf("%s%d",str,&x);
		if(str[0]=='d') w=-1;
		if(str[0]!='c')
		{
			int pre=x>>8,cur=x&255,cp=cur^255;
			a[pre][cur]+=w;
			for(int i=cp;i;i=(i-1)&cp)
			{
				a[pre][i|cur]+=w;
			}
		}
		else
		{
			int pre=x>>8,cur=x&255;
			int ans=a[0][cur];
			for(int i=pre;i;i=(i-1)&pre)
			{
				ans+=a[i][cur];
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}