在bzoj混不下去了，开始在各大oj上鏼题。

[CF691F]Couple Cover

题意：n个数，q个询问，每次询问有多少对数的积大于等于p。

cnt[i]表示i出现的次数。f[i]表示有多少对数积为i。

f[i]=Σcnt[d]*cnt[n/d]

根据调和级数计算即可。

#include <cstdio>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define F 3000000
#define ll long long
int cnt[F+10],n,x,q;
ll f[F+10],all;
int main()
{
	scanf("%d",&n);
	rep(i,1,n) scanf("%d",&x),cnt[x]++;
	rep(i,1,F)
		for (int j = i,k = 1;j <= F;j += i,k++)
		{
			if (k == i) f[j] += (ll)cnt[i]*(cnt[i]-1);
			else f[j] += (ll)cnt[i]*cnt[k];
		}
	rep(i,1,F) f[i] += f[i-1];
	scanf("%d",&q); all = (ll)n*(n-1);
	rep(i,1,q)
	{
		scanf("%d",&x);
		printf("%I64d\n",all-f[x-1]);
	}
	return 0;
}

[bzoj4566]求两个串有多少相同的子串。

建SAM，然后求出每个串在原串中的出现次数。

ans=Σ(mx[i]-mx[fa[i]])*sz[0]*sz[1];

#include <cstdio>
#include <cstring>
#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 N 200010
#define M 800010
using namespace std;
int len,cnt=1;
char s1[N];

int last,np,p,q,nq,fa[M],mx[M],a[M][26],sz[M][2],c[N],t[M];
long long ans;
void extend(int c)
{
	p=last; np=a[p][c];
	if(np&&mx[np]==mx[p]+1) last=np;
	else
	{
		mx[np=++cnt]=mx[last]+1;
		for(;p&&!a[p][c];p=fa[p])a[p][c]=np;
		if(!p) fa[np]=1;
		else
		{
			q=a[p][c];
			if(mx[p]+1==mx[q]) fa[np]=q;
			else
			{
				nq=++cnt; mx[nq]=mx[p]+1;
				memcpy(a[nq],a[q],sizeof(a[nq]));
				fa[nq]=fa[q]; fa[q]=fa[np]=nq;
				for(;p&&a[p][c]==q;p=fa[p])a[p][c]=nq;
			}
		}
		last=np;
	}
}
int main()
{
	scanf("%s",s1+1);
	len = strlen(s1+1);
	last = 1; rep(i,1,len) extend(s1[i]-'a'),sz[last][0]++;
	scanf("%s",s1+1);
	len = strlen(s1+1);
	last = 1; rep(i,1,len) extend(s1[i]-'a'),sz[last][1]++;
	rep(i,1,cnt) c[mx[i]]++;
	rep(i,1,N) c[i] += c[i-1];
	rep(i,1,cnt) t[c[mx[i]]--] = i;
	drep(i,cnt,1)
	{
		sz[fa[t[i]]][0] += sz[t[i]][0];
		sz[fa[t[i]]][1] += sz[t[i]][1];
	}
	rep(i,1,cnt) ans += (long long)(mx[i]-mx[fa[i]])*sz[i][0]*sz[i][1];
	printf("%lld",ans);
	return 0;
}

[hdu5945]给定X,k,t X可以减去[1,t]的任意数，如果X为k的倍数还可以/k，求最少几步到1。

单调队列优化DP。

#include <cstdio>
#include <cstring>
#include <algorithm>
#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 N 1000010
using namespace std;
int X,k,t,T,f[N],d[N],l,r;
int main()
{
	for (scanf("%d",&T);T--;)
	{
		scanf("%d%d%d",&X,&k,&t);
		memset(f,63,sizeof(f));
		f[1] = 0;
		d[l=r=1] = 1;
		rep(i,2,X)
		{
			if (i % k == 0) f[i] = f[i/k]+1;
			for (;l <= r && d[l]+t < i;l++);
			f[i] = min(f[d[l]]+1,f[i]);
			d[++r] = i;
			for (;l < r && f[d[r]] < f[d[r-1]];d[r-1] = d[r--]);
		}
		printf("%d\n",f[X]);
	}
	return 0;
}

[hdu5946]一棵以1为根的树，每个节点有黑白颜色和一个权值ai，每次操作一个点i，可以使i的子树内深度为d[i]~d[i]+a[i]的节点反色，每次等概率选择一点，求期望几次使整棵树变黑。

首先因为考虑每个操作之间是无法取代的，也就是说，方案是唯一的。

所以题目简化为n个点期望几次后，有k个点被翻奇数次，高斯消元解方程即可。

一开始没加memset(head,0,sizeof(head)),T了好几发。

#include <cstdio>
#include <cstring>
#include <algorithm>
#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 N 55
#define ld long double
using namespace std;
int h[N<<1],last[N<<1],head[N],n,T,l,x,y,ans;
ld a[N][N];

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

void gauss()
{
	memset(a,0,sizeof(a));
	a[n][n] = 1;
	rep(i,0,n-1)
	{
		a[i][i] = 1;
		a[i][i+1] = -(n-i)/(ld)(n);
		if (i) a[i][i-1] = -i/(ld)(n);
		a[i][n+1] = 1;
	}
	rep(i,0,n)
	{
		int k;
		rep(j,i,n) if (a[k=j][i]) break;
		rep(j,0,n+1) swap(a[k][j],a[i][j]);
		rep(j,i+1,n)
		{
			ld t = a[j][i]/a[i][i];
			rep(k,i,n+1) a[j][k] -= a[i][k]*t;
		}
	}
	drep(i,n,0)
	{
		a[i][n+1] /= a[i][i]; a[i][i] = 1;
		rep(j,0,i-1) a[j][n+1] -= a[j][i]*a[i][n+1];
	}
}

int dep[N],c[N],st[N],top,fz[N],A[N];
void dfs(int x,int fa)
{
	dep[x] = dep[fa]+1;
	int col = c[x];
	rep(i,1,top) if (dep[x]-dep[st[i]] <= A[st[i]])
		col ^= 1;
	if (!col) fz[x] = 1,st[++top] = x;
	for (int i = head[x],y;i;i = last[i])
	{
		if ((y=h[i]) == fa) continue;
		dfs(y,x);
	}
	if (!col) top--;
}

int main()
{
	for (scanf("%d",&T);T--;ans = 0)
	{
		scanf("%d",&n);
		l = 0;
		memset(head,0,sizeof(head));
		rep(i,2,n)
		{
			scanf("%d%d",&x,&y);
			add(x,y), add(y,x);
		}
		rep(i,1,n) scanf("%d",&c[i]);
		rep(i,1,n) scanf("%d",&A[i]);
		memset(fz,0,sizeof(fz));
		dfs(1,0);
		gauss();
		rep(i,1,n) if (!fz[i])
			ans++;
		printf("%.3lf\n",double(a[ans][n+1]));
	}
}

[CF671D]给定一棵以1为根的树，有m个工人，每个工人可以覆盖从u到v的边，花费为c，求覆盖所有路径的最小花费。

题目保证v是u的祖先。n,m<=3e5

好神的题啊。

先看了英文题解，完全不知道在讲什么。然后又看了标程，TM的指针完全看不懂。

百度了一下题解，只有两个小哥，一个小哥写的线段树，一个小哥写的可并堆（这个小哥namespace一大堆，全篇代码都是heap::和tree::完全没心情看），不过两个人的代码都看不懂。

在CF上找了一个比较短的可并堆AC代码看了大概一个半小时，终于看懂在干什么了。（不过估计也看不懂我讲的是啥）

考虑一个比较暴力的dp。令f[i][j]表示i这个子树被完全覆盖且向上覆盖了j条边。

那么有两种转移

第一种是f[i][j]=c[p]+Σf[q][1]，q为i的所有儿子，p为出发点在i，且至少能向上走j的最小花费的工人。

另一种是f[i][j]=min(f[p][j+1]+Σf[q][1])p为i的一个儿子，q为i的其他儿子。

这样转移是O(m+n^2)的。

接下来我们这么撕烤，设g[i]=f[i][1]。

对于一棵子树i，一个工人p，如果工人p能够对g有影响（就是终点在i之上），

那么在这棵子树里对于这个工人 g[i]=c[p]+Σg[q] q为p从u到i的所有节点的所有儿子,

那么我们在每次计算子树的时候把Σg[q]加到这个工人上，也就是每次加Σg[q]-g[t]，q为i的所有儿子，t为i的某一个儿子且为工人p的祖先。

用可并堆维护最小值即可（我TM到底在说什么）

没看懂的话可以借助代码理解（语文真的好差，王老师我来上语文课了）

#include <cstdio>
#include <cstring>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define G 900010
#define N 300010
#define ll long long
template<class T> inline void swap(T &x,T &y)
{
	T a = x; x = y;y = a;
}
int h[G],last[G],up[N],head[N],l,rt[N],dep[N];
void Add(int x,int y)
{
	h[++l] = y;
	last[l] = up[x];
	up[x] = l;
}

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

struct heap
{
	int l,r,d,id;
	ll w,lazy;
//	heap(int l,int r,int d,int id,ll w,ll lazy):l(l),r(r),d(d),id(id),w(w),lazy(lazy){}
}a[N];
void pushdown(int u)
{
	ll d = a[u].lazy;
	if (d)
	{
		int L = a[u].l,R = a[u].r;
		a[u].w += d;
		if (L) a[L].lazy += d;
		if (R) a[R].lazy += d;
		a[u].lazy = 0;
	}
}

int merge(int u,int v) //左偏树 
{
	if (!u || !v) return u+v;
	pushdown(u); pushdown(v);
	if (a[u].w > a[v].w) swap(u,v);
	int L = a[u].l,R = a[u].r = merge(a[u].r,v);
	if (a[L].d < a[R].d) swap(a[u].l,a[u].r);
	a[u].d = a[a[u].l].d+1;
	return u;
}

void pop(int &u)
{
	pushdown(u);
	u = merge(a[u].l,a[u].r);
}

int flag,sz,u[N],v[N],c[N],x,y,n,m;
ll f[N],ans;
void dfs(int x,int fa)
{
	ll sum = 0;
	for (int i = head[x],y;i;i = last[i])
	{
		if ((y=h[i]) == fa) continue;
		dep[y] = dep[x]+1;
		dfs(y,x);
		sum += f[y];
	}
	if (flag) return;
	for (int i = up[x],y;i;i = last[i])
	{
		y = h[i];
		a[++sz] = (heap){0,0,0,v[y],sum+c[y],0};
		rt[x] = merge(rt[x],sz);
	}
	for (int i = head[x],y;i;i = last[i])
	{
		if ((y=h[i]) == fa) continue;
		a[rt[y]].lazy += sum-f[y];
		rt[x] = merge(rt[x],rt[y]);
	}
	for (;rt[x] && dep[a[rt[x]].id] >= dep[x];pop(rt[x]));
	if (!rt[x] && x != 1) { flag = 1; return;}
	pushdown(rt[x]);
	f[x] = a[rt[x]].w;
}

int main()
{
	scanf("%d%d",&n,&m);
	rep(i,2,n)
	{
		scanf("%d%d",&x,&y);
		add(x,y); add(y,x);
	}
	rep(i,1,m)
	{
		scanf("%d%d%d",&u[i],&v[i],&c[i]);
		Add(u[i],i);
	}
	memset(f,63,sizeof(f));
	dfs(1,0);
	if (flag) puts("-1");
	else
	{
		for (int i = head[1];i;i = last[i])
			ans += f[h[i]];
		printf("%I64d",ans);
	}
	return 0;
}