QiufengWang424-CSDN博客

原创 tarjan求强连通分量专题

定义：对于有向图上的2个点a,b，若存在一条从a到b的路径，也存在一条从b到a的路径，那么称a,b是强连通的。对于有向图上的一个子图，若子图内任意点对(a,b)都满足强连通，则称该子图为强连通子图。非强连通图有向图的极大强连通子图，称为强连通分量。单独的点也可以是强连通分量学习博客：https://www.byvoid.com/zhs/blog/scc-tarjan下面给几个例题

2017-05-02 22:19:52 776

原创 LCA专题

详细讲解博客：http://dongxicheng.org/structure/lca-rmq/（没有代码）求LCA（最近公共祖先）的算法有好多，按在线和离线分为在线算法和离线算法。离线算法有基于搜索的Tarjan算法比较好，而在线算法则是基于dp的ST算法比较好。当然树链剖分也能写先是ST算法。这个算法是基于RMQ（区间最大最小值编号）的，而求LCA就是把树通过深搜得到一个序列，然后转

2017-04-23 21:55:27 482

原创树链剖分专题

入门的话，这篇还是写的不错的： http://blog.sina.com.cn/s/blog_6974c8b20100zc61.html一个入门小专题：https://vjudge.net/contest/158100#overview1.SPOJ QTREE 树链剖分+线段树题意：给两个操作，一个是把第i条边权值修改成ti，另一个是查询a到b之间最大的边权值基于边权，修改单条边权，查询路径

2017-04-23 21:39:56 336

概要：一般形成环的用高斯消元法求解。但是递推公式只和少数变量相关，可以考虑分离出系数。总结：（看完下面的例题再来看这部分）1.这类题型一般可以先写出原始公式然后分离出困难的变量，比如第二题的dp[1]dp[1] , dp[father[i]]dp[father[i]] , 都是很难处理的变量，就可以把它们作为待定系数的变量 2.将剩下的变量通过待定系数的公式带入消去,比如例题2,∑dp[child

2017-04-18 11:24:43 1054

原创最大团问题

百度上的定义： http://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%9B%A2%E9%97%AE%E9%A2%98简单的讲最大团就是最大完全子图一般做法就是dfs+剪枝可参考这篇博客： http://www.cnblogs.com/zhj5chengfeng/p/3224092.html下面介绍几个例题： 1、第一道裸题：ZOJ 1492 M

2017-04-03 17:39:04 871

原创【HDU 3068】【manacher模板题】最长回文

传送门：http://acm.split.hdu.edu.cn/showproblem.php?pid=3068思路：manacher模板题复杂度O（n），这题二分+hash或者后缀数组复杂度为O（nlogn）,好像会T详细讲解:https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/e

2016-11-23 23:11:08 464

原创【HDU 5973 && 51nod 1185】【威佐夫博弈+大数】

HDU5973 传送门：http://acm.split.hdu.edu.cn/showproblem.php?pid=5973题意：有2堆石子。两个人轮流拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子，但不可不取。拿到最后1颗石子的人获胜。假设两个人都按照最优的策略取石子。给出2堆石子的数量，问先手是否能赢得比赛。每堆石子的大小≤10^100。思路：对于a

2016-11-21 21:30:10 1181

原创最大子段和及其变形小结

最近做刷51nod的时候，看到了这类题目，挺有意思的，小结一下51nod1049 最大子段和题意：O（-1）思路：经典问题复杂度：O（n）代码：#include #include using namespace std; const int MAXN = 50000+5; int a[MAXN]; int main() {

2016-11-13 00:04:26 1211

原创 bitset在图论上的应用传递闭包【例题gym 100342J & gym 100345H 】

bitset优点：bitset在某些常数优化以及状态保存方面被称之为神器并不为过，主要表现在以下几个方面：1. 状态表示。试想，用一个数来表示状态的极限是64位，而bitset可以保存任意位二进制数，并且修改简单，统计方便，并且支持批量操作。2. 常数优化。图论的题，尤其涉及不带权的邻接图，算法经常动辄 n2,n3 ，这个时候我们可以用n个bitset存储每个点的邻接情况，并进行相应位操作

2016-10-15 14:32:29 1729 1

原创【POJ2891】【一般模线性方程模板题】Strange Way to Express Integers

传送门：POJ 2891题意：给的模数不满足互质，求同余方程组的解思路：同样是求这个东西。。X mod m1=r1X mod m2=r2.........X mod mn=rn首先，我们看两个式子的情况X mod m1=r1……………………………………………………………(1)X mod m2=r2……………………………………………………………

2016-10-11 23:18:32 463

原创【POJ 1006】【CRT（中国剩余定理）模板题】Biorhythms

传送门：HDU1006描述：BiorhythmsTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 130935 Accepted: 41750DescriptionSome people believe that there are th

2016-10-11 22:07:31 1075

原创【HDU1402】【FFT求大数乘法】

传送门：HDU 1402 A * B Problem Plus描述：A * B Problem PlusTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 18015 Accepted Submission(s):

2016-09-25 16:57:37 960

转载三个重要的同余式——威尔逊定理、费马小定理、欧拉定理 + 求幂大法的证明

一、威尔逊定理若p为质数，则p|(p-1)!+1亦：(p-1)! ≡ p-1 ≡ -1(mod p)例题：HDU 2973 YAPTCHA (威尔逊定理及其逆定理)解题报告见http://blog.csdn.net/synapse7/article/details/18728157二、费马小定理假如p是质数，且

2016-09-19 18:38:05 3134

原创【HDU 2255】【KM算法模板题+KM算法详解】奔小康赚大钱

传送门：HDU 2255描述：奔小康赚大钱Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 7453 Accepted Submission(s): 3315Problem Description

2016-09-16 17:11:16 616

原创网络最大流-ISAP算法详解与模板

ISAP算法 ISAP（Improved Shortest Augumenting Path）算法是改进版的SAP算法，如果对效率要求很高的时候，可以用该算法。（1）概述：算法基于这样的一个事实：每次增广之后，任意结点到汇点（在残余网络中）的最短距离都不会减小。这样，我们可以利用d[i[表示结点i到汇点的距离的下界。然后再增广过程当中不断地修改这个下界。增广的时候和Dinic算法类似，只

2016-09-04 16:51:54 5685 1

原创 hdu5748 Bellovin（LIS模板）

传送门：点击打开链接其实就是求以ai（0<=i<n）结尾的最长上升子序列的个数。最小的字典序就是f1,f2,f3......这题O(n^2)做法会超时，需要nlongn,套一下模板就好了~#includeusing namespace std;const int inf = 1000000007;const int N = 100005;int a[N], g

2016-08-20 14:49:25 410

原创 01字典树专题（解决异或最大值问题）不断更新ing~

以前一直以为字典树没有多少用，但是最近一直碰到（难道是以前刷题太少的原因么），其中有一类问题叫做01字典树问题，它是用来解决xor的有力武器，通常是给你一个数组，问你一段连续的异或和最大是多少，正常思路贪心dp啥的都会一头雾水，但是用01字典树就能很快的解决，实现起来也十分方便。贴一个01字典树的普遍模版#define Memset(x, a) memset(x, a, sizeof(

2016-08-12 15:12:57 4039 1

原创线段树全新版【最近更新 9月8日】

修改自：http://www.notonlysuccess.com/在代码前先介绍一些我的线段树风格: maxn是题目给的最大区间,而节点数要开4倍,确切的来说节点数要开大于maxn的最小2x的两倍lson和rson分辨表示结点的左儿子和右儿子,由于每次传参数的时候都固定是这几个变量,所以可以用预定于比较方便的表示以前的写法是另外开两个个数组记录每个结点

2016-08-12 00:20:26 1206 1

原创 KMP算法的经典例题（poj 3461、poj 2752、poj 2406、poj1961）

传送门：POJ-3461最简单的KMP题，找出第一个字符串在第二个字符串中出现次数。#include #include #include #define Memset(x, a) memset(x, a, sizeof(x))using namespace std;const int N=1e6+10;char w[N],t[N];int next[N];int s

2016-08-03 23:48:05 9116

原创 ICML2018论文研讨会记录

2018.7.27Mix &amp;amp;amp;amp; Match - Agent Curricula for Reinforcement learning. ICML 2018. http://proceedings.mlr.press/v80/czarnecki18a/czarnecki18a.pdf transfer learning用于强化学习k越大，模型吸收前面模型的内容越多，训练复杂度越高...

2018-08-01 20:03:27 1531

原创《Automatic Proofreading in Chinese: Detect and Correct Spelling Errors in Character-level》baseline实现

平滑算法解释：平滑算法具体分差值(Interpolation) 和回退(backoff)这两个思想[http://www.shuang0420.com/2017/03/24/NLP%20%E7%AC%94%E8%AE%B0%20-%20%E5%B9%B3%E6%BB%91%E6%96%B9%E6%B3%95(Smoothing)%E5%B0%8F%E7%BB%93/]Katz smoothin...

2018-06-08 18:57:04 720

原创用Fiddler抓取手机APP数据包

Fiddler下载地址1.允许远程连接2.允许监听https3.重启Fiddler这步很重要，不要忘了4.手机配置用ipconfig命令查询当前PC的局域网IP 将手机连接上同一个WIFI，并进行设置：iOS手机：设置 > WIFI > 点击进入连接上的WIFI，在最下面会有HTTP代理(默认情况下使关闭)，打开手动选项，在服务...

2018-03-11 14:39:46 10462 1

原创 2017 UESTC Training for Graph Theory 题解

传送门A题生成树对边排序，枚举最小边，然后不断加边，直到1,n在一个生成树中，用最大边更新答案代码B题 Dijkstra+构造题意：给出一个大小为n的集合S，集合里有n个互不相同正整数. 有q个询问，每次询问是否能选择S中的一些数字 ( 同一个数字可以选择多次,也可以任何数字都不选)，使它们相加的和为m.本题思考的启发点是n和a1的数据比较小对于S集合中的数，例如a1，考虑到如果x能

2017-07-13 01:30:29 670

原创 u盘引导在SSD+HHD配置下安装ubuntu16.04

我的电脑是联想G50系列，C盘ssd安装win10系统，从hhd中分出去一部分存储空间准备安装ubuntu16.04 具体步骤1.先去ubuntu官网下载镜像，然后用utral将镜像刻录到u盘里面参考这里2.我的电脑重启立即按按F2进入bios，按F12进入boot（临时修改引导界面），所以重启之后先按F12，改成u盘导入，然后开始安装ubuntu，后续安装参考这里，系统分区方案参考这里3

2017-06-24 02:07:09 3502

原创 splay专题

参考ppt 参考博客例题： 1.bzoj 1588 题意：每读入一个数，在前面输入的数中找到一个与该数相差最小的一个。把所有的差值加起来。思路：三种操作：插入，求前驱，后驱。代码2.hdu 3487 题意：两种操作：操作1. CUT a b c 表示把数列中第 a 个到第 b 个从原数列中删除得到一个新数列，并将它添加到新数列中第 c 个数的后面操作2. FLIP a b 表

2017-06-12 16:09:09 481

原创网络流专题

1.gym 101061 K建二分图，士兵与地点连边当且仅当士兵喜欢的武器在这个地点出现 ps：一开始对武器拆点搞最大流发现不对，然后重新建最大流，但是绕的有点晕，其实二分匹配就好了。要及时调整思路代码

2017-06-02 14:42:17 316

原创 dp专题

1.gym 101061 F dp[i][j]表示前i枚硬币中两人所得硬币总面额差值为j时的的最小差值，那么对于第i枚硬币有两种情况，给第一个人和给第二个人，进而有两种转移： dp[i][j+a[i]]=min(dp[i][j+a[i]],max(dp[i−1][j],abs(j+a[i]))dp[i][j−a[i]]=min(dp[i][j−a[i]],max(dp[i−1][j],abs(

2017-06-02 13:47:37 344

原创树分治总结

推荐:博客树分治用于解决有关路径的问题。树分治分为点分治和边分治（其实还有一种叫“链分治”，是树的路径剖分思想的更高级的体现，一般链分治的题目都可以用路径剖分解决）。点分治就是每次找到重心，然后把重心去掉，对分成的每两棵树之间分别统计路径信息（以重心的每个相邻点为根，遍历整棵子树即可得到这个根到每个结点的统计信息），就可以知道包含这个重心的所有路径的信息，然后对于剩下的路径就是在子树里面进行

2017-05-29 15:59:50 393

原创斜率优化dp

很好的总结很好的专题斜率优化dp基本上都是可以化到 dp[i]=min(dp[j]+cost(j+1,i)) 这样的形式，二维的就是dp[i][m]=min(dp[j][m-1]+cost(j+1,i)); 概括一下： 1.假设第dp[i]dp[i]两个决策点j,k(j<k)j,k(j<k)，且kk的决策要比jj好接下来证明对于dp[i+1]dp[i+1]及其后面的决策都满足kk的决策要

2017-05-24 20:37:52 420

原创 2017UESTC 数据结构专题题解

传送门 G题题意：给出一个序列，支持单点修改，每次查询一个位置成等差数列中所有数的最大值。思路：等差数列如果公差很大的话，那么整个数列中的数并不会很多；但是如果公差很小，我们就可以用线段树来乱搞。具体方法是对于每个公差维护一个线段树，按照对这个公差取模的值来进行划分。这样询问的时候就在一块了。代码戳这里

2017-05-10 19:51:00 783

原创树形dp专题

1.xidian 1070 树形dp dp[i][j]表示以i为根选j个节点的最大值注意：类似于01背包那样逆推，就不会重复选择相同的子树了代码

2017-05-06 19:30:54 439

原创 qscoj 66 ||2017 UESTC Training for Data Structures D(离线+树状数组)

1.qscoj 66 离线+树状数组。询问，如果只有A数组的话，实际上就是权值线段树或者主席树的裸题了。那么我们其实只要将询问按照A数组从小到大排序，然后依次删除对于>A不合法的，然后用个权值树状数组去查询，就可以了。代码：#include <bits/stdc++.h>using namespace std;#define ff first#define ss second#defi

2017-04-30 21:27:09 416

原创【uvalive-5970】【莫队】

传送门：https://cn.vjudge.net/problem/UVALive-5970题意：给N(10^4)个数，Q次询问(10^5),每次询问[l,r]不同的数的平均值。思路：没有修改操作，数据不大，可以用离线莫队去做，7s水过，非常sb，样例还错了当然也可以线段树做，参考： http://mcginn.lofter.com/post/1d50332c_92ac05a代码：#include

2017-04-12 00:22:33 468

原创【玲珑杯 Round#13 B】【倍增+二分】

传送门：http://www.ifrog.cc/acm/problem/1112?contest=1015&no=1题意：定义一个序列的混乱度为累加和：b[i]*v[i]，b[i]为这个序列中第i小的数，v[]数组是给定的。如果当前加进来的数购车的数构成的序列的混乱度大于m，则将当前的序列扔掉，然后将变量C加一，现在给出要加进来的序列的顺序，和v[]数组，求最终C的值。思路：枚举左端点，二分右端点，

2017-04-12 00:13:27 408

原创划分数dp 小结

小结划分数如何dp1.hdu 1028 整数划分首先，我们引进一个小小概念来方便描述吧，dp[n][m]是把自然数划划分成所有元素不大于m的分法，例如：当n=4，m=1时，要求所有的元素都比m小，所以划分法只有1种：{1，1，1，1}；当n=4，m=2时，只有3种{1，1，1，1},{2，1，1}，{2，2}；当n=4，m=3时，只有4种{1，1，1，1},{2，1，1}，{2，2},{

2017-04-04 23:05:18 1044 1

原创【hdu3652】【数位DP】

【cf 487C】【数论+构造】【根据前缀积取模构造序列】传送门：http://acm.hdu.edu.cn/showproblem.php?pid=3652思路：参考：https://wenku.baidu.com/view/9de41d51168884868662d623.html代码：http://paste.ubuntu.com/24293307/

2017-04-01 21:20:39 537

原创 codeforces 789 div2 题解(AB水题，C dp，D图论)

A题意：你有两种框，每个框可以最多装k重量的物品，但是你每个框不能装不一样的物品。现在地面上有n个物品，问你最少多少次，可以把这n个物品全部装回去。思路：其实就是问你得用多少次框，然后把多少次除以2就好了。每次装k的物品装回去就好了。B题意：给你一个b1,q，再给你一个l，m，和m个数a[i]。然后你需要把不等于a[i]，且小于等于l的数记录下来。思路：我是分类讨论的，一不注意就会被hackC题意：

2017-03-31 15:36:15 562 1

原创【uva 12003 Array Transformer】【分块】

题意：给定一个序列，要求查询一个区间内有多少个数小于v。并且把第p个位置的值改为u * k / (R - L + 1)。思路：单点修改和区间查询。线段树的话还要套平衡树，不会写，也不想写(:зゝ∠)还是分块搞吧。。把n个数分成 sqrt（n）个区间，然后把每个区间内都排序。对于查询的时候，对于完全覆盖的块直接二分查，对于没完全覆盖的两端，直接暴力扫。修改的时候，对于原数据直接改，对于排序后

2017-03-22 23:53:58 302

原创【UESTC 1324】卿学姐与公主【分块】

传送门：http://mozhu.today/#/problem/show/1324思路：这里用分块做的，练练分块。当然这题线段树也可以做。代码：#include <set>#include <map>#include <queue>#include <vector>#include <math.h>#include <iostream>#include <stdio.h>#inclu

2017-03-22 19:51:54 437

原创【HDU 5971】二分染色

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5971题意：有n个人，编号为1-n, 已知X个人是good，Y个人是bad，m场比赛，每场比赛都有一个good和一个bad人结合起来，问这n个人是否能被分成两种人思路：其实就是判断是否为二分图，用染色法判断一下就可以了代码：#include <set>#include <map>#include <qu

2017-03-19 20:09:22 385

空空如也

空空如也