这是一个句子测试

2
27
2016
0

Contest20160226滚粗记

看到题目的时候，我的心情是这样的：

再次膜拜神犇NiroBC屠场爷。

T1

给你一个n*n的正方形矩阵，每次操作可以选择(n+1)/2*(n+1)/2的矩阵，将矩阵中的所有点权值变为其相反数，最大化矩阵点权和。

此题有一种似曾相识的即视感。

然而瞪了半天，依然只会打暴力。

发现有20分要用高斯消元，于是不断码码码，把一堆暴力码成一坨，结果自己看不懂了。。。

最后还是欢乐地拿了50分，因为数据里面有个全是0的彩蛋。

正解十分奇怪而且难写，在此不再赘述。

T2

给你一个排列，有m次操作，每次可以：

1、交换相邻的两个元素。

2、将序列完全随机打乱。

问采取最优策略操作完毕后的序列逆序对数的期望值。

感觉这道题非常可做，于是花了两个小时硬肛此题，结果喜闻乐见地爆蛋了。

令f[i][j]表示长度为i逆序对数为j的序列出现的概率，那么f[i][j]可以dp求出。

令F[x]为将序列打乱后，还有x次操作的期望答案，那么：

[tex]F[x]=\sum^{\frac{n(n-1)}{2}}_{i=1}min(F[x-1],max(0,i-x))*f[n][i][/tex]

显然不能枚举i，但是min(F[x-1],max(0,i-x))的取值是连续的，即随着i递增只会改变两次。

算出取值为F[x-1]、0、i-x时的i的范围，然后用前缀和维护即可。

T3

给你一个串S，回答以下两种询问：

1、给出k1、k2，求出S的不同子串中字典序为k1的子串的左右端点l，r；若该子串出现多次，求起始位置第k2小的子串的左右端点l，r。

2、给出l、r，求出左右端点为l、r的子串在S的不同子串中从小到大的字典序排名k1，以及在相同子串中从小到大起始位置的排名k2。

蒟蒻表示考的时候连题目都没看过。。。

考虑询问1，需要求出字典序为k1的子串，那么可以求出后缀数组和height，然后二分来求答案。

接着发现相同的子串在sa中必然是连续的。可以二分+rmq求出左右边界。

然后在这个范围内求出起始位置第k2小的子串，可以用主席树维护。

对于询问2，先知道了该子串的rank，然后就可以前后二分+rmq找到边界。

然后在主席树中求出比S[l,r]起始端点小的子串数就可以了！

【Codes】

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,i,j,cnt,ans;
int a[110][110],equ[210][210],Equ[210][210],stx[10010],edx[10010],sty[10010],edy[10010];
int abs(int x){if (x<0)return -x;else return x;}
void dfs(int k){
	if (k>cnt){
		int tot=0;
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				tot+=a[i][j];
		ans=max(ans,tot);
		return;
	}
	dfs(k+1);
	for (int i=stx[k];i<=edx[k];i++)
		for (int j=sty[k];j<=edy[k];j++)a[i][j]=-a[i][j];
	dfs(k+1);
	for (int i=stx[k];i<=edx[k];i++)
		for (int j=sty[k];j<=edy[k];j++)a[i][j]=-a[i][j];
}
int solve(){
	int flag=0;
	for (int k=1;k<=n*n;k++)
		if (Equ[k][cnt+1]!=-1){
			int l;
			for (l=1;l<=cnt+1;l++)
				if (Equ[k][l])break;
			if (l==cnt+1&&Equ[k][l]){flag=1;break;}
			for (int I=k+1;I<=n*n;I++)
				if (Equ[I][cnt+1]!=-1&&Equ[I][l])
					for (int J=1;J<=cnt+1;J++)Equ[I][J]^=Equ[k][J];
		}
	return flag^1;
}
int main(){
	scanf("%d",&n);
	int m=n+1>>1;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++){
			scanf("%d",&a[i][j]);
			if (i+m-1<=n&&j+m-1<=n){cnt++;stx[cnt]=i;sty[cnt]=j;edx[cnt]=i+m-1;edy[cnt]=j+m-1;}
		}
	ans=-1000000007;
	if (n<=7)dfs(1);
		else if (n<=13){
			for (i=1;i<=cnt;i++){
				for (j=stx[i];j<=edx[i];j++)
					for (int k=sty[i];k<=edy[i];k++)
						equ[(j-1)*n+k][i]=1;
			}
			for (i=1;i<=n;i++)
				for (j=1;j<=n;j++)
					if (a[i][j]>0)equ[(i-1)*n+j][cnt+1]=0;
						else if (a[i][j]<0)equ[(i-1)*n+j][cnt+1]=1;
							else equ[(i-1)*n+j][cnt+1]=-1;
			int tot=0;
			for (i=1;i<=n;i++)
				for (j=1;j<=n;j++)tot+=abs(a[i][j]);
			for (i=1;i<=n*n;i++)
				for (j=1;j<=cnt+1;j++)Equ[i][j]=equ[i][j];
			if (solve())ans=max(ans,tot);
			for (i=1;i<=n;i++)
				for (j=1;j<=n;j++)
					if (equ[(i-1)*n+j][cnt+1]!=-1){
						for (int k=1;k<=n*n;k++)
							for (int l=1;l<=cnt+1;l++)Equ[k][l]=equ[k][l];
						Equ[(i-1)*n+j][cnt+1]^=1;
						if (solve())ans=max(ans,tot-2*abs(a[i][j]));
					}
		}else{
			for (i=0;i<=cnt;i++)
				for (j=0;j<=cnt;j++){
					if (i&j&i==j)continue;
					if (i)
						for (int k=stx[i];k<=edx[i];k++)
							for (int l=sty[i];l<=edy[i];l++)a[k][l]=-a[k][l];
					if (j)
						for (int k=stx[j];k<=edx[j];k++)
							for (int l=sty[j];l<=edy[j];l++)a[k][l]=-a[k][l];
					int tot=0;
					for (int k=1;k<=n;k++)
						for (int l=1;l<=n;l++)tot+=a[k][l];
					ans=max(ans,tot);
					if (i)
						for (int k=stx[i];k<=edx[i];k++)
							for (int l=sty[i];l<=edy[i];l++)a[k][l]=-a[k][l];
					if (j)
						for (int k=stx[j];k<=edx[j];k++)
							for (int l=sty[j];l<=edy[j];l++)a[k][l]=-a[k][l];
				}
		}
	printf("%d\n",ans);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
const int M=50010;
int cas,n,i,j;
ll m;
double f[110][M],sum[M],Sum[M],F[M],a[M];
int main(){
	f[1][0]=1;
	for (i=2;i<=100;i++){
		for (j=0;j<=(i-1)*(i-2)/2;j++)sum[j]=f[i-1][j];
		for (j=1;j<=(i-1)*(i-2)/2;j++)sum[j]+=sum[j-1];
		for (j=0;j<=i-1;j++)f[i][j]=sum[j];
		for (j=i;j<=i*(i-1)/2-i+1;j++)f[i][j]=sum[j]-sum[j-i];
		for (j=i*(i-1)/2-i+2;j<=i*(i-1)/2;j++)f[i][j]=sum[i*(i-1)/2-j];
		for (j=0;j<=i*(i-1)/2;j++)f[i][j]=f[i][j]/i;
	}
	scanf("%d",&cas);
	while (cas--){
		scanf("%d%lld",&n,&m);
		if (m>n*(n-1)/2)m=n*(n-1)/2;
		for (i=0;i<=n*(n-1)/2;i++)sum[i]=f[n][i],Sum[i]=i*f[n][i];
		for (i=1;i<=n*(n-1)/2;i++)sum[i]+=sum[i-1],Sum[i]+=Sum[i-1];
		F[0]=(double)n*(n-1)/4;
		for (i=1;i<=m;i++){
			int now=(int)F[i-1]+i;
			F[i]=Sum[now]-Sum[i]-i*(sum[now]-sum[i])+F[i-1]*(sum[n*(n-1)/2]-sum[now]);
		}
		for (i=1;i<=n;i++)scanf("%d",&a[i]);
		int tot=0;
		for (i=1;i<=n;i++)
			for (j=i+1;j<=n;j++)if (a[i]>a[j])tot++;
		if (m==0)printf("%.12lf\n",(double)tot);
			else printf("%.12lf\n",min((double)max(tot-(int)m,0),F[m-1]));
	}
}
/*━━━━━━神兽出没━━━━━━
 * 　　　┏┓　　　┏┓
 * 　　┏┛┻━━━┛┻┓
 * 　　┃　　　　　　　┃
 * 　　┃　　　━　　　┃
 * 　　┃　┳┛　┗┳　┃
 * 　　┃　　　　　　　┃
 * 　　┃　　　┻　　　┃
 * 　　┃　　　　　　　┃
 * 　　┗━┓　　　┏━┛Code is far away from bug with the animal protecting
 * 　　　　┃　　　┃    神兽保佑,代码无bug
 * 　　　　┃　　　┃
 * 　　　　┃　　　┗━━━┓
 * 　　　　┃　　　　　　　┣┓
 * 　　　　┃　　　　　　　┏┛
 * 　　　　┗┓┓┏━┳┓┏┛
 * 　　　　　┃┫┫　┃┫┫
 * 　　　　　┗┻┛　┗┻┛
 *
 * ━━━━━━感觉萌萌哒━━━━━━
 */

/**
 * 　　　┏┓　　　┏┓
 * 　　┏┛┻━━━┛┻┓
 * 　　┃　　　　　　　┃ 　
 * 　　┃　　　━　　　┃
 * 　　┃　＞　　　＜　┃
 * 　　┃　　　　　　　┃
 * 　　┃  ... O　... ┃
 * 　　┃　　　　　　　┃
 * 　　┗━┓　　　┏━┛
 * 　　　　┃　　　┃　Code is far away from bug with the animal protecting　　　　　　　　　　
 * 　　　　┃　　　┃   神兽保佑,代码无bug
 * 　　　　┃　　　┃　　　　　　　　　　　
 * 　　　　┃　　　┃  　　　　　　
 * 　　　　┃　　　┃
 * 　　　　┃　　　┃　　　　　　　　　　　
 * 　　　　┃　　　┗━━━┓
 * 　　　　┃　　　　　　　┣┓
 * 　　　　┃　　　　　　　┏┛
 * 　　　　┗┓┓┏━┳┓┏┛
 * 　　　　　┃┫┫　┃┫┫
 * 　　　　　┗┻┛　┗┻┛
 */
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
const int M=500010;
int n,m,i,j,opt,left,right,cnt;
char S[M];
int s[M],wa[M],wb[M],wc[M],wd[M],sa[M],rank[M],height[M][30],log[M],root[M];
ll k1,k2,sum[M];
struct node{int l,r,w;}tree[M*20];
bool cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void getsa(int *r,int *sa,int n,int m){
	int i,j,p,*x=wa,*y=wb;
	for (i=0;i<n;i++)wc[i]=0;
	for (i=0;i<n;i++)wc[x[i]=r[i]]++;
	for (i=1;i<m;i++)wc[i]+=wc[i-1];
	for (i=n-1;i>=0;i--)sa[--wc[x[i]]]=i;
	for (j=1,p=1;p<n;j*=2,m=p){
		p=0;
		for (i=n-j;i<n;i++)y[p++]=i;
		for (i=0;i<n;i++)if (sa[i]>=j)y[p++]=sa[i]-j;
		for (i=0;i<n;i++)wd[i]=x[y[i]];
		for (i=0;i<m;i++)wc[i]=0;
		for (i=0;i<n;i++)wc[wd[i]]++;
		for (i=1;i<m;i++)wc[i]+=wc[i-1];
		for (i=n-1;i>=0;i--)sa[--wc[wd[i]]]=y[i];
		swap(x,y),p=1,x[sa[0]]=0;
		for (i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
void getheight(int *r,int *sa,int n){
	int i,j,k=0;
	for (i=1;i<=n;i++)rank[sa[i]]=i;
	for (i=0;i<n;height[rank[i++]][0]=k){
		if (k)k--;
		j=sa[rank[i]-1];
		while (r[i+k]==r[j+k])k++;
	}
}
int rmq(int l,int r){
	if (l>r)return 100000000;
	int p=log[r-l+1];
	return min(height[l][p],height[r-(1<<p)+1][p]);
}
void update(int x,int l,int r,int &p){
	tree[++cnt]=tree[p];p=cnt;tree[p].w++;
	if (l==r)return;
	int mid=l+r>>1;
	if (x<=mid)update(x,l,mid,tree[p].l);
		else update(x,mid+1,r,tree[p].r);
}
int query(int x,int y,int l,int r,int k){
	if (l==r)return l;
	int t=tree[tree[y].l].w-tree[tree[x].l].w,mid=l+r>>1;
	if (t>=k)return query(tree[x].l,tree[y].l,l,mid,k);
		else return query(tree[x].r,tree[y].r,mid+1,r,k-t);
}
int Query(int x,int y,int l,int r,int L,int R){
	if (l==L&&r==R)return tree[y].w-tree[x].w;
	int mid=l+r>>1;
	if (R<=mid)return Query(tree[x].l,tree[y].l,l,mid,L,R);
		else if (L>mid)return Query(tree[x].r,tree[y].r,mid+1,r,L,R);
			else return Query(tree[x].l,tree[y].l,l,mid,L,mid)+Query(tree[x].r,tree[y].r,mid+1,r,mid+1,R);
}
int main(){
	scanf("%s",S);
	n=strlen(S);
	for (i=0;i<n;i++)s[i]=S[i]-'a'+1;
	s[n]=0;
	getsa(s,sa,n+1,27);
	getheight(s,sa,n);
	for (i=0;i<=n;i++)sum[i]=n-height[i][0]-sa[i];
	for (i=1;i<=n;i++)sum[i]+=sum[i-1];
	sa[0]=0;
	for (i=1;i<=n;i++)sa[i]++;
	for (i=1;i<=n;i++)s[i]=rank[i-1];
	rank[0]=0;for (i=1;i<=n;i++)rank[i]=s[i];
	for (i=1;i<=20;i++)
		for (j=1;j<=n-(1<<i)+1;j++)
			height[j][i]=min(height[j][i-1],height[j+(1<<(i-1))][i-1]);
	log[1]=0;for (i=2;i<=n;i++)log[i]=log[i/2]+1;
	for (i=1;i<=n;i++){
		root[i]=root[i-1];
		update(sa[i],0,n,root[i]);
	}
	scanf("%d",&m);
	while (m--){
		scanf("%d",&opt);
		if (opt==1){
			scanf("%lld%lld",&k1,&k2);
			int l=1,r=n;
			while (l<r){
				int mid=l+r>>1;
				if (k1<=sum[mid])r=mid;else l=mid+1;
			}
			int left=sa[l],right=sa[l]+height[l][0]+k1-sum[l-1]-1;
			int L=l,R=n;
			while (L<R){
				int mid=L+R+1>>1;
				if (rmq(l+1,mid)>=right-left+1)L=mid;else R=mid-1;
			}
			l=query(root[l-1],root[L],0,n,k2);
			printf("%d %d\n",l,l+right-left);
		}else{
			scanf("%d%d",&left,&right);
			int l=1,r=rank[left];
			while (l<r){
				int mid=l+r>>1;
				if (rmq(mid+1,rank[left])>=right-left+1)r=mid;else l=mid+1;
			}
			int L=rank[left],R=n;
			while (L<R){
				int mid=L+R+1>>1;
				if (rmq(rank[left]+1,mid)>=right-left+1)L=mid;else R=mid-1;
			}
			printf("%lld %d\n",sum[l-1]+right-left+1-height[l][0],Query(root[l-1],root[L],0,n,1,left));
		}
	}
}
Category: 蒟蒻的滚粗记 | Tags: dp 后缀数组 | Read Count: 242
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com