杂题

联赛倒计时 [UPD 05.11.17] 杂题

联赛倒计时 [UPD 05.11.17]

30.10.17 今天没有考试,从早上开始一直在刷OJ上的各种杂题,把DP的可做题搞掉后继续去搞达哥的最后一波题解。 bzoj2004 [Hnoi2010]Bus 公交线路 p的范围很小,提示我们可以考虑状压。n的范围很大,提示我们可以矩阵优化。 因为每个公交车都是一样的,所以我们可以直接压成二进制···
241017模拟 杂题

241017模拟

好几天不更了= = T1 Star Way To Heaven 一眼二分,再看看就可以发现直接找上下边界即可。但是考试时不仅被卡了常数,还被爆了int。。。正确的方法是并查集合并,每次合并后检查合法情况,可以剪枝。 [crayon-5a5f4ec733ddb087043826/]   T2···
151017模拟 杂题

151017模拟

今天考的题比较简单,一个半小时AK了。但是后来机房突然停电.....幸好代码早早就交了= = T1 表达式 感觉好久没做这种类型的题了,题目给的信息非常准确严谨。首先空格不能直接吃掉,而是应该当作一个正常字符来处理。然后就可以把所有连续的数所在区间设为合法区间,最后DP一下即可。 [crayon-5···
141017模拟 杂题

141017模拟

T2 喝喝喝 思路非常好,就是先把取模的式子变形,化为a[x]-mod=k*a[y],这样可以知道,满足要求的数对就是前面的数减去mod后是后面的数的倍数的数字。那么,我们有两种思路,一是从前往后枚举,每次更新以当前点为右端点,最左能到达哪里,但是这样需要枚举当前数的倍数,如果不加优化或者分块的话时···
BZOJ1033 [ZJOI2008]杀蚂蚁antbuster 大模拟 杂题

BZOJ1033 [ZJOI2008]杀蚂蚁antbuster 大模拟

超级超级恶心!!!(虽然还没有猪国杀复杂,我是写了一半猪国杀然后开坑来做这个的),没有太多可说的,也没有复杂的算法,就是纯粹的模拟,各种基本操作揉到一块,就让我陷入了无尽的调试。。。 说一说大致思路:首先确定程序的大体框架,确定基本的数据结构。这道题虽然使用链表会比较麻烦,但是时间上会有所保证。接着···
101017模拟 杂题

101017模拟

虽然今天考试又翻车了(暴力分都没拿全),但是这套题还是非常值得总结的。 T1 小奇挖矿2 考试的时候注意到+4+7很奇怪,也试着凑了几个数,但是因为写错了没找到规律,乖乖打了暴力(然而处理重复没搞好)。实际上,如果认真把4和7能凑出来的数写出来的话,可以发现,4和7可以凑出{4,7,8,11,12,···
081017模拟 杂题

081017模拟

T1 Blue 这道题结论性非常强,考试的时候想到一种可行的贪心策略是每次选择最远的石头跳,但是没去仔细想就去搞后面了,结果最后打了个暴力查找,50分。正解可以使用多种数据结构来找下一个位置,将O(n)变成O(logn),比如用set然后每次删除,或者是二分右端点+线段树(单点修改+区间最小值查询)···
071017模拟 杂题

071017模拟

T1 排队(line) 想清楚了非常水,十几行搞定。其实就是最后所有男生都会到最后,而越靠后的男生越早到达,所以最晚的永远是最前面的男生,我们关注的也只是最前面的男生。一个男生到达后面的最早时间是后面女生的数量,且中途可能被后面相邻的男生卡住。但是,相邻两男之间的女生可以“缓冲”掉一定的“浪费时间”···
051017模拟 string&&big 杂题

051017模拟 string&&big

这套题又是画风不太正常的那种= =,到现在还差第二道没改过去,还没想明白。   string(T1) 这道题和HEOI2016那道排序有点相似,都是在字符集较小的情况下,通过线段树统计区间内各个字符出现次数,然后直接区间修改做到排序,思路非常简单,代码实现也不难。但是,分析一下复杂度,应该···
BZOJ3712 [PA2014]Fiolki 重构树+并查集 杂题

BZOJ3712 [PA2014]Fiolki 重构树+并查集

又是一道思路非常好的题目。考虑到每个反应最多只进行一次,每个瓶子也只能往外倒一次,我们可以把每个瓶子想成一棵树。初始时,所有节点都是根节点,构成森林,每操作一次,就将两个瓶子表示的节点合并起来,可以用并查集维护,合并后的点重新标号,成为原来两个点的父节点,从下往上建树。注意到当两个物质能发生反应时,···