负担集训-Test12
负担集训-Test14(多校联合训练-5)

负担集训-Test13

YYY posted @ 2017年8月07日 20:30 in ACM with tags 懒得写了 , 153 阅读
------------------------------------------------------
惨啊,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的。

------------------------------------------------------

------------------------------------------------------

LOL

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter