Closed Wizmann closed 4 years ago
Contest Code
我是傻逼。
N个人编号1,2,3...N，两两比赛。 有M个比赛场地，每个比赛场地指定一组编号(a, b)。即编号为a和b的人在该场地进行一轮比赛。
每一轮比赛完成后，所有人的编号x都变为(x % N + 1)。问如何给场地进行编号，使得一个人在一轮比赛最多出场1次（可以不出场）。并且在N轮比赛中，不会有重复的对战。
看不懂描述可以去看原题，题意挺绕的。
首先要看懂题。然后会有一个基本的想法：因为人与人之间的编号差值不会改变，所以每一个差值最多只能出现一次。
然后手写一下N=4，M=1的情况：
1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3
我们可以看到，选择(1, 2)和(1, 4)是可行的，但是(1, 3)不可行。(1, 2), (1, 4)的差值为1和3，(1, 3)差值为2。并且(1, 2)和(1, 4)不能同时出现。 这时就要修正上面的想法。第一，两人编号的差值有两个: |b - a| 和 |a - b + n|。这两个差值都不能重复。第二，|b - a| <= (n - 1) / 2，否则就会发生(a, b)和(b, a)两轮比赛的重复。 也就是说，对于N个人，我们最多能同时进行(N - 1) / 2场比赛，每场比赛(a, b)编号差分别为[1... (N - 1) / 2]。
现在的问题就变成了怎么样来着构造适当的(a,b)编号了。 假设我们从(x, x+1)开始向两边扩展，就可以构造出差为1,3,5..的场地。因为差值最大不能超过(n - 1) / 2，所以只会用掉一半的编号。另外一半我们从(x, x + 2)进行扩展，构造差值为2,4,5..的场地。
给定一颗有根树，树的每一个节点都有一个值。问从根到叶子的路径中，最长上升子序列有多长。
这题比较有新意，但是并不难。
使用栈+二分的方法求LIS应该是非常常见的。在树上做的问题在于怎么样维护这个栈。 因为栈在状态转移过程中可能会修改中间的值或者在后面插入值。所以我们在dfs的每一层记录下当前的操作，在返回上一层的时候恢复回来即可。
可以写一个类似回调的东西骚一下。
Contest Code
E. Rotation Matching
题意
N个人编号1,2,3...N，两两比赛。 有M个比赛场地，每个比赛场地指定一组编号(a, b)。即编号为a和b的人在该场地进行一轮比赛。
每一轮比赛完成后，所有人的编号x都变为(x % N + 1)。问如何给场地进行编号，使得一个人在一轮比赛最多出场1次（可以不出场）。并且在N轮比赛中，不会有重复的对战。
解法
首先要看懂题。然后会有一个基本的想法：因为人与人之间的编号差值不会改变，所以每一个差值最多只能出现一次。
然后手写一下N=4，M=1的情况：
我们可以看到，选择(1, 2)和(1, 4)是可行的，但是(1, 3)不可行。(1, 2), (1, 4)的差值为1和3，(1, 3)差值为2。并且(1, 2)和(1, 4)不能同时出现。 这时就要修正上面的想法。第一，两人编号的差值有两个: |b - a| 和 |a - b + n|。这两个差值都不能重复。第二，|b - a| <= (n - 1) / 2，否则就会发生(a, b)和(b, a)两轮比赛的重复。 也就是说，对于N个人，我们最多能同时进行(N - 1) / 2场比赛，每场比赛(a, b)编号差分别为[1... (N - 1) / 2]。
现在的问题就变成了怎么样来着构造适当的(a,b)编号了。 假设我们从(x, x+1)开始向两边扩展，就可以构造出差为1,3,5..的场地。因为差值最大不能超过(n - 1) / 2，所以只会用掉一半的编号。另外一半我们从(x, x + 2)进行扩展，构造差值为2,4,5..的场地。
F. LIS on Tree
题意
给定一颗有根树，树的每一个节点都有一个值。问从根到叶子的路径中，最长上升子序列有多长。
解法
这题比较有新意，但是并不难。
使用栈+二分的方法求LIS应该是非常常见的。在树上做的问题在于怎么样维护这个栈。 因为栈在状态转移过程中可能会修改中间的值或者在后面插入值。所以我们在dfs的每一层记录下当前的操作，在返回上一层的时候恢复回来即可。