高橋・直樹's Blog

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

题意

两个序列n和m，有权值a（钱）,b（新鲜度）

求满足所有N序列与M序列匹配, 

M序列的元素可以匹配一个N中的元素，当且仅当M序列的值满足 m.a>=n.a && m.b>=n.b

求minΣm.a。

题解

把M和N按b排降序，

枚举N，用一个BST维护满足当前n.b的所有M中的元素。

每次去除BST中满足N.a的最小的M.a;

#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<set>
#define PB push_back
#define MP make_pair
using namespace std;
int n,m;
vector<pair<int,int> > cow,food;
multiset<int> s;
long long ans;
int main()
{
    scanf("%d%d",&n,&m);
    int a,b;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        cow.PB(MP(b,a));
    }
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&a,&b);
        food.PB(MP(b,a));
    }
    sort(cow.begin(),cow.end());
    sort(food.begin(),food.end());
    bool flag=true;int j=m-1;
    for(int i=n-1;i>=0;i--)
    {
        for(;j>=0;)
            if(food[j].first>=cow[i].first)
                s.insert(food[j--].second);
            else    break;
        if(s.size()==0)
        {
            puts("-1");
            return 0;
        }
        multiset<int>::iterator p=s.lower_bound(cow[i].second);
        ans+=*p;s.erase(p);
    }
    printf("%lld\n",ans);
}

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=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]);
}

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

题意

给定一个01序列，每次可以将连续的k个数取反。

确定一个k使得，将所有数全变成0的操作次数m最小。

题解

枚举k，O(N)验证，更新答案。

把所有当前为1的反转。

验证时，用一个队列，记录被修改过的点，每次找到对当前枚举点有作用的队列区间，

如果区间长度为奇数，说明该点之前被反转。

#include<cstring>
#include<cmath>
#include<cstdio>
#include<climits>
using namespace std;
 
const int N=5001;
 
int b[N],a[N],n,m,k,q[N];
 
 
 
int check(int x)
{
    int l=0,r=1,now=0;
    memcpy(b,a,sizeof(a));
    for(int i=1;i<=n;i++)
    {
        while(l<=r && q[l]<=i-x)  l++;
        if(((r-l+1)&1)) b[i]=1-b[i];
        if(b[i])
            if(i<=n-x+1)
                now++,b[i]=0,q[++r]=i;
            else return INT_MAX;
    }
    return now;
}
 
int main()
{
    scanf("%d",&n);
    int m=INT_MAX;
    for(int i=1;i<=n;i++)
        getchar(),a[i]=getchar()=='B';
    for(int i=1;i<=n;i++)
    {
        int tmp=check(i);
        if(tmp<m)
            m=tmp,k=i;
    }
    printf("%d %d\n",k,m);
}