3 nka_kun

尚未进行身份认证

我要认证

ACMer

等级
TA的排名 2w+

2019第十届蓝桥杯B组决赛(国赛)题解[最新题目汇总]

第一题第二题第三题第四题第五题第六题第七题第八题第九题

2019-05-27 17:23:40

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

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

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

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

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

2019第十届蓝桥杯B组决赛题解第四题

现在实在想不起来是什么题了待更++------------------------------------------更新分割线-----------------------------------------------------题意: 寻找有100个约数的最小数思路: 本质上就是用了素因子分解,假设分解出来的素因子有4种,分别有x1个,x2个,x3个,x4个,第i种因子可以...

2019-05-27 16:57:07

2019第十届蓝桥杯B组决赛题解第三题

题意: 将一个7*7的网格沿着边界线裁剪,使得裁剪完右边翻转可以恰好拼成“直角”思路: 发现,右边翻转其实就是沿着 中间大正方形左下到右上这条对角线翻转的,也就是我们的裁剪完应该要让 左右侧 部分按这条对角线对称,既然我们从左上开始裁剪,那么裁剪到对角线上之后,再从右下角开始对称裁剪就好了其实就是问从左上角开始,保证两边块连续的情况下,走到对角线一共有多少种方案代码:待更...

2019-05-27 16:54:56

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

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

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

CodeForces - 1077E Thematic Contests(二分好题)

题目链接:http://codeforces.com/problemset/problem/1077/E题意:给出n个题目,每个题目都有一个主题,现在让你安排若干场考试,每场考试的题目数量恰好是前一场的2倍,并且他们的主题是相同的,问最多能用掉多少题目?思路:我们想要用掉尽量多的题目,但是策略比较难定,因为用掉的题目多少跟我们第一场考试用掉的题目多少好像没有直接关系,为了产生这样的...

2018-11-30 12:42:51

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

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

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

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

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

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

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

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

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。