- 博客(52)
- 收藏
- 关注
RSS订阅原创 二分求最大上升序列长度
#include#includeconst int MAXN=200001;int a[MAXN];int d[MAXN];//二分求最大上升序列长度int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);d[1]=a[1];int len=1;for(int i=2;i<=n;i++){if(a[i]>d[len])d[++len]=a[i];else
2021-05-29 09:07:06
102
原创 alan的字符串
题目链接：https://ac.nowcoder.com/acm/contest/11189/D小y有两个字符串 aa, bbnn 和 mm 分别为 aa 和 bb 的长度小y想选一个 aa 和 bb 的公共子序列，然后她希望这个子序列是回文的并且希望这个公共子序列尽可能长可是小y不会，于是就请教了alanalan瞬间就秒掉了，你知道alan是怎么做的吗？orz输入描述:第一行包含一个字符串，表示字符串 aa 。 第二行包含一个字符串，表示字符串 bb 。输出描述:一行，包含一个整数，表
2021-05-11 21:27:08
363
原创 线段树，树状数组
树状数组单点修改，区间查询void add(int x,int k){while(x<=n){t[x]+=k;x+=x&(-x);}}int ask(int x){ int sum=0； while(x>0) { sum+=t[x]; x-=x&(-x); } return sum;}// add(x,k);// ask(r)-ask(l-1);区间修改，单点查询void add(int x,in
2021-05-10 10:30:36
107
3
原创 加工生产调度（贪心）
题目描述某工厂收到了 个产品的订单，这 个产品分别在 A、B 两个车间加工，并且必须先在 A 车间加工后才可以到 B 车间加工。某个产品 在 A，B 两车间加工的时间分别为 。怎样安排这 个产品的加工顺序，才能使总的加工时间最短。这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在 A，B 两车间加工完毕的时间。输入格式第一行仅—个数据 ，表示产品的数量；接下来 个数据是表示这 个产品在 A 车间加工各自所要的时间；最后的 个数据是表示这 个产品在 B 车间加工
2021-02-28 15:50:10
977
原创 DNA sequence（深度搜索+剪枝）
The twenty-first century is a biology-technology developing century. We know that a gene is made of DNA. The nucleotide bases from which DNA is built are A(adenine), C(cytosine), G(guanine), and T(thymine). Finding the longest common subsequence between DN
2021-02-28 15:32:40
313
原创 求字符串中最长回文串的长度
给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度.回文就是正反读都是一样的字符串,如aba, abba等Input输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c…y,z组成的字符串S两组case之间由空行隔开(该空行不用处理)字符串长度len <= 110000Output每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.Sample InputaaaaababSample Output
2021-02-21 14:04:04
174
原创 非连续递增序列求和
Nowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular in HDU. Maybe you are a good boy, and know little about this game, so I introduce it to you now.The game can be played by two or more than two players. It consists of
2021-02-21 13:22:46
134
原创 最小生成树（Jungle Roads）
The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years ago. But the jungle overtakes roads relentlessly, so the large road network is too expensive to maintain. Th
2021-02-07 11:28:06
87
原创 加权并查集
In 12th Zhejiang College Students Games 2007, there was a new stadium built in Zhejiang Normal University. It was a modern stadium which could hold thousands of people. The audience Seats made a circle. The total number of columns were 300 numbered 1–300,
2021-02-07 10:55:55
54
原创 KMP(b中有几个a)
The French author Georges Perec (1936–1982) once wrote a book, La disparition, without the letter ‘e’. He was a member of the Oulipo group. A quote from the book:Tout avait Pair normal, mais tout s’affirmait faux. Tout avait Fair normal, d’abord, puis sur
2021-01-31 10:17:25
94
1
原创 KMP求循环次数
Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then ab = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (t
2021-01-31 09:58:00
150
原创 线段树(区间修改，区间查询)
You have N integers, A1, A2, … , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.InputThe first line c
2021-01-24 14:55:21
192
原创 排兵布阵（线段树，单点修改，区间查询）
C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地
2021-01-24 14:33:56
49
原创 求平均数最大，长度不小于 L
给定一个长度为 的非负整数序列 ，求一个平均数最大的，长度不小于 的子段。输入格式第一行用空格分隔的两个整数 和 ；第二行为 个用空格隔开的非负整数，表示 。输出格式输出一个整数，表示这个平均数的 倍。不用四舍五入，直接输出。样例样例输入10 66 4 2 10 3 8 5 9 4 1样例输出6500思路直接用二分去找最大平均数代码#include<stdio.h>#include<string.h>#include<math.h&
2020-10-29 21:50:49
1930
原创 愤怒的牛
农夫约翰建造了一座有 间牛舍的小屋，牛舍排在一条直线上，第 间牛舍在 的位置，但是约翰的 头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。John 决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？输入格式第一行用空格分隔的两个整数 和 ；第二行为 个用空格隔
2020-10-29 20:32:38
667
原创 种树
题目描述某条街被划为 条路段，这 条路段依次编号为 。每个路段最多可以种一棵树。现在居民们给出了 组建议，每组建议包含三个整数 ，表示居民希望在路段 到 之间至少要种 棵树。这些建议所给路段的区间可以交叉。请问：如果要满足所有居民的建议，至少要种多少棵树。输入格式第一行为 ，表示路段数。第二行为 ，表示建议数。下面 行描述一条建议：，用一个空格分隔。输出格式输出只有一个数，为满足所有居民的建议，所需要种树的最少数量。样例样例输入941 4 24 6 28 9 23
2020-10-29 19:39:53
145
原创 查单词
lily的好朋友xiaoou333最近很空，他想了一件没有什么意义的事情，就是统计一篇文章里不同单词的总数。下面你的任务是帮助xiaoou333解决这个问题。Input有多组数据，每组一行，每组就是一篇小文章。每篇小文章都是由小写字母和空格组成，没有标点符号，遇到#时表示输入结束。Output每组只输出一个整数，其单独成行，该整数代表一篇文章里不同单词的总数。Sample Inputyou are my friendSample Output4代码#include<stdio.h
2020-09-26 19:30:13
78
原创 最短路径（求1到各点，各点到1的距离）
In the age of television, not many people attend theater performances. Antique Comedians of Malidinesia are aware of this fact. They want to propagate theater and, most of all, Antique Comedies. They have printed invitation cards with all the necessary inf
2020-09-26 09:59:29
481
原创 并查集（小西的迷宫）
上次Gardon的迷宫城堡小希玩了很久（见Problem B），现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。Input
2020-09-26 09:08:20
164
原创 01背包（小偷的概率）
The aspiring Roy the Robber has seen a lot of American movies, and knows that the bad guys usually gets caught in the end, often because they become too greedy. He has decided to work in the lucrative business of bank robbery only for a short while, before
2020-09-26 08:51:12
111
原创 01背包（食堂）
电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。Input多组数据。对于每组数据：第一行为正整数n，表示菜的数量。n<=1000。第二行包括n个正整数，表示每种菜的价格。价格不超过50。第三行包括一个正整数m，
2020-09-26 08:22:59
54
原创 Sticks 【DFS+剪枝】（集木棒）
George took sticks of the same length and cut them randomly until all parts became at most 50 unitslong. Now he wants to return sticks to the original state, but he forgot how many sticks he had originallyand how long they were originally. Please help hi
2020-09-26 08:06:49
134
原创 滑雪
Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-1
2020-06-11 19:27:17
63
原创 吃奶酪
FatMouse has stored some cheese in a city. The city can be considered as a square grid of dimension n: each grid location is labelled (p,q) where 0 <= p < n and 0 <= q < n. At each grid location Fatmouse has hid between 0 and 100 blocks of chee
2020-06-10 21:01:08
204
原创 最大连续数字之和
给定K个整数的序列{ N1, N2, …, NK }，其任意连续子序列可表示为{ Ni, Ni+1, …,Nj }，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和为20。在今年的数据结构考卷中，要求编写程序得到最大和，现在增加一个要求，即还需要输出该子序列的第一个和最后一个元素。Input测试输入包含若干测试用例，
2020-06-09 20:58:53
456
原创 不起眼的约数
A number whose only prime factors are 2,3,5 or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, … shows the first 20 humble numbers.Now given a humble number, please write a program to calcul
2020-06-05 20:59:59
362
原创 Spell checker
You, as a member of a development team for a new spell checking program, are to write a module that will check the correctness of given words using a known dictionary of all correct words in all their forms.If the word is absent in the dictionary then it
2020-06-04 21:04:13
95
原创 中间数
FJ is surveying his herd to find the most average cow. He wants to know how much milk this ‘median’ cow gives: half of the cows give as much or more than the median; half give as much or less.Given an odd number of cows N (1 <= N < 10,000) and their
2020-06-03 20:57:06
234
原创 All in All（是否存在子字符串）
You have devised a new encryption technique which encodes a message by inserting between its characters randomly generated strings in a clever way. Because of pending patent issues we will not discuss in detail how the strings are generated and inserted in
2020-06-03 20:46:50
51
原创 A/B
题意要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。Input数据的第一行是一个T，表示有T组数据。每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。Output对应每组数据输出(A/B)%9973。Sample Input21000 5387 123456789Sample Output79226060思路：设A = k * 99
2020-05-28 21:25:06
260
原创 N！Again
题意Zty，你在干什么？我想计算N！。。。。。。太简单了！N有多大？中兴通讯：1<=N<=10000000000000000000000000000000000000000000…哦！你一定是疯了！你是法少吗？不，我已经说完了。我只是说我想计算N！2009年版提示：0！=1，N！=N*（N-1）！输入每行包含一个整数N（0<=N<=10^9）。处理到文件结尾。输出对于每种情况，输出N！2009年版样本输入4个5个样本输出24个120个思路求N!
2020-05-28 21:08:16
59
原创 2^x%n=1
题意给出一个n，求满足2^x mod n=1的最小x（x>0）。输入每行一个正整数，n的值。输出如果存在最小x，请打印一行，其中2^x mod n=1。打印2^？否则，mod n=1。你应该用特定的数字代替x和n。样本输入2个5个样本输出2^？mod2=12^4mod5=1思路当n是偶数是n%20一定不可能余1；当n是奇数是n%20一定可以余1；特例n=1时，2^0%1=1;代码#include<stdio.h>int main(){ int n
2020-05-27 22:01:18
177
原创 前三项后三项
题意；求a^b的前三项和后三项；Sample Input5123456 1123456 22 312 3229 8751919Sample OutputCase 1: 123 456Case 2: 152 936Case 3: 214 648Case 4: 429 296Case 5: 665 669思路；求后三项直接快速幂；求前三项注意要用double型代码#include<stdio.h>int main(){ int t,q=1; long l
2020-05-27 21:48:49
103
原创 求先序求后序
求先序给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度 \le≤ 8）。输入格式2 行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。输出格式1 行，表示一棵二叉树的先序。输出时每行末尾的多余空格，不影响答案正确性样例输入BADCBDCA样例输出ABCD代码 #include<stdio.h>#includ...
2020-04-23 20:38:32
76
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人