标签:哈希

【题解】 [SDOI2008]郁闷的小J 树状数组 + 哈希表 LUOGU – 2464

1. 题目

传送门= ̄ω ̄=

2. 题解

我做这题的历程:

  1. 普通线段树套平衡树(map),70分
  2. 半递归式(修改变为递推)线段树套平衡树(map),80分
  3. 树状数组套平衡树(map),90分[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 Squares 哈希 POJ – 2002

1. 题目

传送门= ̄ω ̄=

2. 题解

写完才发现原来正方形的边不一定平行于x或y轴。。。
首先无图言diao:

如图,设正方形左上角的点的坐标是(x1,y1),右上角的点是(x2,y2)[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【考试总结】stl大法好,弃c转c++保平安!

三个半小时五道题,CY说考的就是心理素质...
考试策略
做题顺序:T5->T3->T1->T2->T4
T5是哈希水题,花30分钟搞定,T3是一道搜索,花了30分钟,不过剪[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 九数码游戏 BFS 哈希 LUOGU – 2578

1. 题目

传送门= ̄ω ̄=

2. 题解

就是个八数码问题,改了一下变换方式而已。同样是bfs+哈希记录状态。
哈希方法就是把数码的每一个格子里面的数字作为哈希值的每一位数字
哈希可以康托展开,[......]

[继续阅读= ̄ω ̄=]

Read MoreView 1 Comment

【题解】 方程的解数 哈希 中途相遇法 CODEVS – 1735

1. 题目

传送门= ̄ω ̄=

2. 题解

首先如果暴搜,1506的复杂度显然要gg
那么就中途相遇即可。
首先移项,把右边的n/2个项移动到等号右边,这些项的系数全部都乘以-1就行了
然后用df[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 RY哥查字典 哈希 CODEVS – 2875

1. 题目

传送门= ̄ω ̄=

2. 题解

搞个set哈希一下就行了,没啥好说的

代码:

Read MoreComment

【题解】 Crazy Search 哈希 POJ – 1200

1. 题目

传送门= ̄ω ̄=

2. 题解

傻吊出题人,范围不写清楚
数据比较水,乱搞哈希就能过。
字符串哈希一般使用等比数列哈希
不过tmd比例必须用题目给出的nc(脑残),不然过不了。
鬼知道[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 单词背诵 哈希 CODEVS – 3013

1. 题目

传送们= ̄ω ̄=

2. 题解

首先搞个set哈希一下存在的单词,对于文章中不存在的单词直接跳过就行了。
最普通的做法是枚举文章起点、终点,判断是否合法。然而会超时。
我们现在只枚举文[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 排排站 哈希 CODEVS – 1247

1. 题目

传送们= ̄ω ̄=

2. 题解

首先设$sum[i][j]$FJ的奶牛1~n中,有属性j的有多少头。显然这就是个前缀和(都说了是sum了)。
设区间$[l+1,r]$是符合条件的(即是[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 低价购买 动态规划 哈希 LUOGU – 1108

1. 题目

传送门= ̄ω ̄=

2. 题解

一开始看错题以为是统计条数不用判重。。。
统计最长下降子序列条数且不能有重复序列。。。
最先想到hash一下。。。
可是显然,$2^{31}$次方连in[......]

[继续阅读= ̄ω ̄=]

Read MoreComment