2020/02/10

CF 1299D

几乎没有任何思路。不熟悉common knowledge: In an undirected graph there is some subset (not necessarily unique) of simple cycles called basis such that any Eulerian subgraph (in connected graphs also known as a cyclic path) is a xor-combination of exactly one subset of basis cycles.

Cycle basis也算是图论的经典概念了吧，可能之前接触得少。

CF smeke told:
> I'm sure this kind of practice (study, practice solving fast) works before reaching 2600. After that, the strategy wouldn't work well.
> What I imagine about rating 2600 (2600 in Topcoder, 3000 in AtCoder): You can write a code very fast without fatal bugs. You know almost every typical algorithms, including LCA, Dinic, FFT, finding bridges, O(N^2 log K) for k-fibonacci, etc.
> After 2600, you have to solve once boss problem in the problem set in several rounds, and many problems are not solved by knowledge, reflection or one-step consideration. Those are all creative, ad-hoc problems.
> I once heard that in order to tackle with ad-hoc problems effectively, you have to throw yourself into a problem for hours, and try everything you can try, and train your instinct — which kind of algorithm works to certain problems. This is the skill which fast-solving or virtual contests doesn't help you improve.
> On the other hand, although I don't like to say this aloud, from this rating zone I feel your latent ad-hoc (or mathematical) power makes a lot of difference. It is often said that IMO gold medalists can be very strong in programming contests once they know typical algorithms and get used to implementation. (Even if the difference derives from how they trained their mathematical skills when they were young,) you can't change what you are. I realized that I wasn't a genius, when I lost to a lot of OI friends in national math olympiad after studying hundreds of hours for that.
> But that doesn't mean you can't become a skilled competitive programmer. The practice I said surely change your ad-hoc skills in a long view. Sharpen your intuition, tackle novel problems with it. Neither your friends' solution, official summary, nor textbooks help you training your intuition. Find your way of treating with the problems. I've advanced to DCJ2017 Finals with my intuitive answer of E-large.
> That's why I keep saying becoming a red coder is the start of competitive programming.
> (P.S. it's often said that a lot of CF hard problems are typical with demanding implementation. If it's truly so, assume the goal as "becoming 3200 in AtCoder" or "advancing GCJ finals" instead. If you're Cuban or Quebecois etc, then I'm sorry for not giving good alternatives to you.)

2020/06/08

题目
大意：交互题，给定，要猜一个长度为n的01串，每次可以问一个长度不超过n/2+1的串是否是它的子序列，最多问1023次。
解法：数学归纳法的显然题。首先log次询问求出0和1的个数。然后先确定第1位；再假设前k位已确定，求第k+1位。