精美个人网站,wordpress 服务器,张家界酒店网站建设,荣耀手机官网网站4169: Lmc的游戏 Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 44 Solved: 25Description RHL有一天看到lmc在玩一个游戏。愚蠢的人类哟#xff0c;what are you doing#xff0c;RHL说。我在玩一个游戏。现在这里有一个有n个结点的有根树#xff0… 4169: Lmc的游戏 Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 44 Solved: 25 Description RHL有一天看到lmc在玩一个游戏。 愚蠢的人类哟what are you doingRHL说。 我在玩一个游戏。现在这里有一个有n个结点的有根树其中有m个叶子结点。这m个叶子从1到m分别被给予了一个 号码每个叶子的号码都是独一无二的。一开始根节点有一个棋子两个玩家每次行动将棋子移动到当前节点的一 个儿子节点。当棋子被移动到某个叶节点的时候游戏结束这个叶节点的号码即为该局游戏的result。先手的玩家 要最大化result后手的玩家要最小化这个result。 你不先问一下我是谁吗 那么who are you 我是这个世界的创造者维护者和毁灭者整个宇宙的主宰无所不知无所不能的三个字母都大写的RHL。 既然你这么厉害那你一定知道在两个玩家都无限聪明的情况下在树的形态已知的情况下在叶子的编号可 以任意安排的情况下游戏的result最大是多少咯。 Input 输入数据第一行有一个正整数n表示结点的数量。n200000 接下来n-1行每行有两个正整数u和v表示的父亲节点是u。 Output 输出一行2个非负整数分别表示result的最大值和最小值。 Sample Input 5 1 2 1 3 2 4 2 5 Sample Output 3 2 【样例解释】 有3,4,5三个叶子。若令3号叶子的编号是3则先手可以移到3号结点故result最大是3。若3号叶子的编号是2 则先手可以移到3号结点故result最小是2. HINT Source 【分析】 【想出来了】 然而网上没有题解我就写写好少人做这题。 如果你是先手的话你肯定选子树里面能得到答案最大的那个走。 如果你是后手的话你肯定选子树里面能得到答案最小的那个走。 $mx[i]$表示走$i$这棵子树$result$最大是多少指的是你在子树填入$a1a2a3...$最大是排名第几的下同。 $mn[i]$表示走$i$这棵子树$result$最小是多少。 当你是偶数层$root$这层视为0即先手操作你应该是$resultmax子树1子树2子树3....)$ 最大化$result$显然是让各子树的$result$都最大化然后呢因为你取的是$max$所以最好就是把其他子树都堆在前面然后让$mx$最大的子树放在最后。 即$mx[x]max(mx[x],sm[x]-(sm[y]-mx[y]))$; sm是子树里面的叶子节点个数 最小化$result$就是让子树都先选$1~mn$放在前面即$mn[x]mn[y]$; 其实解题本质就是你自己想想怎么样分配最好嘛。。 当$dep$为奇数是$resultmin(max(),max(),...)$这样的形式如下 $mx[x]\sum (mx[y]-1) 1$; $mn[x]min(mn[x],mn[y])$; 也不知道怎么说。。 1 #includecstdio2 #includecstdlib3 #includecstring4 #includeiostream5 #includealgorithm6 using namespace std;7 #define INF 0xfffffff8 #define Maxn 2000109
10 int mymax(int x,int y) {return xy?x:y;}
11 int mymin(int x,int y) {return xy?x:y;}
12
13 int mx[Maxn],mn[Maxn];
14
15 struct node
16 {
17 int x,y,next;
18 }t[Maxn];
19 int first[Maxn],len;
20 void ins(int x,int y)
21 {
22 t[len].xx;t[len].yy;
23 t[len].nextfirst[x];first[x]len;
24 }
25
26 int sm[Maxn];
27 void dfs(int x,int dep)
28 {
29 sm[x]0;
30 if(first[x]0)
31 {
32 sm[x]1;
33 mn[x]mx[x]1;return;
34 }
35 for(int ifirst[x];i;it[i].next)
36 {
37 int yt[i].y;
38 dfs(y,dep^1);
39 sm[x]sm[y];
40 }
41 mx[x]0;mn[x]0;
42 if(dep) mx[x]1,mn[x]INF;
43 for(int ifirst[x];i;it[i].next)
44 {
45 int yt[i].y;
46 if(!dep)
47 {
48 mx[x]mymax(mx[x],sm[x]-(sm[y]-mx[y]));
49 mn[x]mn[y];
50 }
51 else
52 {
53 mx[x]mx[y]-1;
54 mn[x]mymin(mn[x],mn[y]);
55 }
56 }
57 }
58
59 int main()
60 {
61 int n;
62 scanf(%d,n);
63 int rt0;
64 for(int i1;in;i) rti;
65 len0;
66 memset(first,0,sizeof(first));
67 for(int i1;in;i)
68 {
69 int x,y;
70 scanf(%d%d,x,y);
71 ins(x,y);
72 rt-y;
73 }
74 dfs(rt,0);
75 printf(%d %d\n,mx[rt],mn[rt]);
76 return 0;
77 } View Code 转载于:https://www.cnblogs.com/Konjakmoyu/p/6691849.html
