2017新年做题记 - cool's Blog

2017新年做题记

cool posted @ 2017年1月01日 14:46 in 撕烤 with tags 数据结构 CF 撕烤 , 193 阅读

竟然已经2017年了,停课已经快1个月了,但是还是没有很强的鏼题能力,好惨。

[CF750E]给定一个串,求最少移去多少的字符才能使某个子串含有子序列2017不含有子序列2016

考虑暴力,总共有5个状态。

0->啥都没有 1->只有2 2->只有20 3->只有201 4->只有2017

然后可以O(n)转移。经过lbn的指导,可以把这个dp方程变成矩阵,然后只要求一段区间的矩阵和即可。

//world happy new year
#include <cstdio>
#define rep(i,a,b) for (int i = a;i <= b;i++) 
#define N 550000
#define M 200010
#define inf 100000000
char s[M];
int n,q,x,y;
struct xfy
{
	int a[5][5];
	void reset()
	{
		rep(i,0,4) rep(j,0,4) a[i][j] = inf;
		rep(i,0,4) a[i][i] = 0;
	}
	void init(int x)
	{
		reset();
		if (x == 2) a[0][0] = 1, a[0][1] = 0;
		else if (x == 0) a[1][1] = 1, a[1][2] = 0;
		else if (x == 1) a[2][2] = 1, a[2][3] = 0;
		else if (x == 6) a[3][3] = 1, a[4][4] = 1;
		else if (x == 7) a[3][3] = 1, a[3][4] = 0;
	}
}dp[N],ans;
void checkmin(int& x,int y)
{
	if (x > y) x = y;
}

xfy operator +(xfy x,xfy y)
{
	xfy c;
	rep(i,0,4) rep(j,0,4)
	{
		c.a[i][j] = inf;
		rep(k,0,4) checkmin(c.a[i][j],x.a[i][k]+y.a[k][j]);
	}
	return c;
}
#define lson l,mid,k<<1
#define rson mid+1,r,k<<1|1 
void Build(int l,int r,int k)
{
	if (l == r)
	{
		dp[k].init(s[l]-'0');
		return;
	}
	int mid = l+r>>1;
	Build(lson); Build(rson);
	dp[k] = dp[k<<1]+dp[k<<1|1];
}

void query(int L,int R,int l,int r,int k)
{
	if (L <= l && r <= R)
	{
		ans = ans+dp[k];
		return;
	}
	int mid = l+r>>1;
	if (L <= mid) query(L,R,lson);
	if (R > mid) query(L,R,rson);
}

int main()
{
	scanf("%d%d%s",&n,&q,s+1);
	Build(1,n,1);
	for (;q--;)
	{
		scanf("%d%d",&x,&y);
		ans.reset();
		query(x,y,1,n,1);
		if (ans.a[0][4] > n) puts("-1");
		else printf("%d\n",ans.a[0][4]);
	}
	return 0;
}

[CF749E]对于一个1-n的全排列,随机选择一个区间并random_shuffle,求一次操作后的期望逆序对数。

首先一个长度为k的序列,打乱后的期望逆序对为k*(k-1)/4

那么现在只要求出每个区间的逆序对和即可。

考虑ans[i]为所有已i的开始的区间的逆序对和,如果已知ans[i+1],那么第i+1~n个数中每个数被计算的次数要么是0,要么是n-j+1,所以用树状数组维护即可,每次add(a[i],n-i+1)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000007
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 100010
double ans1,ans2,tmp,S;
int a[N],n;
ll g[N];
void add(int x,int y)
{
	for (;x <= n;x += x&-x)
		g[x] += y;
}

ll query(int x)
{
	ll y = 0;
	for (;x;x -= x&-x)
		y += g[x];
	return y;
}

int main()
{
	scanf("%d",&n);
	rep(i,1,n) scanf("%d",&a[i]);
	drep(i,n,1)
	{
		ans1 += (double)query(a[i]);
		add(a[i],1);
	}
	clr(g,0);
	drep(i,n,1)
	{
		ans2 -= (double)query(a[i])*i;
		add(a[i],n-i+1);
	}
	rep(i,1,n)
	{
		tmp += (double)(i-1)/2.0;
		ans2 += (double)tmp*(n-i+1);
	}
	printf("%.10f",ans1+2.0*ans2/n/(n+1));
	return 0;
}

[CF735E]给一棵树黑白染色,要求每个点离最近的黑色点的距离<=k,求方案数。(n<=100,k<=20)

不是很懂这个数据,感觉是nk^2的。dp[0][n][i]表示符合条件的情况下,最近的黑点距自己i。

dp[1][n][i]表示符合条件的情况下,最远的不符合的点距自己i。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000007
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 110
int h[N<<1],last[N<<1],head[N],l;
int n,k,x,y,f[2][N][25],f0[25],f1[25],ans;

void Add(int& x,int y)
{
	x += y;
	if (x >= zhl) x -= zhl;
	if (x < 0) x += zhl;
}

void add(int x,int y)
{
	h[++l] = y;
	last[l] = head[x];
	head[x] = l;
}

void dfs(int x,int fa)
{
	f[0][x][0] = f[1][x][0] = 1;
	for (int i = head[x],y;i;i = last[i])
	{
		if ((y=h[i]) == fa) continue;
		dfs(y,x); clr(f0,0); clr(f1,0);
		rep(w,0,k) rep(j,0,k) Add(f0[min(w,j+1)],(ll)f[0][x][w]*f[0][y][j]%zhl);
		rep(w,0,k) rep(j,0,k) if (w+j+1 <= k) Add(f0[w],(ll)f[0][x][w]*f[1][y][j]%zhl);
			else Add(f1[j+1],(ll)f[0][x][w]*f[1][y][j]%zhl);
		rep(w,0,k) rep(j,0,k) if (w+j+1 <= k) Add(f0[j+1],(ll)f[1][x][w]*f[0][y][j]%zhl);
			else Add(f1[w],(ll)f[1][x][w]*f[0][y][j]%zhl);
		rep(w,0,k) rep(j,0,k) Add(f1[max(w,j+1)],(ll)f[1][x][w]*f[1][y][j]%zhl);
		memcpy(f[0][x],f0,sizeof(f0));
		memcpy(f[1][x],f1,sizeof(f1));
	}
}

int main()
{
	scanf("%d%d",&n,&k);
	rep(i,2,n)
	{
		scanf("%d%d",&x,&y);
		add(x,y); add(y,x);
	}
	dfs(1,0);
	rep(i,0,k) Add(ans,f[0][1][i]);
	printf("%d",ans);
	return 0;
}

[bzoj3513]n个ai的木棍,求选出三根不能拼成三角形的概率。ai<=1e6

做的第一道fft优化dp,裸题。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000007
const double pi=3.141592653589793238462643383279502884197169399375105820974944;
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define NN 400010
struct E
{
	double r,i;
	E(double _r=0,double _i=0):  r(_r),i(_i){}
	E operator+(E x){return E(r+x.r,i+x.i);}
	E operator-(E x){return E(r-x.r,i-x.i);}
	E operator*(E x){return E(r*x.r-i*x.i,r*x.i+i*x.r);}  
}a[NN],b[NN],c[NN];
int n,m,L,R[NN],s[NN],T,mx,N,x;
ll ans,tot,sum;
void fft(E *a,int f,int n)
{
	rep(i,0,n-1) if(i<R[i]) swap(a[i],a[R[i]]);
	for(int i=1;i<n;i<<=1)
	{
		E wn(cos(pi/i),f*sin(pi/i));
		for(int j=0;j<n;j+=(i<<1))
		{
			E w(1,0);
			for(int k=0;k<i;k++,w=w*wn)
			{
				E x=a[j+k],y=w*a[j+k+i];
				a[j+k]=x+y;a[j+k+i]=x-y;
			}
		}
	}
	if(f==-1) rep(i,0,n-1) a[i].r/=n;
}

int main()
{
	for (scanf("%d",&T);T--;)
	{
		scanf("%d",&n); mx = 0; clr(s,0);
		rep(i,1,n) scanf("%d",&x),s[x]++,mx = max(mx,x);
		for (N=1,L=0;N<mx+1;N<<=1,L++);  
		N<<=1; L++; mx++; clr(R,0);
		rep(i,0,N-1) R[i] = (R[i>>1]>>1)|((i&1)<<(L-1));
		rep(i,0,N-1) a[i] = b[i] = E((double)s[i]);
		fft(a,1,N); fft(b,1,N);
		rep(i,0,N-1) c[i] = a[i]*b[i];
		fft(c,-1,N);
		ans=0,tot=1LL*n*(n-1)*(n-2)/6,sum=0;
		rep(i,0,mx)
		{
			sum+=(ll)(c[i].r+0.5);
			if (i%2==0) sum-=s[i/2];
			if (!s[i]) continue;
			ans+=1LL*sum*s[i];
		}
		ans/=2;
		printf("%.7lf\n",1.0-(double)ans/tot);
    }
    return 0;
}

[CF739E]好神的题目,还没有完全理解这个做法。

f[i][j][k]=max(f[i-1][j][k],f[i-1][j-1][k]+p[i],f[i-1][j][k-1]+u[i],f[i-1][j-1][k-1]+t[i])

t[i]=1-(1-u[i])(1-p[i])

这样是O(n^3)的

f[i][j][k]是一个关于k单调的凸函数,我们假定一个常数S,那么f[i][j][k]-S*k一定是一个凸函数,设其极值点为x0.

那么f[n][a]的极值点是可以通过O(n^2)的,如果极值点为b那么f[n][a][b]+S*b就是答案,然后二分S即可。

感觉整个过程,就是通过max传递极值点的性质来做的。撕烤一下如何举一反三。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000007
#define eps 1e-9
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 2010
int n,a,b;
double p[N],u[N],t[N],f[N][N],g[N][N],l,r;
double slop(double K)
{
	double f1,g1;
	rep(i,1,n) rep(j,0,a)
	{
		f1 = g1 = 0;
		if (f[i-1][j] > f1+eps) f1 = f[i-1][j],g1 = g[i-1][j];
		if (f[i-1][j]-K+u[i] > f1+eps) f1 = f[i-1][j]-K+u[i],g1 = g[i-1][j]+1;
		if (j && f[i-1][j-1]+p[i] > f1+eps) f1 = f[i-1][j-1]+p[i],g1 = g[i-1][j-1];
		if (j && f[i-1][j-1]+t[i]-K > f1+eps) f1 = f[i-1][j-1]+t[i]-K,g1 = g[i-1][j-1]+1;
		f[i][j] = f1; g[i][j] = g1;
	}
	return g[n][a];
}

int main()
{
	scanf("%d%d%d",&n,&a,&b);
	rep(i,1,n) scanf("%lf",&p[i]);
	rep(i,1,n) scanf("%lf",&u[i]);
	rep(i,1,n) t[i] = 1.0-(1.0-p[i])*(1.0-u[i]);
	for (l = -2000,r = 2000;r-l>eps;)
	{
		double mid = (l+r)*0.5;
		if (slop(mid)<b) r = mid;
		else l = mid;
	}
	printf("%.5lf",f[n][a]+l*b);
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee