- 博客(36)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 CodeForces-967C（二分查找最近值）
链接：CodeForces-967C题意：n*m的楼房，cl个楼梯，ce个电梯，除了电梯的最大速度是v外，其他速度都是1。给出q次询问，回答(x1, y1)到(x2, y2)，最少需要多少时间？题解：同层直接求距离，不同层二分查找最近的楼梯与电梯，选最快的。#include <bits/stdc++.h>using namespace std;const double EPS =...
2018-04-30 10:25:33
389
原创 CodeForces - 964D（DFA+贪心）
链接：CodeForces - 964D题意：给出一颗树，每次可以删除任意一个度数为偶数的节点，问是否可以将所有节点删完？题解：每次只能删度数为偶数的节点，故每次只能减少偶数条边，所以只有奇数点的树可以被删完。先用DFS扫一遍，将每个点的子树的节点数处理出来，然后跑DFS，先只跑偶数点的子树个数，跑到底，如果此点不可被删则返回FALSE，否则删除此点继续后继续往下跑。#include <bi...
2018-04-28 20:58:44
293
原创 CodeForces - 964C（等比数列求和+逆元）
链接：CodeForces - 964C题意：求 n∑i=0sian−ibi∑i=0nsian−ibi by 109+9109+9 值。s[i]为+1或-1。题解：可证：每k项的和相差(b/a)^k。等比数列求和加逆元。逆元不一定要最后一步用的，而是每步都可以用。#include <bits/stdc++.h>using namespace std;const double EP...
2018-04-26 20:45:54
369
原创 2018年华南理工大学程序设计竞赛：K-小马哥的超级盐水（折半查找）
链接：2018年华南理工大学程序设计竞赛：K-小马哥的超级盐水题意：小马哥有杯盐水，第杯有单位的盐和单位的水。小马哥很无聊，于是他想知道有多少种这杯盐水的非空子集，倒在一起之后盐和水的比是。题解：折半查找。maxn = 35，直接枚举肯定会TLE，折半后时间复杂度就够了。(A1 + A2) / (B1 + B2) = x / y; A1 * y - B1 * x = B2 * x - A2 * ...
2018-04-21 12:56:25
441
原创 第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛：L-K序列（DP）
链接：第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛：L-K序列题意：给一个数组 a，长度为 n，若某个子序列中的和为 K 的倍数，那么这个序列被称为“K 序列”。现在要你 对数组 a 求出最长的子序列的长度，满足这个序列是 K 序列。 题解：看代码。#include <bits/stdc++.h>using namespace std;const double EPS ...
2018-04-18 19:14:03
198
原创 2018年东北农业大学春季校赛：L-wyh的天鹅（Treap）
链接：2018年东北农业大学春季校赛：L-wyh的天鹅题意：插入元素，删除元素，查找第K大。题解：Treap。#include <bits/stdc++.h>using namespace std;#define Lc (o -> Ch[0])#define Rc (o -> Ch[1])#define val (o -> v)#define pre (o...
2018-04-18 18:55:42
159
原创 第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛：B-合约数（DFS）
链接：第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛：B-合约数题意：给出一个树，树的节点编号1-N，每个节点有个val，定义F(i) = 节点i的子树的节点中的val是val[i]的合约数的个数（包括节点i）。合约数：若x是y的约数，且x是合数，则称x是y的合约数。求 对1e9+7取模后的结果。题解：DFS。直接遍历树，遍历时标记非合数节点的val的个数，然后逆求该节点对其祖先节点的贡献...
2018-04-17 17:37:21
241
原创 CodeForces - 958A2（二维hash）
链接：CodeForces - 958A2题意：给出N*M和M*N的两个矩阵，要求在两个矩阵中找出M*M的相同部分。题解：二维hash模板#include <bits/stdc++.h>using namespace std;const int maxn = 200;int N, M;char a[maxn][maxn], b[maxn][maxn];unsigned lo...
2018-04-17 14:37:57
209
原创 CodeForces - 960F（主席树）
链接：CodeForces - 960F题意：一个有向图，可非连通，可重边，可自环，每条边上有权值。问权值严格递增，且路径不能违背输入顺序，的最长路径（指边数最多）的边数是多少。题解：用map存1e5个线段树，Query(u, x),表示以u为终点，且与u相连的边权值不大于x的最长路径边数。 状态按输入顺序转移，比如现在输入<u, v, w>。 那么状态从u转移到v...
2018-04-12 15:44:32
293
原创 CodeForces - 960D（模拟）
链接：CodeForces - 960D题意：给出一个二叉树，根节点是1，节点x的左孩子是2*x，右孩子是2*x+1。给出以下三个操作 1 X K ：将x所在的那一层的所有数右移K位（循环移动） 2 X K ：将x所在的那一层的所有数右移K位（循环移动），并且其每个节点的子树也跟着移动 3 X ：输出X到根节点1的路径题解：因为移动的是值，所以原位置标号是不变的。我们只需记录该层...
2018-04-11 19:08:40
299
原创 CodeForces - 960C（分解+构造）
链接：CodeForces - 960C题意：一个长度为n的序列有2^n-1个子序列，但合法序列需满足：最大值-最小值 < d 。先给出一个序列中子序列合法的个数x和d。要求构造原序列。题解：因为是 最大值-最小值 小于一个正整数，构造考虑特殊值：0。让所有元素相等即可。一个长度为i且元素都相等的序列一定可以被分为2^i-1个合法子序列。对n进行2^i-1的分解，类似于2进制分解，然后让相同...
2018-04-11 09:26:29
707
原创 CodeForces - 961E（树状数组）
链接：CodeForces - 961E题意：给出一个序列A，下标1-N，求满足(1) x < y (2) a[x] >= y (3) a[y] >= x的数对有多少个。题解：求数对个数，考虑到用树状数组。但只用树状数组却无法同时满足条件（2）（3)，故先用vector满足条件（3），再用树状数组。vector[min(i - 1, a[i])].push_back(i);即在满...
2018-04-09 18:58:06
1040
原创 CodeForces - 961D（两线过点）
链接：CodeForces - 961D题意：给出一些点，问是否能用两条直线全部通过这些点。题解：找出不共线的三点，可确定三条直线，依次枚举三条直线是否符合条件即可。#include <bits/stdc++.h>using namespace std;const double EPS = 1e-8;const int mod = 1e9 + 7;const int INF ...
2018-04-08 15:58:52
390
原创 51Nod - 1119（组合数+逆元）
链接：51Nod - 1119题意：M * N的方格，一个机器人从左上走到右下，只能向右或向下走。有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10^9 + 7的结果。Input第1行，2个数M,N，中间用空格隔开。（2 Output输出走法的数量 Mod 10^9 + 7。Input示例2 3Outpu
2018-01-29 11:22:08
230
原创 51Nod - 1298（点到线段的距离）
链接：51Nod - 1298题意：给出圆的圆心和半径，以及三角形的三个顶点，问圆同三角形是否相交。相交输出"Yes"，否则输出"No"。（三角形的面积大于0）。Input第1行：一个数T，表示输入的测试数量(1 <= T <= 10000)，之后每4行用来描述一组测试数据。4-1：三个数，前两个数为圆心的坐标xc, yc，第3个数为圆
2018-01-29 10:58:36
165
原创 UVA - 11212（IDA*）
链接：UVA - 11212题意：给出一个数字为1~n的某种排列，只能用剪切和粘贴操作，求将其变得有序的最小操作次数。题解：用IDA*，枚举上界进行搜索，并找出剪枝所用的乐观函数h。此题的乐观函数为，g( ) #include using namespace std;const int maxn = 10;int n, a[maxn];bool judge(){
2018-01-27 11:32:25
257
原创 CodeForces - 913C（贪心）
链接：CodeForces - 913C题意：n种饮料，每种饮料的体积是2^(n-1)，给出每种每瓶的花费，求不小饮料体积不小于L的最小花费题解：先求出每一种饮料的性价比。如果有饮料可以一瓶满足当前所求值就与ans进行比较选取，再从前面一瓶不够的饮料中选取性价比最高的购买。#include using namespace std;const long long INF = (1L
2018-01-25 17:08:57
387
原创 HDU - 5527（DFS+贪心）
链接：HDU - 5527题意：一共有{1，5，10，20，50，100，200，500，1000，2000}种类的硬币，给出每种硬币的个数，恰好凑出p，求硬币最多的个数。题解：要求最多用多少个，就要先保证能凑出来，再用面值小的换掉面值大的。观察出来50和500以外，其它的面值一定可以用前面的任意一个换得，顾可直接从后往前遍历钱币，如果前面的钱币和大于所求值时，就不需要用当前面值的钱币了，
2018-01-25 16:36:44
193
原创 HDU - 1043（康拓展开+BFS）
链接：HDU - 1043题意：九宫格还原题解：康拓展开+BFS#include using namespace std;const int maxn = 9;const int maxm = 370000;struct Node{int a[maxn], num, n;};struct Path{int fa; char dir;}Fa[maxm];int f[ma
2018-01-24 15:17:35
291
原创 Wannafly挑战赛8 - C 小C打比赛（DP）
链接：Wannafly挑战赛8 - C 小C打比赛题意：题目描述小C现在要参加一场wannafly挑战赛，一场挑战赛一共有n道题，一共有m分钟。对于第i道题，小C解决它需要恰好j分钟的概率是pi,j。小C每次会选择某一道没做完的题，然后把它解决（不能中途放弃），之后再决策下一道要做的题是哪道。求小C在最优策略下，期望能做出几道题。输入描述:第一行两个
2018-01-23 15:45:43
255
原创 CodeForces - 652D（树状数组+离散化）
链接：CodeForces - 652D题意：给出n个区间，求每个区间中包含了几个其它的区间。题解：将每个区间的起点和终点视为一个坐标，那么问题就转化为了求一个点的左下方有几个点。将坐标按照x降序y升序排列，用树状数组维护y。要用离散化。#include <bits/stdc++.h>using namespace std;const int maxn = 2e5 + 10;i...
2018-01-23 11:59:26
454
1
原创 HDU - 1024（DP）
链接：HDU - 1024题意：给出m，n 和 长度为n的序列，求不相交的m个子区间的最大和题解：dp[i][j] = max( dp[i][j-1] + a[j], Max( dp[i-1][k] ) + a[j]) {1#include using namespace std;const int INF = 0x3f3f3f3f;const int maxn =
2018-01-22 10:51:03
265
原创 CodeForces - 914C（DP+组合数）
链接：CodeForces - 914C题目：C. Travelling Salesman and Special Numberstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard
2018-01-21 21:44:12
632
原创 CodeForces - 916B（思维+位运算）
链接：CodeForces - 916B题意：B. Jamie and Binary Sequence (changed after round)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutp
2018-01-20 10:45:18
1052
原创 Wannafly挑战赛5 A珂朵莉与宇宙（思维）
题目链接：题目描述星神是来自宇宙的所以珂朵莉也是吧所以我就出了个题给你一个长为n的序列a，有n*(n+1)/2个子区间，问这些子区间里面和为完全平方数的子区间个数输入描述:第一行一个数n第二行n个数表示序列a输出描述:输出一个数表示答案示例1输入60 1 0 9 1 0输出
2017-12-08 22:44:30
543
原创 牛客练习赛7 - E（树状数组+离散化）
链接：题目描述珂朵莉给了你一个序列，有个子区间，求出她们各自的逆序对个数，然后加起来输出输入描述:第一行一个数 n 表示这个序列 a 的长度之后一行 n 个数，第i个数表示ai输出描述:输出一行一个数表示答案示例1输入101 10 8 5 6 2 3 9 4 7输出270
2017-12-03 11:25:10
406
原创 CodeForces - 825F（DP）
题目链接：CodeForces - 825F题意：将给出的字符串压缩，压缩规则是将重复的循环节压缩成一个循环单位并在循环单位前标上被压缩的循环节的循环单位的的个数，求压缩后的字符串的最小长度。如：aaaaa -> 5a ，所以长度是2；abc -> 1abc ，所以长度是4。题解：这题要用dp的思想，dp[i]里存的是前i个字符组成的串能被压缩的最小长度，从前往后依次枚
2017-11-06 10:00:47
355
原创 The Heaviest Non-decreasing Subsequence Problem（LIS+思维）
题目链接：Let SS be a sequence of integers s_{1}s1, s_{2}s2, ......, s_{n}sn Each integer is is associated with a weight by the following rules:(1) If is is negative, then its weight is
2017-09-28 21:35:19
254
原创 CodeForces - 814B（思维）
题目链接：CodeForces - 814B题意：有两个序列，本来应该是1~n，但是都有一个数据错了，要求可能的原来序列。题解：因为两个序列a，b都是只有一个错误，那么改变其中一个序列，就可以改回原来的序列。将b中与a不相同的数全部放入一个数组c中（注意c中只可能有一个或两个元素），将其它相同的数放入map中，以便于随时判断存在。如果c中只有一个元素的那么遍历一遍b数组，找
2017-08-24 19:13:43
294
原创 CodeForces - 750C（思维）
题目链接：题意：Codeforces里分两个等级，分数在1900及其以上是dev1，在1899及其以下是dev2，分数可以是负的。给出最近几场比赛的数据，求可能的最大分数。给出n对数据c和d。d是指在在参加这场比赛之前的等级，c是指这场比赛结束后变化的分数。题解：经过思考过后你会发现，最后一个c是无所谓的，因为它没给出变化后的等级。所以我们将数据错一分开，如：c
2017-08-24 09:43:09
430
原创 BZOJ - 4974（KMP+思维）
题目链接：BZOJ - 4974题意：给出n和per[1~n]，per[i]表示字符串前i个字符的最小循环节。要求构造出符合条件的字典序最小的小写字母字符串。题解：给出的per数组其实是一种next数组，将i - per[i]，就可以得到正常的next数组。然后根据next的构造方法，可以得到字符串中的相等与不想等关系，再贪心每次用符合条件的最小字母构造，还原字符串。
2017-08-21 17:40:44
1290
原创 HDU - 1540（STL）
题目链接：HDU - 1540题意：给出数字1~n和三种操作 操作D：删除一个数（但是那个位置依然空在那）。 操作Q：询问一个数，回答包括这个数在内的连续区间的长度。（若那个数被删，返回0） 操作R：重建最后被删除的数。题解：对于询问Q，如果我们每次都遍历1~n寻找连续区间的长度，肯定是要超时的。这题可以用线段树维护求解。但我
2017-08-17 08:44:20
242
原创 HDU - 5969（位运算）
题目链接：HDU - 5969题意：找出区间[L, R]中的两个数x、y，使x|y（位或）最大。题解：位或是二进制运算，二进制中只有0和1，要使位或最大，就要使R位或后的1尽可能的多。因为位或的性质，不可能位或后使数的最高位大于R。所以其中一个数必须是R。首先要知道，在剩下的数中能使R增加的1的位数是有限的。那么能增加多少呢？能使L与R出现的L的最高不同位之后的低位全部变成1。...
2017-08-04 21:06:08
840
4
原创 CodeForces - 808D（STL+思维）
题目链接：CodeForces - 808D题意：给一个长度为n的正整数序列，要求最多移动移动数使得数列可以分为相等的两个部分（前面的和与后面的和 相等），注意不是交换两个数，而是移动一个数，其它数的相对顺序保持不变。题解：因为要求前面的和与后面的和，那么用前缀和数组记录前缀和，用的时候作一个减法就能很快的求出两部分的 和。要满足题目要求，没移动
2017-08-04 19:56:41
416
原创 CodeForces - 816B（区间计数）
题目链接：CodeForces - 816B题意：给出n个区间和一个k值，再给出q次询问，每次询问给出一个区间，要求这个区间中的数在开始的n区间中出现次数不少于k次的数目。解法：将n个区间的每个数每出现一次就加一，最后统计q询问的区间中不小于k的数的个数。写这题主要是想讲一个常用的区间更新的方法，其实这题也可以用线段数或树状数组写，但在这里就不讲了。 操作
2017-08-04 12:08:29
539
原创 CodeForces - 673B（思维）
题目链接：CodeForces - 673B题意：数字1~n表示一堆题目，数字越大，题目越难。将题目分组，一组的任何题目都要比二组难。给出类型相似的题目，一个组中不能出现类型相似的题目。相似关系并不传递。解法：每次给出两个类似的，大的一定进入dev1，小的一定进入dev2。每次记录dev1的最小值k1，dev2的最大值k2,这是分界点，比k1大的一定在dev1，比k2小的一
2017-08-02 13:55:22
587
2
数据结构课设-表达式求职-带界面
2018-01-10
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人