T1：
题意：求1~n的排列中逆序对的个数为k的排列数。
DP，再求简洁表达式即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<iomanip>
#include<ctime>
#include<climits>
#include<cctype>
#include<algorithm>
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
#define smax(x,tmp) x=max((x),(tmp))
#define smin(x,tmp) x=min((x),(tmp))
#define maxx(x1,x2,x3) max(max(x1,x2),x3)
#define minn(x1,x2,x3) min(min(x1,x2),x3)
const int INF=0x3f3f3f3f;
const int maxn = 1005;
const int mod = 10000;
const int N = 1000;
const int K = 1000;
int dp[maxn][maxn];
void dynamic()
{
for(int i=0;i<=N;i++) dp[i][0] = 1;
for(int i=1;i<=N;i++)
for(int j=1;j<=K;j++)
{
dp[i][j] = dp[i][j-1] + dp[i-1][j];
if(i<=j) dp[i][j] -= dp[i-1][j-i];
((dp[i][j]%=mod)+=mod)%=mod;
}
}
int main()
{
freopen("permut.in","r",stdin);
freopen("permut.out","w",stdout);
dynamic();
int T;
scanf("%d",&T);
while(T--)
{
int n,k;
scanf("%d%d",&n,&k);
printf("%d\n",dp[n][k]);
}
return 0;
}
T2：
题意： 定义序列中的一个数的美丽值为以其为中位数的最长区间长度。
关键在于每个数美丽值的求法。
O(n^2logn)： 枚举起点，Splay或者优先队列解决。
O(n^2)： 用类似于前缀和的方法，小于a[i]的数贡献为-1，大于的贡献为1，那么当左右的代数和为0的的时候表示左边和右边所表示的区间的中位数为a[i]。用大小为maxn的两个桶O(n)判断最大美丽值即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<iomanip>
#include<ctime>
#include<climits>
#include<cctype>
#include<algorithm>
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
#define smax(x,tmp) x=max((x),(tmp))
#define smin(x,tmp) x=min((x),(tmp))
#define maxx(x1,x2,x3) max(max(x1,x2),x3)
#define minn(x1,x2,x3) min(min(x1,x2),x3)
const int INF=0x3f3f3f3f;
const int maxn = 2005;
const int range = 205;
int ans[maxn];
int a[maxn];
int n;
int Low[maxn],High[maxn];
void pre_work()
{
for(int i=1;i<=n;i++)
{
int cur;
memset(Low,0,sizeof(Low));
memset(High,0,sizeof(High));
Low[0]=High[0]=i;
cur = 0;
for(int j=i-1;j>=1;j--)
{
if(a[j]<=a[i]) cur--;
else cur++;
if(cur<=0) Low[-cur] = j;
}
cur = 0;
for(int j=i+1;j<=n;j++)
{
if(a[j]<a[i]) cur--;
else cur++;
if(cur>=0) High[cur] = j;
}
for(int k=0;k<=n;k++)
if(Low[k] && High[k]) smax(ans[i],High[k]-Low[k]+1);
else break;
memset(Low,0,sizeof(Low));
memset(High,0,sizeof(High));
Low[0]=High[0]=i;
cur = 0;
for(int j=i-1;j>=1;j--)
{
if(a[j]<=a[i]) cur--;
else cur++;
if(cur>=0) High[cur] = j;
}
cur = 0;
for(int j=i+1;j<=n;j++)
{
if(a[j]<a[i]) cur--;
else cur++;
if(cur<=0) Low[-cur] = j;
}
for(int k=0;k<=n;k++)
if(Low[k] && High[k]) smax(ans[i],Low[k]-High[k]+1);
else break;
}
}
const int maxd = 15;
const int D = 12;
int dp[maxn][maxd];
void ST()
{
for(int i=1;i<=n;i++) dp[i][0] = ans[i];
for(int k=1;k<=D;k++)
for(int i=1;i+(1<<k)-1<=n;i++)
dp[i][k] = max(dp[i][k-1],dp[i+(1<<k-1)][k-1]);
}
int query(int i,int j)
{
int k = 0;
while((1<<k+1)<=(j-i+1)) k++;
return max(dp[i][k],dp[j-(1<<k)+1][k]);
}
void work()
{
int q;
scanf("%d",&q);
while(q--)
{
int x,y;
scanf("%d%d",&x,&y);
int tmp = query(x,y);
printf("%d\n",tmp);
}
}
int main()
{
freopen("beautiful.in","r",stdin);
freopen("beautiful.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",a+i);
pre_work();
ST();
work();
return 0;
}
T3：
题意： 维护一个可重集，支持三种操作：
- 插入x
- 删除一个x
- 查询a属于集合 且 a&s=a 的个数
考虑前30%，完全没有必要写Trie树，数据没有梯度。。直接用桶枚举即可。
100%：
折半搜索的方法。dp[pre][suf]表示前八位为pre，后八位为suf的子集的个数。
那么插入一个数就把dp[pre][S]++，其中suf包含于S，这里注意和常规枚举子集的方法不同，这里枚举取反后的子集，这样suf包含于suf|S。
删除同理。
查询的时候由于a包含于S，那么给定S，枚举S前八位的子集，Sigma(dp[S][suf])就是答案。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<iomanip>
#include<ctime>
#include<climits>
#include<cctype>
#include<algorithm>
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
#define smax(x,tmp) x=max((x),(tmp))
#define smin(x,tmp) x=min((x),(tmp))
#define maxx(x1,x2,x3) max(max(x1,x2),x3)
#define minn(x1,x2,x3) min(min(x1,x2),x3)
const int INF=0x3f3f3f3f;
const int maxn = (1<<8)+5;
int dp[maxn][maxn];
inline void insert(int x)
{
int pre = (x>>8) , suf = x&0xff;
int base = (~x)&0xff;
dp[pre][suf]++;
for(int S=base;S;S=base&(S-1)) dp[pre][S|suf]++; // base belongs to S
}
inline void erase(int x)
{
int pre = (x>>8) , suf = x&0xff;
int base = (~x)&0xff;
dp[pre][suf]--;
for(int S=base;S;S=base&(S-1)) dp[pre][S|suf]--; // base belongs to S
}
int query(int x)
{
int pre = (x>>8) , suf = x&0xff;
int ret = 0;
for(int S=pre;;S=pre&(S-1))
{
ret += dp[S][suf];
if(!S) break;
}
return ret;
}
int main()
{
freopen("subset.in","r",stdin);
freopen("subset.out","w",stdout);
int Q;
scanf("%d",&Q);
char cmd[10];
while(Q--)
{
scanf("%s",cmd);
int x;
scanf("%d",&x);
switch(cmd[0])
{
case 'a': insert(x); break;
case 'd': erase(x); break;
case 'c': printf("%d\n",query(x)); break;
}
}
return 0;
}