负担集训-Test13
_THIS_IS_START_OF_ARTICLE_
------------------------------------------------------
_THIS_IS_END_OF_ARTICLE_
------------------------------------------------------
惨啊，3h后就没动过了...
------------------------------------------------------
B:
题意就是说，给你两个连分数$a$,$b$，比较这两个数的大小
为了表示连分数，每次给出一个数组$c[0...n]$，表示$c[0]+{1 \over c[1] + {1 \over c[2] + ...}}$
$n\leq 10^5，c[i]\leq 10^9$
我们发现一个连分数的大小和偶数位置的数的值成正相关，和奇数位置的值成负相关，且越靠前的数影响越大，且一个数组后面可以视为有无数个$+\infty $，所以我们只需要找到$a$和$b$第一个不相同的位置，比较他们的大小，再看一下这个位置的奇偶性就可以了
------------------------------------------------------
C:
说是给你一个无向图，保证每个点的出度$\leq 5$，现在请用三种颜色给每个点染色，使得每个点最多有一个颜色和自己相同的相邻的点。
图的点数$\leq 10^5$
首先我们发现最小的无解的情况是大小为7的完全图，而这个图是不存在这种情况的，所以他一定有解。
然后就有一种暴力，就是先随便染色，然后每次找到一个矛盾的点，改一改。
但是这样太慢了，于是优化一下，维护一个队列，每次我们改了一个点后，会受影响的一定只有他周围的那些点，于是每次我们改了一个点之后，就把他周围的所有点入队。当然这样会把一些不需要改的点也入队，没关系，当我们发现一个点不需要改时就不干任何事。
------------------------------------------------------
D:
给出数组$f$,$g$求$h(x)=\sum_{i\ or\ j = x}f(i)\times g(j)$
$f$,$g$的长度都小于等于$2^{16}$
就是个裸的FWT。
------------------------------------------------------
记录：
一开始我们看到有队伍一来就交了一发B，于是就推测B能写，然后想了一想就会写了，于是写写写，然后yyy这sb交错文件了，于是就wa了一发，然后gmr又跳出来说A他会写了，然后就写写写，然后yyy跟lzj就跑去看D、F，然后发现D好像说是个模板题啊，然后就让gmr让开yyy要写D，然后写写写，然后果断wa了，然后gmr又跑回去写A，然后过了一会儿A A了，过了一会儿yyy发现了D的错误，然后就把D A了，然后ljz说他会写F了，然后写写写，然后就A了，然后gmr和ljz讨论了很久，好像就会写H了，然后写写写，然后就A了，然后gmr说，“我好像会做G了”，然后就写写写，然后就WAWAWA，然后我们就说，要不搞一搞J把，然后ljz发现了一些结论，然后yyy就觉得可以乱搞一下，然后写写写，然后就要么是WA，要么是T，然后大家就弃疗了。然后ljz觉得C这么多人过了肯定是个sb题，然后我们就集体想C，然后就没想出来。
总结：
这把感觉一直卡住的C就是个乱搞的，我们一直在搞J，但是对于这种图论题总觉得很畏惧，所以没敢去搞C，感觉在一筹莫展的时候要是敢去乱搞的话说不定还是能A的。
------------------------------------------------------
------------------------------------------------------
评论 (0)
