合集

之前因为极验验证码被墙掉了，博客园登不上去，于是现在得把一堆东西补一下……

咕咕咕……

20190908

过程

作者不要×

T1提示

这是水题,快A掉它 (QaQ) !

T2提示

题目并不难 (QwQ) 。

T3提示

读到这里你应该一道题都还没写吧 ..... 快去写题目! (QeQ)

这××是人话？

T1

像个最长下降子序列。

T2

树，打个暴力

T3

阴阳师……呵呵（我××是不会入这个坑的）

好像很难的样子。

能骗点分

T1

在远古时代,量子科技实验室？？？这××是人话？

应该可以dp，$N^2$

线性dp？？

1.如果$p$可以与$q$同时被摧毁($p<q$)，那么$A_p>B_q$,

  如果$q$可以与$t$同时被摧毁($q<t$)，那么$A_q>B_t$,

  那么只有在$A_p>B_t$时才可以被转移。好复杂QAQ

  好像转着转着就变阶乘复杂度了。

2.或者考虑建边。合法的就建，最后跑拓扑。$N^2$

  然后发现好像不是那么回事。

  可以直接考虑 入度一类的。试试ing

仿佛崩掉了……

正在乱搞。

估计得分：0

（我觉得我能猜对qwq）

水题个××

T2

暴力……

每个节点搞

$N^2$过100000.你值得拥有

不难个××。

5 5
1 2 2 3 3
1 1 3 3
1 0
1 3
1 2
2 1
3 2

 咕分：30

T3

没错作者你对了。

我××一个题也没做。

而且你是不是诅咒我？？

ad dead e^^^^

 这××是什么？？

维护前后缀，然后用枚举字符断点位置解决

不过是有误的，因为我们要保证字符数要变化。

正在保证……

$O(L\,?\,N)$

估计分：10

总分：40

太好了。又得了个省三。（欢天喜地）

（欢你××）奔着0分去了。

结果

20190908 - Night

经过

这是什么玩意……

可能是晚饭次的太饱了，为啥困的一批呢？？

T1

没想法，有点像那个钉子什么的题。

T2

只会打暴力

T3

好像有个类似的题，但是不记得了。

教练员说的对，之前留的坑，考试会一个个填回来。

数学差太多了……………

T1

要不……打个表？

$4000×4000$（坏笑

就是打欧拉函数的表也可行。

××我$gedit$差点报废。$18K$

先$N^2$求出欧拉函数，$16000000$

然后求T个ans

如果可以$\Theta(1)$求，A了

如果要$\Theta(N)+40000000$ T了。

可以设一个$dp$柿子，我们每次先$N^2$处理出所有$ans$，然后$\Theta(1)$回答

测了一下M掉了。

于是现在就只能改int然后运算时强转了

用uint卡mod上限。

然后有一个呵呵的问题：有一个phi的部分值没办法搞，于是可能要嵌套在求phi的过程中了

这题空间限制要杀人啊？

好像卡过去了……试试看。

4
2 2
7 10
23 34
100 100

出锅了，不对。

交个暴力就走吧。

这××连暴力都写不对。要爆零了QAQ

×，我今晚上就爆给泥萌看。

估计得分：$0×0.0+0-0^0 and 0 or 0 \times 0 \ll 0 \gg 0$

××程序太NB，差点把我Firefox搞爆，它白了……白了……白了……

不过后来就好了

结果

20190910

经过

T1

DAG上DP？？？

有可能不联通？？？

考虑一个比较氢气的思路。

好像就是siz(搜索树)-出度

我风了？

T2

没看懂题，但是有Dp的味道。

T3

明显是数学题，我在想ooo会不会拿Python去水这个题=。=

$10^{1000}$

想打表

T1

知道考什么了，如何求出DAG上的所有siz

先打个$N^2$的hiahia

可以跑$tuop$

暴力对了QAQ

上辈子造了多少镍让我的正解复杂到这种狗地步……Q×Q，根本改不过来……

仿佛回忆起了学长讲的一道题，

好像就是求所有点可到的点数……但是不会呃啊。

T2

好像不是Dp，二分图？？？？

好像就是Dp

但是不会啊(°Д°)

如何写暴力……

贪心？？(｡♥‿♥｡)

所以先存下所有的元件，

然后sort（二元组）

然后一边输入需求，一边lower_bound？？

可以证明（感性理解）需求与现有的差距越小越优？？

可以搞个事，拿sort排好一维另一维线段树？？

想一下：

如果有一个差距较小的a，大的b

现在有一个需求：c(c<a<b)

于是我们一定会用a去满足c而不会用b

分情况如下：

如果用a满足c

下面又来了一个d

1.a<d<b

用b去满足d，OK

2.d<a

用b去满足d，OK

3.d>b

无法满足。并且与满足的顺序无关，用a也满足不了。

如果用b满足c

1.a<d<b

因为我们用b满足了c所以剩下a无法满足d（与顺序有关）

2.d<a

用a去满足d，OK

3.d>b

无法满足

所以综上我们需要找一个差距较小的，使用 lower_bound 

那么我们可以用长度先排序，

然后长度一样的用l，这样就可以先去排除长度不同的了～～

因为排序规则一样仿佛可以减少一些冗余搜索

一次次让步，时间复杂度一步步上升

然后是多测的1,2,7轮流爆，我××和大样例有仇。

先咕了，

T3

没时间了，水！

结果

20190914

经过

有点不爽……

T1

像数学题

T2

像数据题

T3

像~~毒瘤~~Dp题

Upd:根本说不清T2T3是个什么玩意

T1

这仿佛是秦九韶算法……

但是也没个×用。

好像可以逆用秦九韶……

倍增枚举$S \times b^x$

然后减，再倍增枚举$k\times a \times b^y$

至于秦九韶算法，ta就是个$a+b$  qwq

$$\begin{array}{rl}ans&=a_0 + a_1 \times x^1 + a_2 \times x^2 + \cdots + a_n \times x^n\\   &=a_0 + x^1 \times(a_1 + a_2 \times x^1 + \cdots + a_n \times x^{n-1})\\   &\vdots\\   &=a_0 + x^1 \times(a_1+ \cdots +(a_{n-1}+a_n \underbrace{\times x)\times x)\cdots \times x)}_{\text{n times}} \end{array}$$

所以逆用就是展开多项式

试试叭……

我×

我也没法子对拍诶……

但是还是拍了，然后测了极限数据

检查出两个错呼呼。

这个数据范围真容易爆龙龙。

复杂度$\Theta(\log^2 N)$

T2

只会$\Theta(N^P)$的电风扇（DFS）

或者$\Theta(N*P^2)$的大盘

性质：

1.每次的更新都是固定的，

   因为乘积的原因。

   k如果从p更新过来，那么每一位的k都会从p更新过来

T3

我想，加热器是类似电热毯那样的东西，而并非烤炉=。=

仿佛并不会把植物烤死……

得把热量需求高的先提起来，

然后用特殊加热器猛升。

但对于t>n的时候不一定最优啊……

可以想方设法算出一个

可以等同于一起升的并区间（但是仿佛要处理交集）

如果比t要优，那么可以把t更新掉

类似，可以用大区间去覆盖小区间。

不过都现在了，不妨搞个电风扇

发现一个××问题，有时候 -O0 比 -Ofast 都快=。=

部分内容注释：

电风扇-DFS

蝙蝠屎-BFS

大盘-DP

龙龙-long long

结果

转载于:.html