这场SB了,用了花式语言…

C

终点可以在1-t里面随便选择一个

终点之后都是陷阱,然后有两个人在比赛,一个人一步走w米,一个人一步走b米,谁能不越过终点的情况,走的最远,就算谁赢

然后问你两人平局的概率是多少

可以发现可选长度即 k*lcm(w,b)+min(w,b) (k = 0,1,2…) 的每一段

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
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const double eps = 1e-8;

LL gcd(LL a,LL b)
{
return !b?a:gcd(b,a%b);
}

int main()
{
//freopen("test.txt","r",stdin);
LL t,w,b,ans = 0;
scanf("%lld %lld %lld",&t,&w,&b);

if(w > b) swap(w,b);
LL g = gcd(w,b);

if((double)w/g <= (double)t/b)
{
LL lcm = w/g*b;
ans = (t/lcm)*w - 1 + min(w,t%lcm + 1);
}
else
{
ans = min(w-1,t);
}

if(ans == 0) printf("%d/%d",0,1);
else
{
LL d = gcd(ans,t);
printf("%lld/%lld",ans/d,t/d);
}
return 0;
}

D

一棵树,选取其中的一些结点,求一条路径,遍历所有选定结点,最短且字典序最小。

我们可以以选定结点重新建树,可以发现叶子结点均为选定结点。
然后从一个结点出发遍历所有结点又回到这个结点的路径长度为2e(e为树的边数)
若不需要回到原来的结点,我们只需要求树的直径(最远路径) l
从其中一个出发,答案即为 2e-l

而树的直径可以两次dfs求出

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
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 2e6 + 10;

int vis[maxn];
vector<int> G[maxn],g[maxn];
int n,m,ans;

struct Node
{
int d,p;
};

bool dfs(int u,int fa)
{
bool flag = false;
for(int i=0;i<G[u].size();++i)
{
int v = G[u][i];
if(v == fa) continue;
if(dfs(v,u) || vis[v])
{
flag = true;
g[u].push_back(v);
g[v].push_back(u);
++ans;
}
}
return flag;
}

Node dfs1(int u,int fa)
{
bool leaf = true;
Node now = (Node){0,maxn};
for(int i=0;i<g[u].size();++i)
{
int v = g[u][i];
if(v == fa) continue;
leaf = false;
Node p = dfs1(v,u);
if(p.d+1 > now.d || (p.d+1 == now.d && now.p > p.p)) now = (Node){p.d+1,p.p};
}
if(leaf) return (Node){0,u};
return now;
}

void gao(int d)
{
Node p = dfs1(d,-1);
// printf("%d %d\n",p.d,p.p);
Node t = dfs1(p.p,-1);
printf("%d\n%d\n",min(t.p,p.p),2*ans - t.d);
}

int main()
{
// freopen("test.txt","r",stdin);
scanf("%d %d",&n,&m);
for(int i=1;i<n;++i)
{ int u,v;
scanf("%d %d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
memset(vis,0,sizeof vis);
int d;
for(int i=0;i<m;++i)
{
scanf("%d",&d);
vis[d] = 1;
}
ans = 0;
dfs(d,-1);
/*
for(int i=1;i<=n;++i)
{
printf("%d:",i);
for(int j=0;j<g[i].size();++j) printf(" %d",g[i][j]);
puts("");
}
*/
gao(d);
return 0;
}