0 lpc大菜逼

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 19w+

2020牛客NOIP赛前集训营-普及组(第二场)

T1:面试牛牛内推了好多人去牛客网参加面试,面试总共分四轮,每轮的面试官都会对面试者的发挥进行评分。评分有 A B C D 四种。如果面试者在四轮中有一次发挥被评为 D,或者两次发挥被评为 C,就不会通过面试。如果面试者没有一次被评为 D,并且有三个或以上的 A,则会获得 special offer。其余情况会获得普通 offer。现在告诉你一些面试者的发挥,请你算一算,他们的面试结果分别是什么。输入描述:第一行输入一个 T,代表面试者的个数。接下来有 T 行,每行都有一个长度为 4 的字符串,每

2020-10-21 14:01:58

数论总结

整除:概念:设a, b为整数, 如果存在一个整数q,使得 a * q = b,则 b 能被 a 整除,记为a∣ba \mid ba∣b 。性质:传递性:如果a∣ba \mid ba∣b 且 b∣cb \mid cb∣c 则 a∣ca \mid ca∣c。a∣ba \mid ba∣b且a∣ca \mid ca∣c等价于对于任意的整数x,y,有a∣(bx+by)a \mid (bx + by)a∣(bx+by)。设mmm不为0,则a∣ba \mid ba∣b等价于ma∣mbma \mid mbma∣

2020-10-17 11:07:53

松鼠的新家(树上点差分 + LCA)

题目:松鼠的新家是一棵树,前几天刚刚装修好了新家,新家有 个房间,并且有 根树枝连接,每个房间都可以相互到达,且任两个房间之间的路线都是唯一的。天哪,他居然真的住在「树」上。松鼠想邀请小熊维尼前来参观,并且还指定一份参观指南,他希望维尼能够按照他的指南顺序,先去 ,再去 ,……,最后到 ,来参观新家。可是这样会导致维尼重复走很多房间,懒惰的维尼不停地推辞。可是松鼠告诉他,每走到一个房间,他就可以从房间拿一块糖果吃。维尼是个馋家伙,立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃,他需要在每一个房

2020-10-05 16:08:12

最短路模板

BellmanFord:#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int MAXN = 1e5 + 5;int n, m, s, t, d[MAXN], pre[MAXN];struct node{ int u, v, d;}a[MAXN];void print(int x) {

2020-09-30 12:52:50

纪念品(CSP-J)

题目:小伟突然获得一种超能力,他知道未来 T 天 N 种纪念品每天的价格。某个纪念品 的价格是指购买一个该纪念品所需的金币数量,以及卖出一个该纪念品换回的金币数量。每天,小伟可以进行以下两种交易无限次:任选一个纪念品,若手上有足够金币,以当日价格购买该纪念品;卖出持有的任意一个纪念品,以当日价格换回金币。每天卖出纪念品换回的金币可以立即用于购买纪念品,当日购买的纪念品也可以当日卖出换回金币。当然,一直持有纪念品也是可以的。T 天之后,小伟的超能力消失。因此他一定会在第 T 天卖出所有纪念品换回金币

2020-09-23 13:39:18

ST算法(倍增)

作用:ST算法是用来对任意一个数组,求其任以(l~r)区间内的最大值(最小值也可以)。引出:首先遇到这一类题,我们可以暴力查找,但是这种方法如果询问多次,直接让您原地起飞,显然我们机智的前人是不能忍的,于是牛逼的ST算法出现了。...

2020-08-24 18:33:14

单词游戏题解

题目:来自 ICPC CERC 1999/2000,有改动。有NNN个盘子,每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序,使得相邻两个盘子中,前一个盘子上单词的末字母等于后一个盘子上单词的首字母。请你编写一个程序,判断是否能达到这一要求。如果能,请给出一个合适的顺序。输入:多组数据。第一行给出数据组数TTT ,每组数据第一行给出盘子数量NNN ,接下去NNN 行给出小写字母字符串,一种字符串可能出现多次。输出:若存在一组合法解输出Ordering is po

2020-08-20 18:40:43

木棒题解

题目:乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序,帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。输入格式:输入包含多组数据,每组数据包括两行。第一行是一个不超过64的整数,表示砍断之后共有多少节木棍。第二行是截断以后,所得到的各节木棍的长度。在最后一组数据之后,是一个零。输出格式:为每组数据,分别输出原始木棒的

2020-08-17 21:09:56

老旧的桥题解

题目:现在有NNN个岛屿和M坐桥。第iii个桥双向连接着第AAAi和第BBBi个岛屿。刚开始的时候,我们可以用其中的一些桥在任何两个岛之间旅行。然而,经调查显示,这些桥都将会因老旧而倒塌,而且倒塌的顺序为从第1座桥到第M坐桥。由于剩下的桥不能够使第aaa个岛和第bbb个岛互相到达,这会使岛屿对变得很不方便。对于每一个,找出在第i(1<=i<=M)(1 <= i <= M)(1<=i<=M)座桥倒塌之后,这样不方便的岛屿对(a,b)(a<b)(a, b)(

2020-08-11 21:12:37

关押罪犯题解【并查集】

题目:S城现有两座监狱,一共关押着N名罪犯,编号分别为1 N1~N1 N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。如果两名怨气值为c的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并造成影响力为c的冲突事件。每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,然后上报到S城Z市长那里。公务繁忙的Z市长只会去看列

2020-08-10 20:35:46

新的开始题解

题目:发展采矿业当然首先得有矿井,小 FF 花了上次探险获得的千分之一的财富请人在岛上挖了 口矿井,但他似乎忘记考虑的矿井供电问题……1.为了保证电力的供应,小 FF 想到了两种办法:2.在这一口矿井上建立一个发电站,费用为 vvv(发电站的输出功率可以供给任意多个矿井)。将这口矿井与另外的已经有电力供应的矿井之间建立电网,费用为 ppp。小 FF 希望身为「NewBe_One」计划首席工程师的你帮他想出一个保证所有矿井电力供应的最小花费。输入:454430 2 2 22 0 3

2020-08-08 21:32:04

最大回文串(palindrome.cpp)题解(回文串输出路径)施工中

题目:每次考试,奶牛都想作弊,而且他又找回了一些朋友,于是他就试一下作弊的滋味了。他是怎么作弊的呢?奶牛的朋友太强悍了,他生怕被老师发现,又害怕被其他同学偷去,于是他每次递给奶牛都是一段只含有a,b,c,da, b, c, da,b,c,d的字符串,那么答案是什么呢?“答案就是该字符串内最长的回文串。”哈哈哈,奶牛瞬间就发现了这个秘密,可是,奶牛的朋友是个**狂,他每次递给奶牛的都是一些非常长的字符串,奶牛在短时间内没发找到答案,所以奶牛又找到了你,帮他找出字符串内最大的回文串。回文串: 从左往右写和从

2020-08-03 09:56:39

最短路计数题解(图论版题)

题目:给出一个NNN个顶点MMM条边的无向无权图,顶点编号为111~NNN 。问从顶点111开始,到其他每个点的最短路有几条。题解:用一个b数组来存路径,如果遇到可以从某点经过k(中转点)点到终点,且最短路与此时相同,那么路径数为:路径数 = 起点最短路径数 + 终点最短路径数 + 1如果遇到更短的最短路,那么路径为:路径数 = 起点最短路径数初值:起点步数置为1局部代码:int Dijkstra(int s, int t) { qu.push(edge(s, 0)); dj[s] =

2020-08-01 07:14:20

Sightseeing Trip题解(图论)

题目给定一张无向图,求图中一个至少包含333个点的环,环上的节点不重复,并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中,你需要输出最小环的方案,若最小环不唯一,输出任意一个均可。若无解,输出 No solution.图的节点数不超过100100100 。输入格式第一行两个正整数n,mn,mn,m表示点数和边数。接下来mmm行,每行三个正整数 x,y,zx, y, zx,y,z,表示节点x,yx, yx,y之间有一条长度为zzz的边。输出格式输出一个最小环的方案:按环上顺序

2020-07-30 19:00:50

「JXOI2017」加法题解

题解:主要思路:(1)首先要想到贪心,若想要满足最小数最大,那么我们尽量选区间长度长的修改方法修改,这样同是加a,但是长度长的加的更多,明显比较优越。(2)如何找到最大区间,我们可以在输入后对其左端点排序,令最小的左端点排在前面,然后要用时再依次插入优先队列,而优先队列即是要用来将区间的排在第一位(因为已经满足了左端点最小,右端点尽量大,那么区间也是最大,最划算的)(3)我们可以二分枚举最小的最大值,然后再从1——n循环,如果a[i]还小于mid,就说明还未到最大,可以继续修改区间使其最大,如果大于

2020-07-27 23:48:06

一.二维 单点修改,区间查询【最好学完树状数组的基本操作再来】

一维:题意:1 i x表示i位置+x, 2 i j表示i——j的所有数之和。题解:这是一道灰常简单的模拟题,首先将原数组改为树状数组,写好模板代码,碰到一个直接输处即可,注意输出i——j为闭区间,所以答案应为sum(i) - sum(j - 1),此处sum是前缀和。代码:#include <iostream>#include <cstdio>using namespace std;int n, a[1000005], s, l, r, ww;long long

2020-07-26 23:26:31

数三角题解【noip难题】

1.题目:这是一个数三角的游戏。长度为1或SQRT(2)的小木棍放在一个网格上。如图所示,有水平的,垂直的或对角的。对角放置的木棍可以交叉。将木棍随意地放在网格上得到的图案可能不含三角形,也可能含一个或多个三角形。如下图所示,(a),(b),©,(d)和(e)分别含有2,5,12,0,0个三角形。你的任务是写一个程序数出一个图案中的三角形个数。。cpp输入文件count.in包括N+1行:先输入图案中木棍的个数N。下面输入这N根木棍的位置,用两个网格坐标表示,这两个坐标分别为木棍两端的位置。网

2020-07-25 23:42:45

括号涂色题解(区间DP)

题目:Petya遇到了一个关于括号序列的问题: 给定一个字符串S,它代表着正确的括号序列,即(“(”)与 (“)”)是匹配的。例如:“(())()” 和 “()”是正确的,“)()”与“(()”则不是正确的。 在正确的括号序列中,一个左边的括号一定是匹配一个右边的括号(反之亦然)。例如,在下图中,第 3 个括号匹配第 6 个括号,第 4 个括号匹配第 5 个括号。现在你需要对一个正确的括号序列做涂色操作,严格满足以下三个条件:1、每个括号要么不涂色,要么涂红色,要么涂蓝色。2、一对匹配的括号需要且

2020-07-19 23:38:34

分离与合体题解(区间DP)

题目:经过在机房里数日的切磁,LYD从社神牛那里学会了分离与合体,出关前,杜神牛给了他一个测试杜神牛造了个区域,它们紧邻着排成了一行,编号1-n。在这經个区域里都放着一把OI界的金钥匙,每一把都有一定的价值,LYD当然想得到它们了。然而杜神牛规定LYD不可以一下子把它们全部拿走,而是每次只可以拿一把。为了尽快地拿到所有的金钥匙,LYD自然就用上了刚学的分离与合体特技。开始LYD可以选择从1~n-11~n-11~n-1的任何一个区域(记为K)进入,进入后LYD会在K区域发生分离,从而分离为两个小L

2020-07-19 21:03:49

能量项链【题解】(区间DP)

思路:其实这应该是“石子合并2”的升级版,首先我们要按照题目的说法,把n个数变为(N1,N2)(N2,N3)(N3, N4)(N4, N5)…(Nn, N1)。这里推荐读者用结构体来保存每一组的数,之后简单分析一下题目,这题应该是可以环状相加的,所以再用二倍链的方式解决。状态:dp[i][j]表示合并i——j的最大开销转移方程:(i为左端点)dp[i][r] = max(dp[i][r], dp[i][k] + dp[k + 1][r] + b[i].x * b[k].y * b[r].y);

2020-07-18 23:41:36

查看更多

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