- 博客(206)
- 资源 (8)
- 收藏
- 关注
RSS订阅原创 2019第十届蓝桥杯B组决赛题解第九题
题意: 两种操作，C x y,将x位置的数修改为y，Q x y,查询[x,y]之间的第8大值，y-x+1<= 8的话输出0思路: 区间第8大值，线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)每个节点存储它管辖的这个区间的前8大值，修改的时候暴力merge，单次修改复杂度log(n)*8查询的时候返回含有8个值得list，并不断merge代码:#include<...
2019-05-27 17:18:08
2173
原创 2019第十届蓝桥杯B组决赛题解第八题
题意：外圈12个，中圈8个，内圈4个，'R','B','Y'分别有12个，8个，4个，分布在这个24个位置上，每次可以把三个圈同时旋转一个单位，可以在0位置把三者做交换，外->内->中->外，问能否把'R'都弄到外，'B'都弄到中,'Y'都弄到内找规律题目？对所有数对4取余，红黄蓝都应该是0，1，2，3代码待更...
2019-05-27 17:14:51
1868
原创 2019第十届蓝桥杯B组决赛题解第七题
场上暴力写的后来看了下别人思路，dp[i][j]=dp[i-1][j]*j+dp[i-1][j-1]*2+dp[i-1][j-2]*(i-j)待更++
2019-05-27 17:10:47
2134
2
原创 2019第十届蓝桥杯B组决赛题解第六题
题意:输入一个S串和一个T串，|S|>= |T|,问最少要修改S中的几个字母才能使S中有子序列T思路:dp+贪心f[i][j]表示以S中第i个字母开头的串包含T中第j个字母开头的串所要修改的最少的字母数，即S中i之前的字母已经包含T中j之前所有的字母，所以分别从i和j位置继续匹配过程简述如下：S： ABCECDFFT： BBDEC开始i=1,j=1在S[i]开始寻...
2019-05-27 17:07:58
2696
4
原创 2019第十届蓝桥杯B组决赛题解第五题
在一个5*5的方格上走边界点，其实也就是6*6的图，从左上角开始走，不走重复点且在12步之内走回左上角点，问方案数直接dfs,需要减掉 (0,0)->(1,0)->(0,0)和(0,0)->(0,1)->(0,0)，这两个路线都重合了结果: 208-2=206 代码:#include<bits/stdc++.h>#define mem(a,b...
2019-05-27 17:02:47
2535
8
原创 2019第十届蓝桥杯B组决赛题解第四题
现在实在想不起来是什么题了待更++------------------------------------------更新分割线-----------------------------------------------------题意: 寻找有100个约数的最小数思路: 本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以...
2019-05-27 16:57:07
2854
4
原创 2019第十届蓝桥杯B组决赛题解第三题
题意: 将一个7*7的网格沿着边界线裁剪，使得裁剪完右边翻转可以恰好拼成“直角”思路: 发现，右边翻转其实就是沿着 中间大正方形左下到右上这条对角线翻转的，也就是我们的裁剪完应该要让 左右侧 部分按这条对角线对称，既然我们从左上开始裁剪，那么裁剪到对角线上之后，再从右下角开始对称裁剪就好了其实就是问从左上角开始，保证两边块连续的情况下，走到对角线一共有多少种方案代码:待更...
2019-05-27 16:54:56
3313
2
原创 2019第十届蓝桥杯B组决赛题解第二题
求两两不同的素数组成2019的方案数注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long结果: 55965365465060代码:#include<bits/stdc++.h>#define mem(a,b) memset(a,b,sizeof(a))using namespace s...
2019-05-27 16:48:13
4581
6
原创 2019第十届蓝桥杯B组决赛题解第一题
题意: 求2019<X<Y ,使2019*2019,X*X,Y*Y组成等差数列且X+Y最小.结果: 7020代码:#include<bits/stdc++.h>#define mem(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long ll;const int inf = 0x3f...
2019-05-27 16:45:48
5408
原创 POJ - 1947 Rebuilding Roads (树形DP)
题目链接：http://poj.org/problem?id=1947题意：给出一棵n个节点的树，问剖出一颗含有p个节点的子树最少需要砍掉多少条边.(n<= 150)思路：树形DP，f[i][j]表示在以i为根的树上剖出j个节点并且包含i节点的子树最少需要砍掉的边数。初始f[i][1]等于他的孩子树. f[i][j] = min(f[k][l]+f[i][j-l]-1),减1...
2018-11-30 13:00:42
173
1
原创 CodeForces - 1077E Thematic Contests(二分好题)
题目链接：http://codeforces.com/problemset/problem/1077/E题意：给出n个题目，每个题目都有一个主题，现在让你安排若干场考试，每场考试的题目数量恰好是前一场的2倍，并且他们的主题是相同的，问最多能用掉多少题目？思路：我们想要用掉尽量多的题目，但是策略比较难定，因为用掉的题目多少跟我们第一场考试用掉的题目多少好像没有直接关系，为了产生这样的...
2018-11-30 12:42:51
341
原创 CodeForces - 1077F1 Pictures with Kittens (hard version) （DP+双端队列）
题目链接：http://codeforces.com/problemset/problem/1077/F2题意：https://blog.csdn.net/nka_kun/article/details/84645060的增强版思路：我们根据上一题发现，其实更新f[i][j]的过程就是在f[i-1][j-1]到f[i-k][j-1]之间找一个最大值，用这个值来更新f[i][j].这里我...
2018-11-30 11:04:01
194
原创 CodeForces - 1077F1 Pictures with Kittens (easy version)（DP）
题目链接：http://codeforces.com/problemset/problem/1077/F1题意：从n个物品中挑选x个物品，每个物品都有一个价值，我们想选出的价值尽量大，还有保证任意连续的k个物品中都至少有一个物品被选出来.思路：既然我们想选择x个物品，我们就可以令f[i][j]表示选择以第i个物品结尾的j个物品的最大价值.这样更新的话f[i][j] = max(f[...
2018-11-30 10:55:57
434
原创 CodeForces - 401D Roman and Numbers(状压)
题目链接：http://codeforces.com/problemset/problem/401/D题意：问给出的数位的全排列组成的数当中，那些数模m等于0.思路：二进制表示选了哪些数，f[i][j]表示选了i表示的那些数，余数为j的方案数.直接状压DP或者记忆化搜索都可以，搜索比较好理解.代码：#include<bits/stdc++.h>#define m...
2018-11-30 10:45:04
271
原创 Garden Gathering Gym - 100792G(求距离最远的两个点)
题目链接:http://codeforces.com/gym/100792/problem/G题意：给出n个坐标整数点，求出距离最远的两个点.两点之间的路径为只能走整数点.思路：显然两点之间的路径为sqrt(2)*min(|x1-x2|,|y1-y2|)+max(|x1-x2|,|y1-y2|)-min(|x1-x2|,|y1-y2|) =(sqrt(2)-1)*min(|x1-x2|...
2018-10-22 16:40:25
494
原创 HDU - 4312 Meeting point-2(最小切比雪夫距离和)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4312题意:选中一个点，使其他点到这个点的切比雪夫距离之和最小.思路:将一个点(x,y)的坐标变为(x+y,x−y)后,原坐标系中的曼哈顿距离 = 新坐标系中的切比雪夫距离将一个点(x,y)的坐标变为((x+y)/2,(x−y)/2) 后,原坐标系中的切比雪夫距离 = 新坐标系中的曼哈顿距离参...
2018-10-21 10:30:40
384
原创 HDU - 4311 Meeting point-1(最小曼哈顿距离和)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4311题意：选中一个点，使其他点到这个点的曼哈顿距离之和最小.思路：加入我们选中一个点(x,y)，那么其他点到这个点的曼哈顿距离之和为|x-x1|+|x-x2|+···+|x-xn| + |y-y1|+|y-y2|+···+|y-yn|我们发现其实就是x被用了很多次，然后对其他x求和,y同理....
2018-10-21 10:22:57
2221
原创 POJ-2926 Requirements(最远曼哈顿距离)
**题目：http://poj.org/problem?id=2926题意：求五维空间最远曼哈顿距离.思路：曼哈顿距离:dis = |x1-x2|+|y1-y2|切比雪夫距离:dis = max(|x1-x2|,|y1-y2|)求曼哈顿距离若去掉绝对值，即在以下4项中选择最大值.(x1-x2)+(y1-y2)(-x1+x2)+(y1-y2)(x1-x2)+(-y1+y2)(-x1+...
2018-10-21 10:09:39
265
原创 HDU - 6274 Master of Sequence
There are two sequences a1, a2, · · · , an, b1, b2, · · · , bn. Let S(t) =∑⌊(t−bi)ai⌋. . There are m operationswithin three kinds as following:• 1 x y: change value ax to y.• 2 x y: change value bx...
2018-10-13 10:57:49
253
原创 POJ - 3648 Wedding
WeddingTime Limit: 1000MS Memory Limit: 65536KSpecial JudgeDescriptionUp to thirty couples will attend a wedding feast, at which they will be seated on either side of a long table. The bride and ...
2018-10-13 10:40:05
176
原创 POJ - 3683 Priest John's Busiest Day
Priest John’s Busiest DayTime Limit: 2000MS Memory Limit: 65536KSpecial JudgeDescriptionJohn is the only priest in his town. September 1st is the John’s busiest day in a year because there is an ...
2018-10-13 10:32:52
174
原创 CodeChef - VRTXCOVR
All submissions for this problem are available.You are given an undirected graph G = (V, E) containing N nodes and M edges. The nodes are numbered from 1 to N. A subset C of V is a vertex cover if fo...
2018-10-13 10:27:17
249
原创 CodeForces - 27E Number With The Given Amount Of Divisors(恰好有n个因子的数)
Given the number n, find the smallest positive integer which has exactly n divisors. It is guaranteed that for the given n the answer will not exceed 10^18.InputThe first line of the input contains ...
2018-10-05 21:46:44
225
原创 51Nod 1060 最复杂的数(反素数)
1060 最复杂的数基准时间限制：1 秒 空间限制：131072 KB把一个数的约数个数定义为该数的复杂程度，给出一个n，求1-n中复杂程度最高的那个数。例如：12的约数为：1 2 3 4 6 12，共6个数，所以12的复杂程度是6。如果有多个数复杂度相等，输出最小的。Input第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 100)第2 - T +...
2018-10-05 21:37:01
207
原创 51nod 1405 树的距离之和
1405 树的距离之和基准时间限制：1 秒 空间限制：131072 KB给定一棵无根树，假设它有n个节点，节点编号从1到n, 求任意两点之间的距离（最短路径）之和。Input第一行包含一个正整数n (n <= 100000)，表示节点个数。后面(n - 1)行，每行两个整数表示树的边。Output每行一个整数，第i(i = 1,2,…n)行表示所有节点到第i个点的距离之和。I...
2018-10-05 21:30:25
202
原创 CodeForces - 1060E Sergey and Subway(树上任意两点之间的距离和)
Sergey and SubwaySergey Semyonovich is a mayor of a county city N and he used to spend his days and nights in thoughts of further improvements of Nkers' lives. Unfortunately for him, anything and eve...
2018-10-05 21:26:22
939
原创 P1290 欧几里德的游戏(博弈,SG)
P1290 欧几里德的游戏题目描述欧几里德的两个后代Stan和Ollie正在玩一种数字游戏，这个游戏是他们的祖先欧几里德发明的。给定两个正整数M和N，从Stan开始，从其中较大的一个数，减去较小的数的正整数倍，当然，得到的数不能小于0。然后是Ollie，对刚才得到的数，和M，N中较小的那个数，再进行同样的操作……直到一个人得到了0，他就取得了胜利。下面是他们用(25，7)两个数游戏的过程：...
2018-09-25 20:23:57
984
原创 CodeForces - 1051F The Shortest Statement(最短路,lca)
题意：给出一个图，询问任意两点之间最短路，边比点多不过20.思路：因为边多的很少，所以可以看成一个树，又多加了几条边.这样其实我们可以把那几个点看成中转节点，这样我们可以求出那些点到任意点的最短路径，然后询问的时候，对于x,y，要不从树上直接从x,y这里用lca即可，要么经过其中一个节点，为什么不是结果其中几个节点呢?其实经过一个节点就够了，那个节点到任意节点的最短路我们是知道的，他如果需要会...
2018-09-24 10:00:43
322
原创 HihoCoder - 1391(离线树状数组)
1391 : Countrie时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 There are two antagonistic countries, country A and country B. They are in a war, and keep launching missiles towards each other.It is know...
2018-09-11 22:27:53
270
原创 HihoCoder - 1387(树的直径,树上距离)
1387 : A Research on “The Hundred Family Surnames”时间限制:3000ms 单点时限:3000ms 内存限制:256MB 描述 The Hundred Family Surnames is a classic Chinese text composed of common Chinese surnames. The book was co...
2018-09-11 22:14:07
195
原创 HihoCoder - 1384 Genius ACM(倍增)
1384 : Genius ACM时间限制:3000ms 单点时限:3000ms 内存限制:256MB描述 Advanced CPU Manufacturer (ACM) is one of the best CPU manufacturer in the world. Every day, they manufacture n CPU chips and sell them all...
2018-09-11 20:49:02
293
原创 CodeForces - 600E Lomsat gelral(DSU ON TREE)
Lomsat gelral Time limit 2 secon...
2018-08-29 11:37:25
156
原创 P1578 奶牛浴场
题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显然不能在浴场中产奶，于是，John希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于Clevow了。你还能帮助Clevow吗？John的牛场和规划的浴场都是矩形。浴场要完全位...
2018-08-29 11:03:13
683
原创 洛谷 P1169 [ZJOI2007]棋盘制作
题目描述国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个8 \times 88×8大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。而我们的主人公小Q，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。小Q找到了一张由N \time...
2018-08-29 10:37:00
219
2018第九届蓝桥杯C/C++B组决赛真题
2018-05-28
2018省赛第九届蓝桥杯真题BC组下载
2018-04-01
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人