- 博客(510)
- 资源 (2)
- 收藏
- 关注
原创 【 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
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人