A、B略
C. Mice problem
给定一个矩形，和一堆在线上跑的点，给出所有的点都在这个矩形内的最初时刻是多少？
这个题很糟糕...我没有参与这个比赛，不过看了看board发现FST了一坨...而且不乏红名 自己写了一下，果然边界条件好多...错了好多次。 方法倒是很简单，就是计算出每个点在矩形内的时间，然后做一个区间合并就好了。
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
119
120
121
122
123
124
| #include<bits/stdc++.h>
#define maxn 100010
#define pb push_back
using namespace std;
const double eps=1e-10;
int n;
double x1,y1,x2,y2;
double rx[maxn],ry[maxn],vx[maxn],vy[maxn];
vector<pair<double,double> > p;
int main()
{
scanf("%d",&n);
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
for(int i=1;i<=n;i++) scanf("%lf%lf%lf%lf",&rx[i],&ry[i],&vx[i],&vy[i]);
for(int i=1;i<=n;i++)
{
double a,b;
a=-1;
b=-1;
int bj=0;
if(rx[i]>=x1&&rx[i]<=x2&&ry[i]>=y1&&ry[i]<=y2)
{
bj=1; a=0.0;
if(vx[i]==0&&vy[i]==0)
{
bj++;
b=2147483600;
}
}
if(x1==rx[i]&&fabs(vx[i]-0.0)<eps) continue;
if(x2==rx[i]&&fabs(vx[i]-0.0)<eps) continue;
if(y1==ry[i]&&fabs(vy[i]-0.0)<eps) continue;
if(y2==ry[i]&&fabs(vy[i]-0.0)<eps) continue;
if((vy[i]*1.0/vx[i]*(x1-rx[i])+ry[i])>=y1&&(vy[i]*1.0/vx[i]*(x1-rx[i])+ry[i])<=y2&&((x1-rx[i])*1.0/vx[i])>=0)
{
if(bj==0)
{
a=(x1-rx[i])*1.0/vx[i];
}
else if(bj==1)
{
b=(x1-rx[i])*1.0/vx[i];
}
bj++;
}
if(fabs(b-a)<eps&&bj>1)
{
bj=1;
}
if((vy[i]*1.0/vx[i]*(x2-rx[i])+ry[i])>=y1&&(vy[i]*1.0/vx[i]*(x2-rx[i])+ry[i])<=y2&&((x2-rx[i])*1.0/vx[i])>-eps)
{
if(bj==0)
{
a=(x2-rx[i])*1.0/vx[i];
}
else if(bj==1)
{
b=(x2-rx[i])*1.0/vx[i];
}
bj++;
}
if(fabs(b-a)<eps&&bj>1)
{
bj=1;
}
if((vx[i]*1.0/vy[i]*(y1-ry[i])+rx[i])>=x1&&(vx[i]*1.0/vy[i]*(y1-ry[i])+rx[i])<=x2&&((y1-ry[i])*1.0/vy[i])>-eps)
{
if(bj==0)
{
a=(y1-ry[i])*1.0/vy[i];
}
else if(bj==1)
{
b=(y1-ry[i])*1.0/vy[i];
}
bj++;
}
if(fabs(b-a)<eps&&bj>1)
{
bj=1;
}
if((vx[i]*1.0/vy[i]*(y2-ry[i])+rx[i])>=x1&&(vx[i]*1.0/vy[i]*(y2-ry[i])+rx[i])<=x2&&((y2-ry[i])*1.0/vy[i])>-eps)
{
if(bj==0)
{
a=(y2-ry[i])*1.0/vy[i];
}
else if(bj==1)
{
b=(y2-ry[i])*1.0/vy[i];
}
bj++;
}
if(fabs(b-a)<eps&&bj>1)
{
bj=1;
}
if(bj>=2||(vx[i]==0&&vy[i]==0))
{
if(a>b) swap(a,b);
p.pb({a,b});
}
}
if(p.size()!=n)
{
printf("-1\n");
return 0;
}
double t=-1;
for(auto &i:p)
{
t=max(t,i.first);
}
for(auto &i:p)
{
if(t<i.first||t-i.second>-eps)
{
printf("-1\n");
return 0;
}
}
printf("%.10lf",t);
return 0;
}
|
D. Presents in Bankopolis 这个题不算太难... 其实就是规定一个区间，然后最短路只能在这个区间里面找。 然后每找到一个新的点，就把区间分裂成左右两半就好了。 就是一个[左边界][右边界][所在位置][走过的点数]的一个四维状态，然后跑spfa即可。
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
| #include<bits/stdc++.h>
using namespace std;
#define pb push_back
struct pp
{
int l,r;
int s;
int num;
};
bool v[82][82][82][82];
int d[82][82][82][82];
int n,k;
int m;
vector<int> e[82];
vector<int> w[82];
int ans=-1;
int main()
{
scanf("%d%d",&n,&k);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
e[a].pb(b);
w[a].pb(c);
}
for(int i=0;i<=n+1;i++)
for(int j=0;j<=n+1;j++)
for(int k=0;k<=n+1;k++)
for(int u=0;u<=n+1;u++)
{
v[i][j][k][u]=0;
d[i][j][k][u]=2147483600;
}
for(int g=1;g<=n;g++)
{
queue<pp> q;
pp o;
o.l=0; o.r=g; o.s=g; o.num=1;
d[o.l][o.r][o.s][o.num]=0;
v[o.l][o.r][o.s][o.num]=1;
q.push(o);
o.l=g; o.r=n+1; o.s=g; o.num=1;
d[o.l][o.r][o.s][o.num]=0;
v[o.l][o.r][o.s][o.num]=1;
q.push(o);
while(!q.empty())
{
pp f=q.front();
q.pop();
v[f.l][f.r][f.s][f.num]=0;
if(f.num==k)
{
if(ans==-1) ans=d[f.l][f.r][f.s][f.num];
else ans=min(ans,d[f.l][f.r][f.s][f.num]);
continue;
}
for(int i=0;i<e[f.s].size();i++)
{
if(e[f.s][i]>f.l&&e[f.s][i]<f.r&&d[f.l][f.r][f.s][f.num]+w[f.s][i]<d[f.l][e[f.s][i]][e[f.s][i]][f.num+1])
{
d[f.l][e[f.s][i]][e[f.s][i]][f.num+1]=d[f.l][f.r][f.s][f.num]+w[f.s][i];
if(v[f.l][e[f.s][i]][e[f.s][i]][f.num+1]==0)
{
v[f.l][e[f.s][i]][e[f.s][i]][f.num+1]=1;
pp u;
u.l=f.l;
u.r=e[f.s][i];
u.s=e[f.s][i];
u.num=f.num+1;
q.push(u);
}
}
if(e[f.s][i]>f.l&&e[f.s][i]<f.r&&d[f.l][f.r][f.s][f.num]+w[f.s][i]<d[e[f.s][i]][f.r][e[f.s][i]][f.num+1])
{
d[e[f.s][i]][f.r][e[f.s][i]][f.num+1]=d[f.l][f.r][f.s][f.num]+w[f.s][i];
if(v[e[f.s][i]][f.r][e[f.s][i]][f.num+1]==0)
{
v[e[f.s][i]][f.r][e[f.s][i]][f.num+1]=1;
pp u;
u.l=e[f.s][i];
u.r=f.r;
u.s=e[f.s][i];
u.num=f.num+1;
q.push(u);
}
}
}
}
}
printf("%d\n",ans);
return 0;
}
|
E. Problem of offices 这个题看了半天题意...终于理解到了错误的题意... 然后去看题解...才发现正确的题意...
给定一棵树，问存不存在一个欧拉路径，使得a到b之间的叶子节点数量和b到a之间相同，同时使c到d之间和d到c之间叶子节点数量也相同。a,b,c,d的最近公共祖先是树根
这个a,b,c,d的最近公共祖先是树根的条件隐藏在input中，难以发现。 知道这个条件之后，这个题就没那么难了。设一棵子树的\(size\)是子树的叶子节点数。 那么使a到b中间的叶子节点数和b到a中间的相同，那么整棵树的叶子节点数必定是偶数，而且a和b之间的叶子节点数量一定是\(\frac{m}{2}-1\)(\(m\)为叶子节点数量) 然后就是a到b路径上所有子树的\(size\)做一个大小为\(\frac{m}{2}-1\)的背包。 c,d和a,b类似。 因为a,b,c,d的最近公共祖先为树根，那么如果a,b,c,d的背包都可以构造出来，那么一定存在一个解使得这两个情况都满足。
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
| #include<bits/stdc++.h>
using namespace std;
#define pb push_back
int n;
int a,b,c,d;
int p[5010];
int size[5010];
vector<int> e[5010];
bool v[5010];
bool ff(int x,int y)
{
memset(v,0,sizeof(v));
bitset<5010> w;
w.reset();
w[0]=1;
int a,b;
a=x; b=y;
while(p[a]>1) a=p[a];
while(p[b]>1) b=p[b];
v[a]=1; v[b]=1;
for(int i=x;i!=0;i=p[i])
{
v[i]=1;
for(auto &j:e[i])
{
if(!v[j]) w|=w<<size[j];
}
}
for(int i=y;i!=1;i=p[i])
{
v[i]=1;
for(auto &j:e[i])
{
if(!v[j]) w|=w<<size[j];
}
}
return w[size[1]/2-1];
}
int main()
{
scanf("%d",&n);
scanf("%d%d%d%d",&a,&b,&c,&d);
for(int i=2;i<=n;i++)
{
scanf("%d",&p[i]);
e[p[i]].pb(i);
}
for(int i=n;i>=1;i--)
{
size[i]=max(size[i],1);
size[p[i]]+=size[i];
}
if(size[1]&1)
{
puts("NO");
return 0;
}
if(ff(a,b)&&ff(c,d)) puts("YES");
else puts("NO");
return 0;
}
|