一所悬线-CSDN博客

原创后缀数组+主席树

https://vjudge.net/problem/Gym-102302K后缀数组去重，主席树查询区间内在l,r之间的数的个数#include<iostream>#include<stack>#include<algorithm>#include<stdio.h>#include<string.h>#include&...

2019-08-28 10:35:52 180 1

原创区间异或最大值线性基+贪心

题意：在l，r之间的元素中选择任意，使异或和最大。#include<bits/stdc++.h>#include <cstdio>#include <vector>#include <algorithm>using namespace std;int b[1000006][35],pos[1000006][35];void up(i...

2019-08-01 10:01:23 542

原创组合数取模

模数大于n时直接用阶乘逆元求就行，否则可以用Lucas求。模数较小时预处理阶乘优化。#include<bits/stdc++.h>using namespace std;#define inf 0x3f3f3f3f#define ll long longll qpow(ll a,ll b,ll mod){ ll ans=1; while(b) ...

2019-06-19 20:23:59 136

翻译 Two Triangles FZU - 2270

通过叉积判断边的相对位置，（类似极角排序），就可以判断两个三角形是否可以通过旋转重合。https://blog.csdn.net/w326159487/articl#include<iostream>#include<stdio.h>#include<cmath>#include<algorithm>#include<stri...

2019-06-10 10:04:23 134

翻译 FFT模板 [ZJOI2014]力

多项式有多种表示方法，比如系数表示，点值表示。FFT就是实现快速在这两种表示法之间转换。多项式在点值时进行多项式乘法是o（n）的，在系数表示法中，多项式相乘中两个系数序列会进行卷积，但是n^2的，所以转化成点值进行计算可以优化卷积。#include<bits/stdc++.h>using namespace std;#define pi acos(-1)struct Co...

2019-06-09 10:52:45 84

原创 Split The Tree HDU - 6504

题意：给你一颗树，每个点有权值，每个树的的价值是这颗树上点权不同的个数，现在你可以去掉一条边变成两棵树，问这两颗树的价值和最大是多少。思路：去掉一条边相当于选取了整颗树的一个子树，子树所有节点dfs序是连续的，就是求连续区间不同数的个数，剩下的部分可以通过将序列复制一遍相连。求连续区间不同数的个数有多种方法，莫队算法，主席树，树状数组。树状数组：对于一个数列，每个数字第一次出现的位置标...

2019-05-07 14:37:04 133

原创 distance on the tree 树上主席树

题意：求树上两点之间边权不超过k的边的个数。思路：树剖之后建主席树，或者直接利用父子关系直接建树。#include<bits/stdc++.h>#define inf 0x3f3f3f3fusing namespace std;#define ll long long#define maxx 1e9struct code{ int l,r,d;} tr...

2019-04-23 11:31:23 125

类似于二分查找，三分搜索法也是比较常用的基于分治思想的高效查找方法。但是和二分不同，二分只适用于单调函数，比如常用的对单调递增或单调递减的一个序列中的某一个元素进行查找，三分却突破了这种限制，可以用于左边递增右边递减或者相反的，这么一类函数，也就是常说的凸函数和凹函数。但是为什么三分法可以用于凸函数或者凹函数呐，这其实是因为这种函数总是有一个最大值或者最小值，这样就可以借此判断出三分法中两个中点相...

2019-03-19 15:10:38 227

原创 P2530 [SHOI2001]化工厂装箱员

状态:f[i][j][k][m] : 前i个物品当前手中有j个"A" k个"B" m个"C"时的最小卸货次数很明显对于第i个物品可以1:)只取出来暂时不装进去前提就是当前手中货物数量<102:)取出来后装进去没有前提所以转移方程就出来了:f[i][j][k][m] = f[i-1][j-1][k][m] if(ob[i]=='A' && j)...

2019-03-06 22:15:39 126

原创 Codeforces Round #533 (Div. 2)E. Helping Hiasat

题意：求一个无向图的最大独立集，就是求其补图的最大团。最大独立集 = 补图的最大团#include<iostream>#include<queue>#include<map>#include<string.h>#include<stdio.h>#define inf 0x3f3f3f3fusing namespace...

2019-01-22 15:07:09 161

原创 A - Aragorn's Story 树剖

树上区间更新和查询，原理就是把树拆成几条链，dfs序是连续的，所以就把他们强加到线段树上，进行更新和查询。进行两遍dfs，第一遍把深度，重儿子，父节点等一些信息找出，然后第二遍dfs时记录每个节点的链头，遍历时先走重儿子，把树上的每个节点按dfs序应到数组上，建树就行了。具体过程找个视频看看就懂了。写的不太规范，自己能看懂就好了。#include<bits/stdc++.h>...

2019-01-17 19:37:28 173

原创 D. GCD Counting 树形dp

题意：一棵树，每个节点有权值，找一条gcd不唯一的最长路，输出长度。思路：gcd不唯1，即两个数有相同的素因子，dp[i][j]就表示以i个节点通过这个数的第j个素因子最长的子链，然后路的长度就是在遍历的时候选两个最长的相加，dfs遍历一遍树不断更新答案。#include<bits/stdc++.h>using namespace std;int dp[200005]...

2019-01-14 21:36:10 250

原创 Codeforces Round #532 (Div. 2)E. Andrew and Taxi

题意：给一个有向图，反转某些边让这个图无环，反转的花费是反转的所有边中权值最大的，求花费最小的方式，输出花费和需要反转的边。思路：把某个边反转其实就相当于把这条边删除，二分答案，用拓扑排序判断是否又环，最后删完了之后是ACG，求每个点的拓扑序，然后检验删去的边是否能形成环。#include<bits/stdc++.h>using namespace std;#define...

2019-01-14 11:49:42 108

原创筱玛的字符串

https://ac.nowcoder.com/acm/contest/342/E题意：给一个匹配的括号串，首先选择一个区间（可以不选），让字符反转，然后隐藏其中一些位置，变成？，让你还原，问可以还原多少种情况。思路：dp[i][j][k],i表示处理的位置，j表示（比）多几个，k表示当前位置的状态，1表示没有进行反转，2表示正在进行反转，3表示已经完成反转。转移的时候对不同字符根据不同状...

2019-01-13 20:59:53 188

原创 String painter HDU - 2476

题意：给两个字符串，通过涂色把第一个串构造成第二个串，每次将一个连续区间涂成一种颜色，后涂会覆盖之前的。思路：之前做过类似的是相当于在空串上构造第二个串，现在类似的可以同样进行那个操作，然后再一次区间dp，去求最小次数。在得到了一个s2串的相关dp数组后，我们考虑s1串，如果s1串和s2串在某一个点相等了，即表示这一点可以不用特意去刷一次，那么便可以由这一点来分成两个区间。如果用 an...

2019-01-13 20:32:06 160

原创 Beans HDU - 2430

题意：有n堆豆子，选择其中连续的几堆，装进大小为m的袋子中，问最多能装满几袋，在剩余豆子不超过k的情况下。思路：求(sum[i] - sum[j](i != j)) % m <= k && 使得（sum[i] - sum[j]）/m最大。可以按sum[i] % m，给数组排序，用单调队列来解决这个问题。用余数的差距去维护是否出队列。维护队列递增sum[i]（头小尾大）。...

2019-01-12 16:56:56 159

原创 C - Subsequence HDU - 3530

题意：给定一个序列，求一个连续区间满足区间最大差距在l,r之间。思路：单调队列维护最大值最小值。分析：记录起点，维护最大值最小值在队头，当队头的差距大于l时出队，出队时选择两个队列中较小的下标，具体过程按照代码跑一遍就差不多可以理解单调队列的作用。#include<bits/stdc++.h>using namespace std;#define ll long lo...

2019-01-12 12:04:38 126

原创 Rabbit的工作(1) dp

题意：给你n和k，和一个长度为n的字符串，字符串中的0表示休息，1表示工作，连续工作会损耗连续的体力值，从1开始，但是休息后就重新计算体力值，一共最多损耗k点体力值，求解最多工作多少天题解：动态规划，状态定义为，dp[j][k]表示在第i天之前工作j天，并且已经连续工作k天的情况下的最小体力花费，最后扫一遍，保存满足条件的j的最大值即可，转移过程很好理解。 https://ac.nowcod...

2019-01-11 20:36:49 159

原创多边形面积

原理：任意多边形的面积可由任意一点与多边形上依次两点连线构成的三角形矢量面积求和得出。矢量面积=三角形两边矢量的叉乘。分析：假设任意一点为原点，则最后取一下绝对值即为多边形面积。sum=0;for(int i=1; i<=n; i++){ scanf("%lf%lf",&point[i].x,&point[i].y); ...

2019-01-07 21:46:04 263

原创 D. Easy Problem dp

题意：给你一个字符串，让你删除某些字符使得这个串的所有子串不包括hard，删除每个字符有花费，求一个最小花费。思路：dp[i][j]表示到第i个字符可以组成hard的前j个字母，然后对每一个字符，递推转移一下。#include <iostream>#include <cstdio>#include <cstring>#define ll long...

2018-12-29 11:33:58 171

原创 P4170 [CQOI2007]涂色区间dp

假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。用尽量少的涂色次数达到目标。很简单的区间dp，dp[i][j]由dp[i][...

2018-12-27 21:00:51 120

原创 K - Count the string HDU - 3336

https://cn.vjudge.net/problem/HDU-3336题意：求一个字符串中所有前缀在这个字符串中出现的总次数（可重叠）。思路：利用next数组dp一遍,然后求一遍dp的总和。#include<iostream>#include<stdio.h>using namespace std;#define ll long long#def...

2018-12-26 11:41:01 175

原创 The Battle of Chibi HDU - 5542

https://cn.vjudge.net/problem/HDU-5542题意：求从长度为n的序列中最多能找出长度为k的严格递增子序列的个数。思路：dp[i][j],表示第i个数作为子序列的第j个数的序列有多少个。 for (int i = 0; i < n; i++) { dp[i][1] = 1; } ...

2018-12-25 20:34:50 116

原创 Roads in the North POJ - 2631

树上最大距离的裸题，就是在树上找两点这两点的距离比其他任意的都大。题意：给出一棵树的两边结点以及权重，就这条路上的最长路。思路：求树的直径。这里给出树的直径的证明：主要是利用了反证法：假设 s-t这条路径为树的直径，或者称为树上的最长路，现有结论，从任意一点u出发搜到的最远的点一定是s、t中的一点，然后再从这个最远点开始搜，就可以搜到另一个最长路的端点，即用两遍广搜就可以找出树...

2018-12-19 21:55:59 108

原创 G - Extreme XOR Sum UVALive - 7639

题意：一个序列，q次询问，每次问你某个指定区间内的EXtreme XOR值。一个长度为l的区间的EXtreme XOR值被定义为，从左到右，将每相邻的两个数XOR起来，产生l-1个新的值，……如此循环，总共l-1次，直到剩下一个值。问的就是这个值是多少。一个区间的答案，只和每个数被异或的次数的奇偶性有关,而这个被异或的次数恰好是二项展开式的系数,手写观察下。然后预处理每个长度奇数的位置...

2018-12-18 18:25:33 187

原创首尾相连数组的最大子数组和

推荐博客：https://blog.csdn.net/lin_disguiser/article/details/50821885当时想到的是第一个思路，但不如第二个好，第一个时间复杂度比第二个要高。#include <iostream>#include <cstdio>using namespace std;#define inf 0x3f3f3f3f#...

2018-12-16 16:31:40 173

原创 GCD-莫比乌斯反演

https://blog.csdn.net/Let_life_stop/article/details/84843854https://blog.csdn.net/qq_20200047/article/details/71091339利用两个函数的关系，已知一个，可以求出另一个。具体内容参考大佬博客。#include<iostream>#include<stdi...

2018-12-15 21:57:17 166

原创牛客多校赛 G transform（二分）

https://blog.csdn.net/Lee_w_j__/article/details/81157488题目描述White Cloud placed n containers in sequence on a axes. The i-th container is located at x[i] and there are a[i] number of products in it....

2018-12-12 15:22:42 215

原创 J - Straight Master Gym - 101775J ----差分

题意：给你一个序列，每次可以随便选一个大小为3~5的区间，将区间内的数减1，问最后能不能把整个序列变为0思路：构造差分序列b【i】=a【i】-a【i-1】，比如1 3 2 5 1的差分序列就是1 2 -1 3 -4，这样将区间【l，r】内的所有数减一相当于把b【l】减一，把b【r+1】加一，基于这个思想我们从左到右扫整个序列，遇到正数就找他右面离他最近的负数，把这个负数尽量变为0，变为0后若...

2018-12-07 19:19:09 176

原创 Origami

Chiaki has a very big sheet of paper. This sheet has a form of rectangle with dimensions 1 x n and numbers from 1 to n was written on each small 1 x 1 grid. Chiaki would like to fold the paper using t...

2018-12-02 12:58:32 149

原创 Sabotage UVA - 10480 网络流求最小割边

这是一道很典型的最小割最大流定理，通过这道题，我再一次学习了最小割的定义最小割，就是在所有割中，容量之和最小的割，这就是我的理解，而最小割的值就是最大流的值，因为很容易想到，从源点s到汇点t的最大流必然会经过割边，那么就有最大流f<=c(割边的值），那么也就是说，当c==f的时候，就是c为小割，即最大流==最小割第二点，怎么求出最小割的边：在求出最大流之后，残余网络会分成两个部分，和...

2018-11-26 19:27:27 157 1

原创 Find a Number CodeForces - 1070A

题意：给定d和s，求一个最小整数能被d整除，且各位数字之和等于s。一开时直接按位数去搜，因为之前做过个位数为0和1，的一个类似的题，打出来之后根本跑不出来，数据量太大。然后参考了网上代码。记忆化搜索，以余数和各位数之和为状态去搜（我一直感觉记忆化搜索长得和dp是的）然后递归输出。#include <iostream>#include<queue>#incl...

2018-11-21 19:57:41 152

原创求1～n的lcm

题意很简单，但数据量巨大，出题人给了4s.利用唯一分解定理和1-n数字因子的特点去解决。详见代码，很容易理解。、#include <iostream>#include<algorithm>#include<stdio.h>#include<map>#include<iomanip>#include<string....

2018-11-18 21:33:42 236

原创 Jailbreak 个人训练赛

https://vj.e949.cn/5e9d1ef965fc5f2bb34f0d3ff5e7eca4?v=1542378645 j题题意：两个人逃出监狱的最小开门数，门打开后不会关闭。思路：对图加边，默认空地，然后最优为两人最后会和一起出去。以（0，0）和两个人的起点搜三遍存图。遍历所有点假设这是集结点求最小开门数。搜图的时用优先队列维护最小开门的点，普通队列维护的是步数最小。...

2018-11-17 11:52:01 118

原创 Island Transport HDU - 4280 网络流模板

　　In the vast waters far far away, there are many islands. People are living on the islands, and all the transport among the islands relies on the ships.　　You have a transportation company there. So...

2018-11-13 08:54:26 117

原创 Palindrome HDU - 6230

题目中要求的串，可以概括为两个回文串的组合：_____ i ____ j _____以 i 和以 j 为中心的两个回文串拼接起来，注意 i 的回文串范围要覆盖 j，j 的回文串范围要覆盖 i设p[i]是以 i 为中心的回文串覆盖半径（不包括 i ）那么要符合三个条件：j>i ; j<=i+p[i] ; i>=j-p[j] ;先用Manacher算法算出以每个点为中...

2018-10-27 16:14:12 168

原创 Sum of Consecutive Integers—数论推特点

题目链接：http://lightoj.com/volume_showproblem.php?problem=1278题意：给你一个数n(n<=10^14)，然后问n能用几个连续的数表示;例如: 15 = 7+8 = 4+5+6 = 1+2+3+4+5，所以15对应的答案是3，有三种; 我们现在相当于已知等差数列的和sum = n, 另首项为a1,共有m项，那么am = a1...

2018-10-26 20:15:58 213

原创 Pairs Forming LCM

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=109329#problem/B 题意：在a,b中(a,b<=n)(1 ≤ n ≤ 1014),有多少组(a,b) (a<b)满足lcm(a,b)==n; 先来看个知识点：素因子分解：n = p1 ^ e1 * p2 ^ e2 *..........*pn ...

2018-10-26 16:14:59 133

原创调和级数

题意:求n级调和级数之和：h[n] = 1/1 + 1/2 + 1/3 + 1/4 +…+ 1/n。(n <= 1e8)。要求误差不超过1e-8. 网上的题解主要有两个思路,思路1: 由于 n 最大是 1e8的大小,显然打不了这么大的表.于是考虑每100个数记录一下.于是对于在最后一个区域中时,然后询问时就是在这个基础上最多在查100个数.代码/** 调和级数...

2018-10-22 20:48:57 1140

原创 Mysterious Bacteria 唯一分解定理+素数筛

题目大意：给你一个数x = b^p,求p的最大值 x = p1^x1*p2^x2*p3^x3*...*ps^xs开始我以为是找x1、x2、... 、xs中的最大值，后来发现想错了，x = b^p, x只有一个因子的p次幂构成如果x = 12 = 2^2*3^1，要让x = b^p,及12应该是12 = 12^1所以p = gcd(x1, x2, x3, ... , xs)...

2018-10-22 20:08:42 183

空空如也

空空如也