Codeforces Round #327

    打一场Div2加了246的rating简直不能更爽...

【Div.2 A】Wizard's Duel

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
inline void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}

int l,a,b;
double ans;

int main()
{
	scanf("%d%d%d",&l,&a,&b);
	if (b==0) ans=l;
	else if (a==0) ans=0;
	else ans=l*a/(a+b+0.0);
	printf("%.4f\n",ans);
	return 0;
}

【Div.2 B】Rebranding

    用两个数组a,b,a[ch]表示ch在经过若干次操作后变成了a[ch],b[ch]表示a[b[ch]]=ch,即当前ch在a中的下标。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
inline void readchar(char &ch) {while ((ch=getchar())<'a' || ch>'z');}
inline void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}

char s[200010];
char tra[256],trb[256];
int n,m;

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) readchar(s[i]);
	for (int i=0;i<256;i++) tra[i]=char(i),trb[i]=char(i);
	for (int i=1;i<=m;i++)
	{
		char ch1,ch2;
		readchar(ch1),readchar(ch2);
		swap(trb[ch1],trb[ch2]);
		tra[trb[ch1]]=ch1;tra[trb[ch2]]=ch2;
	}
	for (int i=1;i<=n;i++) putchar(char(tra[s[i]]));
	putchar('\n');
	return 0;
}

【Div.1 A】Median Smoothing

    两个相邻的1或0是不会被改变的，即被改变的序列为01交替的序列。然后模拟一下变化的过程。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;

int a[500010];
int n,ans;

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	a[0]=a[1];
	a[n+1]=a[n];
	for (int i=1,cnt=0;i<=n;i++)
		if (a[i]!=a[i-1] && a[i]!=a[i+1]) cnt++;
		else
		{
			for (int j=1;j<=cnt/2;j++) if (j&1) a[i-j]^=1,a[i-cnt+j-1]^=1;
			if ((cnt&1) && ((cnt/2+1)&1)) a[i-cnt/2-1]^=1;
			ans=max(ans,(cnt+1)/2),cnt=0;
		}
	printf("%d\n",ans);
	for (int i=1;i<=n;i++) printf("%d ",a[i]);
	printf("\n");
	return 0;
}

【Div.1 B】Chip 'n Dale Rescue Rangers

    因为风速是一定小于飞行器的速度的，所以只有一个时刻使得飞行器选择最优方向飞行时刚好到达目的地，可以二分最终时刻，也可以直接公式算。

    飞行器不是飞行时一直朝向目的地最快，而是沿出发地到目的地的矢量减去风速累积矢量方向飞行最优。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const double eps=1e-8;

double dis(double x1,double y1,double x2,double y2) {return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}

double x_1,y_1,x2,y2,ex,ey;
double vx,vy,wx,wy;
double v,t;

int main()
{
	scanf("%lf%lf%lf%lf",&x_1,&y_1,&x2,&y2);
	ex=x2-x_1;ey=y2-y_1;
	scanf("%lf%lf",&v,&t);
	scanf("%lf%lf%lf%lf",&vx,&vy,&wx,&wy);
	double l=0,r=1e20,mid;
	while (r-l>eps)
	{
		mid=(l+r)/2.0;
		double nx=min(t,mid)*vx+max(mid-t,0.0)*wx,ny=min(t,mid)*vy+max(mid-t,0.0)*wy;
		if (dis(nx,ny,ex,ey)<=v*mid+eps) r=mid;else l=mid;
	}
	printf("%.7f\n",l);
	return 0;
}

【Div.1 C】Three States

    预处理出每个国家到地图上每个点的距离和国家到国家之间的最短距离。最优的修路方案是直接国家与国家之间修道路或道路之间有汇聚点然后修道路。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
const int mov[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
const int inf=~0u>>1;
inline void readchar(char &ch) {while ((ch=getchar())!='1' && ch!='2' && ch!='3' && ch!='.' && ch!='#');}

char map[1010][1010];
int dis[4][1010][1010];
int discm[4][4];
int n,m,ans;

int qx[1010*1010],qy[1010*1010],step[1010*1010];
int vis[1010][1010];
int top,qn;

void BFS(int o)
{
	top=qn=0;
	memset(vis,0,sizeof(vis));
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	if (map[i][j]==o+'0') qx[++qn]=i,qy[qn]=j,step[qn]=0,vis[i][j]=1;
	while (++top<=qn)
	{
		int x=qx[top],y=qy[top],c=step[top];
		for (int mv=0;mv<4;mv++)
		{
			int nx=x+mov[mv][0],ny=y+mov[mv][1];
			if (nx<=0 || nx>n || ny<=0 || ny>m || vis[nx][ny] || map[nx][ny]=='#') continue;
			qn++;qx[qn]=nx;qy[qn]=ny;step[qn]=c+1;
			dis[o][nx][ny]=c+1;
			vis[nx][ny]=1;
			if (map[nx][ny]=='1') discm[o][1]=min(discm[o][1],c+1);
			if (map[nx][ny]=='2') discm[o][2]=min(discm[o][2],c+1);
			if (map[nx][ny]=='3') discm[o][3]=min(discm[o][3],c+1);
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++) readchar(map[i][j]);
	for (int i=1;i<=3;i++) for (int j=1;j<=3;j++) discm[i][j]=inf;
	BFS(1),BFS(2),BFS(3);
	if (discm[1][2]==inf || discm[1][3]==inf) {printf("-1\n");return 0;}
	ans=min(discm[1][2]+discm[1][3]-2,discm[1][2]+discm[2][3]-2);
	ans=min(ans,discm[1][3]+discm[2][3]-2);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	if (dis[1][i][j] || dis[2][i][j] || dis[3][i][j])
		ans=min(ans,dis[1][i][j]+dis[2][i][j]+dis[3][i][j]-2);
	printf("%d\n",ans);
	return 0;
}