Rewinner

未归档

ACM(1) dfsdd(1) DP(6) hash(1) STL(1) 图论(24) 小技巧(4) 思维(6) 搜索(2) 数学(5) 数据结构(16)

/ 注册

全部文章 / 未归档（共69篇）

GCD 【HDU - 1695】容斥定理

给出a,b,c,d,k,求出a<=x<=b, c<=y<=d 且gcd(x,y) == k 的（x,y）的对数。 Input 样例个数T (T <= 3000) 每个样例输入a,b,c,d,k，保证所有的a和c都等于1. (a==1 , c==1 , 0 &...

2018-11-20

0 580

Minimal Ratio Tree HDU 2489

题目链接：传送门题意：给你一个有n个节点的完全双向图，在这张图中找有m个结点的数，使表达式的值最小，并将节点按照字典序输出。做法：看到表达式第一想法是最优比例生成树，但是找不到排序的条件，就换一种方法，题目上给的数据很小，可以尝试着暴力一下，题目按照节点字典序输出，我们可以深搜节...

2018-11-15

0 444

第一周周训 1-1 E大大走格子

大大走格子有一个h行w列的棋盘，里面有一些格子是不能走的，现在要求从左上角走到右下角的方案数。 Input 单组测试数据。第一行有三个整数h, w, n(1 ≤ h, w ≤ 10^5, 1 ≤ n ≤ 2000)，表示棋盘的行和列，还有不能走的格子的数目。接下来n行描述格子，第i行有...

2018-09-23

0 434

HDU 2588

题意很简单，思路却有点难想。从已知条件一步步来分析：因 GCD（X，N）>=MGCD（X，N）>=M 而 1<=X<=N1<=X<=N 可得出结论1，也是该题重要的突破口： GCD（X，N）一定是N的约数这个条件可以给我们一定启发，因为 N 的约数一...

2018-08-05

0 461

HDU 3911 (线段树,区间合并,延迟标记)

题意：就是给你一段由0和1组成的序列，然后有两种操作：0 a b就是问从a到b最长的连续的1的长度为多少，1 a b就是把 [a,b]中的1变为0，0变为1。// 进行一次反转操作，就是将区间0和1ji'l记录的数据对换。：用一个结构体，lmaxn1表示从最左边数连续1的长度，lmaxn0表示从...

2018-07-31

0 375

dij优化

普通的Dijkstra算法复杂度为n平方，当数据量稍大时就会超时，所以诞生了时间复杂度为nlogn的优先队列优化的Dijkstra算法。原来版本有大量时间浪费在通过邻接矩阵找边和搜索当前最短路径中，而优化后的算法中，用结构体Edge存储边信息，省却了找有效边的麻烦。而且采用优先队列，可以快速找到最...

2018-07-22

0 490

矩阵快速幂---矩阵构造

矩阵构造方法 Fibonacci数列：F(0)=1 , F(1)=1 , F(n)=F(n-1)+F(n-2) 我们以前快速求Fibonacci数列第n项的方法是构造常系数矩阵（一） Fibonacci数列f[n]=f[n-1]+f[n-2],f[1]=f[2]=1的第n项快速求法（不...

2018-07-18

0 352

POJ - 2184 Cow Exhibition （01背包中负数的处理）

"Fat and docile, big and dumb, they look so stupid, they aren't much fun..." - Cows with Guns by Dana Lyons The cows want to prove to ...

2018-07-08

0 342

Codeforces 979B

题意：给出三个字符串，每个字符串长度相同，给出n，要求在n轮内，每一轮改变一个字符。问最后哪个字符串中拥有最多相同的字符，即美丽度最大。思路：题中给出了样例（abcdabc）//美丽值为2，美丽值可以是（abc）（a）（b）（c）。所以说我们只需要找出每一个字符串中出现次数最多的字符...

2018-05-15

0 528