lyzlyz?lyzlyz!

听说这是JSOI2015

膜了贵省的一试题目，感到不明觉厉。

T1 树形dp

怎么说呢。。。真是水题啊。。。

对于每个点可经过次数，实际上就是最多可以走过多少个儿子。所以处理出所有儿子的最优值然后取最优的若干个就可以了。

对于方案是否唯一，会有以下三种情况：

1、某个儿子的方案不唯一。

2、存在一个未选过的儿子，其最优值与某个选过的儿子的最优值相等。

3、该节点的最优值为0。

刚转C的Sb，不会用stl，于是手写了一个qsort

接着qsort写错了。。。（对此我还能说什么呢）

T2 hash

表示一看到题目被吓到了，心想究竟是打N^5还是N^4呢。

最后毅然决然打了N^5强势骗40分。

正解是：

首先预处理出矩阵对称、翻转的情况及其hash值。

枚举中心，二分边长，hash判断相同。

有一个技巧：用一个unsigned int自然溢出，可以为懒癌晚期患者提供便利。

T3 乱搞

蒟蒻表示看不懂题意。。。

请看神犇Gold7的题解：

http://gold7.is-programmer.com/posts/189435.html

【Codes】

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=200010;
int n,i,x,y,top,ans,flag,edgenum;
int head[M],vet[M],next[M],c[M],w[M];
int h[M][2];
void addedge(int x,int y){
    vet[++edgenum]=y;
    next[edgenum]=head[x];
    head[x]=edgenum;
}
bool cmp(int x,int y){
    return x>y;
}
void qsort(int l,int r){
    int i=l,j=r,mid=h[l+r>>1][0];
    do{
        while (h[i][0]>mid)i++;
        while (h[j][0]<mid)j--;
        if (i<=j){
            swap(h[i][0],h[j][0]);
            swap(h[i][1],h[j][1]);
            i++,j--;
        }
    }while (i<=j);
    if (l<j) qsort(l,j);
    if (i<r) qsort(i,r);
}
int dfs(int u,int pre){
    int e,v,i;
    int sum=w[u],st=top+1;
    for (e=head[u];e;e=next[e]){
        v=vet[e];
        if (v!=pre&&c[v]>=1)h[++top][0]=dfs(v,u),h[top][1]=flag;
    }
    flag=0;
    if (c[u]==1) {
        if (!sum) flag=1;
        return sum;
    }
    qsort(st,top);
    for (i=st;i<=top;i++){
        sum+=h[i][0];
        flag=flag|h[i][1];
        if (i-st+2==c[u])break;
    }
    if (i<top&&h[i+1][0]==h[i][0]&&h[i][0]||sum==0)flag=1;
    top=st-1;
    return max(sum,0);
} 
int main(){
    scanf("%d",&n);
    for (i=2;i<=n;i++)scanf("%d",&w[i]);
    c[1]=1000000000;
    for (i=2;i<=n;i++)scanf("%d",&c[i]);
    for (i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        addedge(x,y);
        addedge(y,x);
    }
    printf("%d\n",dfs(1,-1));
    if (flag)printf("solution is not unique\n");
        else printf("solution is unique\n");
}

#include<cstdio>
#include<algorithm>
#include<cstring>
typedef unsigned int uint;
using namespace std;
const int d1=233,d2=2333;
int n,i,j;
uint a[7][510][510];
uint Ppow[1010],Qpow[1010];
void build(int x){
	for (int i=1;i<=n;i++){
		int P=Ppow[n-i];
		for (int j=1;j<=n;j++){
			a[x][i][j]=a[x][i][j]*P*Qpow[n-j];
			a[x][i][j]+=a[x][i-1][j]+a[x][i][j-1]-a[x][i-1][j-1];
		}
	}
}
uint clac(int i,int j,int len,int x){
	return (a[x][i][j]-a[x][i-len][j]-a[x][i][j-len]+a[x][i-len][j-len])*Ppow[i]*Qpow[j];
}
int isok(int i,int j,int len,int x){
	int sum=clac(i,j,len,0);
	if (x==8)return isok(i,j,len,90)&isok(i,j,len,0);
	if (x==4)return isok(i,j,len,180)&isok(i,j,len,0);
	if (x==180&&sum==clac(n-i+len,n-j+len,len,6))return 1;
	if (x==90&&sum==clac(j,n-i+len,len,5))return 1;
	if (x==0&&(sum==clac(i,n-j+len,len,1)||sum==clac(n-i+len,j,len,2)||sum==clac(j,i,len,3)||sum==clac(n-i+len,n-j+len,len,4)))return 1;
	return 0;              
}
int check(int len,int x){
	for (int i=len;i<=n;i++)
		for (int j=len;j<=n;j++) if (isok(i,j,len,x)) return 1;
	return 0;
}
int solve(int x){
	int l,r,mid;
	for (l=1,r=n/2;mid=l+r>>1,l<=r;){
		if (check(2*mid,x))l=mid+1;else r=mid-1;}
	l--;if (!check(2*l+1,x)) return 2*l;
	for (r=n/2;mid=l+r>>1,l<=r;)
		if (check(2*mid+1,x))l=mid+1;else r=mid-1;
	l--;return 2*l+1;
}
int main(){
	scanf("%d",&n);
	char ch[n];
	for (i=1;i<=n;i++){
		scanf("%s",&ch);
		for (j=1;j<=n;j++){
			int x=ch[j-1]-'0';
			a[0][i][j]=a[1][i][n-j+1]=a[2][n-i+1][j]=a[3][j][i]=a[4][n-j+1][n-i+1]=a[5][j][n-i+1]=a[6][n-i+1][n-j+1]=x;
		}
	}
	Ppow[0]=1; for (i=1;i<=n;i++)Ppow[i]=Ppow[i-1]*d1;
	Qpow[0]=1; for (i=1;i<=n;i++)Qpow[i]=Qpow[i-1]*d2;
	for (i=0;i<=6;i++)build(i);
	printf("%d %d ",solve(8),solve(90));
	int x1=solve(4),x2=solve(180),x3=solve(0);
	if (x1==8&&x2==8&&x3==9)printf("8 8 8\n");else printf("%d %d %d\n",x1,x2,x3);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
#define A first
#define B second
using namespace std;
const int M=20010;
int n,m,cas,edgenum,i,u,v,t,cnt;
int head[M],vet[M],next[M],f[M],fa[M],hash[M],price[M],b[M],c[M];
pair<int,int>data[M];
priority_queue<int>h[M];
void addedge(int x,int y){
    vet[++edgenum]=y;
    next[edgenum]=head[x];
    head[x]=edgenum;
}
int search(int x){
    if (f[x]!=x)f[x]=search(f[x]);
    return f[x];
}
void dfs(int u){
    int e,v;
    for (int e=head[u];e;e=next[e]){
        v=vet[e];
        if (v==fa[u])continue;
        fa[v]=u;
        if (price[u]==2)f[search(v)]=search(u);
        dfs(v);
    }
}
int main(){
    scanf("%d",&m);
    for (int cas=1;cas<=m;cas++){
        edgenum=0;
        memset(head,0,sizeof head);
        memset(price,0,sizeof price);
        scanf("%d",&n);
        for (i=1;i<n;i++){
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
            price[u]++;
            price[v]++;
        }
        for (i=1;i<=n;i++)f[i]=i,hash[i]=1;
        int shit=0;
        for (i=1;i<=n;i++)if (price[i]!=2){shit=i;break;}
        fa[shit]=shit;
        dfs(shit); 
        for (i=1;i<=n;i++)b[i]=search(i),c[i]=b[i];
        sort(c+1,c+n+1);
        cnt=unique(c+1,c+n+1)-c-1;
        for (i=1;i<=n;i++)b[i]=lower_bound(c+1,c+cnt+1,b[i])-c;
        for (int t=1;t<=2;t++){
            for (i=1;i<=cnt;i++)while(!h[i].empty())h[i].pop();
            for (i=1;i<=n;i++)
                for (int e=head[i];e;e=next[e])
                    if (b[i]!=b[vet[e]])h[b[vet[e]]].push(hash[b[i]]);
            for (i=1;i<=cnt;i++){
                hash[i]=1;
                while (!h[i].empty()){
                    hash[i]=(hash[i]*10007^h[i].top()+6667)%10009;
                    h[i].pop();
                }
            }
        }
        sort(hash+1,hash+cnt+1);
        for (i=1;i<=cnt;i++) data[cas].B=(data[cas].B*10007^hash[i]+6667)%10009;
        data[cas].A=cnt;
    }
    sort(data+1,data+m+1);
    m=unique(data+1,data+m+1)-data-1;
    printf("%d\n",m);
    for (i=1;i<=m-1;i++)printf("%d ",data[i].A);
    printf("%d\n",data[m].A);
}