- 博客(510)
- 资源 (2)
- 收藏
- 关注
RSS订阅
原创 【 AtCoder - abc311_e】 Defect-free Squares【二分】
看到题面一个n3的做法显然已经跳出来了，只需要一个二维前缀和统计一下看是不是全为0就行（有洞设为1）。但是复杂度不达标，至少要Onmlogn，可以考虑压一维。发现他都是正方形，对于左上角相同的正方形，他是有包含关系的，所以只用找最大的一个正方形就可以了，又考虑到我们可以用前缀和O1判断是否最大，明显有二分的特点。于是二分能扩展多少个点，找到最大的正方形统计答案。
2023-08-22 15:30:34
117
原创 【AtCoder - abc311_d】Grid Ice Floor【DFS】
显然搜索题，但是范围是两百，不能每个点都递归，参照之前的题，会出现一些能递归的关键点。我们先对于每个点上下左右走到头，求出每个点对应的下一个关键点，然后从起点开始递归，对于每个点记录有没有“走过”，和有没有递归过，然后到达每个点都去找关键点就行。
2023-08-22 15:14:02
125
原创 【AtCoder - abc310_e】NAND repeatedly【找规律】
看完题面终于知道NAND是什么意思（not and），想到这个应该是线性的时间复杂度。进一步看，这个运算有个规律，对于任意一个区间，只要结尾是0，那运算结果就是1，对于连续的1，结果0,1交替出现。考虑对于每个位置为结尾的区间统计答案，先把所有单点为1的加进答案，然后找到所有结尾为0的位置i，然后答案加上i−1。对于为1的区间，发现答案交替的顺序与结尾连续1的个数有关，这个预处理是很容易的，以i结尾的区间连续1的个数记为si。
2023-08-22 15:01:36
79
原创 【AtCoder - abc315_e】Prerequisites【拓扑，BFS】
一眼拓扑，但是写到一半发现又问题，注意到从1开始，每个出边所对应的书都必须读，所以改为从1开始BFS，记录所有要读的书，然后按照拓扑序跑一边碰到要读的就输出，保证可以符合顺序上的要求。但是实际上搜一遍就可以了，直接DFS，从1开始对于每个最先搜完的节点输出就行，也就是逆DFS序（posdfn），等同于拓扑序。
2023-08-21 16:57:46
52
原创 【CF1846E】Rudolf and Snowflakes【数学】
简单的version可以直接暴力枚举k判断。难的version范围到了1018，所以考虑更加数学的方法。数据范围是n<=1e18,k>1雪花中点的个数是1kk2k3...kp，根据数据范围，显然p的范围是p<=62关键在于缩小k的范围，我们考虑从k的几次方开始枚举，发现如下事实：如果我们直接存入最小的值是1kk2，那么k的范围是k<1e9,此时时间复杂度是O1e9∗62如果我们直接存入最小的值是1kk2k3。
2023-08-21 16:37:38
45
原创 【hdu3183】A Magic Lamp【暴力】
这种题之前貌似做过，显然方案就是每次找到第一个“峰顶”，并删去，反复找k次就可以了。这道题主要是一些细节，删去一个数之后要更新链表，前导0要判断好，详见代码。
2023-08-21 15:43:26
30
原创 【HDU1540】Tunnel Warfare【树状数组】
一看跟区间有关，线段树应该可以做，但是不想写线段树，于是考虑树状数组行不行。因为这个前面后面都要考虑，所以就用两个树状数组。在一次摧毁之后，直接通过更新这个位置到以后的贡献，前缀和之后后面的全都会改变，修复时同理，记录摧毁顺序用个stack就可以。
2023-08-21 15:37:50
34
原创 【CF1671E】Preorder【计数】
赛时已经想到了子树*2的方法，但是没想到怎么去掉重复的东西，实际上已经很接近答案了。在子树本质相同的时候，通过交换是没法*2的，所以就记录字典序，比较最小字典序是否相同，这个可以用DFS实现。
2023-08-21 15:33:06
28
原创 【CF734E】Anton and Tree【树的直径】
一开始理解错题意了，直接暴力判断连通块个数，我就说怎么这么简单。。。其实这个颜色的连通块是会动态变化的，染色之后可能会有合并连通块的发生。问题好像瞬间复杂了起来。但是在染色的时候连通块一定会一起被染色，于是就相当于一个点了，我们也用DFS去缩成一个点，不难发现，新的一棵树上，都是黑白点交替出现的。想到这里可能觉得跟树的深度有关，但是换根深度也会变化。实际上答案就是(树的直径+1)/2，从直径的中点开始染色就行，只要想到直径方案是显然的。
2023-08-19 21:02:35
58
原创 【CF1763C】Another Array Problem【数学，思维】
发现操作一次就会将区间元素变得一样，操作两次就会全部变成0，那么就想怎么把全部都变成最大的那个数。显然的方案：将它左右的全部变成0，然后左右包含上它一起变成最大。但如果只有四个数呢？那也很好构造方案：将一边的两个变成0，然后带上它一起变成最大，然后它跟左边的一个一起变成0，最后带上右边已经变成最大的那个就行了。结论：n>3的时候答案就是最大的数*n。考虑暴力解决n<=3的情况：n=2时直接判断的大小关系n=3时只有三种情况，每个判断一下就行。关键在于，然后剩下的显然。
2023-08-19 20:23:47
39
原创 【hdu2819】Swap【二分图匹配】
说：既然男女能够做匹配，那么花和草也能，行和列也能。以后看到这种黑白多少往二分图想想。。。同一行的两个1，不论如何行交换或列交换，都依然处于同一行。要让主对角线全是1，首先1的总个数要>=n，其次所有行都要出现1，所有列都要出现1。如果某个格子ij是1，则从结点i连边到结点j，构造二分图。求二分图最大匹配，检查最大匹配是否等于n，如果是，输出“Yes”，否则输出“No”。本题用二分图最大匹配的正确性：任意位置的“1”都是可以移动到主对角线上任意位置的。
2023-08-19 20:13:21
50
原创 【CF1747D】Yet Another Problem【位运算，思维】
题面有两个关键词：“异或”和“奇数”。要按位来考虑吗？还是利用异或操作的特性？为什么要求操作区间的长度是“奇数”？1次操作后区间中某一段变成了相同的数字，那么再对它们异或一次，不就变成全0（当长度为偶数时）或者保持不变（当长度为奇数）吗？原来当R−L1和r−l1（两个区间的长度）为偶数的时候，我们只需要2次操作就可以将所有数字变成0。如果所有数字本身异或结果就是0，那就只需要1次操作。如果所有数字本身是0，那就需要0次操作。题目设置区间长度为奇数，必然有更多含义。
2023-08-19 19:59:04
41
原创 【洛谷P3177】树上染色【树形DP(背包)】
有一棵点数为n的树，树边有边权。给你一个在0∼n之内的正整数k，你要在这棵树中选择k个点，将其染成黑色，并将其他的n−k个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的收益。问收益最大值是多少。
2023-08-18 14:39:26
177
原创 【CF1740C】Bricks and Bags【暴力】
赛时想简单了。。先排序，蹲坑想到的做法是一定把最后或者第一个放中间，然后一定有一个最近的和一个极差。但是在赛后手摸数据的时候发现不对，万一最大那个往前走一个相距很近的点，但是离那个数距离最近的又很远，极差又不会有什么变化，那不就不成立了吗？于是分类再细一点，把绝对值符号拆开成三种情况（大小关系），一个一个枚举到底哪个才作为中间的量，确定中间的量之后也就可以根据一开始“极差”的思想算出答案，最后取最大值就可以了。
2023-08-18 08:31:02
33
原创 【Atcoder abc246_f】Typewriter【状态压缩】【组合数学，容斥】
计数题，DP状态都存不下，考虑组合数学。先用单个字符串手摸一下，发现一个长度为k的字符串打出L个字符最多有kL种。答案显然不可能是简单相加。于是我又想到了去重，但是不是一个字符串直接去重肯定是不行。那么数学方法又有什么能达到“求并集，去重”的效果呢？n个集合的容斥原理公式参考百度就非常清楚了，发现是偶数个集合的交集前面就是减号，反之则为加号。注意到n的值特别小，仿佛跟状压DP的一样，于是考虑存储所有字母存在性的状态，一共226完全可以枚举和存储。
2023-08-17 20:28:58
56
原创 【poj1195】手机【树状数组】
一眼二维树状数组，维护单点修改矩阵求和。其实还有区间修改区间求和and矩阵修改矩阵求和。那几种的处理方法是维护多个数组，记录不同量的出现次数。
2023-08-15 11:35:46
33
原创 【AtCoder abc308_e】MEX【计算】
第一眼看上去又是n3枚举？？不太可能。仔细一看这个答案只能是0,1,2,3。但是到这里赛时还是没分析出什么有用的性质。想到可以记录每个E前面M后面X的个数，但是个数貌似没什么用。统计个数实际上复杂度已经达标了，考虑能不能记录多一点信息，于是就想到了正解：对于每个E把前面权值为0,1,2的M，后面权值为0,1,2的X全部记录，可以线性时间统计答案，只需要判断各种组合情况然后对于每个E暴力计算就行，要不重不漏。
2023-08-15 11:32:24
60
原创 【CF1789D】Serval and Shift-Shift-Shift【构造】
没有要求最小化步数，也就是与DP没多大关系，只需要考虑如何操作能一定在有限步数里面完成调整，这是构造题的一般思路。看到是位运算，就从位的角度分析，看能不能一定有策略每一步都接近b。想到这里就很接近了，也就是用逐位调整的思想，看能不能每次改变至少确定一位，并且之后不会受到后面的影响。最后考虑无解的情况。我们先考虑如何将a与b的第一个1对齐。先找到b的第一个1，然后用这个位置往前更新，每找到a的一个1（证明突出来了），就用a的最后一个1去异或它，因为后面全是0了，所以对于已经更新过的不会有任何影响。
2023-08-15 09:52:48
34
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人