test20190720

Posted on | Views:

好题.

$A\ Safe\ Bet$

$25$ 分做法:枚举镜子摆放的位置,模拟光线,每次用 $set$ 找到下一面镜子,修改方向,最后检验是否从 $(R,C)$ 出来.

满分做法:不额外增加镜子,直接模拟光线,若最后从 $(R,C)$ 出来,答案为 $0$ .

否则,模拟反向光线,从 $(R,C+1)$ 反向射入,可以发现放镜子的可行位置为两条光线的所有交点.

用扫描线 + 线段树求交点数目以及字典序最小的交点即可.

考试情况:只写了 $25$ 分的做法.

$std$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<cstdio>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
#define rep(i,n) for (int i=0;i<n;++i)
#define pb push_back
#define mk make_pair
#define X first
#define Y second
#define tree int t,int l,int r
#define left t*2,l,mid
#define right t*2+1,mid+1,r
#define M int mid=l+r>>1
const int N=1000005;
typedef pair<int,int> pr;
typedef vector<pair<int,pr> > seq;
set<pr> a[N],b[N];
seq f1,g1,f2,g2;
int Case,n,m,R,C,x,y,ll,rr,c[N];
long long ans;
int get(int x)
{
	int res=0;
	for (; x; x-=x&-x) res+=c[x];
	return res;
}
void add(int x,int v)
{
	for (; x<=C; x+=x&-x) c[x]+=v;
}
void ins(int side)
{
	scanf("%d%d",&x,&y),a[x].insert(mk(y,side)),b[y].insert(mk(x,side));
}
bool track(int x,int y,int d,seq &f,seq &g)
{
	f.clear(),g.clear();
	set<pr> :: iterator it;
	for (;;)
	{
		if (d&1)
		{
			if (d==1)
			{
				it=b[y].upper_bound(mk(x,1));
				f.pb(mk(x+1,mk(y,1)));
				if (it==b[y].end()) return f.pb(mk(R+1,mk(y,-1))),0;
				f.pb(mk(it->X,mk(y,-1))),x=it->X,d=it->Y?2:0;
			}
			else
			{
				it=b[y].lower_bound(mk(x,0));
				f.pb(mk(x,mk(y,-1)));
				if (it==b[y].begin()) return f.pb(mk(1,mk(y,1))),0;
				--it;
				f.pb(mk(it->X+1,mk(y,1))),x=it->X,d=it->Y?0:2;
			}
		}
		else
		{
			if (d==0)
			{
				it=a[x].upper_bound(mk(y,1));
				if (it==a[x].end()) return g.pb(mk(x,mk(y+1,C))),x==R;
				g.pb(mk(x,mk(y+1,it->X-1))),y=it->X,d=it->Y?3:1;
			}
			else
			{
				it=a[x].lower_bound(mk(y,0));
				if (it==a[x].begin()) return g.pb(mk(x,mk(1,y-1))),0;
				--it;
				g.pb(mk(x,mk(it->X+1,y-1))),y=it->X,d=it->Y?1:3;
			}
		}
	}
}
void work(seq &f,seq &g)
{
	sort(f.begin(),f.end()),sort(g.begin(),g.end());
	int m=f.size(),n=g.size(),j=0;
	rep(i,n)
	{
		while (j<m && f[j].X<=g[i].X) add(f[j].Y.X,f[j].Y.Y),++j;
		ll=g[i].Y.X,rr=g[i].Y.Y;
		int res=get(rr)-get(ll-1);
		ans+=res;
		if (g[i].X<x && res)
		{
			x=g[i].X,y=ll;
			for (int j=20; j>=0; --j)
				if (y+(1<<j)<=rr && !(get(y-1+(1<<j))-get(y-1))) y+=1<<j;
		}
	}
	while (j<m) add(f[j].Y.X,f[j].Y.Y),++j;
}
int main()
{
	freopen("safe.in","r",stdin);
	freopen("safe.out","w",stdout);
	while (scanf("%d%d%d%d",&R,&C,&n,&m)!=EOF)
	{
		rep(i,R+1) a[i].clear();
		rep(j,C+1) b[j].clear();
		rep(i,n+m) ins(i<n);
		printf("Case %d: ",++Case);
		if (track(1,0,0,f1,g1))
		{
			puts("0");
			continue;
		}
		track(R,C+1,2,f2,g2);
		ans=0,x=R+1,work(f1,g2),work(f2,g1);
		if (ans) printf("%I64d %d %d\n",ans,x,y);
		else puts("impossible");
	}
	return 0;
}

$Room\ Service$

$25$ 分做法:一堆特判.矩形的情况答案就是对角线长度 $\times 2$ .

我的 $60$ 分做法:其实就是乱搞,出题人是没有设计这一部分的,也没有卡我.

把每条边 $K$ 等分,拆成 $K+1$ 个点,设 $f(i,j,S)$ 表示从出发点到达第 $i$ 条边上的第 $j$ 个点,已经到达过的边集合为 $S$ 时走过的最短长度.大力转移,时间复杂度为 $O(n^2\cdot2^n\cdot K^2)$ .实际上有很多无用状态.参数 $K$ 取 $200$ 就可以了.

满分做法:若需要到的线段为直线,显然只需要将点 $P$ 关于 $n$ 条边都镜面反射一次,得到 $P’$ , $dis(P,P’)$ 即为答案.

但现在是线段,有可能交点在线段外,此时一定是某一个端点处最优.于是只有端点或交点处的状态有用, $flyod$ 预处理两点间最短路后,枚举第一个到的关键点和最后一个到的关键点,更新答案.时间复杂度 $O(n^3)$ .

考试情况:乱搞获得 $60$ 分.

$std$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define rep(i,n) for (int i=1;i<=n;++i)
const double eps=1e-8;
int Case,n;
double ans,d[205][205];
struct node
{
	double x,y;
	node() {}
	node(double _x,double _y):x(_x),y(_y) {}
	node operator +(const node &A)
	{
		return node(x+A.x,y+A.y);
	}
	node operator -(const node &A)
	{
		return node(x-A.x,y-A.y);
	}
	node operator *(const double &A)
	{
		return node(x*A,y*A);
	}
	double operator *(const node &A)
	{
		return x*A.x+y*A.y;
	}
	double operator %(const node &A)
	{
		return x*A.y-y*A.x;
	}
	double norm()
	{
		return x*x+y*y;
	}
	double len()
	{
		return sqrt(norm());
	}
	void read()
	{
		scanf("%lf%lf",&x,&y);
	}
} a[205];
bool cross(node &A,node &B,node &C,node &D)
{
	return ((C-A)%(B-A))*((D-A)%(B-A))<=0 && ((C-A)%(B-A))*((D-A)%(B-A))<=0;
}
void rev(node A,node B,node &C)
{
	node V=B-A;
	C=(A+V*(((C-A)*V)/V.norm()))*2-C;
}
double work(node A,int l,node B,int r)
{
	for (int i=l; i<r; ++i) rev(a[i],a[i+1],A);
	for (int i=r; i>l; --i)
	{
		if (!cross(A,B,a[i-1],a[i])) return 1e9;
		rev(a[i-1],a[i],A),rev(a[i-1],a[i],B);
	}
	return (A-B).len();
}
inline int chg(int x)
{
	return x>n?x-n:x;
}
inline void Min(double &x,double y)
{
	if (y<x) x=y;
}
int main()
{
	freopen("room.in","r",stdin);
	freopen("room.out","w",stdout);
	while (scanf("%d",&n)!=EOF)
	{
		ans=1e9,a[0].read();
		rep(i,n) a[i].read(),a[n+i]=a[i];
		rep(i,n) rep(j,n-1) d[i][chg(i+j)]=work(a[i],i+1,a[i+j],i+j-1);
		rep(k,n) rep(i,n) rep(j,n) Min(d[i][j],d[i][k]+d[k][j]);
		rep(i,n)
		{
			ans=min(ans,work(*a,i,*a,i+n));
			for (int j=0; j<n; ++j) 
				d[0][chg(i+j)]=work(*a,i,a[i+j],i+j-1),
				d[chg(i+j)][0]=work(a[i+j],i+j+1,*a,i+n);
			rep(j,n) rep(k,n) Min(ans,d[0][j]+d[j][k]+d[k][0]);
		}
		printf("%.2lf\n",ans);
	}
	return 0;
}

$Rain$

满分做法:一个点的水面高度取决于它到边界必须经过的点中的最高海拔.

预处理出边界,从边界上的点出发跑 $Dijkstra$ ,求出每个点的水面高度,然后 $bfs$ 求联通块.

求边界可以先极角排序,从 $x$ 坐标最小的点出发,绕一圈就是边界.

时间复杂度 $O(m\cdot \log m)$ .

考试情况: puts(“0”);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
#define rep(i,n) for (int i=0,_=n;i<_;++i)
#define pb push_back
#define mk make_pair
const int N=52*52;
int Case,n,m,u,v,X,Y,now,o,x[N],y[N],h[N],d[N],id[N],ans[N];
bool b[N];
priority_queue<pair<int,int> > H;
vector<int> e[N];
char st[5];
int C(char x)
{
	return x<'a'?x-65:x-71;
}
int get()
{
	scanf("%s",st);
	int v=C(st[0])*52+C(st[1]);
	if (id[v]<0) id[v]=now++;
	return id[v];
}
bool cmp(const int i,const int j)
{
	return atan2(y[i]-Y,x[i]-X)<atan2(y[j]-Y,x[j]-X);
}
void dfs(int i)
{
	if (!b[i] || d[i]<=h[i]) return;
	b[i]=0;
	rep(k,e[i].size()) dfs(e[i][k]);
}
int main()
{
	freopen("rain.in","r",stdin);
	freopen("rain.out","w",stdout);
	while (scanf("%d%d",&n,&m)!=EOF)
	{
		rep(i,N) b[i]=1,id[i]=-1,e[i].clear(),d[i]=1<<20;
		now=0,o=0;
		rep(i,n)
		{
			u=get(),scanf("%d%d%d",x+u,y+u,h+u);
			if (x[u]<x[o]) o=u;
		}
		rep(i,m) u=get(),v=get(),e[u].pb(v),e[v].pb(u);
		rep(i,n) X=x[i],Y=y[i],sort(e[i].begin(),e[i].end(),cmp);
		d[o]=h[o],H.push(mk(-d[o],o));
		for (int j=o,i=e[o][0];; j=i,i=e[i][u])
		{
			rep(k,e[i].size()) if (e[i][k]==j)
			{
				u=k;
				break;
			}
			if (++u==e[i].size()) u=0;
			d[i]=h[i],H.push(mk(-d[i],i));
			if (i==o && !u) break;
		}
		while (!H.empty())
		{
			pair<int,int> t=H.top();
			H.pop();
			int i=t.second;
			if (-t.first==d[i]) rep(k,e[i].size())
			{
				int j=e[i][k];
				if (max(d[i],h[j])<d[j]) d[j]=max(d[i],h[j]),H.push(mk(-d[j],j));
			}
		}
		int L=0;
		rep(i,n) if (b[i] && d[i]>h[i]) ans[L++]=d[i],dfs(i);
		if (!L) puts("0");
		sort(ans,ans+L);
		rep(i,L) printf("%d\n",ans[i]);
	}
	return 0;
}