Diary of March 11th

3
11
2016

今天没有模拟赛

又是悠闲的一天

Codeforces635C

搜索大法好

剪枝保平安

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline int IN(){
	int x=0,ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void Out(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) Out(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
ll a[45],s,x,Ans;
int ax;
void DFS(int dig,ll sum){
	if (dig==-1){
		if (sum==s) Ans+=a[ax];
		return;
	}
	if ((x>>dig)&1){
		if (sum+a[dig]<=s) DFS(dig-1,sum+a[dig]);
	}
	else{
		if (sum+a[dig+1]<=s) DFS(dig-1,sum+a[dig+1]);
		if (sum+a[dig+1]-2>=s) DFS(dig-1,sum);
	}
}
int main(){
	a[0]=1;
	Rep(i,1,41) a[i]=a[i-1]<<1;
	scanf("%I64d%I64d",&s,&x);
	if (x==0){
		if (s&1||s<2) puts("0");else puts("1");
		return 0;
	}
	Rep(i,0,40) if ((x>>i)&1) ax++;
	DFS(40,0);
	if (s==x) Ans-=2;
	Out(Ans);
}

Codeforces178F

先按字典序排一下序

然后把每两个相邻串的lcp都暴力求出来

比较显然的就是$f(i,j)=min\{f(k,k+1)\},其中i≤k<j$

然后就可以区间DP了

$F$ 数组每个节点表示一段区间

处理时找出其中的$min$，递归处理$l\sim min$,$min+1\sim r$

以此类推主要就是这样了

不懂的可以看代码很容易懂

复杂度就是$O(n^2)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline int IN(){
	int x=0,ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void Out(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) Out(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
string s[2005];
char S[505];
int n,k,T;
ll f[2005][2005],pre[2005];
int solve(int l,int r){
	if (l==r) return 0;
	int now=++T,Mn=oo,pos;
	Rep(i,l,r-1) if (pre[i]<Mn) Mn=pre[i],pos=i;
	int L=solve(l,pos),R=solve(pos+1,r);
	Rep(i,0,pos-l+1) Rep(j,0,r-pos)
		f[now][i+j]=max(f[now][i+j],f[L][i]+f[R][j]+1ll*i*j*Mn);
	return now;
}
int main(){
	n=IN(),k=IN();
	Rep(i,1,n){
		scanf("%s",S);
		s[i]=string(S);
	}
	sort(s+1,s+n+1);
	Rep(i,1,n-1){
		int cur=0;
		while (cur<s[i].size()&&cur<s[i+1].size()&&s[i][cur]==s[i+1][cur]) cur++;
		pre[i]=cur;
	}
	Out(f[solve(1,n)][k]);
}

Codeforces631E

斜率优化DP

首先读入数据存到数组$ A $中，再设一个$ P $数组。

其中$P_i=\sum_{j=1}^{j≤i}{A_j}$ （嘿嘿嘿，就是前缀和）

考虑 $k,j$ 换到位置 $i$ 的贡献 $(k<j<i)$

如果 $j$ 比 $k$ 优，就是

$P_k-P_i+A_k*(i-k)<P_j-P_i+A_j*(i-j)$

移项之后，得到

$P_k-k*A_k-P_j+j*A_j<i*(A_j-A_k)$

然后就可以斜率优化辣！

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline int IN(){
	int x=0,ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void Out(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) Out(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=200005;
int h,t,n,q[N];
ll Ans,Max=-oo,a[N],p[N],b[N];
ll Y(int k,int j){return p[k]-a[k]*k-p[j]+a[j]*j;}
ll X(int k,int j){return a[j]-a[k];}
int main(){
	n=IN();
	Rep(i,1,n) a[i]=IN(),b[n-i+1]=a[i],Ans+=a[i]*i;
	Rep(i,1,n) p[i]=p[i-1]+a[i];
	h=t=1;q[1]=1;
	Rep(i,2,n){
		while (h<t&&Y(q[t],i)*X(q[t-1],q[t])<=Y(q[t-1],q[t])*X(q[t],i)) t--;
		q[++t]=i;
		while (h<t&&Y(q[h],q[h+1])<X(q[h],q[h+1])*i) h++;
		Max=max(Max,p[q[h]]-p[i]+a[q[h]]*(i-q[h]));
	}
	Rep(i,1,n) a[i]=b[i];
	Rep(i,1,n) p[i]=p[i-1]+a[i];
	h=t=1;q[1]=1;
	Rep(i,2,n){
		while (h<t&&Y(q[t],i)*X(q[t-1],q[t])<=Y(q[t-1],q[t])*X(q[t],i)) t--;
		q[++t]=i;
		while (h<t&&Y(q[h],q[h+1])<X(q[h],q[h+1])*i) h++;
		Max=max(Max,p[i]-p[q[h]]+a[q[h]]*(q[h]-i));
	}
	Out(Ans+Max);
}

Codeforces633E

首先把每个l的r处理出来……

怎么处理呢？？？二分

因为R不下降，C不上升

所以就可以每次二分找到R和C相差最小的

这个可以用ST表 $O(nlog_2^n)$预处理，$O(1)$查询

然后排序一下

某个数产生贡献的概率就是它前面全都不选，

它一定选，然后后面随便选

所以第i个数产生贡献的概率就是$\frac{C_{n-i}^{k-1}}{C_n^k}$

从前往后搞一搞就好了

不懂的可以看代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline int IN(){
	int x=0,ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void Out(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) Out(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=1000005;
int lg[N],pw[25],v[N][25],c[N][25],val[N]; 
int t,h,n,k,sx;
int BnrSac(int l,int r){
	while (l<r){
		int mid=l+r+1>>1,bl=lg[mid-l+1];
		int V=max(v[l][bl],v[mid-pw[bl]+1][bl]);
		int C=min(c[l][bl],c[mid-pw[bl]+1][bl]);
		if (V<=C) l=mid;else r=mid-1;
	}
	return l;
}
int main(){
	n=IN(),k=IN();
	lg[1]=0;Rep(i,2,n) lg[i]=lg[i>>1]+1;
	pw[0]=1;Rep(i,1,lg[n]+1) pw[i]=pw[i-1]<<1;
	Rep(i,1,n) v[i][0]=IN()*100;
	Rep(i,1,n) c[i][0]=IN();
	Rep(j,1,lg[n]+1) Rep(i,1,n-pw[j-1])
		v[i][j]=max(v[i][j-1],v[i+pw[j-1]][j-1]),
		c[i][j]=min(c[i][j-1],c[i+pw[j-1]][j-1]);
	Rep(i,1,n){
		int pos=BnrSac(i,n),bl=lg[pos-i+1];
		int V=max(v[i][bl],v[pos-pw[bl]+1][bl]);
		int C=min(c[i][bl],c[pos-pw[bl]+1][bl]);
		val[i]=min(V,C);
		V=max(V,v[pos+1][0]),C=min(C,c[pos+1][0]);
		val[i]=max(val[i],min(V,C));
	}
	sort(val+1,val+n+1);
	long double Ans=0,nrt=1.0*k/n;
	Rep(i,1,n-k+1){
		Ans+=nrt*val[i];
		nrt=nrt/(n-i)*(n-k+1-i);
	}
	printf("%.10lf\n",(double)Ans);
}

Category: Diary | Tags: 搜索区间DP DP 凸包二分概率/期望 | Read Count: 415

WTRC's Memory

三世烟火沧笙踏歌