uvalive专题

CSU 1623 Inspectors（二分图最大权匹配 KM算法）（UVAlive 6879）

题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1623 选用一些边覆盖所有的点使得这些边的权值和最小比赛时的想法是用一般图最大权匹配样例也过了但是提交总是WA 看kuangbin模版中写的是点的个数必须是偶数。。是不是有可能是这个原因改用二分图最大权匹配之后就过了。。。。 #include <cstdio>

UVALive 6493 - Round Robin

题目链接：题目链接就是初学编程的经典例子： N个小孩围成一个圈，给出一个数T，每次数到一个小孩，该小孩就得一分；数到T的小孩退出。。。但这里不同的是结束条件不再是只剩最后一个小孩，而是当剩余所有小孩的分数都相同时结束，并输出剩余的小孩数，和他们的得分组队做题，我在这道题上坑了很久。。。原因不是我不知道怎么做，而是想着优化模拟，比如N=5，T=17时，第一次可以判断每个小孩肯定

UVALive 6499 - sort me

题目是PDF文档格式的，所以直接贴题目链接吧：题目链接一般我们对字符串排序是根据ABC……XYZ的字母序进行排序，现在题目给出新的字母序，和待排序的字符串；要求根据这些新的字母序题意是给出新的排序后的字符串我想一般人的想法肯定是类比ABC……XYZ序列，再排序吧我的想法就是为每一个待排序的字符串关联一个字符串，在这个关联字符串中保存当前字符串对应的ABC……XYZ序

【UVAlive】康托展开的思想

题目链接：点击打开链接题目大意：就是给你一个n 求0~n之间的数的k-进制和（-k）进制相同的数目题目分析：要是的k和（-k）进制的数相同，那么就是在转化为k（-k）进制之后，在奇数位上为全零。对于n在转化为长度为len的k进制数后从最高位开始“递归”看即康托展开的思想。 #inclu

UVALive 4513 Stammering Aliens (hash+二分 or 后缀数组)

大白书上的一道例题，后缀数组的模板题吧，今天想练练hash，结果就wa+Tle了一脸。还真没见过不卡自然取模，而卡自行取模的题，今天算是见到了。。取了好几个x，还是发生了碰撞？！题意：让你根据所给字符串，找出至少出现m次的最长字符串，输出最长的长度和起始位置的最大值。思路：字符串hash+二分。（等学会了后缀数组再来套下模板）二分len，然后判断长度是否合法。判断

UVALive - 2191 Potentiometers

题意：S操作将x改为y，M操作求[x,y]的和思路：稍加改动一下树状数组就行了，当然线段树也可以 #include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int MAXN = 400005;int n,t[MAXN];int lowbi

UVALive - 3942 Remember the Word （Trie）

题意：给你一个有S个不同单词组成的字典和一个长字符串，把这个字符串分解成若干个单词的连接，有多少种方法思路：转化为Trie树的形式储存，用d(i)表示字符从i开始的字符串的分解方案，每次搜索到一个单词末的时候就可以累加了 #include <iostream>#include <cstdio>#include <cstring>#include <algorithm>const

UVALive - 3644 X-Plosives

题意：每个化合物都是有两种元素组成的，如果车上存在k个简单化合物时，如果它和已装车的化合物形成易燃物的话，你就应该拒绝装车，否则装车，输出没有装车的个数思路：简单的并查集应用 #include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const in

UVALive - 3135 Argus

题意：有一系列的事件，它每Period秒钟就会产生编号为qNum的事件，你的任务是模拟出前k个事件，如果多个事件同时发生，先处理qNum小的事件思路：用优先队列模拟 #include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <algorithm>using namespace s

uvalive 2088 - Entropy(huffman编码）

题目连接：2088 - Entropy 题目大意：给出一个字符串，包括A~Z和_，现在要根据字符出现的频率为他们进行编码，要求编码后字节最小，然后输出字符均为8字节表示时的总字节数，以及最小的编码方式所需的总字节数，并输出两者的比率，保留一位小数。解题思路：huffman编码。 #include <stdio.h>#include <string.h>#

uvalive 2949 - Elevator Stopping Plan(贪心+二分）

题目连接：2949 - Elevator Stopping Plan 题目大意：某个抠门的公司只有一个电梯，现在有n 个人从1楼，他们有各自想要到达的楼层，然后电梯每上一楼需要4 秒，每在一个楼层开门需要10 秒，然后然爬楼梯的话需要20一楼。问，如何用最短的时间让所有人都到达各自想要到的楼层。解题思路：因为人可以爬楼梯，所以可以在某个楼层下楼之后走楼梯到达想要到的

uvalive 2519 - Radar Installation(区间选点问题）

题目连接：2519 - Radar Installation 题目大意：给出n和半径r，然后给出n个坐标，现在要求在x轴选出最少的点，以这些点为圆心，半径为r画圆，要求将所有点均在画的圆内。解题思路：区间选点问题，就是变形了一下。 #include <stdio.h>#include <string.h>#include <math.h>#includ

uvalive 3971 - Assemble(二分搜索 + 贪心）

题目连接：3971 - Assemble 题目大意：有若干个零件，每个零件给出的信息有种类，名称，价格，质量，现在给出一个金额，要求在这个金额范围内，将每个种类零件都买一个，并且尽量让这些零件中质量最小的越大，输出质量最小的值。解题思路：首先可以用二分搜索确定质量，然后在搜索的过程中要判断这个质量是否能被满足，判断函数可以用贪心，在每一类的零件中选择价格

uvalive 3635 - Pie(二分搜索）

题目连接：3635 - Pie 题目大意：有m个派，要分给n + 1个人，要求每个人拿到的大小相同，并且每个人的派必须是一整块，不能说分别从两个派切出一块凑成。现在给出m个派的半径(派均为圆柱，高为1），输出每人可以拿到的最大派的体积。解题思路：二分查找。 #include <stdio.h>#include <string.h>#include <m

uvalive 2322 Wooden Sticks(贪心）

题目连接：2322 Wooden Sticks 题目大意：给出要求切的n个小木棍，每个小木棍有长度和重量，因为当要切的长度和重量分别大于前面一个的长度和重量的时候可以不用调整大木棍直接切割，否则要进行调整。现在要求求出一个序列，使得调整的次数最少，输出调整的次数。解题思路：将n个小木棍先按照长度和重量的大小排序，然后按照顺序将小木棍分堆，可入堆的要求是长度和重量大于当

UVALive 6428 A+B 【扩展欧几里得】

题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4439 题目大意：给出a，b，S三个数，每次可以选择从a的位置加到b上，也可以从b的位置加到a上，问a或者b的位置上能否达到S。比如：给出a和b，可以得到的是

Problem on Group Trip UVALive - 7219 （模拟+优先队列处理）

点击打开链接题目大意：有三个浴池s1,s2,s3,有n个人。每个人在每个浴池中所呆的时间为s[i].m1,s[i].m2,s[i].m3. 每次进浴池的时候要按n个人的序号的大小进行排队。 3 10 25 15 0 0 25 0 15 10 例如上面这组数据，有三个人，第一个人在s1中的时间是10，在s2中的时间是25,在s3中的时间是15， 0表示这个人不需要再该浴池中，而且每

Sum of xor sum UVALive - 8518 —— 求区间所有子区间异或和

This way 题意：给你一些数，每次问你从l到r这个区间的所有子区间异或和是多少。题解：这种题目总是会把自己绕进去啊，看了别人的题解发现和自己想的差不多，但是自己还是没有想出来。这种题目的话一般就是看每个数的每一位的贡献，这一位只有在奇数个区间内才有贡献。那么对于这一道题目来说，答案的计算方法可能是sum[r]-sum[l]-（左区间对右区间的影响）。那么为了求出sum数组，

LOL UVALive - 8521 —— 状压DP

This way 题意：现在有100个英雄，有5个人打人机正在进行办选局，5个人拥有的英雄都以01的方式告诉你，每个人的办选不同视为不同情况，也就是说玩家1选了德莱文和玩家二选了德莱文是两种情况，玩家1选a办b和选a办c是两种情况，但是电脑无视顺序，问你有多少种办选的情况。题解：这道题过了好多人。。本来是不想写题解来着，但是状压DP的话还是有写一写的价值的。因为玩家办人是按照排列情

LOVER II UVALive - 8522 —— 线段树区间比较的方法

This way 题意：给你n个女生和m个男生的值，如果第i个女生的值和第j个男生的值相加>=k，他们就可以在一起，现在有q次询问，每次问你l-r的区间内的男生能否将所有女生拿下。题解：这题我想了很久啊，到结束过10分钟才想出来，但是有点复杂，就不敲了。看了别人的代码感觉和我差不多，但是方法比我简单，很优秀，推崇。首先将所有a变成k-a，为什么，因为直接比较大小一般比相加再比较大小

UVALive 3683/UVa 1380 A Scheduling Problem（树形DP）

题意：有n（n<=200）个恰好需要一天完成的任务，要求用最少的时间完成所有任务。任务可以并行完成，但必须满足一些约束，约束分为有向约束和无向约束两种，其中A->B表示A必须在B之前完成，A-B表示A和B不能在同一天晚上。输入保证约束图是将一颗树的一些边定向之后得到的。分析：参考紫书P297-298，写的很详细。算是一道比较复杂的树形dp了。 LRJ代码： #include<bits

UVa 1513 / UVALive 5902 Movie collection (树状数组)

1513 - Movie collection Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=448&page=show_problem&problem=4259 https://icpcarchive.

Arrangement for Contests UVALive - 8519

点击打开链接贪心的思想线段树操作每次取区间最小值然后拿掉这个最小值并不影响区间内非最小值的匹配 #include <bits/stdc++.h>using namespace std;#define N 0x3f3f3f3fstruct node1{int l;int r;int minn;int pos;int laz;};struct node2{int minn;i

Today Is a Rainy Day UVALive - 7263

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5275 给两个串s1 s2 有两种操作一是把单个字符改变二是吧一种字符改变问最少几次操作将s2变为s1 第二种操作肯定是越多越好预处理第二种操作各个状态与原始状态123456的距离

UVALive - 8325 Barareh on Fire

UVALive - 8325 Barareh on Fire 题目链接题目大意：以一个样例来说明， 7 7 2f-------f---f-----f---------------f---s---t----f- 7 7代表图有7行7列。图中，f表示该点有火，s表示起点，t表示终点，-为空地。 2表示火向四周蔓延一次所需要的时间为2秒，火蔓延一次，会同时向8个

uvalive 5781 Chain of Fools

竟然没有读懂题意，一个很简单的题到比赛结束都没有写。。。算是一个教训吧。 /** Author: stormdpzh* Created Time: 2012/5/26 21:01:58*/#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <cmath>#include