实话镇楼本来想昨天写的，但开了局文明几个小时就过去了OI花了很多时间去搞，自以为还是学的挺认真的，但结果并不是那么如人意。CSP2019退役记现在想来其实颓的也不少，有些东西自以为不会考就没怎么研究，考的难自然就容易出锅；还有所谓“想赢就会输”，考前心理负担还是挺大的，总觉得想把之前失去的补回来。颓了几周后，我感觉自己大概还是不想彻底放弃。以后每周五下午还是去机房做两道题，CF还是尽量打打，...
由于Pjax与自带反垃圾保护的冲突，请在 设置->评论 中关闭反垃圾保护！ 否则可能无法评论。推荐使用插件smartspamGithub镜像（更快下载）示例站点Edge[edʒ]n.边缘；棱；角；锋Feature一款棱角分明的主题。Pjax 支持。代码高亮、文章目录支持。使用下载（或clone）后将文件夹命名为 Typecho-Theme-Edge ，然后放入 /usr/themes/...
今天是2019.12.15，心情还是不好，但已经过去一个月了，感觉还是应该把这玩意了结了。先摆分数：$$95+60+0+32+12+55=254$$菜的真实。游记Day1自信满满去考，自信满满出来，回家去自测发现T1T2都爆了，T2甚至连个保底分都没有。大概说下我T2出的锅吧：我的做法是用个数组模拟栈，在退到上一层时计算贡献，但我忘记了清空最后一层。当时看出来了大样例3是链，但感觉大样例2挺...
最近都是各种校内模拟赛，好久没写题解了。题意题解用线段树维护列，每个线段树记录这个区间内：最左边一列每个方块所属的集合最右边所属的集合四联通颜色块个数，即答案合并时对中间两列遍历所有行，如果两块颜色相同就用并查集把两个集合给合并起来，并将答案 $-1$ 。#include<bits/stdc++.h>
#define fi first
#define se second
#def...
题意挺简单的自己去看吧~题解因为有开闭两种区间，所以对每两个数中间也建一个点，总的点数即为 $2N$ 。维护一个长度为 $2N$ 的 $0/1$ 序列，支持区间覆盖，区间翻转操作。令 $T=[l,r]$ （$l,r$ 为新编的点）：U T：覆盖 $[l,r]$ 为 $1$I T：覆盖 $[0,l-1],[r+1,2N]$ 为 $0$D T：覆盖 $[l,r]$ 为 $0$C T：翻转整个区间...
题意题解每个数有 $3$ 种状态，直接搜索 $O(3^{26})$ 会爆，但折半搜索的 $O(2\times 3^{13})$ 就可以。注意到第一次搜索需要保存两个值 $cnt$ 和 $sum$ ，表示用阶乘的次数以及当前的数。可以用 unordered map 来维护，把第一个值开在外面。#include<bits/stdc++.h>
#define ll long long
...
题意给出一个 $n(\le 1000)$ 点 $m(\le 10^6)$ 边的有向图，求 $1\rightarrow n$ 的边权积最小的路径。题解因为需要松弛所以不能取模，如果直接乘起来又会爆。不过 $\log(a\times b)=\log(a)+\log(b)$ ，可以改为求边权为 $\log(w)$ 的最短路。在最短路过程中记录 $y$ 的上一个点 $lst[v]$ 以及两点之间的真...
题意有 $n(\le 5\times 10^5)$ 个四维空间点，坐标为 $(x_i,y_i,z_i,q_i)$ 。要求点对 $(i,j)$ 满足：$$x_i-x_j=y_i-y_j=z_i-z_j=q_i-q_j$$求 $j-i$ 的最小值及 $i+j$ 的最大值。题解题意即要求两点的 $x-y,y-z,z-q$ 相等。直接拿个 map 就能水过去。#include<bits/std...
2019-10-30 题解
提高+/省选-
题意有一个长为 $n(\le 10000)$ ，高为 $m(\le 1000)$ 的游戏场景。玩Flappy Bird，在位置 $i$ 点一下会上升 $x_i$ ，否则会下降 $y_i$ ，手速极快每秒可以点多下。有 $k$ 个位置有管道，其中空隙的范围为 $[L_i,H_i]$ 。可以从位置 $0$ 的任意高度出发，问至少要点几次才能到位置 $n$ ？如果无法到达，最多能跨过多少个管道？题...
题意给一个 $n(\le 5\times 10^5)$ 点 $m(\le 5\times 10^5)$ 边的有向无环图，求一个拓扑序满足拓扑序的前缀最大值最少/最多。题解最大的情况比较容易想到，从当前能走的点中选编号最小的点即可，用堆维护。至于最小的情况，直接选最大的点拓展会喜提46分。很容易想到这种方法的问题所在，如果很小的一个点连着一个很大的点，把这两个都选了有可能最优。考虑对贪心进行优...
题意有一棵 $n(\le 100004)$ 个点的树，从根节点出发。节点 $x$ 能放梅花，仅当其所有子节点 $y$ 上都放了 $w_y$ 朵梅花。对于 $\forall i\in [1,n]$ ，如果要在 $i$ 上放 $w_i$ 朵梅花，则至少需要在过程中准备多少梅花？题解可以发现对于节点 $x$ ，一定是按某种顺序遍历所有子节点 $y$ 放上梅花，而且不同的顺序得到的答案也不相同。考虑...
省略的程序头：#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define ha 1000000007
#define ui unsigned int
#define pii pair<int,int>
#defi...
题意有 $n(\le 100)$ 个软件可以安装，每个软件会占 $w_i$ 的磁盘空间，价值为 $v_i$ ，每个软件都有至多一个依赖。剩余磁盘空间为 $m(\le 500)$ ，问安装软件的价值最大值。题解环上的软件必须要全装才有收益，所以先缩点。然后把 $0$ 看成树根，并将它与无依赖的软件连边。剩下的就是标准的树形背包问题，只是注意当前枚举的软件一定会安装，否则无法安装子树上的软件。#...
语文阅读题题意有 $n(\le 4000)$ 对夫妻，还有 $m(\le 20000)$ 对此前的交往关系（都是在这 $2n$ 个人之间）。如果某对夫妻吵架，那么他们都会找此前交往的人复合，然后又一对夫妻被拆散……如果某对夫妻吵架，发生上述过程后可以组成新的婚姻关系，那么就称该婚姻不稳定；否则稳定。询问每个婚姻是否为稳定婚姻。题解先考虑吵架后丈夫的行为，可以发现关系的传递是 男 $\righ...
题意给出一个长度为 $n(\le 2\times 10^6)$ 的数列，有 $m(\le 2\times 10^6)$ 次询问，求 $[l,r]$ 之间有多少个出现了两次及以上的数。题解和 HH的项链 差不多，只是要求出现两次。所以把树状数组维护的值修改一下，变成只有出现了两次才更新节点的权值。先预处理出每种数字下一次和下下次出现的位置 $nxt[]$ 和 $nxt2[]$，并把所有数字出现...
A.Yet Another Dividing into Teams略B.Books Exchange题意题解把关系连边后，可以发现一定是形成若干个环，那么 $O(n)$ 搜索一遍即可。#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read()
{
char ch...
当时比赛的时候没做出来这题，做了 洛谷3586 才知道这题的做法。题意有 $N(\le 3\times 10^5)$ 张卡，卡上有数字 $A_i(\le n)$ 。$\forall k$ ，问：每次取 $k$ 张数字互不相同的卡，能取多少次。题解记录每个数字出现的次数为 $s_i$ ，问题就转化为：每次选 $k$ 个正数 $-1$ ，最多操作多少次。然后就可以直接用 洛谷3586 的结论了（...