早上考试被题目虐成猪头了

第一题：refrain 

第一问随便递推  然后第二问burnside定理乱搞

第二题：resonance

大意就是求一个内部无给定点的最大面积凸包  各种预处理 然后就开始无脑维护凸性进行DP

第三题：recompile

丧心病狂的题目啊啊啊啊啊啊啊  

一棵树  支持三个操作 ①将一个点到根的路径全部染成一种之前没有的颜色  ②把一个点设为根 然后进行一遍①操作   ③查询一棵子树中的所有点到跟的路径上的颜色数的平均值

据说这个②操作与LinkCutTree的access（有些人叫expose）操作一个意思  然后经过的颜色数就是经过的轻边数+1

再以tsinsenA1353的思想用线段树+DFS序维护换根操作 然后就能AC了

对于新的根在原树中考虑与查询点的相对位置 然后分三种情况讨论

①root=x 查询全树

②root的DFS序区间包含x区间或无包含关系 查询x对应区间

③root的DFS序区间被x的区间所包含 查询x区间的两边的两个区间

下面贴一下tsinsenA1353（BZOJ3306）的代码 （风格分93分 ^_^）

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
using namespace std;

const int maxn=100086;

struct Segment_Tree
{
	int l;
	int r;
	int min;
}node[maxn*4];

struct Edge
{
	int next;
	int to;
}edge[maxn*2];

int head[maxn],n,m,num_edge,dep[maxn],seq[maxn],val[maxn],pos1[maxn],corres[maxn]
	,pos2[maxn],a,b,f[maxn][25],len,now_root;
char order[10];

inline int imin(int p,int q){if(p<q)return p;return q;}

void add_edge(int from,int to)
{
	edge[++num_edge].to=to;
	edge[num_edge].next=head[from];
	head[from]=num_edge;
	
	edge[++num_edge].to=from;
	edge[num_edge].next=head[to];
	head[to]=num_edge;
}

void BFS()
{
	queue<int>qs;
	int tmp;
	qs.push(1);
	dep[1]=1;
	while(!qs.empty())
	{
		tmp=qs.front();
		qs.pop();
		for(int i=1;i<=20;i++)
			f[tmp][i]=f[f[tmp][i-1]][i-1];
		for(int i=head[tmp];i!=0;i=edge[i].next)
		{
			if(!dep[edge[i].to])
			{
				dep[edge[i].to]=dep[tmp]+1;
				f[edge[i].to][0]=tmp;
				qs.push(edge[i].to);
			}
		}
	}
}

void DFS(int now)
{
	seq[++len]=now;
	pos1[now]=len;
	for(int i=head[now];i!=0;i=edge[i].next)
		if(!pos1[edge[i].to])
			DFS(edge[i].to);
	pos2[now]=len;
}

void build(int l,int r,int pos)
{
	node[pos].l=l;
	node[pos].r=r;
	if(l<r)
	{
		int mid=(l+r)>>1;
		build(l,mid,pos*2);
		build(mid+1,r,pos*2+1);
		node[pos].min=imin(node[pos*2].min,node[pos*2+1].min);
	}
	else node[pos].min=val[corres[l]];
}

void modify_min(int key,int pos)
{
	if((node[pos].l==key)&&(node[pos].r==key))
	{
		node[pos].min=val[corres[key]];
		return;
	}
	int mid=(node[pos].l+node[pos].r)>>1;
	if(key<=mid)modify_min(key,pos*2);
	else modify_min(key,pos*2+1);
	node[pos].min=imin(node[pos*2].min,node[pos*2+1].min);
}

int query_min(int l,int r,int pos)
{
	if((node[pos].l==l)&&(node[pos].r==r))return node[pos].min;
	int mid=(node[pos].l+node[pos].r)>>1,t,t1,t2;
	if(l>mid)return query_min(l,r,pos*2+1);
	else if(mid>=r)return query_min(l,r,pos*2);
	else 
	{
		t1=query_min(mid+1,r,pos*2+1);
		t2=query_min(l,mid,pos*2);
		t=imin(t1,t2);
		return t;
	}
}

int anc(int now,int k)
{
	for(int i=20;i>=0;i--)
		if(k&(1<<i))
			now=f[now][i];
	return now;
}

int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d",&a,&val[i]);
		if(a!=0)add_edge(a,i);
	}
	BFS();
	DFS(1);
	now_root=1;
	for(int i=1;i<=n;i++)
		corres[pos1[i]]=i;
	build(1,n,1);
	for(int i=1;i<=m;i++)
	{
		scanf("%s",order);
		if(order[0]=='E')
			scanf("%d",&now_root);
		if(order[0]=='V')
		{
			scanf("%d %d",&a,&b);
			val[a]=b;
			modify_min(pos1[a],1);
		}
		if(order[0]=='Q')
		{
			scanf("%d",&a);
			if(a==now_root)
				printf("%d\n",query_min(1,n,1));
			else if((pos1[a]<pos1[now_root])&&(pos2[a]>=pos2[now_root]))
			{
				int tmp=anc(now_root,dep[now_root]-dep[a]-1),t1,t2,t;
				t1=query_min(1,pos1[tmp]-1,1);
				t2=query_min(pos2[tmp]+1,n,1);
				t=imin(t1,t2);
				printf("%d\n",t);
			}
			else 
				printf("%d\n",query_min(pos1[a],pos2[a],1));
		}
	}
	return 0;
}

讲课：

马尔科夫过程：（1）解方程O（n^3）（2）生成函数（形式函数）（牛逼闪闪）

纳什均衡 

缓存规划

BLAS

线性规划：大系数 辅助 布兰德规则 线性规划对偶

后面没听懂......

就这样吧