高橋・直樹's Blog

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

题意

n个人，每个人说Xi个人比我低，Yi个人比我高

问最少有多少个人说假话

题解

其实想的和题解一样，但是忽略题解中所说的情况，一直wa，

掉（xi + yi ≥ n）的，

每句话都可以表示成一个[yi + 1, n - xi]的区间。

一开始所有的区间权值为1；

然后把同样的区间合并，权值设为合并在一起的区间数量

选出最多的互补相交的区间，记为k

那么答案就是n-k。

需要注意的是如果某个同样区间的数量>区间长度，要改成区间长度

#include<cstdio>
#include<algorithm>
#include<vector>
#define MP make_pair
#define PB push_back
#define s first
#define t second
using namespace std;
typedef pair<int,int> pr;
int n,f[100001],tot;
vector<pr> p;

bool cmp(pr a,pr b)
{
	if(a.t!=b.t) return a.t<b.t;
	else return a.s<b.s;
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		if(x+y>=n)	continue;
		p.PB(MP(y+1,n-x));tot++;
	}
	sort(p.begin(),p.end(),cmp);
	int j=0;
	for(int i=1;i<=n;i++)
	{
		f[i]=f[i-1];
		while(j<tot && p[j].t==i)
		{
			int k;for(k=j;k<tot && p[k]==p[j];k++);
			f[i]=max(f[i],f[p[j].s]+min(k-j,p[j].t-p[j].s));
			j=k;
		}
	}
	printf("%d\n",n-f[n]);
}

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

大意

在一个4*4的方框内摆放了若干个相同的玩具，将这些玩具重新摆放成为理想的状态，规定移动时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具。求最小移动次数。

题解

暴力BFS，因为格子很少，直接用位运算

萌神的写法非常厉害，看代码吧。

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=65536,
dx[24]={15,14,13,15,14,13,12,11,10,9,11,10,9,8,7,6,5,7,6,5,4,3,2,1},
dy[24]={14,13,12,11,10,9,8,10,9,8,7,6,5,4,6,5,4,3,2,1,0,2,1,0};
int q[N],d[N],S,T;

int main()
{
	memset(d,127,sizeof(d));
	for(int i=0;i<4;i++,getchar())
		for(int j=0;j<4;j++)
			S=(S<<1)+getchar()-'0';
	getchar();
	for(int i=0;i<4;i++,getchar())
		for(int j=0;j<4;j++)
			T=(T<<1)+getchar()-'0';
	if(S==T){puts("0");return 0;}
	d[S]=0;int l=0,r=1;q[1]=S;
	while(l<r)
	{
		int now=q[++l];
		for(int i=0;i<24;i++)
		{
			int x=now&(1<<dx[i]),y=now&(1<<dy[i]);
			int next=now-x-y;
			if(x)	next+=1<<dy[i];
			if(y)	next+=1<<dx[i];
			if(d[next]>d[now]+1)
			{
				d[next]=d[now]+1;
				q[++r]=next;
				if(next==T)
				{
					printf("%d\n",d[T]);
					return 0;
				}
			}
		}
	}
}