- 博客(132)
- 收藏
- 关注
RSS订阅
原创 Gym - 101170J 网络流好题
题意：太空探测器有s个传感器，q个保存数据的队列，n个消息传递的事件，每个传感器对应一个队列，表示传感器收集到的数据保存在相应的队列当中，一个队列可能对应多个传感器。对于一个事件，它获取所有队列中的信息，然后传递到地球。在每个事件的间隔中，传感器会不断的收集数据，在传递事件进行时，传感器不会收集数据，问最后传递到地球的数据和传感器收集的数据是否相同。分析：题意很难读，场上读了快两个小时，到...
2019-07-31 16:37:57
279
原创 旋转卡壳 POJ - 2187 gym101635K
POJ - 2187（求凸包直径）#include <iostream>#include <algorithm>#include <cstdio>#include <map>#include <set>#include <vector>#include <cstring>#include <...
2019-03-26 19:26:43
215
原创 扫描线算法 求矩形面积交并和周长并
矩形面积并 HDU - 1542#include <set>#include <map>#include <list>#include <cmath>#include <queue>#include <vector>#include <cstdio>#include <cstring>...
2019-03-26 19:24:10
434
原创 UVALive 4589 Asteroids (三维凸包&&重心)
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <map>#include <vector>#include <queue>
2019-02-26 21:41:02
250
原创 UVALive 3890 Most Distant Point from the Sea (半平面交)
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <map>#include <vector>#include <queue>
2019-02-26 14:22:05
165
2
原创 UVA 1633 Dyslexic Gollum (状压dp)
分析：dp[i][j]表示当前为i长度，长度为k的后缀状态，有多少个串。考虑一下k和k+1长度的串是否为回文串即可代码：#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include &...
2019-02-25 21:53:48
179
原创 UVA 1343 The Rotation Game (IDA*)
分析：IDA*往下搜就行了，刚开始想不写估价水过去，想多了，还得写估价。我们可以发现，每旋转一次，不同的数字最多会减少1，即相同的数字最多会增加一。所以我们找到1，2，3中目前最多的那个数的数目，然后用8减去这个数，就是我们至少需要旋转的次数。代码：#include <iostream>#include <cstdio>#include <cstring...
2019-02-21 15:38:31
206
原创 求LCA的三种方法
1.Tarjan O(n+q) HDU - 2586#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <map>#include <vector>#
2019-02-20 21:12:28
553
原创 二维凸包 Andrew算法
凸包：二维平面内，给定n个散乱的点，求一个最小凸多边形（凸包），使得n个点都不在凸多边形外。这里介绍 Andrew算法求解凸包步骤：首先将点排序（x从小到大，如果x相同，y从小到大），删除重复点，到到点集p1,p2,...... 首先将p1,p2放进凸包里。从p3开始，当新节点在前进方向的左边时继续，否则依次删除最近加入到凸包中的点，直到新点在左边，具体如下图：一个7个...
2019-02-19 23:16:32
581
原创 极角排序
极角排序这里的极角就是我们高数上所学习的极角坐标系中的极角（先来复习一下），极角坐标系中还包括极轴和极径，如下图：其中射线OX叫做极轴，规定正方向（一般为逆时针方向）。点O于空间中一点M连接，所称角θ为极角，这条长度为ρ的线段叫做极轴，这两者组成坐标（ρ，θ）为点M在此坐标系下的极坐标。极角排序就是根据极坐标对点进行排序的操作极角排序的常用的三种方法1.atan2()函数atan2(...
2019-02-19 20:58:28
1603
原创 二维几何基础
二维几何基础常用定义struct Point{ double x,y; Point(double _x=0,double _y=0):x(_x),y(_y){}};typedef Point Vector;Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}Vector operat...
2019-02-19 14:08:03
316
原创 UVA 1601 The Morning after Halloween (BFS/双向BFS)
单向BFS 1150ms#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <map>#include <vector>#include &
2019-02-18 15:28:36
179
原创 SCU 4438 Censo (字符串hash)
题意：在串b中不断的删除串a，输出剩余的串分析：hash+前缀和代码：#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <map>#include <...
2019-02-17 19:39:14
882
原创 HDU 2222 Keywords Search (AC自动机模版)
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <map>#include <vector>#include <queue>
2019-02-17 17:24:33
134
原创 Gym 101864J Non Super Boring Substring (manacher)
题意：求一个串有多少个字串不含长度至少为k的回文串#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <map>#include <vector>#i
2019-02-17 14:54:42
326
原创 HDU 2595 Simpsons’ Hidden Talents (扩展kmp)
题意：给出串s1,s2 求是否s2的一个后缀等于s1的一个前缀分析：kmp和exkmp都行#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <map>#inc...
2019-02-16 21:30:02
201
原创 UVA 10801 Lift Hopping (最短路)
分析：题目规定了换乘的时间，所以这题就与根据时间的流逝没有关系的，变成了一个最短路问题，每个状态有两个属性，一个是所在电梯 i ，所在楼层 j ，以为本题的数据较小。可以用 i * 100 + j 来表示状态。然后就是求个最短路就行了#include <iostream>#include <cstdio>#include <cstring>#incl...
2019-02-10 17:39:07
209
原创 UVA 1660 Cable TV Network (割点)
题意：求无向图的点连通度分析：拆点，连一条容量为1的边，其余的边容量为inf，枚举源点和汇点。这样拆点之后一个点就变成的一条边，可是当成割边来做。#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm&g...
2019-02-10 15:24:05
219
原创 UVA 1658 Admiral (费用流+拆点)
分析：把每个点分为 n 和 n' ，两点之间连一条容量为1，费用为0的边，这样就能保证一个点只能被经过一次。#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <map&...
2019-02-10 13:33:29
215
原创 UVA 10570 Meeting with Aliens (枚举)
分析：枚举序列起点和升降顺序，我写的很暴力，没有什么优化的地方。。。#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <map>#include <vect...
2019-02-09 23:37:50
147
原创 UVA 753 A Plug for UNIX (网络流二分图匹配)
题意：有n个插座，m个插头，k种不同的转换器，只能相同名字的插头和插座才能匹配，问最少剩余多少个插头无法匹配。分析：用floyd算出使用使用转换器之后插头 i 能否插到插座 j 上，源点和插头连容量为1的边，插座和汇点连容量为1的边，插头和插座连容量为inf或者为1的边都行。然后跑一个网络流，本质上是二分图匹配。结果就是m-最大流代码：#include <iostream>...
2019-02-09 20:22:56
170
原创 UVA 658 It's not a Bug, it's a Feature! (最短路)
题意：假定有n个潜在的bug和m个补丁，每个补丁用长为n的字符串表示。首先输入bug数目以及补丁数目。然后就是对m个补丁的描述，共有m行。每行首先是一个整数，表明打该补丁所需要的时间。然后是两个字符串，地一个字符串是对软件的描述，只有软件处于该状态下才能打该补丁该字符串的每一个位置代表bug状态（-代表该位置没bug,+代表该位置有bug，0表示该位置无论有没有bug都可打补丁）。然后第二个字符串...
2019-02-09 17:16:54
216
原创 UVA Sum of Different Primes (数论+dp)
题意：给出一个数，用k个不同的素数组成他，素数不能重复，求有多少种方法分析：首先打一个表，然后用类似01背包的方法来写dp[i][j]表示的是数字i用j个数字来组成的方法数，状态转移方程如下dp[i][j] = sum{dp[i-prime][k-1]};for(int i=0;i<tot;i++){ for(int j=maxn-1;j>=prime...
2019-02-06 23:04:24
166
原创 UVA 10817 Headmaster's Headache (状压dp+记忆化搜索)
题意：这间学校开设S门课，给出校长已经有的师资n，然后再给出m个应聘者，每门课至少有两名任课老师，求最少需要的雇佣工资。分析：一开始没什么头绪，看到网上说01背包，一想是那么回事。还有一个技巧是把2*s位的二进制数表示状态，假设有两门课，那么1100表示两门课都有两个以上老师，0011表示这两门课都只有一个老师。根据现有老师算出初始状态，然后转移，转移终点是到达1100的状态（假设有两门课）。...
2019-01-29 17:40:07
179
原创 UVA 1218 Perfect Service (树形dp)
题意：给出一个图，每个点如果不是服务器，那么他必定和一个且只能和一个服务器相连，问最少有多少个服务器分析：dp[u][0] : u是服务器 dp[u][1] : u不是服务器，但是u的父亲是服务器 dp[u][2] : u不是服务器，且u的父亲也不是服务器状态转移：当前节点为u，子节点为v dp[u][0] = sum{...
2019-01-28 17:56:07
146
原创 UVA 1220 Party at Hali-Bula (树形dp)
紫书P282 9-13#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <map>#include <vector>#include <
2019-01-28 17:43:55
178
1
原创 UVA 12186 Another Crisis (树状dp)
题意：有一家公司，有一个老板和n个员工，老板标号为0，每个员工都有它的上级，工人(最底层)想联名给老板上书，但是一个员工只有它的下级超过t%时它才会递给它的上级，求接下来要想传递信息给老板，至少需要多少个员工签字。分析：入门树状dp，算下这个人u如果要同意，那么dp[u] = 前c=(K*T - 1）/100 + 1的人的dp[v]相加；状态转移:dp[u]=sum{ dp [ son[...
2019-01-28 17:30:25
174
原创 UVA 116 Unidirectional TSP （dp）
题意：给定一个n*m的矩阵，要求从第一列的任何一行出发，每次沿右或右下或右上到达后面一列，最后到第m列任何一行整个路程的最小值，并且要求是字典序最小的。、分析：正推不好做，选择逆推，同时记录路径代码：#include <iostream>#include <cstdio>#include <cstring>#include <cmath...
2019-01-27 22:47:07
188
原创 UVA 1347 Tour (记忆化搜索dp)
题意：见紫书分析：可以看成两个人一起走，dp[i][j]表示已经走过了max(i,j)个点还剩多长距离到达最后的点，规定i走在j前面，走的时候只往下走max(i,j)+1的那个点即可，最后的状态就是一个人在第n-1个点，求出另一个人在其他点时的最后所剩距离，然后dfs代码：#include <iostream>#include <cstdio>#inclu...
2019-01-27 22:43:26
114
原创 UVA 437 The Tower of Babylon (记忆化搜dp)
题意：有集中长方体，将其摞在一起，上面的底面面积要严格小于下面，每种长方体可以无限次使用，问最高可以摆放多高分析：DAG最长路算法，将一个长方体当成3个长方体使用，不用建边，转移的时候判断一下大小关系即可，最后dfs代码：#include <iostream>#include <cstdio>#include <cstring>#includ...
2019-01-27 22:39:01
133
原创 UVA 1025 A Spy in the Metro (dp)
题意：紫书分析：三种决策转移一下，时间逆向。代码：#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <map>#include <vector>
2019-01-27 22:35:14
127
原创 UVA 11925 Generating Permutations (贪心)
题意：给出一个排列，有两种操作1.交换前两个 2.将第一个数移动到最后，通过不超过2*n^2次操作使得一个升序的排列变成所给排列（紫书题意有误）分析：逆向来做，通过操作使得所给序列变为生序，对于操作1不用改变，对于操作2可以将后面的数拿到前面来，最后逆向输出操作序列。代码：#include <iostream>#include <cstdio>#inclu...
2019-01-27 22:32:52
180
原创 UVA 10285 Longest Run on a Snowboard（记忆化搜索）
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <map>#include <vector>#define FRER() freopen("
2019-01-16 19:06:29
123
原创 UVA 1610 Party Games(构造)
分析：分情况讨论太复杂。可以从每个字母下手，从‘A’开始构造，讨论下特殊情况即可#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <map>#include &l...
2019-01-16 17:46:29
182
原创 UVA 1608 Non-boring sequences(瞎搞)
用map和两个数组保存和一个数左右距离最近相同的数的位置#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <map>#define FRER() freopen(...
2019-01-16 16:41:46
130
原创 UVA 12174 Shuffle (滑动窗口)
题意：有一个播放器用于播放音乐，现在给出s（已有曲目的数量），n给出记录的长度。播放器有随机播放的功能，每次生成一个1~s的随机系列进行播放，当s首歌全部播放完后，重新生成一个播放序列。现在有一段长度为n的播放记录片段（即不完全，前后可能还有歌曲），问下一次随机排序的位置有几种可能。（这题意读了好久。。）分析：可以开一个n+s的数组，从后向前处理，判断每一个窗口是否能成为一个播放列表，之后枚举...
2019-01-16 15:20:20
155
原创 2018EC-Final 总结
EC-FINAL总结 周六考完四级，火急火燎的赶往了西安，坐了一天的飞机和车，脑子涨涨的，到了宾馆放下东西，出去吃个饭回来收拾收拾就睡觉了，梦到了我第二天睡到了10点，没赶上比赛，心情极度失落……还好只是个梦！ 进入赛场，赛场布置的很好，桌子也大，给了每个人一个方便的活动空间，好评！比赛开始，我和祥正开始读题，天心调试机器，由于没打热身赛，我们对机器比较陌生，中...
2018-12-21 17:52:31
1238
4
原创 7-6 银行排队问题之单队列多窗口加VIP服务 （30 分）
7-6 银行排队问题之单队列多窗口加VIP服务 （30 分）假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。有些银行会给VIP客户以各种优惠服务，例如专门开辟VIP窗口。为了最大限度地利用资源，VIP窗口的服务机制定义为：当队列中没有VIP客户时，...
2018-12-21 17:50:35
2247
原创 7-15 字符串关键字的散列映射 （25 分）
7-15 字符串关键字的散列映射 （25 分）给定一系列由大写英文字母组成的字符串关键字和素数P，用移位法定义的散列函数H(Key)将关键字Key中的最后3个字符映射为整数，每个字符占5位；再用除留余数法将整数映射到长度为P的散列表中。例如将字符串AZDEG插入长度为1009的散列表中，我们首先将26个大写英文字母顺序映射到整数0~25；再通过移位将其映射为3×322+4×32+6=32...
2018-12-06 21:38:10
1096
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人