- 博客(119)
- 收藏
- 关注
RSS订阅原创 GukiZ hates Boxes CodeForces - 551C 思维 + 二分
link很明显的提示用二分来解决问题。证明单调性: 因为时间更长完成任务的可能性越大，时间越短完成任务可能性越小。让后讲一下check函数怎么来写。考虑每个人所进行的操作。仔细分析一下发现是从后面搬箱子是最优的。那么我们直接找到最后一个不为零的位置，让后依次往前模拟，令每个人最多走 mid 秒，贪心的搬箱子。最后检查一下是否全 0 即可。//#pragma GCC optimize(2)#include<cstdio>#include<iostream>#inclu.
2020-12-14 00:26:03
287
3
原创 CF819B Mister B and PR Shifts 思维 + 模拟
link思路： 涉及绝对值，我们分为两类数来看，第一类是 pi−i>0p_i-i>0pi−i>0 第二类是 pi−i<=0p_i-i<=0pi−i<=0 。记zcnt为第一类个数，ztot为第一类的贡献。fcnt为第二类个数，ftot为第二类的贡献。先不考虑边界情况，对于右移一位 i 会增加1，第一类数 ztot - zcnt，第二类数 ftot + fcnt。当然随着移动会有第一类数变成第二类数的情况，我们用 te 数组记录一下什么时候会改变，让后减去对应的
2020-12-02 16:30:56
202
原创 CF351E Jeff and Permutation 思维
link题意：给定一个数组，可以选择将其中元素取反，问逆序对最多是多少。一个比较有意思的题。在读入的时候 a 都取正数。我们考虑其中的最大值 a [ i ](1)如果 a [ i ] 为正的时候，前面的数不管是否取反都比他小，不会产生逆序对。后面的数不管是否取反也都比他小，会产生 n - i + 1 个逆序对。(2)如果 a [ i ] 取负的时候，前面的数不管是否取反都比他大，产生 i - 1 个逆序对。后面的数不管是否取反也都比他大，不产生逆序对。我们发现除了最大值之外的所有数是否取反与
2020-12-02 16:20:01
222
2
原创 牛客 Laptop 二维偏序
link也是一个裸的二维偏序，但是要求有多少个被完虐，那么只需要把 x 和 y 反着排序就好啦。//#pragma GCC optimize(2)#include<cstdio>#include<iostream>#include<string>#include<cstring>#include<map>#include<cmath>#include<cctype>#include<vector&
2020-11-30 16:11:59
214
2
原创 CF1311F Moving Points 二维偏序
link题意比较简单，容易提取出来对于 j<ij<ij<i 并且 xj<xix_j<x_ixj<xi 如果 vj<=viv_j<=v_ivj<=vi 的话，那么他们最小距离即为初始距离之差，否则最小距离为0。这容易启发我们用二维偏序来做:以 x 为横坐标， v 为纵坐标。按照 v 从小到大的顺序添加 x ， 每次用树状数组求一下贡献就好啦。因为要求距离，所以我们维护一个统计数量的树状数组和一个统计距离的树状数组即可。//#pragma
2020-11-30 15:44:43
133
原创 CodeForces - 698B Fix a Tree 并查集 + 思维
link题意：给定一些父子关系，要求更改其中一些关系后使其成为一棵树，更改的次数尽可能少。我们可以从头开始用并查集合并不在同一集合两个点，这个时候两个集合一定是可以合并的，自己做的时候傻了，以为有可能让其中一个联通块上有父节点的点连到另一个连通块上。所以当当前点不能合并的时候，记录一下当前的 i ，最后我们就成功的维护了几个联通块，现在我们需要把这些联通块合并起来就可以得到一个树了。我们记录的 i 现在就派上用场了，对于 fa[ i ] = i 的点，我们可以把它作为老大，让其他连通块的 i 连到这个点
2020-11-29 10:47:48
179
4
原创 Educational Codeforces Round 4 The Union of k-Segments 离散化 + 差分
link( 又是一个被刘成哥秒的题/(ㄒoㄒ)/~~ )题意(依旧白嫖) ：给你 n 条线段，再给你一个整数 k。如果一个点至少被 k 条线段覆盖，那么这个点是符合条件的，如果符合条件的点可以不间断的连起来组成一条条的线段（注：线段中间是不能有断开的），并且要求符合条件的线段数越少越好。 （注：只有一点也可以）。 换句话说就是让你将覆盖 k 次及 k 次以上所有的区间都找出来，如果两个区间能够合并，那么输出他们合并的结果，例如：k=1,区间[0-3],[3-5]可以合并成[0-5]。如果区间大小很小
2020-11-26 10:47:08
161
4
原创 CodeForces - 487B Strip dp + 线段树
link题意：给定序列n，让你尽可能少的分成几段，每段都需要满足以下要求：(1) 每段长度必须 >= l(2) 每段 最大值 - 最小值 <= s看出来是dp后，转移方程也比较明显了dp[i]=Min(dp[i],dp[j]+1)dp[i]=Min(dp[i],dp[j]+1)dp[i]=Min(dp[i],dp[j]+1)其中 [j+1,i][j+1,i][j+1,i]这段区间必须是合法的，直接转移的话是O(N2)O(N^2)O(N2)的复杂度。考虑优化，可以发现我们要求的 j
2020-11-26 10:32:55
150
3
原创 E. Greedy Shopping 线段树
link比较裸的线段树了吧，不过没写出来还是有点思路不清楚，对线段树理解还是不够。对于操作1，可以看成区间覆盖，维护一个区间最大值和最小值，最小值用来剪枝，让后大于最大值的时候覆盖掉即可。对于操作2，当当前区间sum<=x的时候，说明可以直接减去。否则的话先递归左区间，让后递归右区间，依次处理即可。实现起来就so easy了。//#pragma GCC optimize(2)#include<cstdio>#include<iostream>#include&l
2020-11-18 14:23:43
1765
10
原创 D. Extreme Subtraction 差分
传送门(这个题感觉就是进阶指南的原题，但是我还是wa了好几发)题意：给定一个数组，让后可以选择前k个或者后k个数，将其减少1，问最终能否将其变成全0。一开始用假算法把自己骗了，今天走路的时候秃然想起来用差分就可以秒了这个题。可以构造出差分数组，那么两个操作就转换成了(1) 在第一个位置-1，让后在[2,n+1]选择一个位置+1。(2) 在[1,n]选择一个位置-1,让后在n+1的位置+1。对于差分之后正数的位置我们不需要考虑，因为操作(2)就可以解决。对于负数的位置，只能由第一个位置来消去，那么
2020-11-04 16:11:02
1318
12
原创 Gym - 273287 G Swapping Places 拓扑排序 + 建图
传送门题意：给定s个人，m个关系，每个关系代表这两个人是朋友，且此关系并不具有传递性。让后给了n个人名依次排列，满足以下两个条件时可以交换两个人的位置：(1) 两个人是朋友 (2) 两个人相邻。 可以交换无数次，现在需要求出其最小字典序。通过题面比较容易发现，两个人如果不是朋友关系的话，那么这两个人的相对位置是固定的，一定是一个人在前面，一个人在后面，只有前面那个人输出之后，才能输出后面的人。这样的结构显然很像拓扑结构。所以我们考虑如何建图。可以考虑将每个没有关系的两个人之间连一条边，不过这样的话时空复
2020-11-01 22:49:58
267
3
原创 P2921 [USACO08DEC]Trick or Treat on the Farm G
传送门题意比较明显了，直接说怎么搞。可以发现每个点的出度都是1，用tarjan缩点后，每一个强连通分量一定是一个环。如果它本身在一个环里，那么答案就是环的长度。如果不是在一个环里，那么一定是在链上。沿着链一直走，走到环为止。那么答案就是走过链的长度加上环的长度。dfs写的话需要一下特判环为1的情况。#include<cstdio>#include<iostream>#include<string>#include<cstring>#in
2020-10-05 14:06:12
207
原创 upc Get Strong 整体二分
题意很简单，就是分组背包。n只有20，队友想写dfs，我直呼内行。显然直接爆搜是不行的，复杂度高达2402^{40}240。反应了一会，发现这不是整体二分板子题嘛。。。2402^{40}240不行显然可以转换成两个2202^{20}220搜，让后两边体积拼凑起来。但是直接拼的话最坏也是2402^{40}240的，显然我们可以优化一下，枚举其中一个的体积，让后在另一个的 [0,m−v[i]][0,m - v[i]][0,m−v[i]] 体积里面找最大价值就行了。找最大价值的话因为是从0开始，所以可以O(N).
2020-10-03 18:51:56
174
1
原创 upc Cafebazaar’s Chess Tournament 思维 + FFT
说实话，题我没大读懂。听zwz大佬说这个题挑战者的两个能力值不能与被挑战者能力值相等，不过可以取实数，所以这句话看没看到都不影响这个思路，因为每个相等的数都可以+0.1或-0.1来实现不相等且不影响答案，所以以下按照能力值可以相等来讲比较清楚，具体的还是看下面吧。。。以下设挑战者(能力值不固定的人)为A，给出的n个人都为B。这个题容易被两个能力值限制住思维，觉得两个变量应该放在一起看。先说一下怎么做。我们尝试是否可以把两个值分开看。而考虑单个值的贡献时候，显然只需要考虑A在[0,n+1][0,n+1.
2020-09-26 23:40:08
166
2
原创 upc A Rush Hour Puzzle bfs
题意：给定6*6矩阵，相同数字代表一辆车，且只能前后移动。出口在第三行最右边。问编号为1的车能不能出去。看大佬们都讨论的dfs写的，比赛的时候我这个dfs菜鸡不会写，所以写了个bfs。灵感来源于八数码问题，主要是借鉴了当时做八数码的时候，将矩阵转换成了一个字符串。这个题基本可以实现O(1)O(1)O(1)转移，但是比赛的时候瞎搞的，也没优化，完全可以把bfs中字符串转换成矩阵的一层循环优化掉。转移的时候从头遍历找到每个数字的第一个位置，所以这个数字代表的车辆一定是从这个数字向右延伸或者向左延伸得到的，.
2020-09-12 23:00:30
214
原创 upc Typo 字符串哈希
题意：给你n个串，找出去掉任意一个字符后，与其他串相同的串，并输出。以前学过前缀哈希这么nb的哈希方法，自己竟然不会用，fw实锤了。对于前缀哈希，去掉一个字符后就相当于前后两个串的哈希值相加啊，当时想到了直接相加，但是没这么用过，学艺不精。。。让后就是一个裸哈希了，怎么写都能过，比赛没过属实有点亏。字符串没告诉多长所以用vector来存一下就好了。#pragma GCC optimize(2)#include<cstdio>#include<iostream>#in.
2020-09-12 10:50:07
163
2
原创 cf 1405 C Balanced Bitstring 思维
传送门题意：给一个01串，其中有些字符为′?′'?'′?′，′?′'?'′?′可以当做000或111。给定一个kkk，问能否给′?′'?'′?′赋上特定值后，其所有长度为k的字串0和1数量都相等。我们用两个指针来维护长度为k的区间。假设当前区间符合条件，当r+1r+1r+1,l+1l+1l+1的时候，可以发现必须要s[l]=s[r+1]s[l]=s[r+1]s[l]=s[r+1]才可以满足条件。那么就可以转换成s[i]=s[j mod k]s[i]=s[j\bmod k]s[i]=s[jmodk]，当s
2020-09-07 15:55:22
1502
1
原创 第三场 Two Famous Companies 最小生成树 + 二分
Two Famous Companies时间限制: 1 Sec 内存限制: 128 MB题目描述In China, there are two companies offering the Internet service for the people from all cities: China Telecom and China Unicom. They both are planning to build cables between cities. Obviously, the govern
2020-09-07 11:43:03
294
原创 石油大第四场 C: A^X mod P
问题 C: A^X mod P时间限制: 5 Sec 内存限制: 128 MB题目描述It’s easy for ACMer to calculate A^X mod P. Now given seven integers n, A, K, a, b, m, P, and a function f(x) which defined as following.f(x) = K, x = 1f(x) = (a*f(x-1) + b)%m , x > 1Now, Your task is to
2020-09-06 09:29:55
161
原创 李超线段树
模板题大佬博客#pragma GCC optimize(2)#include<cstdio>#include<iostream>#include<string>#include<cstring>#include<map>#include<cmath>#include<cctype>#include<vector>#include<set>#include<queue>
2020-09-05 16:23:34
128
原创 线段树 标记永久化
永久化标记就是不需要下传lazy标记，修改的时候一路更改要改的点，询问的时候累加标记即可。这里以区间赋值为例，注意modify的时候不需要pushup。#pragma GCC optimize(2)#include<cstdio>#include<iostream>#include<string>#include<cstring>#include<map>#include<cmath>#include<cctyp
2020-09-05 14:59:41
276
原创 P4396 [AHOI2013]作业 莫队 + 树状数组
P4396题意：给定一个序列，m个询问，每次询问给定一个区间 [ l , r ] 和两个数 a b ，求这个区间中有多少数在 [ a , b ] 区间之间和有多少数出现在 [ a , b ] 之间。文字可能表述不好，下面给一组样例：序列 1 2 2询问 1 3 1 3 ( l , r , a , b )答案 3 2最近学莫队肯定是用莫队来搞了，显然 [ a , b ] 可以转换成前缀来搞，用两个树状数组来维护就行了，一个直接维护前缀个数，一个维护当前数是否出现即可。时间复杂度：O(NNlogN
2020-09-03 16:31:54
178
原创 P3604 美好的每一天 莫队 + 思维
传送门真是个练习卡常的好题呢题意：给定一个串，让后每次给定一个区间，问这个区间的子区间为回文子区间有多少个。这里的回文串是区间内字母重排之后是回文串即可。既然重排之后是回文就行，那么只需要知道这个区间内奇数的个数就行了。字母只有26个，那么可以状态压缩一下，用一个数组记录一下每一位即可。既然只关心个数的奇偶，那么可以用异或来判断。区间异或显然可以转换成前缀异或，假设当前区间为 [ x , y ] ，那么需要选择两个数 i j ∈ [ x - 1 , y ] ，使其异或值为 0 (此时奇数个数为0)
2020-09-03 14:37:00
119
原创 Vladik and fractions CodeForces - 743C 思维
vj比较有意思的思维题，不过在巨巨们眼里都是小学六年级题。先看式子 1/x + 1/y + 1/z = 2/n ，n分子是2，我们想办法变成1，所以让z=n，这样就消去变成了 1/x + 1/y = 1/n ，而我们知道 1/n可以表示成 1/(n+1) + 1/(n*(n+1)) 这样 x = n + 1 , y = n * (n+1)。这样构造出来答案为x=n,y=n+1,z=n×(n+1)。显然 n<=1 无解。#pragma GCC optimize(2)#include<c
2020-09-02 08:40:42
185
原创 P3709 大爷的字符串题 莫队 离线求众数
传送门比赛卡题挂机先溜了离散化一下，让后记录一个cnt数组代表这个数出现次数，num数组记录出现次数为i的数有几个。让后直接维护就好了#pragma GCC optimize(2)#include<cstdio>#include<iostream>#include<string>#include<cstring>#include<map>#include<cmath>#include<cctype>#i
2020-09-01 22:02:03
127
原创 P4462 异或序列 莫队 + 异或技巧
传送门题意：给定一个k，一段序列。有m个询问，每次给定 [ l , r ] ，询问该区间内，有多少子序列满足异或和等于k。以下数组 x 为当前点的 value， a 为 x 的前缀异或和。看到区间异或和，不由的想到可以转换成前缀异或：a( l ) ^ a( l + 1 ) ^ … ^ a( r ) == a( l - 1 ) ^ a( r ) ，现在问题转换成了在 [ l , r ] 内是否存在两个数异或等于k。也就是 a [ x ] ^ a [ y ] = k 。让后看到了这个式子之后还是有点不可做
2020-09-01 15:18:52
220
原创 Count on a tree 树上主席树
vj某谷此代码在原 oj ac ，在某谷re全家福。裸的板子，调了4个小时了快，某谷还是re，给跪了，蒟蒻求助。两个题有一点点区别，某谷输入数据是加密的，vj是直接输入的。#include<cstdio>#include<iostream>#include<string>#include<cstring>#include<map>#include<cmath>#include<cctype>#incl
2020-08-31 01:04:29
214
原创 Educational Codeforces Round 36 (Rated for Div. 2) E 线段树 || 珂朵莉树
传送门尘封多个月的题。。。以前看见要动态开点没学，拿线段树敲崩了，秃然想起来就补上了。题意就是比较简单，给定一个全1序列，给你若干区间，两个操作，每次操作后区间 1 ~ n 1的个数。：(1)把区间全改成0(2)把区间全改成1算比较简单的区间修改吧，不过这个 n 范围是 1e9 需要离散化一下，离散化之后用线段树每个点维护一个区间，不过注意要把r加一，因为如果 l == r 可能 find 之后 l > r ，而且区间也不好维护。所以加一就比较舒服了。还要注意加上询问没涉及的区间长度。让
2020-08-30 21:17:36
125
原创 Vases and Flowers HDU - 4614 线段树 + 二分
传送门题意：编号为 0 ~ n - 1 个花瓶，有两个操作(1)以 a 为起点，选择之后的 k 个花瓶放上花，输出左右端点。(2)清空 l ~ r 的所有花瓶中的花，输出清除的花数量对于第二个操作就是线段树区间赋值和区间查询了。第一个操作如果知道左右端点直接区间赋值即可。现在问题是怎么求左右端点。比较显然可以在线段树上进行二分，分别二分出来第一个数位置和最后一个数位置。如果填不满k个的话显然第二个答案是INF，不会被更新。那么就需要把k改成 l ~ n - 1 中空花瓶个数，再二分一次就行了。#
2020-08-30 09:37:12
253
原创 CodeForces - 896C 珂朵莉树
传送门用set搞的比较神奇的树吧，玄学时间复杂度，代码简洁好写，无聊学了用来水题再好不过了 ~ ~ ~#include<cstdio>#include<iostream>#include<string>#include<cstring>#include<map>#include<cmath>#include<cctype>#include<vector>#include<set>
2020-08-28 23:41:30
229
原创 P4513 小白逛公园 线段树
传送门动态维护区间最大子段和比较简单的一个题吧，复习一下。让后就是注意读题，存在 x > y 情况。。不判断后面点全部re渍渍渍，痛击不读题的小菜鸡。。之前石油大还做过一个直接题目不给，让后数据存在 x > y 的情况，真是毒瘤了。#include<cstdio>#include<iostream>#include<string>#include<cstring>#include<map>#include<cma
2020-08-28 21:16:06
132
原创 P3391 文艺平衡树
功能：实现区间反转比如当前需要反转 [ l , r ] ，那么只需要把 l - 1 和 r + 1 分别旋到根节点，让后根节点右子树的左子树就是 [ l , r ] 区间内的数，在上面加一个 tag 懒标即可。注意各个地方pushdown。#include<cstdio>#include<iostream>#include<string>#include<cstring>#include<map>#include<cmath&
2020-08-28 16:55:01
135
原创 P2824 排序 线段树 + 二分
传送门比较有意思的一个题。直接排序肯定是不可以的。那看最后询问，只是一个位置，那说明是一个确定的值 x 。可以考虑讲原序列转换成01序列，>= x 的为1 ，< x 的为0，用线段树维护区间内1的值。那么排序的操作即可转换成对区间内01两个数的操作。假如当前区间为 [ l , r ] ，1 的个数为 cnt 。如果要升序的话，只需要 modify(1,r,r-cnt+1,1) 和 modify(1,l,r-cnt,0) 即可 ，也就是把 [ r , r - cnt + 1 ] 改成 1 ，
2020-08-28 00:10:51
160
2
原创 左偏树（可并堆）
洛谷3377#include<cstdio>#include<iostream>#include<string>#include<cstring>#include<map>#include<cmath>#include<cctype>#include<vector>#include<set>#include<queue>#include<algorithm>
2020-08-27 20:53:33
92
原创 Splay 板子
BST是个好东西，不过在成一条链的时候就会退化成 O(n) ，所以Splay诞生了~Splay可以改善这种情况，没事就Splay一下，就有可能把链变成别的结构，反正就很神奇。下面是洛谷第一个题解的模板，虽然有点问题，但是稍微修改一下就可以过了~#include<cstdio>#include<iostream>#include<string>#include<cstring>#include<map>#include<cmat
2020-08-27 16:43:26
156
原创 Reverse and Swap CodeForces - 1401 F 线段树 + 思维
传送门题目：要求实现四个操作如下第一个第四个用线段树比较容易了。第二个和第三个都是在分成 2 ^ k 长度区间操作，比较容易想到线段树就是分成 n+1 层，每层都由 2 ^ k 长度区间构成。规定根节点为第 n 层，叶子节点为第 0 层。先看第三个swap：相当于交换线段树两个相邻区间，也就是相当于访问的时候直接访问另一个区间即可。可以用一个变量来记录以下是否需要改变访问的左右结点。比如当前swap的是第 k 层 ，那么只需要改变第 k + 1 层标记即可。第二个跟第三个道理相同，假如当前需要r
2020-08-26 15:34:01
313
原创 HDU - 1688 Sightseeing 最短路和次短路计数
HDU 1688不是很难的一个题，因为只是求次短路，用k短路求就有点大材小用了，所以可以用dijkstra求次短路。只需要在原来松弛的时候进行改动：(1) 当前权值比最短路小，那么把当前最短路的数据复制到次短路，让后更新最短路(2) 当前权值等于最短路，那么直接将次数加起来(3) 当前权值比次短路小，那么直接更新次短路(4) 当前权值等于次短路，那么直接将次数加起来wa了20多发，照网上代码改了好几个，一模一样都能wa掉，结果发现是我自己写的变量有歧义了。。测试数据用的t，终点也用的t，直接当
2020-08-02 10:43:16
150
原创 POJ - 3723 Conscription 最小生成树
poj3723大意：题目给定n个女同学，m个男同学，让后给若干个男女关系，每个关系都有一个特定值c，雇佣一个人10000元，而如果当前雇佣的人与已经雇佣的人有关系的话，雇佣钱数就可以-c。要求雇佣所有人花的最少钱数。还是比较简单的，被自己的假算法骗到了。。。把给定的若干关系看成一个个连通块，对于每个连通块，拿10000元买一个人，让后剩下的人就都可以用优惠之后的价格购买了。这也是比较显然的，因为每个优惠关系最终只能优惠到一个人，需要另一个被雇佣了才能优惠嘛，所以跑一遍最小生成树，让后加上连通块个数*10
2020-07-31 23:01:17
169
原创 poj 3764 The xor-longest Path 字典树 + 前缀和
题目链接题意：在一棵树上选择一个路径，使路径权值异或之和最大。既然是在字典树专题里的，自然也就想到了字典树，不过只能求两个数的最大异或，而这个题不确定是不是两个数，而且路径也很难找出来，这个时候想起来之前学主席树做 “最大异或和” 这道模板题的时候，将区间异或转换成了前缀异或，茅塞顿开，发现可以用dfs处理前缀和，让后每一条路径不就是两个前缀异或起来嘛。这样就转换成了两个数的异或，可以用字典树轻松解决。我不会算字典树的空间，每个题基本都得re一次，开的可能有点大。#include<cstdio
2020-07-28 10:50:46
111
原创 hdu 3333 Turing Tree 线段树 + 离线
题目链接题目给定一个序列，让后查询m个区间，输出区间内数的和，重复的不计算多次。想了半天也没想出来怎么在线维护这样的线段树，那就考虑一下离线怎么做。如果把区间按右端点排序，那么每次查询 [ l , r ] 的时候，如果都能保证 [ 1 , r ] 内重复数字的下标都在最右边，那这样即可避免重复了，而且还能保证每次查询的准确性。也就是说每次询问，看一下 [ 1 , r ] 是否已经确定，如果还没确定的话就需要遍历到 r ，这样就保证了每次 [ 1 , r ] 区间内没有重复的数字，且下标都只保留最右边。
2020-06-30 10:00:30
168
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人