Difference between revisions of "ACM-ICPC 2018 Qingdao Online Contest"
Xiejiadong (talk | contribs) |
|||
| (16 intermediate revisions by 4 users not shown) | |||
| Line 33: | Line 33: | ||
题意：$n \times m$ 的棋盘上，水彩笔涂了 $k$ 条不相交的线，求前 $i$ 行的黑块和黑联通块数量。 | 题意：$n \times m$ 的棋盘上，水彩笔涂了 $k$ 条不相交的线，求前 $i$ 行的黑块和黑联通块数量。 | ||
| − | + | 题解：将每条线记在左上角处，每对交点会在 “较低” 的线计算，可以证明这样交点数量是 $O(N)$ 的。这样就只需要记录上一行的横线和能影响到这两行的竖线，然后大力讨论接上的情况。讨论有点烦，不是特别好写，贡献不少罚时，浪费不少机时。 | |
== Problem E == | == Problem E == | ||
| Line 39: | Line 39: | ||
== Problem F == | == Problem F == | ||
| − | + | Upsolved by ultmaster. 04:59 (-5) | |
| + | |||
| + | 题意：给一个 split graph，求最大团和最大独立集计数。 | ||
| + | |||
| + | 题解：首先要把 split graph 的团和独立集分出来。思路如下，把点按度数从大到小排序，然后把度数相等的点一批一批加进来。如果有一批不能完全加入，则至多只能加入一个点，而且后面的批次都不能加入了。证明如下：假设团的大小为 $k$，则团内点的度数 $\ge k-1$，团外点的度数 $\le k-1$。如果出现了第一批点（度数为 $d$）不能完全加进来，则至多只能加进来一个：因为 $d \ge k-1, d \le k-1$，所以 $d=k-1$，一旦加入一个 $k$ 就固定下来了。 | ||
| + | |||
| + | 分完以后就比较直观了。最大团计数初始有一个，然后枚举外面的点，一旦发现该点与团内 $n-1$ 个点相连，它就可以跟团内剩下的那个点换，计数加 1。最大独立集计数枚举团内的点，要看存不存在有一个点跟外面没有点相连，如果有独立集大小就是 $n-clique+1$，计数是团内不跟外面相连的点的个数；否则独立集大小是 $n-clique$，计数是团内跟外面只有一个点相连的点的个数 + 1。 | ||
| + | |||
| + | 实现的时候绝不要搞出 $n \sqrt {n}$，但有 log 是可以接受的。 | ||
| + | |||
| + | ultmaster: 我把度数桶排了，结果度数为 0 的 vector 没清零。背锅。 | ||
== Problem G == | == Problem G == | ||
| Line 60: | Line 70: | ||
== Problem I == | == Problem I == | ||
| + | |||
| + | Upsolved by kblack. | ||
| + | |||
| + | 题意：一个圆在 $(2r, 0)$ 以 $v$ 的速度向 $x$ 轴正方向运动，拿着另一个在 $(0, 0)$ 的圆，以不超过 $2v$ 的速度，用最快的方式将他移动到 $(d, 0)$。 | ||
| + | |||
| + | 题解：将运动的圆的半径放到 $2r$，这样变成自己的圆的点不进另一个圆中。最快的方式肯定是切着过去，切着过去的方程是 $2r\frac{d\theta}{dt} = v(\sqrt{3+\sin^2\theta}-\sin\theta)$，移项得 $\frac{2rd\theta}{v(\sqrt{3+\sin^2\theta}-\sin\theta)} = dt$，两边积分并移项可得 $\displaystyle \frac{2r}{v}\int_0^\phi{\frac{d\theta}{\sqrt{3+\sin^2\theta}-\sin\theta}} = t$，这样就可以通过切着走的角度 $\phi$ 计算时间了，这破玩意儿积不动的，只能自适应辛普森。接下来分两种情况，如果切着走完以后目标点已经被覆盖了，那么干脆以 $v$ 的速度跟着走会更快；否则需要切着走到 $\phi$ 然后直达目的地，这个溜走位置显然可以二分，算一通三角函数就好了。 | ||
| + | |||
| + | kblack: 赛场上看错了题，虽然大部分点都想到了然后并没有卵用，甚至补题写了一个半小时怎么都调不对才发现这一点，这么看好像不怎么遗憾了呢。QAQQQ | ||
== Problem J == | == Problem J == | ||
| Line 80: | Line 98: | ||
Solved by oxx1108. 00:10(+) | Solved by oxx1108. 00:10(+) | ||
| + | |||
| + | 题意：签到 | ||
| + | |||
| + | 题解：签到 | ||
== Problem B == | == Problem B == | ||
| − | + | Upsolved by dreamcloud. | |
| + | |||
| + | 题意：给一棵红黑树，定义红点代价为 0，黑节点代价为到最近的红节点祖先的距离。每次询问一个点集，允许修改一个黑节点为红节点，求点集中代价最大的节点的最小值。 | ||
| + | |||
| + | 题解：赛后过了好久，才惊奇地发现题意读错了，黑节点的代价读为了到最近的红节点的距离。尝试了上述的二分答案，果断超时。只需要对点集种的点按照代价从大到小排序，依次枚举前面的LCA。 | ||
| + | |||
| + | Xiejiadong：题目读错了。题目复杂了好多。背锅。 | ||
== Problem C == | == Problem C == | ||
Solved by Xiejiadong. 00:53(+1) | Solved by Xiejiadong. 00:53(+1) | ||
| + | |||
| + | 题解：给一个程序，判断是否是死循环。 | ||
| + | |||
| + | 题解：死循环就是回到原来一个语句，且这个变量的值已经出现过。 | ||
| + | |||
| + | 直接暴力模拟。复杂度$O(n*256)$。 | ||
== Problem D == | == Problem D == | ||
| Line 104: | Line 138: | ||
Solved by Xiejiadong. 03:21(+2) | Solved by Xiejiadong. 03:21(+2) | ||
| + | |||
| + | 题意：每次删除一个数，把序列分开，求每次删除以后每一段序列里面逆序对最多的数量是多少。 | ||
| + | |||
| + | 题解：每次都暴力的做。 | ||
| + | |||
| + | 用主席树预处理权值线段树。 | ||
| + | |||
| + | 枚举短的一段，暴力计算跨区间的逆序对数量，从这一段中分成两段，并减去。 | ||
| + | |||
| + | 口胡还是很轻松的。写起来巨恶心。还卡读入。 | ||
== Problem H == | == Problem H == | ||
| − | Solved by . 00:48(+) | + | Solved by dreamcloud. 00:48(+) |
| + | |||
| + | 题意：一条直线上有$n$个点，每相邻节点之间有红绿灯，每秒变换，走过两个相邻节点的时间也是1s，求所有点对的旅行代价之和。 | ||
| + | |||
| + | 题解：DP 一下就好了，枚举每个点奇时刻到底和偶时刻到达向后走总的旅游代价之和。 | ||
== Problem I == | == Problem I == | ||
| − | + | Unsolved. | |
== Problem J == | == Problem J == | ||
| − | Solved by oxx1108 && | + | Solved by oxx1108 && dreamcloud. 02:00(+5) |
| + | |||
| + | 题意：周期性按按钮，求亮着的情况按下的次数。 | ||
| + | |||
| + | 题解：周期 $a \times c$，周期只有 $a+c$ 个关键点，周期内乘系数再加上最后一段。边界没考虑清楚写自闭了…… | ||
== Problem K == | == Problem K == | ||
Solved by Xiejiadong. 00:15(+) | Solved by Xiejiadong. 00:15(+) | ||
| + | |||
| + | 题意：签到。 | ||
| + | |||
| + | 题解：把二进制下位数相同的分为一组即可。统计组里最大的数量。 | ||
Latest revision as of 00:27, 20 September 2018
ECNU Foreigners
ultmaster: 题目比较。。正常的比赛。
Problem A
Solved by zerol. 00:12 (+)
温暖的签到。
Problem B
Solved by ultmaster. 02:14 (+)
题意：给一棵黑白树，定义白节点代价为 0，黑节点代价为到最近的白节点祖先的距离。每次询问一个点集，允许修改一个黑节点为白节点，求点集中代价最大的东西的最小值。
题解：二分答案，然后求超过答案的部分的 LCA。然后将这个点染白，检查超过答案的部分是不是被卡进答案范围内了。
Problem C
Solved by zerol. 00:35 (+)
题意：给一些指令，问是否有限步内结束。
题解：状态数很少，直接模拟，如果遇到重复状态就不停机了。
Problem D
Solved by kblack. 04:10 (+4)
题意：$n \times m$ 的棋盘上，水彩笔涂了 $k$ 条不相交的线，求前 $i$ 行的黑块和黑联通块数量。
题解：将每条线记在左上角处，每对交点会在 “较低” 的线计算，可以证明这样交点数量是 $O(N)$ 的。这样就只需要记录上一行的横线和能影响到这两行的竖线，然后大力讨论接上的情况。讨论有点烦，不是特别好写，贡献不少罚时，浪费不少机时。
Problem E
Problem F
Upsolved by ultmaster. 04:59 (-5)
题意：给一个 split graph，求最大团和最大独立集计数。
题解：首先要把 split graph 的团和独立集分出来。思路如下，把点按度数从大到小排序，然后把度数相等的点一批一批加进来。如果有一批不能完全加入，则至多只能加入一个点，而且后面的批次都不能加入了。证明如下：假设团的大小为 $k$，则团内点的度数 $\ge k-1$，团外点的度数 $\le k-1$。如果出现了第一批点（度数为 $d$）不能完全加进来，则至多只能加进来一个：因为 $d \ge k-1, d \le k-1$，所以 $d=k-1$，一旦加入一个 $k$ 就固定下来了。
分完以后就比较直观了。最大团计数初始有一个，然后枚举外面的点，一旦发现该点与团内 $n-1$ 个点相连，它就可以跟团内剩下的那个点换，计数加 1。最大独立集计数枚举团内的点，要看存不存在有一个点跟外面没有点相连，如果有独立集大小就是 $n-clique+1$，计数是团内不跟外面相连的点的个数；否则独立集大小是 $n-clique$，计数是团内跟外面只有一个点相连的点的个数 + 1。
实现的时候绝不要搞出 $n \sqrt {n}$，但有 log 是可以接受的。
ultmaster: 我把度数桶排了，结果度数为 0 的 vector 没清零。背锅。
Problem G
Solved by zerol. 02:50 (+)
题意：给一个数列，每次删除其中一个数，求出每一段的逆序对数量的最大值。强制在线。
题解：考虑新分裂出的两段，短的那段暴力计算，长的那段把短的那段以及删除掉的数的贡献从中扣除，复杂度 $O(n \log^2 n)$。
zerol: 自闭了近两小时，两度做成另一道题，所以根本过不了样例。背锅
Problem H
Solved by ultmaster. 00:55 (+)
题意：直线上红绿灯每秒变换，求所有点对的旅行代价。
题解：应该瞎 DP 一下就好了。奇偶搞错了自闭了好一会儿。
Problem I
Upsolved by kblack.
题意：一个圆在 $(2r, 0)$ 以 $v$ 的速度向 $x$ 轴正方向运动，拿着另一个在 $(0, 0)$ 的圆，以不超过 $2v$ 的速度，用最快的方式将他移动到 $(d, 0)$。
题解：将运动的圆的半径放到 $2r$，这样变成自己的圆的点不进另一个圆中。最快的方式肯定是切着过去，切着过去的方程是 $2r\frac{d\theta}{dt} = v(\sqrt{3+\sin^2\theta}-\sin\theta)$，移项得 $\frac{2rd\theta}{v(\sqrt{3+\sin^2\theta}-\sin\theta)} = dt$，两边积分并移项可得 $\displaystyle \frac{2r}{v}\int_0^\phi{\frac{d\theta}{\sqrt{3+\sin^2\theta}-\sin\theta}} = t$，这样就可以通过切着走的角度 $\phi$ 计算时间了，这破玩意儿积不动的，只能自适应辛普森。接下来分两种情况，如果切着走完以后目标点已经被覆盖了，那么干脆以 $v$ 的速度跟着走会更快；否则需要切着走到 $\phi$ 然后直达目的地，这个溜走位置显然可以二分，算一通三角函数就好了。
kblack: 赛场上看错了题，虽然大部分点都想到了然后并没有卵用，甚至补题写了一个半小时怎么都调不对才发现这一点，这么看好像不怎么遗憾了呢。QAQQQ
Problem J
Solved by kblack. 01:04 (+)
题意：周期性按按钮，求亮着的情况按下的次数。
题解：周期 $a \times c$，周期只有 $a+c$ 个关键点，周期内乘系数再加上最后一段。
Problem K
Solved by kblack. 00:14 (+)
温暖的签到。
One,Two,Three,AK
Problem A
Solved by oxx1108. 00:10(+)
题意：签到
题解：签到
Problem B
Upsolved by dreamcloud.
题意：给一棵红黑树，定义红点代价为 0，黑节点代价为到最近的红节点祖先的距离。每次询问一个点集，允许修改一个黑节点为红节点，求点集中代价最大的节点的最小值。
题解：赛后过了好久，才惊奇地发现题意读错了，黑节点的代价读为了到最近的红节点的距离。尝试了上述的二分答案，果断超时。只需要对点集种的点按照代价从大到小排序，依次枚举前面的LCA。
Xiejiadong：题目读错了。题目复杂了好多。背锅。
Problem C
Solved by Xiejiadong. 00:53(+1)
题解：给一个程序，判断是否是死循环。
题解：死循环就是回到原来一个语句，且这个变量的值已经出现过。
直接暴力模拟。复杂度$O(n*256)$。
Problem D
Unsolved.
Problem E
Unsolved.
Problem F
Unsolved.
Problem G
Solved by Xiejiadong. 03:21(+2)
题意：每次删除一个数，把序列分开，求每次删除以后每一段序列里面逆序对最多的数量是多少。
题解：每次都暴力的做。
用主席树预处理权值线段树。
枚举短的一段，暴力计算跨区间的逆序对数量，从这一段中分成两段，并减去。
口胡还是很轻松的。写起来巨恶心。还卡读入。
Problem H
Solved by dreamcloud. 00:48(+)
题意：一条直线上有$n$个点，每相邻节点之间有红绿灯，每秒变换，走过两个相邻节点的时间也是1s，求所有点对的旅行代价之和。
题解：DP 一下就好了，枚举每个点奇时刻到底和偶时刻到达向后走总的旅游代价之和。
Problem I
Unsolved.
Problem J
Solved by oxx1108 && dreamcloud. 02:00(+5)
题意：周期性按按钮，求亮着的情况按下的次数。
题解：周期 $a \times c$，周期只有 $a+c$ 个关键点，周期内乘系数再加上最后一段。边界没考虑清楚写自闭了……
Problem K
Solved by Xiejiadong. 00:15(+)
题意：签到。
题解：把二进制下位数相同的分为一组即可。统计组里最大的数量。