A 夹娃娃 题意：给你n个排列好的娃娃，并给你每个娃娃的价值，求l-r这个区间的娃娃价值(包括l和r)？ 题解：知识点：前缀和直接就是维护一个前缀和，然后做差就是他区间的中价值，没啥好说的。 代码: #include <map> #include <queue> #include <string> #include<iostream> #include<stdio.h> #include<string.h> #include <algorithm> #include <math.h> typed...

扑克牌 题意：给你n种牌，并给你这n种牌的张数，再给你m张万能牌，让你求最多配出多少套牌(就是n中 种牌，一种一张) 题解：知识点：二分从整体上来看，配出的多少套牌是单调的，想到二分。重点说一下check判断函数吧，因为你二分出来结果是，一定要判断结果是否符合，如果你配x套，需要大于m张万能牌，那么这样肯定是不行的，再者一套牌中有两张万能牌也是不符合题意的，所以生成了这两个判断条件。注意一下：他的右端不要设5e8，我当时就看到他给的范围是5e8我就设的5e8，这样想一下，如果n种牌都有5e8，再有5e8个万能牌，会怎样？当然结果就不在5e8范围内了。所以最右端应该是2*5e8。因为一套牌最多...

德玛西亚万岁 题意：n*m的矩阵 1能站人，0不能站人，相邻的地方不能站人，问总方案数？ 题解：知识点状态DP.通过题意我们可以知道：1，当位置(i,j)为0时，不能站人。2，如果(i,j)站人，那么[i-1,j],[i+1,j],[i,j+1],[i,j-1]这四个地方不能站；因为数据量不是很大所以我们可以想到用二进制来表示当前该位置上是否站人。针对1，我们可以样做，因为那这个位置不能站人，所以他这个为对应的二进制位为0，这样之后判断就可以知道，这个位置可不可以站人了。针对2，我们先看左右的，由于我们把能不能站人转化成了二进制，那么我们也可以用二进制来表示那些位置上站没站人，然后利用错位来...

A-符合条件的整数 题意：给定两个整数N,M,表示区间 [， ) ,请求出在这个区间里有多少个整数i满足i % 7=1 题解：两种方法一种推公式，另一种暴力枚举推公式：我们细心列出一部分就会发现 0 1 2 3 4 5 6 1 1 1 2 3 5 10后一个是前一个的2倍-1 如果这个指数能整除3那么那是前一个的二倍，就不用减一，其实就是因为他本身是%7=1，所以把他本身加上。知道这个都简单多了暴力枚举：找到左端点第一个%7=1，然后+7循环就好。 公式代码： #include <map> #include <queue> #incl...

比赛链接J-最大值题目链接 题意：有一个字符串s，对于字符串中一个非前缀子串恰好为字符串的前缀我们称之为ac串。请问给出一个字符串他的ac串最大长度为多少？ 题解：他这个ac串是非前缀子串与前缀相同，就像abab 他是最长ac串是ab，非前缀子串是第一个起点不是原字符串的起点，就是如果表上号的话就是 abab 1234ac串开始点不能是1，且ac串与原串从1开始对应相等。就从3开始走到4就是ab然后最长就是2。 知道这个我们可以知道他就是KMP，可惜我不会。哈哈~ 官方题解正好就KMP看就自取吧（嘻嘻嘻）。 另一种；直接二分找也可以，因为长度是单调的，他可以是n就肯定可以是n-1之后.....

比赛链接F三角形题目链接 题意：小明有一根长度为a的木棒，现在小明想将木棒分为多段（每段木棒长度必须为整数），使得分隔后的木棍中，取出的任意三段都不能构成三角形，小明想知道木棒最多被分成几段？（就是题目嘻嘻~） 题解：知识点：有点斐波那契数列的意味在里面 三角形两边之和大于第三边，因此不构成三角形的条件就是存在两边之和不超过另一边。所以按照斐波那契数列的方法切割可以使得切割的段数最大，1，1，2，3，5这样可以使得任意三根木棒不能组成三角形，最后无法切割的部分组成一根长的木棒。 三角形两边之和大于第三边，也可以这样想，一个堆，将1放进去符合题意，放最小的数并且符合题意，第三个最小就是前两个...

比赛链接H-直线题目链接 题意：n个点，求最多有多少个交点？ 题解：大数运算1条点：0个交点，2条线：1个交点，3条线：1+2个交点，4条线：1+2+3个交点，.....n条线：1+2+3+....+n-1个交点，即 公式退出来之后看数据量，1e15超出long long 所以选择大数运算。直接大数模板往上一套用，ok。 代码： #include <map> #include <queue> #include <string> #include<iostream> #include<stdio.h> #include<st...

比赛链接E-赛马题目链接 题意：两个人，各有N匹马，分别给出这2*n匹马的战力，两个人要对马，你知道对手的排序，求你最多可以赢几场？ 题解：知识点：算个贪心吧。就跟田忌赛马一样，你无非是找到比对手马略强一点的马来跟他的马比，这样才能应最多场。把你和对手的马匹各自排序，从小到大，每次找比对手现在最小的马匹略大的马跟他比，这样你就赢一场，如果比最小的都小直接拉出去让他跟对手战力最大的马比。然后让后一个再跟这个最小的比。 代码： #include <map> #include <queue> #include <string> #include<ios...

比赛链接C面积题目链接 题意：给出里面正方形的边长求出整个图形的面积。 题解:这个图形就是里面一个正方形加上两个直径为正方形边长一半的圆直接写出求解公式： 直接带入算就行了 代码： #include <map> #include <queue> #include <string> #include<iostream> #include<stdio.h> #include<string.h> #include <algorithm> #include <math.h> typedef long...

比赛链接B 减成一题目链接 题意：存在n个数，每次操作可以任选一个区间使得区间内的所有数字减一。问最少多少次操作，可以让所有数都变成1。数据保证一定有解。(也就是这个题本身) 题解：知识点：暴力枚举 直接从头到尾跑一遍就行了。我们这样想； 1.如果前面那个数比这个数大，那我们是在前一个数区间减1是肯定可以带着这个数一起减一就是区间向右扩一。所以这个数就不产生代价。2.如果前面那个数比这个数小，那我们扩展区间是只能扩到前一个数这么大，至于这个数比前一个数大的那部分还要减去，就产生(a[i]-a[i-1])这么多代价。 都减一是因为把他们都化成零，这样直接一遍for 就行了，或者吧第一个数前面...

问题 E: 种南瓜 时间限制: 2 Sec 内存限制: 128 MB 题目描述 一班的同学们决定在班上种南瓜时，pac 感到十分震惊，因为种南瓜是分耗费班级空间的。一班拥有一块 n×m 的地，可以在其中任意一个单元格上种南瓜秧，而南瓜会长在种上的相邻格子，一个格子最多长一个南瓜 。 当然，并不像 MC 中的南瓜长成方式，一班的南瓜经过基因变异，一只南瓜秧可以长出多个南瓜，也就是说，如果四周都没有被占用，仅种下一枝就可收获 4 个南瓜。 pac 已经得知同学们种南瓜的具体方案，她想知道最多可以收获多少个南瓜。 班长 Marser 还想知道，如果南瓜没有经过变异，也就是说一枝南瓜秧只能长出...

题号 NC25043名称 Protecting the Flower来源 USACO英文版-2007 January Contest-Silver 题目描述Farmer John went to cut some wood and left N (2 ≤ N ≤ 100,000) cows eating the grass, as usual. When he returned, he found to his horror that the cluster of cows was in his garden eating his beautiful flowers. Wanting to m...

链接：https://ac.nowcoder.com/acm/contest/5803/B来源：牛客网 题目描述赛时提示：魔法值和财富值初始为0 帕秋莉掌握了一种金属性魔法她决定去捡一些石头，施展点石成金魔法 帕秋莉将捡到的n块石头排成一排，并决定将一些石头点为黄金 对于第i块石头，如果将其变为黄金，会增加ai的财富，消耗bi的魔法（需要说明的是，就算魔法值不够，也可以操作，操作后魔法值归零） 否则，帕秋莉将会回复ci的魔法，但减少di的财富（财富值同理，可以无限制减少） 帕秋莉想知道，按照1-n的顺序以此操作每块石头，如何决策，可以使自己最后的收益值最大只需要输出最大收益收益值=财富值*魔...

链接：https://ac.nowcoder.com/acm/contest/5803/A来源：牛客网 题目描述小A最近开始沉迷买彩票，并且希望能够通过买彩票发家致富。已知购买一张彩票需要3元，而彩票中奖的金额分别为1,2,3,4元，并且比较独特的是这个彩票中奖的各种金额都是等可能的。现在小A连续购买了n张彩票，他希望你能够告诉他至少能够不亏本的概率是多少。输入描述:一行一个整数N，为小A购买的彩票数量一行一个整数N，为小A购买的彩票数量输出描述:输出一个最简分数a/b，表示小A不亏本的概率。\若概率为1，则输出1/1，概率为0，则输出0/1。输出一个最简分数a/b，表示小A不亏本的概率。若...