最近做了HNOI2014 day1和day2的题目，决定学习skydec来一发题解。。。

---

3571 画框

sol:类似于最小乘积生成树。。，把(Σa,Σb)看做平面上的一个点，易发现答案在所有的点的下凸壳内，由于点比较多，而下凸壳内的点数期望不会很多，于是分治解决。先找到Σa和Σb最小的点。然后找到离这两个点连成的这条直线最远的点。分治解决就行了。。。，计算用KM解决。。。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#define inf 21000000000000ll
#define maxn 75
using namespace std;
 
 
int visx[maxn],visy[maxn];
long long dx[maxn],dy[maxn];
int link[maxn];
long long slack[maxn];
int a[maxn][maxn],b[maxn][maxn];
long long w[maxn][maxn],ans,n,T;
struct sol
{
    int a,b;
    sol(int T=0,int C=0){a=T;b=C;}
    sol operator -(const sol &e)
    {
        return sol(a-e.a,b-e.b);
    }
    long long operator *(const sol &e)
    {
        return 1ll*a*e.b-1ll*b*e.a;
    }
};
 
 
int dfs(int x)
{
    visx[x]=1;
    for(int i=1;i<=n;i++)
    {
        if(visy[i])continue;
        long long t=dx[x]+dy[i]-w[x][i];
        if(t==0)
        {
            visy[i]=1;
            if(link[i]==-1||dfs(link[i]))
            {
                link[i]=x;
                return 1;
            }
        }else
        {
            if(t<slack[i])slack[i]=t;
        }
    }
    return 0;
}
 
 
inline sol KM()
{
    memset(dy,0,sizeof(dy));
    memset(link,-1,sizeof(link));
    for(int i=1;i<=n;i++)
    {
        dx[i]=-inf;
        for(int j=1;j<=n;j++)
        if(w[i][j]>dx[i])dx[i]=w[i][j];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)slack[j]=inf;
        while(1)
        {
            memset(visx,0,sizeof(visx));
            memset(visy,0,sizeof(visy));
            if(dfs(i))break;
            long long d=inf;
            for(int j=1;j<=n;j++)
            if(!visy[j]&&slack[j]<d)d=slack[j];
            for(int j=1;j<=n;j++)
            if(visx[j])dx[j]-=d;
            for(int j=1;j<=n;j++)
            if(visy[j])dy[j]+=d;else slack[j]-=d;
        }
    }
    int reta=0,retb=0;
    for(int i=1;i<=n;i++)
    if(link[i]!=-1)
        reta+=a[link[i]][i],
        retb+=b[link[i]][i];
    if(1ll*reta*retb<ans)ans=1ll*reta*retb;
    return sol(reta,retb);
}
 
 
inline void work(sol L,sol R)
{
    int ka=R.a-L.a,kb=R.b-L.b;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    w[i][j]=-1ll*a[i][j]*kb+1ll*b[i][j]*ka;
    sol p=KM();
    if((p-R)*(L-R)<=0)return;
    work(L,p);
    work(p,R);
}
 
 
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        ans=inf;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&b[i][j]);
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            w[i][j]=-a[i][j];
        sol ulim=KM();
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            w[i][j]=-b[i][j];
        sol dlim=KM();
        work(dlim,ulim);
        printf("%lld\n",ans);
    }
}

---

3572：世界树

sol:学习了一种叫做虚树的高大上的东西。。。虚树就是包含了所有给定点，并收缩了连续的不分叉的边的树的联通子图。在这道题中，我们需要对所有的点构建一颗虚树。至于虚树的构建么，只需要对给出的点按照dfs序的时间戳排序，然后按照笛卡尔树的思想，用单调栈维护树的最右链，并补上需要的lca节点就可以了。

    sort(h+1,h+N+1,cmp);
    for(int i=1;i<=N;i++)
    {
        int x=h[i];
        if(!top)
        {
            stack[++top]=x;
            Fa[x]=0;
            continue;
        }
        int anc=lca(x,stack[top]);
        while(top)
        {
            if(dep[stack[top]]<=dep[anc])break;
            if(dep[stack[top-1]]<=dep[anc])
                Fa[stack[top]]=anc;
            top--;
        }
        if(stack[top]!=anc)
        {
            t[++tot]=anc;
            Fa[anc]=stack[top];
            stack[++top]=anc;
            g[anc]=mp(inf,0);
        }
        Fa[x]=anc;
        stack[++top]=x;
    }

然后我们在虚树上做DP。对于虚树上的一个节点维护把这个点控制的点的编号和这个点到它的距离，然后扫描徐虚树上的每一条边并计算边的贡献。如果控制I和他父亲的点相同，那么I和父亲这一段的虚边显然属于哪个把他们控制的点。否则找到断点分别计算贡献即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 300005
#define pii pair<int,int>
#define mp make_pair
#define inf 2100000000
using namespace std;
 
 
struct e
{
    int u,v,pre;
    e(int U=0,int V=0,int P=0){u=U;v=V;pre=P;}
}edge[maxn<<1];int dex;
int n,adj[maxn],fa[maxn][21],cnt=0;
int dep[maxn],sz[maxn],st[maxn];
 
 
void dfs(int x)
{
    sz[x]=1;st[x]=(++cnt);
    for(int i=adj[x];i;i=edge[i].pre)
    {
        int v=edge[i].v;
        if(v==fa[x][0])continue;
        fa[v][0]=x;
        for(int j=1;j<=19;j++)
        fa[v][j]=fa[fa[v][j-1]][j-1];
        dep[v]=dep[x]+1;
        dfs(v);
        sz[x]+=sz[v];
    }
}
 
 
inline int cmp(const int &e,const int &f)
{
    return st[e]<st[f];
}
 
 
inline int get(int x,int d)
{
    for(int i=19;i+1;i--)
    if(dep[fa[x][i]]>=d)x=fa[x][i];
    return x;
}
 
 
inline int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    for(int i=19;i+1;i--)
    if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
    if(x==y)return x;
    for(int i=19;i+1;i--)
    if(fa[x][i]!=fa[y][i])
    {
        x=fa[x][i];
        y=fa[y][i];
    }
    return fa[x][0];
}
 
 
pii g[maxn];
int N,mem[maxn],val[maxn],w[maxn];
int stack[maxn],top,Fa[maxn],ans[maxn];
int h[maxn],t[maxn],tot=0;
inline void work()
{
    tot=0;
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        scanf("%d",&h[i]);
        mem[i]=h[i];
        t[++tot]=h[i];
        ans[h[i]]=0;
        g[h[i]]=mp(0,h[i]);
    }ans[0]=0;top=0;
    sort(h+1,h+N+1,cmp);
    for(int i=1;i<=N;i++)
    {
        int x=h[i];
        if(!top)
        {
            stack[++top]=x;
            Fa[x]=0;
            continue;
        }
        int anc=lca(x,stack[top]);
        while(top)
        {
            if(dep[stack[top]]<=dep[anc])break;
            if(dep[stack[top-1]]<=dep[anc])
                Fa[stack[top]]=anc;
            top--;
        }
        if(stack[top]!=anc)
        {
            t[++tot]=anc;
            Fa[anc]=stack[top];
            stack[++top]=anc;
            g[anc]=mp(inf,0);
        }
        Fa[x]=anc;
        stack[++top]=x;
    }
    sort(t+1,t+tot+1,cmp);
    for(int i=1;i<=tot;i++)
    {
        int z=t[i];
        val[z]=sz[z];
        if(i>1)
           w[z]=dep[z]-dep[Fa[z]];
    }
    for(int i=tot;i>1;i--)
    {
        int x=t[i];
        int father=Fa[x];
        g[father]=min(g[father],mp(g[x].first+w[x],g[x].second));
    }
    for(int i=2;i<=tot;i++)
    {
        int x=t[i],father=Fa[x];
        g[x]=min(g[x],mp(g[father].first+w[x],g[father].second));
    }
    for(int i=1;i<=tot;i++)
    {
        int x=t[i],father=Fa[x];
        if(i==1)
        {
            ans[g[x].second]+=n-sz[x];
            continue;
        }
        int G=get(x,dep[father]+1);
        int sum=sz[G]-sz[x];
        val[father]-=sz[G];
        if(g[x].second==g[father].second)
        {
            ans[g[x].second]+=sum;
            continue;
        }
        int mid=dep[x]-((g[father].first+g[x].first+w[x])/2-g[x].first);
        if(!((g[father].first+g[x].first+w[x])&1)&&g[father].second<g[x].second)++mid;
        int y=sz[get(x,mid)]-sz[x];
        ans[g[x].second]+=y;
        ans[g[father].second]+=sum-y;
    }
    for(int i=1;i<=tot;i++)ans[g[t[i]].second]+=val[t[i]];
    for(int i=1;i<=N;i++)printf("%d ",ans[mem[i]]);
    puts("");
}
 
 
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("3572.in","r",stdin);
    freopen("3572.out","w",stdout);
    #endif
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        edge[++dex]=e(u,v,adj[u]);adj[u]=dex;
        edge[++dex]=e(v,u,adj[v]);adj[v]=dex;
    }
    dep[1]=1;
    dfs(1);
    int test;
    scanf("%d",&test);
    while(test--)
        work();
    return 0;
}

---

3573：米特运输

sol:语文好题。。。读懂了题目之后发现如果某个点的值被确定，那么整棵树每个点的权值都会被确定。我们只需计算出这个点被确定时根节点的权值应该是多少，排序取众数即可。这个值会很大，需要hash

#include <cstdio>
#include <cstring>
#include <algorithm>
#define mod1 10000000000007ll
#define mod2 999999999997ll
#define maxn 500006
#define unsigned long long u64
using namespace std;
 
 
struct e
{
    int u,v,pre;
    e(int U=0,int V=0,int P=0){u=U;v=V;pre=P;}
}edge[maxn];
struct Node
{
    long long x,y;
    friend bool operator ==(const Node &e,const Node &f)
    {
        return (e.x==f.x)&&(e.y==f.y);
    }
    friend bool operator <(const Node &e,const Node &f)
    {
        return (e.x<f.x)||((e.x==f.x)&&(e.y<f.y));
    }
}c[maxn];
int adj[maxn],dex=-1,size[maxn];
int w[maxn],n;
 
 
 
 
inline void dfs(int x,long long y,long long z)
{
    c[x].x=1ll*y*w[x]%mod1;
    c[x].y=1ll*z*w[x]%mod2;
    long long newy=1ll*y*size[x]%mod1;
    long long newz=1ll*z*size[x]%mod2;
    for(int i=adj[x];i!=-1;i=edge[i].pre)
    {
        int v=edge[i].v;
        dfs(v,newy,newz);
    }
     
}
 
 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    memset(adj,-1,sizeof(adj));
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        edge[++dex]=e(u,v,adj[u]);  adj[u]=dex;
        size[u]++;
    }
    dfs(1,1ll,1ll);
    sort(c+1,c+n+1);
    int ans=2100000000;
    for(int i=1,k=0;i<=n;i++)
    {
        if(c[i]==c[i-1]||i==1)k++;else k=1;
        if(n-k<ans)ans=n-k;
    }
    printf("%d\n",ans);
    return 0;
}

---

3574 抄卡组

sol:太弱的我果断去膜拜了ydc的题解。发现只要hash就行了。。。

不难发现，如果每个点都有通配符。那么只要判断是否所有的字符串的前后缀相等就行了。如果某个单词没有通配符，那么我只要判断是否所有串都可以和他匹配。现在问题就变成了判断一个没有通配符的串和一个有通配符的串是否相等，这部分可以用hash解决。先进行第一个位置到第一个通配符的匹配和最后一个通配符到最后一个位置的匹配，再把通配符作为分割点把有通配符的串分多次去匹配就行了。。。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxE 100005
#define maxn 11000005
#define base 233
using namespace std;
typedef unsigned long long ULL;
 
 
int n,nowlen,com,now;
char str[maxn];
int cnt[maxE];
int from[maxE],to[maxE];
ULL sum[maxn],pow[maxn];
int prev[maxE],next[maxE],head,tail;
 
 
inline int check(char x)
{
    if(x>='0'&&x<='9')return 1;
    if(x>='a'&&x<='z')return 1;
    if(x=='*')return 1;
    return 0;
}
 
 
inline ULL gethash(int L,int R)
{
    return sum[R]-sum[L-1]*pow[R-L+1];
}
 
 
 
inline void init()
{
    int maxlen=0;
    com=-1;now=0;
    scanf("%d",&n);
    for(int k=1;k<=n;k++)
    {
        cnt[k]=0;
        scanf("%s",str+now+1);
        from[k]=now+1;
        int mark=1;
        for(int i=now+1;check(str[i]);i++)
        {
            str[++now]=str[i];
            if(str[now]=='*')mark=0;
            else ++cnt[k];
        }
        if(mark)com=k;
        to[k]=now;
        maxlen=max(maxlen,now);
    }
    if(nowlen<maxlen)
    for(int i=nowlen+1;i<=maxlen;i++)
        pow[i]=pow[i-1]*base;
    if(nowlen<maxlen)maxlen=nowlen;
    for(int i=1;i<=now;i++)
        sum[i]=sum[i-1]*base+str[i];
}
 
 
inline int check(int x,int y)
{
    int l=from[y],r=to[y];
    while(from[x]<=to[x]&&l<=r&&str[from[x]]!='*')
    {
        if(str[from[x]]!=str[l])return 0;
        ++from[x];++l;
    }
    while(from[x]<=to[x]&&l<=r&&str[to[x]]!='*')
    {
        if(str[to[x]]!=str[r])return 0;
        --to[x];--r;
    }
    while(from[x]<=to[x])
    {
        while(str[from[x]]=='*'&&from[x]<=to[x])
            ++from[x];
        if(from[x]>to[x])break;
        int st=from[x],ed;
        for(ed=st;str[ed]!='*';++ed);
        ULL val=gethash(st,ed-1);
        int len=ed-st;
        for(int i=l;i<=r+1;i++)
        {
            if(i+len-1>r)return 0;
            if(gethash(i,i+len-1)==val)
            {
                l=i+len;
                break;
            }
        }
        from[x]=ed;
    }
    return 1;
}
 
 
inline void work()
{
    if(com!=-1)
    {
        ULL G=gethash(from[com],to[com]);
        for(int i=1;i<=n;i++)
        {
            if(cnt[i]>cnt[com])
            {
                puts("N");
                return;
            }
            if(cnt[i]==to[i]-from[i]+1)
            {
                if(gethash(from[i],to[i])!=G)
                {
                    puts("N");
                    return;
                }
            }else
            {
                if(!check(i,com))
                {
                    puts("N");
                    return;
                }
            }
        }
        puts("Y");
        return;
    }else
    {
        head=1;tail=n;
        for(int i=1;i<=n;i++)
        {
            prev[i]=i-1;
            next[i]=i+1;
        }
        while(head<=tail)
        {
            char c=0;
            for(int i=head;i<=tail;i=next[i])
            {
                if(str[from[i]]=='*')
                {
                    prev[next[i]]=prev[i];
                    next[prev[i]]=next[i];
                    if(i==head)head=next[i];
                    if(i==tail)tail=prev[i];
                }else
                if(c==0)c=str[from[i]];
                else
                if(c!=str[from[i]])
                {
                    puts("N");
                    return;
                }
                ++from[i];
            }
        }
        head=1;tail=n;
        for(int i=1;i<=n;i++)
        {
            prev[i]=i-1;
            next[i]=i+1;
        }
        while(head<=tail)
        {
            char c=0;
            for(int i=head;i<=tail;i=next[i])
            {
                if(str[to[i]]=='*')
                {
                    prev[next[i]]=prev[i];
                    next[prev[i]]=next[i];
                    if(i==head)head=next[i];
                    if(i==tail)tail=prev[i];
                }else
                if(c==0)c=str[to[i]];
                else if(c!=str[to[i]])
                {
                    puts("N");
                    return;
                }
                --to[i];
            }
        }
        puts("Y");
        return;
    }
}
 
 
int main()
{
    int T;
    *pow=1;
    scanf("%d",&T);
    while(T--)
    {
        init();
        work();
    }
    return 0;
}

---

3575：道路阻塞

sol:基本的想法是这样的：如果一条在最短路上的边被删掉了，那么要用一些非最短路上的边来替换原来的最短路，一定是

1号点->最短路上的某个点->不在最短路上的一些点->最短路上的某个点->N号点。也就是说，一条边影响的一定是最短路上的某个区间。如果我们知道每条边影响的区间，那么我们就可以把所有边的代价（即新的路径上一定要包含这条边的代价）压到一个堆中。然后取堆的最小值即可。

想法一：一条边的新权值定义为:ds[fs[u[x]]]+w[x]+dt[ft[v[x]]] ds,dt表示1号点到它的最短路和他到N号点的最短路，fs,ft分别表示他在1~N的最短中最早什么时候离开最短路，然后用线段树区间最小维护即可。但是这个想法是错误的，它无法处理二元环的情况。。。

想法二：想法一的错误主要是对于最短路径上的区间求错。假定我们已经知道了经过前K条最短路边的最短路的情况。那么我们要求删掉第(K+1)条边的最短路，我们暴力更新每条边的区间，再把新的边权丢到堆里取最小值即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf 0x7f7f7f7f
#define INF 21000000000000ll
#define ls(x) ((x)<<1)
#define rs(x) (((x)<<1)|1)
using namespace std;
 
 
struct E
{
    int u,v,w,pre;
    E(int U=0,int V=0,int W=0,int P=0){u=U;v=V;pre=P;w=W;}
}edge[200005];
int dis[100005],pos[200005],pe[200005];
int L,fs[100005];
int ft[100005],adj[100005],deg[100005];
int rt[200005],inr[200005],n,m;
int pre[200005],suf[200005];
int p;
struct Node
{
	int x,dis;
	bool operator <(const Node &e)const
	{
		return dis>e.dis;
	}
}q[500005];


#define CH getchar()
inline void read(int &x)
{
	x=0;
	char ch=CH;
	while(!(ch>='0'&&ch<='9'))ch=CH;
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=CH;
	}
}
 


int queue[1500005],vis[100005];
int occur[100005],id,stack[100005];
int val[100005],top;
inline void spfa(int ds,int S,int lim)
{
	memset(vis,0,sizeof(vis));
	++id;dis[S]=ds;
	int l=1,r=1;
	queue[1]=S;vis[S]=1;
	for(;l<=r;l++)
	{
		int u=queue[l];
		for(int i=adj[u];i;i=edge[i].pre)
		if(!inr[i])
		{
			int v=edge[i].v;
			if(pos[v]>lim)
			{
				if(occur[v]!=id)
				{
					occur[v]=id;
					stack[++top]=v;
					val[v]=dis[u]+edge[i].w+suf[pos[v]];
				}else
				{
					val[v]=min(val[v],dis[u]+edge[i].w+suf[pos[v]]);
				}
			}else
			if(dis[u]+edge[i].w<dis[v])
			{
				dis[v]=dis[u]+edge[i].w;
				if(vis[v])continue;
				queue[++r]=v;
				vis[v]=1;
			}
		}
		vis[u]=0;
	}
	for(;top;top--)
	{
		++p;
		q[p].x=stack[top];
		q[p].dis=val[stack[top]];
		push_heap(q+1,q+p+1);
	}
}

 
inline void work()
{
    memset(dis,0x7f,sizeof(dis));
    dis[1]=0;
    for(int i=1;i<=L;i++)
    {
    	inr[rt[i]]=1;
    	spfa(pre[i],pe[i],i);
    	inr[rt[i]]=0;
    	while(p&&pos[q[1].x]<=i)
    	{
    		pop_heap(q+1,q+p+1);
    		p--;
    	}
    	if(!p)puts("-1");else printf("%d\n",q[1].dis);
    }
}
 
 
int main()
{
    read(n);read(m);read(L);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        read(u);read(v);read(w);
    	edge[i]=E(u,v,w,adj[u]);
    	adj[u]=i;
    }
    pos[1]=1;pe[1]=1;    
	for(int i=1;i<=L;i++)
    {
    	read(rt[i]);
    	pe[i+1]=edge[rt[i]].v;
    	pos[edge[rt[i]].v]=i+1;
    }
    for(int i=1;i<=L;i++)
    	pre[i+1]=pre[i]+edge[rt[i]].w;
    for(int i=L;i;i--)
    	suf[i]=suf[i+1]+edge[rt[i]].w;
    work();
    return 0;
}

---

3576：江南乐

70分的SG函数是比较显然的

考虑100分算法。发现对于一个数字x  floor(x/i)的取值只有sqrt(x)种。于是考虑分块。对于连续的一段floor(x/i)相等的数字只要考虑块内的第一个数和第二个数即可，具体如下：

设这个块中第一个数为first,floor(x/first)的值为P，x%first=Q.那么当分出first堆时，P堆石子的有first-Q个，(P+1)堆的有Q个。当分出(first+K)堆时，(P+1)堆石子的有(Q-P*K)堆，P堆石子的有((first+P)*K-Q)堆由于我们只关心P堆石子个数和(P+1)堆石子个数的奇偶性，那么当K=K0和K=K0-2时的情况是一样的，于是我们只要求K=0和K=1的情况即可。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
 
 
int test,sg[100005],F,vis[100005];
int sG[100005];
 
 
void SG()
{
    for(int i=0;i<F;i++)sg[i]=0;
    for(int i=F;i<=100000;i++)
    {
        for(int l=2,last=2;l<=i;l=last+1)
        {
            last=i/(i/l);
            int len=i/l,rem=i-len*l,REM=l-rem;
            vis[sg[(rem&1)*(len+1)]^sg[(REM&1)*len]]=i;
            int now=-1;
            if(rem>=len&&l+len+1-rem>=0)
            {
                if(now<0)now=0;
                now^=sg[((rem-len)&1)*(len+1)]^sg[((l+len+1-rem)&1)*len];
            }
            if(now>=0)vis[now]=i;
        }
        int e=0;
        for(;;e++)if(vis[e]!=i)break;
        sg[i]=e;
    }
}
 
 
void Sg()
{
    for(int i=0;i<F;i++)sG[i]=0;
    memset(vis,0,sizeof(vis));
    for(int i=F;i<=1000;i++)
    {
        for(int j=2;j<=i;j++)
        {
            int p=i/j;
            int q=i%j;
            int x=j-q;
            int now=0;
            if(q&1)now^=sG[p+1];
            if(x&1)now^=sG[p];
            vis[now]=i;
        }
        int e=0;
        for(;;e++)if(vis[e]^i)break;
        sG[i]=e;
    }
}
 
 
int main()
{
    scanf("%d%d",&test,&F);
    SG();
    while(test--)
    {
        int N,M;
        scanf("%d",&N);
        int ans=0;
        for(int i=1;i<=N;i++)scanf("%d",&M),ans^=sg[M];
        if(ans)printf("1");else printf("0");
        if(test)printf(" ");else puts("");
    }
    return 0;
}

渣代码跑的慢。。。

[取消回复评论]

昵称 登录 E-mail: *
Web:
Twitter:

当有新评论通过 E-mail 通知我

(输入验证码)

or Ctrl+Enter