Rewinner

分类

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

/ 注册

全部文章（共136篇）

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

Karen and Coffee 差分+前缀

题目链接：传送门题意：给你n个区间，一个K值和q次询问，输出区间中重复次数>=k的点的个数。做法：这道题有一个巧妙做法，输入区间（l，r）时，将数组的下标为 l 的 +1，r+1 的 -1 （假设数组为 coffe ,初始化为0，即 coffe[l]++,coffe[r...

2018-11-14

0 424

【HDU 1811】 Rank of Tetris 并查集+拓扑

题目链接：传送门中文题目就不阐述题意了，我最开始的想法是种类并查集，但是细想一下，发现并不可行，因为题目没有告诉有多少类型。做法：关键问题是处理等号的两个点，其实两个点相等，就相当于这两个人的排名是一样的，我们用并查集搞定这么些个相等排名的点，之后把有全序关系的点入度入图，然后拓扑排序走一发...

2018-11-05

0 378

【HDU - 1598】 find the most comfortable road

题目链接：传送门题目是一道中文题目，大概题意：给一些双向边，多次询问从起点s，到终点e，（权值max-权值min）的最小值。本题的正确做法：并查集+思维（暴力求解，不会超时） ///并不是最小生成树做法：题目求最小值与最大值的差值最小，我们可以将权值从小到大排序，然后枚举最小...

ACM

2018-11-04

0 429

2015上海现场赛 HDU 5573

这是一道在克隆赛碰到的题，当时看题队友以为是树形dp或者是暴搜，想了一下都没有思路，其实是一道 " 思维+二进制 "。题目链接：传送门题意：给你一棵有K层的满二叉树，让你从根节点开始走（根节点为1），经过K个节点（包括根节点），走到叶子节点，途中经过节点的值，...

2018-10-23

0 494

hash算法

计算理论中，没有Hash函数的说法，只有单向函数的说法。所谓的单向函数，是一个复杂的定义，大家可以去看计算理论或者密码学方面的数据。用“人类”的语言描述单向函数就是：如果某个函数在给定输入的时候，很容易计算出其结果来；而当给定结果的时候，很难计算出输入来，这就是单项函数。各种加密函数都可以被认为...

hash

2018-10-22

0 590

区间DP HDU4632

这是我做的第二道区间DP题，开始把题意读错了，导致一直没有思路题意：给你一个字符串，求里面的回文子序列的数量mod10007. 传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4632 因为是判断回文串，所以跟区间的头和尾的字符相关 ...

dfsdd

2018-10-15

0 439

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

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

2018-09-23

0 434

二分图

关于最大匹配，最小点覆盖，最少路径覆盖和最大独立集的总结 (1)二分图的最大匹配匈牙利算法 (2)二分图的最小点覆盖二分图的最小点覆盖=二分图的最大匹配求最小点覆盖：从右边所有没有匹配过的点出发，按照增广路的“交替出现”的要求DFS。最终右边没有访问过的点和左边访问过的点组成最小点覆...

2018-08-06

0 603