高橋・直樹's Blog

http://www.lydsy.com/JudgeOnline/problem.php?id=1772

题意

给定一个N行的三角形矩阵，如图

求一个点到另外几个给定的点的距离中，最短的距离。

题解

挺好玩的，重建三维坐标系

对于三角形（i，j）

x=i,y=(j+1)div 2,z=(i*2-1-j+1)div 2=i-j div 2

可以证明对于任意两个三角形，

他们的距离恰为|x1-x2|+|y1-y2|+|z1-z2|。

#include<cstring>
#include<algorithm>
#include<cstdio>
#include<climits>
using namespace std;
const int N=10001;
int X[N],Y[N],n,m,sx,sy,sz,ax,ay,d;
 
int main()
{
    int a,b,x,y,z;
    scanf("%d%d%d%d",&n,&m,&a,&b);
    //x=i,y=(j+1)div 2,z=i-j div 2;
    sx=a;sy=(b+1)/2;sz=a-b/2;
    d=INT_MAX;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        x=a;y=(b+1)/2;z=a-b/2;
        int tmp=abs(x-sx)+abs(y-sy)+abs(z-sz);
        if((tmp<d)||(tmp==d && ax>a)||(tmp==d && ax==a && ay>b))
            ax=a,ay=b,d=tmp;
    }
    printf("%d %d\n",ax,ay);
    printf("%d\n",d+1);
}

http://www.lydsy.com/JudgeOnline/problem.php?id=1878

题意

给定一个序列，询问每个区间上有多少不同的数字。

题解

因为没有修改，所以离线做就可以了。

把询问按右端点排序，

从前到后，对于每个颜色，

在它上一次出现的地方的后一点+1，

在当前位置的后一点-1；

当前询问答案为ΣXi（1..L)

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N=1000002;
int n,m;
struct rec{int n,x,y;}a[N];
int color[N],last[N],pre[N],ans[N];
int c[N];
inline bool cmp(rec a,rec b)
{
  return a.y<b.y;
}
inline void inc(int x,int w)
{
  for(;x<=n;x+=lowbit(x))c[x]+=w;
}
inline int sum(int x)
{
  int s=0;
  for(;x;x-=lowbit(x))s+=c[x];
  return s;
}
 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
	{
        scanf("%d",color+i);
        pre[i]=last[color[i]];
        last[color[i]]=i;
    }
    scanf("%d",&m);
    for(int i=0;i<m;++i)
    {
        scanf("%d%d",&a[i].x,&a[i].y);
        a[i].n=i;
    }
    sort(a,a+m,cmp);
    int now=0;
    for(int i=0;i<m;++i)
    {
        while(now<a[i].y)
            inc(pre[++now]+1,1),inc(now+1,-1);
        ans[a[i].n]=sum(a[i].x);
    }
 	for(int i=0;i<m;++i)printf("%d\n",ans[i]);
}

http://www.lydsy.com/JudgeOnline/problem.php?id=1532

题意

n个人，m场比赛，求赢得最多的人最少赢多少场。

题解

二分答案X；

S向每场比赛连边，容量为1；

每场比赛向参赛的两个人连边容量oo；

每个人向T连边，容量为X。

如果答案合法，最大流为m。

sap卡了，不知道为什么在这种二分图上dinic会快

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<climits>
#include<queue>
using namespace std;
const int N=20011,M=5*N;
int u[M],v[M],w[M],next[M],head[N],cur[N],k;
int n,m,a[10001],b[10001];
int s,t,pre[N],low[N],d[N],vd[N];
queue<int> q;
void add(int x,int y,int z)
{
    u[++k]=x;v[k]=y;w[k]=z;next[k]=head[x];head[x]=k;
    u[++k]=y;v[k]=x;w[k]=0;next[k]=head[y];head[y]=k;
}
 
bool bfs()
{
    int now;bool flag=false;
    memset(d,-1,sizeof(d));
    q.push(t);d[t]=0;
    while(!q.empty())
    {
        now=q.front();q.pop();
        for(int i=head[now];i;i=next[i])
            if(d[v[i]]==-1 && w[i^1])
            {
                d[v[i]]=d[now]+1;
                q.push(v[i]);
                if(v[i]==s) flag=true;
            }
    }
    return flag;
}
int dfs(int now,int low)
{
    if(now==t)  return low;
    int ret=low,tmp;
    for(int i=head[now];i;i=next[i])
    {
        if(d[v[i]]!=d[now]-1 || !w[i])  continue;
        tmp=dfs(v[i],min(low,w[i]));
        low-=tmp;
        w[i]-=tmp;w[i^1]+=tmp;
        if(low==0)  break;
    }
    if(low==ret)d[now]=-1;
    return ret-low;
}
int solve()
{
    int ans=0,flow;
    while(bfs())
        while(flow=dfs(s,INT_MAX))
            ans+=flow;
    return ans;
}
void build(int x)
{
    memset(head,0,sizeof(head));k=1;
    for(int i=1;i<=m;i++)
    {
        add(s,i,1);
        add(i,m+a[i],1);add(i,m+b[i],1);
    }
    for(int i=1;i<=n;i++)
        add(m+i,t,x);
}
 
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",a+i,b+i);
    s=n+m+1;t=s+1;
    int l=1,r=m,mid;
    while(l<=r)
    {
        mid=l+r>>1;
        build(mid);
        if(solve()==m)  r=mid-1;
        else    l=mid+1;
    }
    printf("%d\n",l);
}

http://www.lydsy.com/JudgeOnline/problem.php?id=1596

题意

一棵树，每个点可以支配直接与它相邻的点，求最小支配集。

题解

经典题目0.0

f[i][0]：以i为根的子树中均被覆盖且草地i上无信号塔所需的最小塔数

f[i][1]：以i为根的子树中均被覆盖且草地i上有信号塔所需的最小塔数

f[i][2]：以i为根的子树中除i点以外其余点均被覆盖所需的最小塔数

 转移方法：

f[i][1]=Σ(min(f[i.son][0..2]))

f[i][2]=Σ(f[i.son][0])

令sum=Σ(min(f[i.son][0..1]))

f[i][0]=min(f[i.son][1]+sum-min(f[i.son][0..1]))

i为叶节点时，f[i][0]显然是不合法的，所以应设为无穷大。 

#include<cstring>
#include<cstdio>
#include<cmath>
#include<climits>
#include<algorithm>
using namespace std;
const int N=100001,M=2*N;
int n,k,f[N][3],v[M],next[M],head[N];
 
void add(int x,int y)
{
    v[++k]=y;next[k]=head[x];head[x]=k;
}
 
void dfs(int x,int fa)
{
    int sum=0;
    f[x][1]=1;
    for(int i=head[x];i;i=next[i])
        if(v[i]!=fa)
        {
            dfs(v[i],x);
            f[x][1]+=min(f[v[i]][0],min(f[v[i]][1],f[v[i]][2]));
            f[x][2]+=f[v[i]][0];
            sum+=min(f[v[i]][0],f[v[i]][1]);
        }
    f[x][0]=N;
    if(x!=1&&!next[head[x]])    return;
    for(int i=head[x];i;i=next[i])
        if(v[i]!=fa)
            f[x][0]=min(f[x][0],f[v[i]][1]+sum-min(f[v[i]][0],f[v[i]][1]));
}
     
 
int main()
{
    scanf("%d",&n);
    int x,y;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(1,0);
    printf("%d\n",min(f[1][1],f[1][0]));
}

http://www.lydsy.com/JudgeOnline/problem.php?id=1776

题意

一棵树，每个节点有一个编号，一共K种编号，输出每种编号的控制范围，即所有该编号的点，在树上的最远点对。

题解

对于每种编号，

最远点对中的其中一个点肯定离根最远，

所以先找出这个点，

枚举剩下的点，用lca算出每个点和找出的点的距离，更新答案即可。

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<climits>
using namespace std;
const int N=200001,K=100001,M=N*2,Q=N*3;
int q[Q],d[N],num[N],p[N],Max[K],ans[N];
int v[M],next[M],head[N],k;
int n,m;

struct SegmentTree
{
	int m[Q*3];
	void update(int x)
	{
		int l=x<<1,r=l+1;
		m[x]=m[l];
		if(d[m[x]]>d[m[r]])
			m[x]=m[r];
	}
	void build(int x,int s,int t)
	{
		if(s==t)
		{
			m[x]=q[s];return;
		}
		int mid=s+t>>1;
		build(x<<1,s,mid);build((x<<1)+1,mid+1,t);
		update(x);
	}
	int get(int x,int s,int t,int ll,int rr)
	{
		if(ll<=s&&t<=rr)	return m[x];
		int t1=0,t2=0,mid=s+t>>1;
		if(ll<=mid)	t1=get(x<<1,s,mid,ll,rr);
		if(rr>mid)	t2=get((x<<1)+1,mid+1,t,ll,rr);
		if(d[t1]<d[t2])	return t1;
		else return t2;
	}
}a;
void add(int x,int y)
{
	if((!x)||(!y))	return;
	v[++k]=y;next[k]=head[x];head[x]=k;
}
void dfs(int x,int fa,int deep)
{
	q[++q[0]]=x;num[x]=q[0];d[x]=deep;
	if(d[x]>d[Max[p[x]]])	Max[p[x]]=x;
	for(int i=head[x];i;i=next[i])
		if(v[i]!=fa)
			dfs(v[i],x,deep+1),q[++q[0]]=x;
}
int lca(int x,int y)
{
	if(num[x]>num[y])	swap(x,y);
	return a.get(1,1,q[0],num[x],num[y]);
}
int main()
{
	scanf("%d%d",&n,&m);
	int x,y,z;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",p+i,&x);
		add(x,i);add(i,x);
	}
	dfs(1,0,0);d[0]=INT_MAX;
	a.build(1,1,q[0]);
	for(int i=1;i<=n;i++)
	{
		int tmp=d[i]+d[Max[p[i]]]-d[lca(i,Max[p[i]])]*2;
		ans[p[i]]=max(ans[p[i]],tmp);
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
}