高橋・直樹's Blog

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

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

题意

一棵树，每次询问给三个点，求一个点使得到这三个点的距离和最小。

题解

理解一下，可知答案必定在这三个点中，某两个点的LCA上，

于是枚举a,b;a,c;b,c的LCA。

最后发现这三个LCA有规律，有两个一定相同，但是不会用。

LCA写的RMQ比较慢啊

#include<cstring>
#include<climits>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=500001,M=1000001,Q=2000002;

int q[Q],d[N],tot,n,k,v[M],next[M],head[N],num[N],m;

struct SegmentTree
{
	int m[6000002];
	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)
{
	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;
	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",&x,&y);
		add(x,y);add(y,x);
	}
	dfs(1,0,0);d[0]=INT_MAX;
	a.build(1,1,q[0]);
	int p,q;
	while(m--)
	{
		int ans,sum=INT_MAX;
		scanf("%d%d%d",&x,&y,&z);
		int s=d[x]+d[y]+d[z];
		p=lca(x,y);q=lca(p,z);
		if(s-d[q]*2-d[p]<sum)
			sum=s-d[q]*2-d[p],ans=p;
		p=lca(x,z);
		if(s-d[q]*2-d[p]<sum)
			sum=s-d[q]*2-d[p],ans=p;
		p=lca(y,z);
		if(s-d[q]*2-d[p]<sum)
			sum=s-d[q]*2-d[p],ans=p;
		printf("%d %d\n",ans,sum);
	}
}

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

题意

一个图，每条边有边权，每个点也有点权，

定义两个点之间的费用为，两点之间的路径长度加上路径上最大的一个点权。

询问任意两个点对的最小费用。

题解

一看到是求任意点对的费用，就要floyd

然后floyd的性质保证当过渡点循环到k时，所有经过的点的编号<=k;

于是，我们按点权从小到大排序后，floyd。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=251;
int f[N][N],ans[N][N],num[N],n,m,p;
struct node
{
	int w,n;
}a[N];
inline bool cmp(node a,node b)
{
	return a.w<b.w;
}
int main()
{
	memset(f,63,sizeof(f));
	memset(ans,63,sizeof(ans));
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].w);a[i].n=i;
		f[i][i]=0;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)	num[a[i].n]=i;
	int x,y,z;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		x=num[x];y=num[y];
		f[x][y]=f[y][x]=min(f[x][y],z);
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
				ans[i][j]=min(ans[i][j],f[i][j]+max(a[k].w,max(a[i].w,a[j].w)));
			}
	for(int i=1;i<=p;i++)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",ans[num[x]][num[y]]);
	}
}

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

题意

这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。

题解

这题我是一定不会的。。。

可是数据范围比较厉害。偶然翻题解发现原来m≤2，坑爹。

于是DP。

当 m=1 时

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=101,M=3,K=11;
int n,m,p,s[N],s1[N],s2[N];
int g[N][K],f[N][N][K];

void work1()
{
	for(int i=1;i<=n;i++)
	{
		scanf("%d",s+i);
		s[i]+=s[i-1];
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=p;j++)
		{
			g[i][j]=g[i-1][j];
			for(int k=i-1;k>=0;k--)
				g[i][j]=max(g[i][j],g[k][j-1]+s[i]-s[k]);
		}
	printf("%d\n",g[n][p]);
}
void work2()
{
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",s1+i,s2+i);
		s1[i]+=s1[i-1];s2[i]+=s2[i-1];
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=p;k++)
			{
				f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);
				for(int x=i-1;x>=0;x--)
					f[i][j][k]=max(f[i][j][k],f[x][j][k-1]+s1[i]-s1[x]);
				for(int y=j-1;y>=0;y--)
					f[i][j][k]=max(f[i][j][k],f[i][y][k-1]+s2[j]-s2[y]);
				if(i==j)
					for(int x=i-1;x>=0;x--)
						f[i][j][k]=max(f[i][j][k],f[x][x][k-1]+s1[i]-s1[x]+s2[j]-s2[x]);
			}
	printf("%d\n",f[n][n][p]);
}
					
int main()
{
	scanf("%d%d%d",&n,&m,&p);
	if(m==1)	work1();
	else work2();
}

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

题意

太复杂了。。所以

http://www.nocow.cn/index.php/USACO/cowwar

题解

这题感觉就是利用网络流，瞪眼建模，通过流量来满足条件。

http://www.dxmtb.com/blog/usaco2010-hol-cowwar/

1.一个E点拆成两个点。把一个J点拆成三个点。T点不变。

2.从原点向每个J的第一个点连一条边容量为1，表示只有一只牛。

3.从J的第一个点连边到能到的点。能到的J点连第二个点，能到的E点连第一个点，容量都为1。注意，J也能到他自己。

4.对于每个能攻击的J点，把第三个J点连一条容量为1的边到能攻击的T。对于每个能攻击的E点，把第二个E点连到能攻击的T点，容量还是1。

5.把E的第一个点连一条容量为1的边到第二个点，表示只能从这个点攻击一次。J的第二个点连一条容量为1的边到第三个点，也表示只能从这个点攻击一次。

6.每个T点连一条边到汇点，容量为1。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>
#include<algorithm>
using namespace std;
const int N=3005,M=100000;
int u[M],v[M],w[M],next[M],head[N],k=1;
int low[N],pre[N],d[N],vd[N],cur[N];
int n,m;
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;
}
int solve(int s,int t)
{
    int now=s,i,ans=0;
    low[s]=INT_MAX;vd[0]=t;
    while(d[s]<t)
    {
        for(i=cur[now];i;i=next[i])
            if(w[i]>0 && d[now]==d[v[i]]+1)
                break;
        cur[now]=i;
        if(i)
        {
            low[v[i]]=min(low[now],w[i]);pre[v[i]]=i;now=v[i];
            if(now==t)
            {
                for(;now!=s;now=u[pre[now]])
                {
                    w[pre[now]]-=low[t];w[pre[now]^1]+=low[t];
                }
                low[s]=INT_MAX;ans+=low[t];
            }
        }
        else
        {
            if(!--vd[d[now]])   break;
            d[now]=t;
            for(i=head[now];i;i=next[i])
                if(w[i]>0 && d[now]>d[v[i]]+1)
                {
                    d[now]=d[v[i]]+1;
                    cur[now]=i;
                }
            vd[d[now]]++;
            if(now!=s)  now=u[pre[now]];
        }
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    char c[N];scanf("%s",c+1);
    int S=0,T=n*3+1;
    for(int i=1;i<=n;i++)
    {
        if(c[i]=='J')
        {
            add(S,i,1);
            add(i,i+n,1);
            add(i+n,i+n+n,1);
        }
        if(c[i]=='T')   add(i,T,1);
        if(c[i]=='E')   add(i,i+n,1);
    }
    while(m--)
    {
        int x,y;scanf("%d%d",&x,&y);
        if(c[y]=='J')   swap(x,y);
        if(c[x]=='J')
        {
            if(c[y]=='T')   add(x+n+n,y,1);
            if(c[y]=='J')   add(x,y+n,1),add(y,x+n,1);
            if(c[y]=='E')   add(x,y,1);
        }
        if(c[x]=='T')
            if(c[y]=='E')
                add(y+n,x,1);
        if(c[x]=='E')
            if(c[y]=='T')
                add(x+n,y,1);
    }
    printf("%d\n",solve(S,T));
}