四维2000-CSDN博客

原创 ICPC World Finals 2018 （ABHIFK）

A - Catch the Plane题意：你要从0号点坐公交到1号点，给你m个公交车的起始点、终点、出发时间、到达时间、发车概率，问你选择最优策略时，到达1号点的概率是多少。分析：首先在做策略的时候肯定要考虑坐完公交之后的概率，所以考虑从后往前进行dp。在dp的时候每个点到达的时间不同，可以到达1号点的概率也不同，很明显有一个单调性，就是越早到达一个点，从这个点到达终点的概率越大，所以我们的dp的状态f_i，代表在某个时间点到达i之后可以到达1号点的最终概率。非常关键的一点就是每个f_

2021-09-04 15:45:17 415 1

原创 ICPC World Finals 2019 （AH）

A - Azulejos题意：两组pair，排出两个顺序满足每组pair的first升序，first相等的任意排，且a[i].second>b[i].second思路：显然最终顺序中first的序列都是确定的，所以我们只需要考虑first序列相同时的second的顺序。对于两个每一段first来说，用长的那边尽量满足短的那边。不断重复，只解决最短那边的问题，过程中用set维护。代码：#include<bits/stdc++.h>#define fi firs

2021-04-09 19:40:14 253

原创 [SCOI2005]互不侵犯King （状压DP）

题意：给一个n*n(n<=9)的棋盘，问放k(k<=n*n)个国王满足不冲突的方案数，国王的攻击范围是周围的八个位置。分析：非常经典的状压dp，dp[i][j][s]代表第i行，已经存了j个棋子，这一行的国王存放状态为s的方案数，空间复杂度n*k*(2^n)大概1e6，时间复杂度n*k*(2^2n),大概2e8，最后在darkoj上运行是150ms，应该是常数比较小。代码：#include<bits/stdc++.h>using namespace std;

2021-03-08 23:18:34 242

原创四维的板子

四维的板子1、头文件#include <cmath> //定义数学函数#include <cstdio> //定义输入／输出函数#include <cstdlib> //定义杂项函数及内存分配函数#include <cstring> //字符串处理...

2021-01-28 01:01:59 499

原创 Codeforces 1452F Divide Powers (模拟)

题意：有cnt_i个大小为2^i的数，你可以把一个数拆成两个大小一半的数，问最少拆几次可以拆成k个小于等于2^x的数分析：就是贪心模拟，发现如果只拆小于等于x^2的数时，说每拆一次多一个，而如果时把大于2^x的数全都拆成2^x时，是可以节省一次的，因此我们只需要在保证小于等于2^x的数大小足够的情况下，尽可能地把大于2^x的数完整地拆成2^x就是最少的拆法细节真的挺多的，硬撕出来一大坨乱七八糟的代码，这种大模拟题也懒得优化简洁代码了代码：#include<bits/stdc++.h&

2020-11-20 10:53:39 205

原创 Codeforces 1452E Two Editorials (预处理优化)

题意：在长度为n的范围内有m个区间，现要求另选两个长度为k的区间染色，现求每个区间被最大染色和的最大值。分析：对于每个位置i往后染k个颜色预处理对最终答案的贡献ans[i]，以及染完这k个之后如果下一个区间从j开始染，由于j处染色部分大，i处的染色无法计算而丢失的贡献sub[i][j]。维护好ans[N],sub[N][N]这两个数组后就只需要O(n^2)找出哪选哪两个最大就好了。大体思路就是这样，具体细节还需要注意很多，比如预处理sub[N][N]数组时需要用到差分，区间内染色大小相同时都要减

2020-11-20 10:45:22 481

原创 2020CCPC威海站 L Clock Master（分组背包）

题意：给出一个数拆成若干个数的和，使这些数的lcm最大分析：题意非常难懂，给了很多无关的概念干扰项，比赛时读了三遍才搞懂，赛场时一直再猜结论，一直卡了有俩小时吧。补题时知道是分组背包后很快就有思路了，想来还是对于dp不够熟悉，另外需要一提的是log(n)的复杂度很大，需要预处理否则会T代码：#include<bits/stdc++.h>#define fi first#define se second#define mid (l+r>>1)#define end

2020-11-09 22:33:01 185

原创威海G题gym102798G Caesar Cipher（hash+线段树）

题意：一个数组，两种操作，区间+1，和查询两段子数组是否完全一样。思路：用线段树维护hash值，但是过程中问题很多，比如这个数组的值最大只能是65535，再加会进位，给人一种错觉是可以unsighed short来自然进位，但这样就无法维护hash值了，所以还需要在线段树里面加上一个删除最大值的，这样复杂度也不会加很多。但是这时候仍然有问题，就是这道题的数据比较强，可以卡掉我一直用的unsighed long long的hash方法，最后还是需要两个大质数，一个作为底数，一个作为模数进行hash，看来之

2020-11-09 21:02:57 189

原创 HDU - 6153 A Secret （KMP）

题意：给出两个长度小于1e6的字符串，问第一字符串的所有字串中有多少个和第二个字符串的后缀相同，输出每个相同的字串的长度和，答案还需要%1e9+7分析：把第二个字符串反转后，用KMP预处理，在算出nxt数组之外还需要记录下当前字符匹配后对答案的贡献base，计算的公式为base[i]=base[nxt[i]]+i代码：#include<bits/stdc++.h>#define fi first#define se second#define mid (l+r>

2020-11-04 19:47:48 119

原创 2020CCPC网络赛 HUD6888-6900部分

10021003签到题#include <bits/stdc++.h>#define x first#define y second#define mid (l+r>>1)#define lo (o<<1)#define ro (o<<1|1)using namespace std;typedef long long ll;typedef vector<int>vi;typedef pair<int,int&g

2020-10-27 07:31:47 140

原创 HDU - 6808 Go Running(图论)

一.题意:给出n(1e5)个点,问最少几个斜着的线可以覆盖所有的点二.分析:用二分图最大匹配即最小点覆盖的性质做题,把每个点当作一条边,点所在的斜线当作点,然后这两条斜线所代表的点直接建一条有向边,然后跑二分图匹配就好了,亲测匈牙利算法会超时,dinic就可以卡着边过去.三.代码:#include <bits/stdc++.h>#define fi first#define se second#define mid (l+r>>1)#define lo (o&.

2020-10-09 21:13:21 126

原创 POJ 1811 Prime Test (pollard_rho）

题意：给一个1e18的大数，求最小质因子分析：裸板子题，可以测试板子，需要注意的是POJ G++不可以用srand，C++不可以用__gcd，而且__gcd存在出现负数的情况，所以还是手写一个gcd函数。另外那个快速乘mul_mod这样写比较长但是可以优化大概10%的速度代码：#include <cmath> //定义数学函数#include <cstdio> //定义输入／输出函数#include <cstdlib> //定义杂项函数及内存分配函数

2020-10-03 10:08:59 140

原创 LightOJ1282 leading and trailing （double技巧）

题意：给定两个数n,k 求n^k的前三位和最后三位解析：后三位很好弄，快速幂就好了，前三位当然也可以类似快速幂一样模拟，把后面的位数省去，但是这种做法也就和double的原理一样，就想着用double来做就可以方便很多。需要注意的是double的有效精确位数也就15位，所以也没必要保存很多位，一旦超过30位就除到15位就好了。另外看还有大佬使用log10函数来做，感觉也挺有意思的，但是怕精度有损失就还是自己模拟吧。然后这道题还有个坑，是后三位如果不到三位要补0代码：#include

2020-09-28 08:30:24 154

原创 UVA - 11827 Maximum GCD（流输入）

题意：求所有数对的gcd的最大值解析：单独题意没什么难度，唯一的难点是没有给出m，也就是读入个数不确定，这里可以读入字符串后用快读来模拟，但也可以用stringstream，非常高级的一种用法，需要注意的一点是使用getline时也存在缓冲区的问题，需要视情况多读一个。代码：#include <bits/stdc++.h>#define x first#define y second#define mid (l+r>>1)#define lo (o<&lt

2020-09-28 08:22:00 126

原创 HDU4689 Prince and Princess （Tarjan+匈牙利匹配）

题意：n个王子，m个公主(n,m<500)，王子喜欢公主就可以匹配，问在总匹配数最多的情况下，每个王子都可以匹配哪几个公主。分析：POJ1904的加强版本，感觉要想做出这题要先搞懂这个简单版。感觉这题的建图是真的神仙，要不看题解根本想不到，看完题解写完后也还是无法完全理解。现在想来大体思路就是，王子喜欢公主就连一条边过去，表示想象成可以把爱传过去，然后需要用二分图匹配求出当匹配数最多时，每个公主所接受的爱意是谁，这时可以理解为公主接受了来自这个王子的求爱，所以这样建图后，在一一匹配的情况下

2020-09-25 18:19:15 92

原创 POJ 3177 Redundant Paths(Tarjan)

题意：无向连通图，问最少加几条边可以使得双连通解析：用tarjan缩点后求度数为1的点，最后的答案是点数/2向上取整代码：#include <cmath> //定义数学函数#include <cstdio> //定义输入／输出函数#include <cstdlib> //定义杂项函数及内存分配函数#include <cstring> //字符串处理#include <algorithm> //STL 通用算法#include

2020-09-25 10:07:33 84

原创 POJ 3695 nework (Tarjan的并查集变形）

题意：一棵无向连通图，存在重边，q次操作每次加一条边，问每次加边后的割边数。解析：最朴实的思想是缩点然后对树上不断求lca，虽然可以但是有点麻烦。可以把low数组的含义改变下，不再存dfn_cnt的最小值，而是可以到达的dfn最小点的下标，这样实际上跑一遍tarjan就可以求出一个用并查集维护好的树。这样修改时只需要不断向上合并父节点就可以了，感觉这个思路很巧妙，是对于tarjan思想的一种变形改造。代码：#include <cmath> //定义数学函数#include &lt

2020-09-25 09:10:13 83

原创 HDU2242空调教室（Tarjan）

题意：给出一个含重边的无向联通图，以及每个点的权值，让你割掉一条边将图分成两部分使得权值和最接近，输出这两部分权值和的差，如果不存在这样的边就输出impossible。题解：我是通过把tarjan算法改了下就过了，但是感觉对于tarjan算法的核心原理理解的还差的很多，可能思路的细节上还有问题，我就写下大致的思路，就是说再对每个点tarjan时维护一个上一个的值，这样就可以保证不在同一条边走回头路，同时为处理重边的问题，再维护一个bool性的flag，也就是说只对于第一次出现的重边不做处理，之后再出现就

2020-09-22 20:57:57 276

原创 Codeforces Round #671 E Decryption (模拟构造)

题意：给出一个合数，让你讲这个数的所有因子构造成一个环，使得环上相邻两个数不互素分析：简单可以证明只有当这个数是仅有两个素因子时无法构造出满足条件的环，如6=2*3只能构造成2 6 3，因此需要特判一下。除去这种特殊状况其余都可以满足条件，我们只需要找到一种合适的就可以，我所想到的一种构造方法是以递归的思想，每次加上的序列是以原有序列为基础的，把原来的序列反过来就可以保证加上后首位都是非互素相连的，再在中间加上一个1就可以把所有含有新的质因子的序列找出来。比如150=2*3*5*5，最初ans为空，我们

2020-09-20 08:51:01 443 2

原创 Codeforces Round #671 D Sage‘s Birthday (模拟构造)

题意：给n个数，要求将这n个数重新排列使得凹进去的数（就是比两边都小的数）最多分析：思考后可以发现，无论是奇数还是偶数，无论中间有多少相同的数，只要把前(n-1)/2个数全部按顺序紧紧塞到后面（如果是偶数第一个后不塞，就可以保证凹进去的数最多，比较好证明，所以只需要用这种方式构造出来目标数组，然后算下有几个满足条件的数就好了代码：#include <cmath> //定义数学函数#include <cstdio> //定义输入／输出函数#include <cs

2020-09-20 08:14:58 179

原创 2020牛客多校二H Happy Triangle (STL 线段树)

题意：一个集合可以对其做三种操作，加上一个x，减去一个已有x，给出一个x问时候存在a和b使得abx可以围成一个三角形分析：看到集合操作马上想到用set，其中可以再用set的指针在map上记录下所以数值之间的差，但这时存在一个问题就是可能存在两个数，这两个数的差满足条件但两个数的和却太小不到x，因此我所用的方法就是提前把所有差都求出来后离散键线段树，线段树上存的是该差中的最大和，这样再动态对每个操作进行修改查询代码：#include <bits/stdc++.h>#define x

2020-09-18 10:17:17 214

原创 2020牛客多校二J Just Shuffle （数论）

题意：问哪个置换执行k次后可以把123……n变成给出的序列，如不存在这样的置换输出-1，其中k为素数。分析：根据置换的性质，置换是由环组成的，由于k是素数，所以无论环的周期m是多少，m和k%m都是互素的，所以一定存在满足要求的置换，所以由数论知识一定可以找到一个b使得b*(k%m)==1(mod m)，这样就可以将给出的序列乘上b次，就得出了符合要求的置换，具体的那个置换逻辑比较绕，看了半天也还是很迷，之后遇到置换最好还是写一下。代码：#include <bits/stdc++.h&gt

2020-09-17 15:13:00 121

原创 2020计蒜之道初赛一染色（dp+线段树）

题意：对一个长度为n的条染色，只能黑或者白，对第i块染色染成黑或白分别加分arr[i]和brr[i]，给出m条线段，对这些线段同时染成某种颜色有额外的加分，求最大的加分数。解析：比赛时用着明显错误的假算法冲过了中等难度，感觉题目的数据有点过水，不能保证代码完全正确 (⊙﹏⊙)现在想来中等难度的O(n+m^2)的正确算法应该是：把黑白区间分别按照右边界从小到大排列，之后在dp的过程中到达右边界时进行dp，状态转移方程就是dp[i]=max(dp[i],dp[j-1]+pre[i]-pre[j-1]+s

2020-09-13 22:38:31 209

原创 HDU 6705 Path （二分+搜索）

题意：给一个有向带权图，找图中第k大的路径思路：不同于常规的优先队列的做法，我考虑的是只要定一个路径的最大值，就可以通过暴力枚举来得出所有不小于这个最大值的路径值，这个暴力的复杂度是O(max(k))的，因此通过二分这个最大值，就可以找到一个满足条件的路径序列，这个路径序列只需要大于等于查询的最大值max(k)就可以，如果序列数小于查询数就扩大最大值，如果大于就减小最大值，由于可能存在一些相同的路径，因此无法保证小于某个值的路径数完全等于max(k)，所以在判断序列数过多时需要把ma再多加100。代

2020-09-11 09:05:39 130

空空如也

空空如也