AtCoder Beginner Contest 184

C - Super Ryuma
每个点可以到的区域可以分为两种情况:
方式1.以起点为原点直线 y=x 和 直线 y=-x 上的点;
方式2.与起点曼哈顿距离小于等于3的点,

任意两点之间至多需要移动三次,过起点做斜率为1的直线,以重点做斜率为-1
的直线(交换一下也可以),一定有交点,如果交点坐标都为整数,则两次就可以,否则就要三次(偏移一个单位即可移动两次)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector> 
using namespace std;
typedef long long ll;
#define first fi
#define second se;
const int N=500010;
int a,b,c,d;
int main()
{
	cin>>a>>b>>c>>d;
	if(a==c&&b==d) puts("0");
	else if((abs(a-c)+abs(b-d)<=3)||(abs(a-c)==abs(b-d))) puts("1");
    else if(abs(a-c)+abs(b-d)<=6) puts("2");//两次方式2,赛后加了一组这个样例
	else 
	{
		int x;
		if(d>=b)
		{
			if(c>=a) x=b+(c-a);
			else x=b-(c-a);
		}
		else
		{
			if(c>=a) x=b-(c-a);
			else x=b+(c-a);
		}
		if(abs(d-x)<=3) puts("2");//判断将起点移到与终点同一水平时是否在方式2的范围内
		else
		{
			a=a-b;c=c-d;
			if((a+c)&1) puts("3");
			else puts("2");
		}
	}
	return 0;
}

D 期望dp,终止状态往回推,终止状态有些特殊,只能有一个是100,且终止状态只有一种转移方式(从是100的那个颜色转移来)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector> 
using namespace std;
typedef long long ll;
//typedef pair<ll,ll> pll;
#define first fi
#define second se;
const int N=110;
int a,b,c,d;
double f[N][N][N]; 
int main()
{
	cin>>a>>b>>c;
	for(int i=100;i>=a;--i)
		for(int j=100;j>=b;--j)
			for(int k=100;k>=c;--k)
			{
				int num=0;
				if(i==100) num++;
				if(j==100) num++;
				if(k==100) num++;
				if(num>1) continue;
				if(i==100 ) f[i-1][j][k]+=(f[i][j][k]+1)*(i-1)/(i+j+k-1);
				else if(j==100) f[i][j-1][k]+=(f[i][j][k]+1)*(j-1)/(i+j+k-1);
				else if(k==100) f[i][j][k-1]+=(f[i][j][k]+1)*(k-1)/(i+j+k-1);
				else
				{
					if(i>0) f[i-1][j][k]+=(f[i][j][k]+1)*(i-1)/(i+j+k-1);
					if(j>0) f[i][j-1][k]+=(f[i][j][k]+1)*(j-1)/(i+j+k-1);
					if(k>0) f[i][j][k-1]+=(f[i][j][k]+1)*(k-1)/(i+j+k-1);
				}
			}
	printf("%.8lf",f[a][b][c]);
	return 0;
}

补:
E 爆搜t了,直接双向宽搜。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector> 
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
const int N=2010;
int a[N];
int sx,sy,dx,dy,n,m;
char s[N][N];
 
int d[4][2]={0,1,0,-1,1,0,-1,0};
struct node
{
	int x,y;
}q1[N*N],q2[N*N];
vector<node> g[N];
int h1,t1,h2,t2;
int f1[N][N],f2[N][N];
bool st1[N][N],st2[N][N];
int bfs()
{
	memset(f1,0x3f,sizeof f1);
	memset(f2,0x3f,sizeof f2);
	f1[sx][sy]=f2[dx][dy]=0;
	h1=t1=h2=t2=1;
	q1[h1]={sx,sy};
	q2[h2]={dx,dy};
	int x,y,tx,ty;
	while(h1<=t1||h2<=t2)
	{
			if((h1<=t1&&h2<=t2&&f1[q1[h1].x][q1[h1].y]<=f2[q2[h2].x][q2[h2].y])||h2>t2)
			{
					x=q1[h1].x,y=q1[h1].y;
					h1++;
					for(int i=0;i<4;++i)
					{
						tx=x+d[i][0],ty=y+d[i][1];
						if(tx>0&&tx<=n&&ty>0&&ty<=m&&s[tx][ty]!='#'&&f1[tx][ty]>f1[x][y]+1)
						{
							f1[tx][ty]=f1[x][y]+1;
							if(f2[tx][ty]!=0x3f3f3f3f) return f1[tx][ty]+f2[tx][ty];
							q1[++t1]={tx,ty};
						}
					}
					for(int i=0;i<g[s[x][y]].size();++i)
					{
						tx=g[s[x][y]][i].x,ty=g[s[x][y]][i].y;
						if(f1[tx][ty]>f1[x][y]+1)
						{
							f1[tx][ty]=f1[x][y]+1;
							if(f2[tx][ty]!=0x3f3f3f3f) return f1[tx][ty]+f2[tx][ty];
							q1[++t1]={tx,ty};
						}
					}
			}
			else
			{
				x=q2[h2].x,y=q2[h2].y;
				h2++;
				for(int i=0;i<4;++i)
				{
					tx=x+d[i][0],ty=y+d[i][1];
					if(tx>0&&tx<=n&&ty>0&&ty<=m&&s[tx][ty]!='#'&&f2[tx][ty]>f2[x][y]+1)
					{
						f2[tx][ty]=f2[x][y]+1;
						if(f1[tx][ty]!=0x3f3f3f3f) return f1[tx][ty]+f2[tx][ty];
						q2[++t2]={tx,ty};
					}
				}
				for(int i=0;i<g[s[x][y]].size();++i)
				{
					tx=g[s[x][y]][i].x,ty=g[s[x][y]][i].y;
					if(f2[tx][ty]>f2[x][y]+1)
					{
						f2[tx][ty]=f2[x][y]+1;
						if(f1[tx][ty]!=0x3f3f3f3f) return f1[tx][ty]+f2[tx][ty];
						q2[++t2]={tx,ty};
					}
				}
			}
	}
	return -1;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%s",s[i]+1);
		for(int j=1;j<=m;++j)
		{
			if(s[i][j]=='S') sx=i,sy=j;
			else if(s[i][j]=='G') dx=i,dy=j;
			if(s[i][j]!='.'&&s[i][j]!='#' )g[s[i][j]].push_back({i,j});
		}
	}
	printf("%d",bfs());
	return 0;
}

F n如果小于等于20就可以二进制枚举了,淦。
n/2就会小于等于20了呀,分别对前半部和后半部分别二进制枚举计算总合,在把两半部分拼接一下就好,拼接可以二分,好像也可以双指针。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector> 
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
const int N=2010;
int n,m,k,a[N];
ll f[1<<21][2];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",a+i);
	k=n/2;
	for(int i=0;i<(1<<k);++i)
	{
		for(int j=0;j<k;++j)
			if(((i>>j)&1)==0)
				f[i+(1<<j)][0]=f[i][0]+a[j+1];
	}
	int x=n-k;
	for(int i=0;i<(1<<x);++i)
	{
		for(int j=0;j<x;++j)
			if(((i>>j)&1)==0)
				f[i+(1<<j)][1]=f[i][1]+a[j+1+k];
	}
	vector<ll> nums1,nums2;
	for(int i=0;i<(1<<x);++i)
	{
		if(i<(1<<k)&&f[i][0]<=m) nums1.push_back(f[i][0]);
		if(f[i][1]<=m) nums2.push_back(f[i][1]);
	}
	sort(nums1.begin(),nums1.end());
	nums1.erase(unique(nums1.begin(),nums1.end()),nums1.end());
	sort(nums2.begin(),nums2.end());
	nums2.erase(unique(nums2.begin(),nums2.end()),nums2.end());
	ll ans=0;
	for(int i=0;i<nums1.size();++i)
	{
		int pos=lower_bound(nums2.begin(),nums2.end(),m+1-nums1[i])-nums2.begin();
		if(pos==nums2.size()) ans=max(nums1[i]+nums2[nums2.size()-1],ans);
		else if(pos>0) ans=max(ans,nums2[pos-1]+nums1[i]);
	}

	for(int i=0;i<nums2.size();++i)
	{
		int pos=lower_bound(nums1.begin(),nums1.end(),m+1-nums2[i])-nums1.begin();
		if(pos==nums1.size()) ans=max(nums2[i]+nums1[nums1.size()-1],ans);
		else if(pos>0) ans=max(ans,nums1[pos-1]+nums2[i]);
	}
	printf("%lld",ans);
	return 0;
}
上一篇:hdu3681 * Break


下一篇:岛屿的周长