Table of Contents


Round #334 (Div 1) [5/5]

DONE T1 (-3) (#)

DONE T2 (-3) (#)

DONE T3 (-6) (*)

DONE T4 (-14) (*)   geometry

DONE T5 (-2) (*)   dsu LCT

Round #327 (Div 1) [5/5]

during I coded in the virtual contest, the server of codeforces had some mistakes. I just submitted the code by vjudge. (My contest score is '0', f**k!)

DONE T1 (-2) (#) (X)   special

I didn't think out all situations.

I just get ans from this situation like this: "…1101011…". but I missed a similar one, such as "…110100…" with two '1' at front and two '0' at rear. This is my failure.

DONE T2 (-2) (*)   binary_search

I didn't think binary search was OK in the beginning… Because of $ vmax ^ 2 >= vx ^ 2 + vy ^ 2 $ (the same as $ wx, wy), the man can stay at any position he reaches.

Just binary search. binary search time and work out the new position of the man. But if your eps is '1e-9' and even smaller when doing binary search, the problem won't stop. eps is too small.

DONE T3 (-2) (#) (X)   graph dfs

I didn't think out all situations, again! There isn't only one way to build the road.

I didn't think out this way: build three roads from a node '.' to three states. It means we can go to any state from the node, and it's the same the other way round. Sometimes this scheme is the best.

DONE T4 (-2) (*) (X)   knapsack

In the beginning, I didn't realize that we could make the first k numbers become any situation with the operator n2 times at most. If we know this, this problem can be solved prefectly by knapsack. If we need to get a maximim scheme, initing all the DP val as '-oo' is useful, at least in this problem. "Think twice, Code once." –by Matthew99

DONE T5 (-2) (*)   AC_trie bipartite_graph DAG 最长反链

Change the problem to a DAG problem. if s(v) is a substring of s(u), then AddEdge(u –> v). This subtask can solved with AC-trie.

Then we get a DAG. We should choose nodes as more as possible which cannot reach to any of others. This is a problem about 最长反链. Solve this with bipartite graph.

Round #319 (Div 1) [5/5]

Some interesting problems.

DONE T1 (-0) (#)   math prime

A easy math problem. For any prime p, query $ p ^ 1, p ^ 2, p ^ 3, … p ^ k $, until $ p ^ {k + 1} > n $. This is best way. If we query $ p1 ^ k1 * p2 ^ k2 $, some numbers can make this scheme worse than the above one.

DONE T2 (-2) (#)   permutation

A problem about permutation. Attention p[] is a permutation.

for two circulation (1 2 3) (4 5), if we add a edge 1 –> 4, then there must be these edges: { 1 –> 4, 2 –> 5, 3 –> 4, 1 –> 5, 2 –> 4, 3 –> 5 } But then there are circle in the graph. this is due to the size of the two circulation.'

Think carefully, and you will get the right way.

DONE T3 (-2) (*)   block

I was so stupid…

Like 莫队. If the size of block is $ S $, then the count is: $ n * S + 2 * n / S $. We can find the best $ S $ and then solve the problem by sort.

DONE T4 (-2) (*)   matrix floyd

The biggest problem is when these edges are available. One way is using matrix. Using matrix to know that after passing $ d $ edges, which nodes node $ 1 $ can reach. Then for those nodes, they can use the edges whose val is lower than $ d $.

DONE T5 (-?) (*)

If you divide and conquer with DSU, the main problem is that we don't know if the edge is changed successfully, and it will influence other edge. So we should add edge to the node dynamically in the segment-tree.

If you use LCT, there will be many details. For unicom nodes, if the size is $ N $, we only keep $ N - 1 $ edges in LCT. But which edges should be keeped? Just like humdrum queue.

Round #313 (Div 1) [5/5]

DONE T1 (#) (0)

A easy problem about area. the answer is the area of the big triangle minus the area of three small triangles.

DONE T2 (#) (-1)   string

A problem about the conversion of string.

But in the beginning, I write a BF whose time complexity is T(n) = 4T(n / 2) + O(n) = O(n ^ 2), and n is at most 1e5… I heard that someone got AC with this wrong algorithm! None hack him?

With this conversion, a string can be changed into many kinds of new strings; and this new strings can also be changed into the origin string.

If string A can be changed into string B, then output "YES", otherwise output "NO". This means that if A can change to a string S, then A can also change to B, otherwise the answer is "NO". We make S the minimum (字典序最小) string which A can change to, and S0 for B. If S0 == S, then the answer is "YES", otherwise the answer is "NO".

DONE T3 (#) (-1)   count

a counting problem. But in the first submission the array size is a little small, then I get RE … Let DP(i) be the count of the schemes to walk from (0, 0) to (h, w), which is the position of point i.

If some point j, whose position is (h0, w0) (h0 < h & w0 < w), cannot be reached, then decrease the contribution of this point. In the beginning, DP(i) is the count of the schemes to walk from (0, 0) to (h, w), ignoring the point cannot be reached. DP(i) -= DP(j) * (the count of the schemes to walk from (h0, w0) to (h, w), ignoring the point cannot be reached).

If you want to know the prove,

DONE T4 (*) (?)

Let think a O(n ^ 2) algorithm first.

Enumerate i and j, calculate how many points won't be in the new polygon when the edge (i –> j) is in it. We need to use Pick's theorem. Attention, if i + 1 == j, the theorem cannot be used normally. it needs special judging. This one is very important.

Then just cal the probability of the edge appearing. the point From i + 1 to j - 1 cannot appear and point i, j must appear. Only one scheme is OK. At least one of the point from j + 1 to i - 1 needs to appear. Only one scheme is not OK, let it be $ sumi, j $. Then $ sumi, j / cntofallschemes $ is the probability.

But if there are many points between point i and j in the origin polygon, the probability is very small. If the count of the point between them is $ cnt $, the probability is smaller than 2 ^ -(cnt). when cnt is bigger than 60, it is very small for 1e-9 — the reqire of this problem. So just Enumerate i and j, j is from (i + 1) % n to (i + n - 1) % n. when j == (i + 60) % n, stop and enumerate a new i.

DONE T5 (*) (-5)

A problem about DP. $ ai $ is too large. Discrete! If let $ DPi $ means at the left of $ DPi $, how long the path is at most, and use every spotlight to update the value, we will found that there will be a problem like this: if the i th spotlight update $ DPs $ with \(DP_{s - 1}\), and the i + 1 th update $ DPs - 1 $ (\(DP_{s - 1}\) become larger), we know that \(DP_{s}\) may be able to be updated by \(DP_{s - 1}\) with the i th. But i + 1 > i, so we won't enumerate i again!

So, we should use a new dp status. Let $ dp(R, i) $ means the length of the longest path with the spotlights numbered 1, 2, 3, … , n, and the scheme should light position i.

But how to update the status? Think by yourself.

With more,


<2016-12-10> arc065 [4/4]

DONE C Daydream

思博题, 略.

DONE D Connectivity


给你一个点集和两个无向边集, 请你计算对于每一个点, 有多少个点在两个边集中都可以到达. (包括自己这个点)


不妨对两个边集分别做并查集, 则对于一个点i, 我们可以用 \((x_i, y_i)\) 来表示, 其中 x 为在第一个边集中并查集的编号, y 为第二个. 那么我们只要计算有多少个点j 满足 \((x_i, y_i) = (x_j, y_j)\) 即是点i 的答案. 用 map 统计即可.

DONE E Manhattan Compass


给你平面上的 n 个点, 第 i 个点的坐标用 \((x_i, y_i)\) 表示. 记 \(d(i, j) = |x_i - x_j| + |y_i - y_j|\). 一开始给你一个点对 合法点对(a, b), 我们定义:

  1. 如果点对 (a, b) 合法, 则点对 (b, a) 合法.
  2. 如果点对 (a, b) 合法且另一个点对(b, c) 满足 d(a,b) = d(b,c), 则点对 (b, c) 合法.

输出 (合法点对的个数) / 2. n <= 100000


我们记 dist = d(a, b), 显然, 我们只要找出 d(a, c) = dist 的所有点 c, 再从 每一个被找到的新点 c 出发来寻找, 依此类推, 直到找不到新的点为止. 所有点找到的合法点数之和即为合法点对的个数. 注意到到某一个点的曼哈顿距离为定值的点组成了一个倾斜45度的正方形的边框. 这些点要么是 x+y 满足某种要求, 要么是 x-y 满足某种要求. 所以可以用数据结构处理. 寻找新点用 set 随便搞一下就行了. 统计个数离散化后 lower_bound 就行了.

DONE F Shuffling


给你一个长度为 n 的数组, 其中的元素只有 0 或 1. 再依次给你 m 个区间, 对于每一个给出的区间, 你可以将这个区间中的元素以任意顺序进行排列, 直到你使用下一个给你的区间. 保证所给区间的左端点递增. 输出使用 m 个区间后数组有多少种可能的排列. n, m <= 3000.


显然, 去掉被其他区间完全覆盖的区间, 答案不变. 这样处理后, 右端点递增. 由于可以任意排列, 因此对于一段区间, 其排列方式只与里面 1 的个数有关. 左端点递增, 显然可以DP, 因为区间的左端点递增能保证: 某一个位置一旦从可以被排列变为不能被排列, 以后也就再也不会变了. 我们从区间 [L, R] 转移到 [L', R'] 时, 只要考虑哪些位置即将被确定. 显然是区间 [L, L') 中的元素. 我们只要枚举有多少个 1 在这段区间内即可得出这段区间的方案数. 由于这会使其他区间内 1 的个数发生改变, 为了记录, 我们再用一维状态记录 [L, R] 中 1 的个数. 于是设状态 dp(L, R, c) 表示当前所给的区间区间 [L, R] 中有 c 个1时, 区间 [0, L) 排列的方案数. 转移方程显然. 不过貌似不能 O(1) 转移啊… 不过均摊是 O(1) 的… 因为总长度只有 n 啊… 每1单位的长度对复杂度的贡献最多是 O(n) 的. 不过还有更有技巧性的做法: 对于 L+1 < L', 我们再添加一个新的区间 [L+1, L+1], 由于长度为 1, 所以答案不变. 同时, 枚举有多少个 1 在 [L, L+1) 中也变为 O(1) 的了. 一直往后做, 不连续就补上即可.

<2016-01-22> agc009 [2/3]

本来十分激动地报名了 GRAND, 打算大打一场… 然而代码能力实在太弱了, T2 错了 N 次, T3 觉得细节太多都没敢打 (其实是自己的做法太复杂了)… 最后就只做了两道题.

其实本质是自己没有完全想清就打, 这样似乎比较容易挂在细节上.

DONE A Multiple Array


给你两个长度为 n 的数组 A, B, 每次你可以选定一个 \(i\), 使 \(A_{1..i}\) 的值全部 +1. 目标是对于所有的 i (1 <= i <= n), 满足 \(B_i | A_i\).

n <= 100000.


由于每次修改一个前缀, 所以应该先满足较大的 \(i\) 的要求. 不妨从大到小枚举 \(i\), 依次计算在考虑之前 +1 操作的贡献后, 当前需要 +1 多少次, 然后令 \(i = i-1\), 继续做.

TODO B Tournament


给定一些编号从 1 到 n 选手, 这些选手之间将进行 n-1 场比赛, 每场比赛两个人参加并淘汰掉输掉的一个人, 直到决出最终的胜利者.
现在给出某次 n-1 场比赛的结局, 即告知每个选手是在与谁的比赛中被淘汰的. 假设当前选手 1 为最终胜利者.
显然有多种安排比赛的方案可以形成这种结局. 现在要你输出一种方案, 使得 胜出所需要比赛的次数最多的人需要的次数最小. 不过为了方便, 只要求输出比赛次数.

\(n \leq 10^5\)



随便 DP 一下呀… 明明很水却讲不清.

DONE C Division into Two


给你 n 个数字 \(a_{1..n}\), 这 n 个数字严格递增. 我们要将这些数分为两个部分 \(X\), \(Y\), 其中 \(X\) 集合中的数两两之间差的绝对值不小于 \(A\), \(Y\) 集合中差的绝对值不小于 \(B\).


由于给定的数字是严格递增的, 那么我们只要在每次选数时判一下和上次选的数的差的绝对值是否满足要求即可.

我们设 \(f(i)\) 为考虑前 i 个数, 第 i 个数在 \(X\) 集合中的方案数, 那么我们枚举 i 之前选的数 j, 然后判断一下 \([j+1, i-1]\) 的数能否放入 \(Y\) 集合. 这个检查一下相邻的数的差的绝对值即可.
然而这样可能会不合法方案. \([j+1, i-1]\) 之间即使合法, \(j+1\) 同 \(j\) 前面在 \(Y\) 集合中的数依然可能不合法.
不妨增设 \(g(i)\), 表示第 \(i\) 个数在 \(X\) 集合中, 且第 \(i-1\) 个数在 \(Y\) 集合中时的方案数. 我们强制 \(A > B\), 则 \(f(j) - g(j)\) 是一定可以贡献 \(f(i)\) 的, 但 \(g(j)\) 当且仅当 \(a_j - a_{j-2} \geq B\) 时对 \(f(i)\) 有贡献. 在满足前面的条件下, 当 \(j \neq i-1\) 时对 \(g(i)\) 有贡献.

算答案也很好算, 枚举以下序列末尾有几个数在 \(Y\) 集合中即可.

这是 \(O(n^2)\) 的, 用前缀和优化至 \(O(n)\).

(我代码里是反过来的, 即 \(f(i)\) 表示第 i 个数在 \(Y\) 集合中的方案数)

E Eternal Average

<2016-02-19> arc069 [/]