- 博客(399)
- 收藏
- 关注
RSS订阅原创 CodeForces 831E-Cards Sorting(树状数组)
链接：http://codeforces.com/problemset/problem/831/E思路：看成一个环，每次找到一个上次移除位置的前面一个最小值的位置，计算位置差，已经移除的空位用树状数组维护。//QAQ//#pragma comment(linker, "/stack:1024000000,1024000000") #include <bits/stdc++.h>...
2018-04-05 19:31:44
348
原创 POJ-1113-Wall（凸包）
链接：http://poj.org/problem?id=1113大致题意：N个点围成的城堡，求距离城堡大于L处建围墙，求围墙的最短距离凸包问题，考虑到对于一个凸包上的一个x度的角，其需要一个180-x度半径为L的圆弧形状围墙，即求凸包周长+以L为半径圆的周长。//FS//#pragma comment(linker, "/stack:1024000000,1024000000") //#i...
2018-03-15 23:13:27
267
原创 2017-山东省第八届ACM省赛
从第一次的懵懂，第二次的遗憾，到今年的首银，这已经是第三次省赛之旅了_(:з」∠)_，第一次打星星，第二次错失银牌，这次感觉像是补回了上次银牌的样子？ 时间回溯到几天前，第一天热身赛，恩，，，题很水，zp在旁边故意交错几发试试评测反馈，（我还交了几发java测反馈눈_눈），看表热身赛还有一个半小时，然而这时候题都水完了，该测的也已经测完了，后悔没带书看ing，Or
2017-05-13 22:43:25
1273
1
原创 POJ-3415-Common Substrings（后缀数组+单调栈）
链接：http://poj.org/problem?id=3415求两串中长度大于k的公共子串有多少个。公共子串可以通过height求，中间分隔连接两串，将height[i]>=k进行分组，对于一组内的height[i]，且sa[i]属于a串，需要找到ji]-k）,采用单调栈维护一个栈顶最小的height[i]，大于栈顶压入，小于更新。每次针对a/b串找前面的b/a串，跑两
2017-05-04 16:16:58
553
原创 POj-3101-Astronomy（分数GCD+BigInteger）
链接：http://poj.org/problem?id=3101题意：给出每颗行星的运行周期，问多久运行到一条直线上角速度为v = 2*π/T以第一颗行星为参照点则其他行星的相对速度为V' = (Ti- T0)*2π/(Ti*T0)半个周期即可在同一条直线上绕过半个圆周的时间为t = π/V' = (T0*Ti)/((T0 - Ti)*2) n
2017-05-03 21:29:53
605
原创 POJ-2154-Color（Pólya）
链接：http://poj.org/problem?id=2154//#include #pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include using namespa
2017-05-03 20:21:38
423
原创 POJ-3683-Priest John's Busiest Day（2-SAT染色）
链接：http://poj.org/problem?id=36832-SAT求其中一个解，详见2-SAT解法浅析//#include #pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include
2017-05-02 21:18:42
775
原创 JAVA-BigDecimal
构造：BigDecimal(int) 创建一个具有参数所指定整数值的对象。 BigDecimal(double) 创建一个具有参数所指定双精度值的对象。 BigDecimal(long) 创建一个具有参数所指定长整数值的对象。 BigDecimal(String) 创建一个具有参数所指定以字符串表示的数值的对象。方法：add(BigDecimal) BigDecimal对象中的值
2017-05-01 15:00:42
706
原创 HDU-5973-Game of Taking Stones（JAVA-BigDecimal+Wythoff博弈）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5973Wythoff博弈套公式b=(b-a)*(1+sqrt(5))/2,,,,a==b?0:1由于BigDecimal无法开根号，所以手动二分精确根5的小数位。//package zzz;import java.util.Scanner;import java.ma
2017-05-01 13:53:53
707
原创 ZOJ-3963-Heap Partition（贪心）（STL）
链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5595大致题意：用给出的数列a1,a2,a3....an构造二叉树，满足对于下标i和j，有i正序建树模拟一下，找到小于等于当前权值的一个可插入最大值，成为其子节点，找不到则新建树。#include using namespace std;
2017-04-25 19:08:52
707
原创 POJ-3694-Network（Tarjan+LCA+并查集）
链接：http://poj.org/problem?id=3694给出无向图，动态加边，求每次加边后图中桥的个数。缩点求并查集，然后按照DFS序找LCA维护桥的个数。//#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #incl
2017-04-22 13:52:51
666
原创 POJ-3686-The Windy's（KM/费用流）
链接：http://poj.org/problem?id=3686N个订单M个车间，N*M的矩阵给出第i个订单在第j个车间生产所需时间，车间有任务则需等待，求完成所有订单所需的平均时间；对于同一个车间的k个订单，有工作时间t=T1+(T1+T2)+(T1+T2+T3)+...+(T1+T2+...+Tk)，则平均工作时间tav=t/k;有t=T1*k+T2*(k-1)+...Tk ,
2017-04-21 20:54:46
408
原创 POJ-2400-Supervisor, Supervisee（KM+DFS）
链接：http://poj.org/problem?id=2400有n个老板和n个员工，他们彼此有一个好感排名，现在要求选出最好的对应关系使他们平均分值最少输出所有最小权匹配，DFS最小匹配找所有匹配，注意剪枝。//#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include
2017-04-21 19:40:17
481
原创 HDU-2255-奔小康赚大钱（KM）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=2255二分图最大权匹配//#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #in
2017-04-20 20:58:16
239
原创 POJ-3155-Hard Life（最大密度子图）（01分数规划+最小割）
链接：http://poj.org/problem?id=3155求最大密度子图，见论文：算法合集之《最小割模型在信息学竞赛中的应用》P20-26//#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #in
2017-04-19 21:17:28
355
原创 ZOJ-2676-Network Wars（01分数规划+最小割）
链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1676while( ( t=DFS(S,T,INF) ) >=eps)没加括弧wa到哭//#pragma comment(linker, "/STACK:1024000000,1024000000")#include #includ
2017-04-18 19:25:20
369
原创 POJ-2002-Squares（hash）
链接：http://poj.org/problem?id=2002给出坐标系中的点，问最多有几个正方形；枚举其中两个点，找剩余两点是否存在，O(n^2)。#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #includ
2017-04-05 15:49:08
232
原创 Uva-7423-Assigning Workstations（贪心+优先队列）
链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5445资源占用问题，x,y,y+m分别表示开始时间，结束时间，离开时间，开始->结束过程中占用资源1，在结束->离开时间内如有新的进程进入则可以继续使用资源而不占用新的资
2017-04-04 14:18:08
621
原创 HDU-5068-Harry And Math Teacher（线段树）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5068根据每层两个点的到下一层两个点的连接情况，可以得到一个2*2的矩阵，初始矩阵全部联通都为1，不连通为0，显然一段区间内的方案数就是区间内矩阵相乘后的矩阵行列值求和。简单的线段树维护区间矩阵乘积就好。#pragma comment(linker, "/STACK:1024000000,1
2017-04-04 10:54:41
463
原创 HDU-5064-Find Sequence（DP）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5064dp[i][j]表示以第j个为结尾，且上一个为第i个的最长序列长度。由于序列递增，当前i，对于ki不必重复枚举其中一边，总复杂度O(n*n)#pragma comment(linker, "/STACK:1024000000,1024000000")#include #incl
2017-04-03 19:32:45
322
原创 HDU-5067-Harry And Dig Machine（状压DP）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5067DP[i][j]表示在已经经过状态为i的格子的情况下，当前在j点的最短路径；显然有 DP[i][j]=min( DP[i][j], dp[i|k][p] + dis[p][j] )#pragma comment(linker, "/STACK:1024000000,10
2017-04-02 15:11:32
517
原创 POJ-3436-ACM Computer Factory（网络流）
链接：http://poj.org/problem?id=3436拆点求最大流，并求出每边的流量。#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include using n
2017-04-02 12:30:27
302
原创 POJ-3026-Borg Maze（Prim+BFS）
链接：http://poj.org/problem?id=3026水题，注意数组大小，测试数据有点坑。#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include u
2017-03-31 12:39:11
199
原创 POJ-3083-Children of the Candy Corn（DFS+BFS）
链接：http://poj.org/problem?id=3083求沿左墙走到目标点的距离，和沿右墙走到目标点的距离，以及到目标点的最短距离；求两个沿边走的路径DFS，按照上一个点的位置分别顺时针和逆时针优先遍历就好了。#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include
2017-03-30 19:29:51
211
原创 POJ-2049-Finding Nemo（BFS）
链接：http://poj.org/problem?id=2049将坐标系转为格子图，两点之间可能有墙，或者门，也可能什么都没有，没有的花费为0，门的花费为1，问到目标点的最少花费是多少注意题目中的输入范围，四位二进制表示下点四周的边墙情况，然后bfs更新下各点最优值。#pragma comment(linker, "/STACK:1024000000,102400
2017-03-29 20:44:11
228
原创 POJ-1062-昂贵的聘礼（SPFA）
链接：http://poj.org/problem?id=1062具有点权限制的最短路，在松弛度内枚举区间限制跑最短路就好。#include #include #include #include #include #include using namespace std;#define INF 0x3f3f3f3f#define MAXN 510#define M
2017-03-28 16:57:55
375
原创 HDU-5985-Lucky Coins（概率）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5985收敛概率，注意n==1的情况。#include #define MAXN 107using namespace std;double temp[MAXN][300],p[MAXN];int num[MAXN];int main(){ int T; scanf("%
2017-03-24 16:13:01
830
原创 HDU-5988-Coding Contest（费用流）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5988题意：n个点，每个点有一定数量的人和面包，对于每条边有容量c限制可以经过的人数，且在第二个人以后经过路径会有概率p破坏网络，问在所有人都拿到面包的情况下求网络破坏概率的最小值。概率直接取个log变成加法就是裸的费用流。#include using namespace st
2017-03-24 16:08:17
479
原创 HDU-4859-海岸线（最大流最小割）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=4859#include #define MAXN 30007#define MAXM 30007using namespace std;#define INF 0x3f3f3f3fstruct node{ int u,v,next,flow;}edge[MAXM];
2017-03-13 19:45:47
350
原创 HDU-5952-Counting Cliques（搜索剪枝）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5952题意：给定n,m,k-----n个点m条边的无向图，求k个点的完全图个数#include //#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define INF 0x3f3f
2016-11-01 20:06:36
287
原创 HDU-5902-GCD is Funny
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5902题意：给出数组a[]，从中取出3个数，放回其中任意两个数的GCD 两次，直到最后剩下两个数字，问最后剩下的数字可能有什么。题解：跑n-2轮两两GCD，不断更新gcd数组直到无新的数产出。CODE：#include //#pragma comment(linker, "/STACK
2016-10-05 16:16:05
380
原创 HDU-5904-LCIS
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5904题意：求两数串的最长公共子序列，且子序列为1的递增题解：dp[ a[i] ] = dp[ a[i]-1 ]+1 求出两个串的lis然后在其中一个串中直接找就行。CODE：#include //#pragma comment(linker, "/STACK:102400
2016-10-05 14:12:47
484
原创 HDU-5908-Abelian Period（暴力）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5908题意：设SSS是一个数字串，定义函数occ(S,x)occ(S,x)occ(S,x)表示SSS中数字xxx的出现次数。例如：S=(1,2,2,1,3),occ(S,1)=2,occ(S,2)=2,occ(S,3)=1S=(1,2,2,1,3),occ(S,1)=2,occ(S,2)=2
2016-10-03 14:37:35
566
原创 HDU-5894-hannnnah_j’s Biological Test（组合数取模）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5894题意：m个无差别的人坐n个座位的环，要求两人间隔之间空座不小于k，问有多少种坐法。题解：第一个人选择一个位子坐好，然后减去必须空出来的n-m*k个位子，那么剩下的人有C(n-m*k-1,m-1)种方法选择座位，则n*C(n-m*k-1,m-1)，m个人无差别则最后除以m；所以：an
2016-09-23 20:30:29
387
原创 HDU-5901-Count primes（大素数模板）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5901题意：求区间[1,N]的质数的个数(1≤N≤1011)CODE：1，O(n^(3/4))#include #define ll long longusing namespace std;ll f[340000],g[340000],n;void init(){
2016-09-21 18:57:19
304
原创 HDU-5900-QSC and Master（区间DP）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5900题意：给出数组a[]，每个数a[i]对应一个权值val[i]，若相邻两数不互质，则可以消除，消除后剩余两区间合并形成新数组仍可以进行消除操作，问消除的最大权值和题解：预处理出可消除的连续区间，然后区间dp。CODE：#include #define maxn 307#def
2016-09-21 18:42:29
234
原创 HDU-5875-Function
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5875题意：给定数组a[]，m 个询问L,R，求a[L]，依次取模a[L+1]...a[R]后的值。题解：找出每个数后面第一个比他小的数的位置，但在最坏的情况下还是O(mn)。。。CODE：#include //#pragma comment(linker, "/STACK:1024000
2016-09-14 19:02:40
231
原创 HDU-5876-Sparse Graph（BFS）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5876题意：求给定图的补图的单源最短路题解：在原图上判断两点间可达性进行bfs，已经遍历过的点直接删掉CODE：#include //#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#
2016-09-12 20:26:43
288
原创 HDU-5877-Weak Pair（离散+树状数组）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5877题意：给定一棵树求解满足以下条件的点对个数1，对于(u,v)，u为v的祖先节点2，对于(u,v)，有au*av题解：DFS过程中维护a[i]的bit，查找k/a[i]，数据只有10W离散化以下就好。CODE：#include //#pragma comment
2016-09-11 14:42:44
286
原创 HDU-3966-Aragorn's Story（树链剖分）
链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=3966题意：给出一棵树，I C1 C2 K: 把C1与C2的路径上的所有点权值加上KD C1 C2 K：把C1与C2的路径上的所有点权值减去KQ C：查询节点编号为C的权值题解：树链剖分CODE：#include #pragma
2016-09-09 20:26:53
303
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人