- 博客(27)
- 收藏
- 关注
RSS订阅转载 动态规划-非法二进制数
描述如果一个二进制数包含连续的两个1，我们就称这个二进制数是非法的。小Hi想知道在所有 n 位二进制数（一共有2n个）中，非法二进制数有多少个。例如对于 n = 3,有 011, 110, 111 三个非法二进制数。由于结果可能很大，你只需要输出模109+7的余数。输入一个整数 n (1 ≤ n ≤ 100)。输出n 位非法二进制数的数目模109+7的余数。样例输入3样例输出3解题思路：一道dp的...
2018-05-04 18:14:16
715
转载 简单想法gcd，lcm
Description这世界上所有的不利状况，都是当事者能力不足导致的。在这个强者生存弱者死亡的世界中，作为一个刚刚进入这个残酷世界中的你，被壁虎抓住了，壁虎是一个特别喜欢折磨人的喰种，因此他对你进行了残忍的折磨，并且在折磨你的同时为了让你保持清醒，他会让你从n开始，每次减掉x，且将每次减掉x后的数读出来（包括n本身也要读），直到这个数再次减掉x后小于0为止（不包括小于0的数）。且在最后他还要让你...
2018-05-04 17:08:29
200
转载 大数相乘java和py
ac代码：java：import java.math.BigInteger;import java.util.*;public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scan=new Scanner(Syste...
2018-05-04 16:32:55
186
转载 动态规划入门
会长大人非常喜欢玩《塞尔达传说:旷野之息》，有一天，手残的会长大人lj拜托游戏达人lmj帮忙开启最困难的第120个祠堂，这个祠堂的通过方法可以转化为一个一维问题。你初始在0这个位置，终点是n这个位置，你每次最多可以跳3格。很不幸的是，有些位置是有陷阱的，每踩一下扣一点血，你开始有k点血，也就是说你最多踩k-1个陷阱。问跳到终点不死有多少种跳法，保证有解。lmj一看这个问题实在是太简单了，所以把这个...
2018-05-04 16:27:51
157
转载 next_permutation入门
链接：https://www.nowcoder.com/acm/contest/116/B来源：牛客网杨老师给同学们玩个游戏，要求使用乘法和减法来表示一个数，他给大家9张卡片，然后报出一个数字，要求大家用表达式的形式来表示出这个数 100 可以表示为这样的形式：100 = 129*67-8543 ， 还可以表示为：100 = 13*489-6257 注意特征：表达式中，数字1~9分别出现且只出现一...
2018-05-04 16:07:18
143
转载 等差数列The sum problem
The sum problem——中级DescriptionGiven a sequence 1,2,3,......N, your job is to calculate all the possible sub-sequences that the sum of the sub-sequence is M.InputInput contains multiple test cases. eac...
2018-03-16 09:34:57
235
转载 排列组合之考新郎
国庆期间,省城HZ刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,叫做"考新郎",具体的操作是这样的:首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个.最后,揭开盖头,如果找错了对象就要当众跪搓衣板...看来做新郎也不是容易的事情...假设一共有N对新婚夫妇,其中有M个...
2018-03-16 07:39:56
120
原创 树状数组之敌兵布阵
DescriptionC国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。中央情报局要研究敌人究...
2018-03-15 15:42:58
143
原创 线段树之敌兵布阵（单点更新）
DescriptionC国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。中央情报局要研究敌人究...
2018-03-15 15:40:44
140
转载 二分答案
记得上学那会， Fbs同学经常会欺负萝卜同学。有一次，他出了这么一道题目，想为难一下萝卜同学。题目是这样的： 有N个整数X_i， X_i值的范围从0到1000000000。要从中选出C个数（ 2<=C<=N），使得任意两个数差的绝对值的最小值尽可能大，求这个最大值。 由于数据太大， 这次萝卜同学的确被难住了，怎么办呢，请你来帮帮萝卜同学吧！ 【输入格式】 第一行是N和C。 接下来的N行...
2018-03-15 15:14:13
884
转载 set之人见人爱a-b
参加过上个月月赛的同学一定还记得其中的一个最简单的题目，就是{A}+{B}，那个题目求的是两个集合的并集，今天我们这个A-B求的是两个集合的差，就是做集合的减法运算。（当然，大家都知道集合的定义，就是同一个集合中不会有两个相同的元素，这里还是提醒大家一下）呵呵，很简单吧？Input每组输入数据占1行,每行数据的开始是2个整数n(0<=n<=100)和m(0<=m<=100)...
2018-03-15 14:50:39
147
原创 F - Load Testing CodeForces - 847H 前缀后缀和
Input 51 4 3 2 5 Output 6 Input 51 2 2 2 1 Output 1 Input 710 20 40 50 70 90 30 Output 0题目大意：问最小要加多少才能使整个数组先递增后递减（包括只递增和...
2018-03-15 14:41:57
181
原创 较优解之人见人爱a-b
参加过上个月月赛的同学一定还记得其中的一个最简单的题目，就是{A}+{B}，那个题目求的是两个集合的并集，今天我们这个A-B求的是两个集合的差，就是做集合的减法运算。（当然，大家都知道集合的定义，就是同一个集合中不会有两个相同的元素，这里还是提醒大家一下）呵呵，很简单吧？Input每组输入数据占1行,每行数据的开始是2个整数n(0<=n<=100)和m(0<=m<=100)...
2018-03-14 21:41:41
332
原创 完全背包入门
设有n种物品，每种物品有一个重量以及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为m，现在从n种物品中选取若干件（同一种物品可以多次选择），使其重量的和小于等于m，而价值的和为最大。Input两个整数m,n(背包容量m<=200, 物品数量n<=30);每行2个整数分别表示每个物品的重量和价值。Output最大总价值Sample Input12 42 13 34 ...
2018-03-14 18:07:10
180
1
原创 01背包入门
Description一个旅行者有一个最多能装m公斤的背包，现有n件物品，它们的重量分别是w1,w2,w3,...,wn，它们的价值分别为c1,c2,c3,...,cn。若每种物品只有一件，求旅行者能获得的最大总价值。Inputm，和n（m<=200, n<=30)接下来共n行每行两个整数wi,ciOutput最大总价值Sample Input10 42 13 34 57 9解...
2018-03-14 18:04:15
195
原创 dfs入门之迷宫（超时）
迷宫Description小C最近在研究机器人，他想看看自己的机器人够不够智能，于是他将机器人放在一个n*m的迷宫中，看看机器人能不能在最短的时间内到达目的地，可是小C不知道最短的时间是多少，现在请你帮他算算机器人到达目的地的最短时间是多少？输入数据第一行两个整数n和m。接下来n行，每行m个元素，表示迷宫的每个方格。'S'表示机器人的出发点,'T'表示目的地，'#'表示该方格不能通过'.'表示可以...
2018-03-14 17:32:28
1414
转载 bfs入门之迷宫
迷宫Description小C最近在研究机器人，他想看看自己的机器人够不够智能，于是他将机器人放在一个n*m的迷宫中，看看机器人能不能在最短的时间内到达目的地，可是小C不知道最短的时间是多少，现在请你帮他算算机器人到达目的地的最短时间是多少？输入数据第一行两个整数n和m。接下来n行，每行m个元素，表示迷宫的每个方格。'S'表示机器人的出发点,'T'表示目的地，'#'表示该方格不能通过'.'表示可以...
2018-03-14 16:47:38
676
原创 前缀和+（尺取法 || 二分）
NanoApe Loves Sequence ⅡTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others)Problem DescriptionNanoApe, the Retired Dog, has returned back to prepare for for the Natio...
2018-03-14 07:34:06
443
原创 选数
Description 已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为： 3＋7＋12=22 3＋7＋19＝29 7＋12＋19＝38 3＋12＋19＝34。 现在，要求你计算出和为素数共有多少种。 ...
2018-03-13 22:12:25
467
原创 01背包+dfs
重物运输--中高级Time Limit: 1000MS Memory Limit: 65536 Description大活附近的新楼终于造好了，包工头准备尽快打扫完工地，立刻交付工程。此时工地上有n个杂物，包工头想要先运走m个重物，但只有一辆载重量为W的卡车停在工地上，包工头想要尽可能大的利用此卡车载重能力。问这辆卡车走的时候运载了多少重量的东西？Input第1行：n(n<=20)，m，...
2018-03-13 21:55:42
286
转载 最简单的bfs
题意大意： 一个特别的电梯，按up可升上k[i]层，到大i+k[i]层，down则到达i-k[i]层，最高不能超过n，最低不能小于1，给你一个起点和终点，问最少可以按几次到达目的地。在一个N层高的楼有一个奇怪的电梯，在每一层只能上升或下降一个特定的层数，中间不会停止，在给定的条件下，问能不能到达指定楼层，可以到达的话返回转操作次数，不可以的话返回-1.InputThe input c...
2018-03-13 21:30:09
169
转载 抽签问题
题目大意： 每次从n个数里抽取一个数记录后并放回，问是否存在抽取的四个数之和为m的情况。解题思路： 当n<10的时候，直接枚举即可；当n<1000时，则需要进行优化，先将四个数分为俩俩之和，再对结果进行二分搜索。下面的算法时间复杂度为O(n^2 log n)。ac代码：#include<bits/stdc++.h>using namespace ...
2018-03-13 20:49:08
323
原创 部分和问题
题目大意： 给定整数a1,a2,..,an，判断是否可以从中选出若干数，使它们的和为k，如果存在请打印，n<=20。ac代码1：#include<bits/stdc++.h>using namespace std;int n,k,a[22],b[22],flag,sum;void dfs(int pos){ if(flag == 1) retur...
2018-03-13 19:11:35
182
原创 01背包+暴力枚举
重物运输--中高级Time Limit: 1000MS Memory Limit: 65536 Description大活附近的新楼终于造好了，包工头准备尽快打扫完工地，立刻交付工程。此时工地上有n个杂物，包工头想要先运走m个重物，但只有一辆载重量为W的卡车停在工地上，包工头想要尽可能大的利用此卡车载重能力。问这辆卡车走的时候运载了多少重量的东西？Input第1行：n(n<=20)，m，...
2018-03-13 18:29:49
1188
原创 三角形
三角形（续）--中高级 Time Limit: 1000MS Memory Limit: 65536Description Zzy现在正在研究三角形的稳定性，所以他想自己做一个三角形测试一下，于是他来到了一堆木棍边上，一共有n条木棍，现已知每条木棍的长度，试问，任意挑选三根木棍能组成三角形的方案数是多少。 Input 输入数据有多组，先输入T，表示组数，接下每组包括...
2018-03-13 18:03:08
375
原创 线段树
B - Manipulate Dwarfs SPOJ - DWARFLOG题目大意： n个小矮人初始编号是 1 - n，1 x y 代表 x 和 y 交换，2 x y 代表询问 x ,x+1...y这些小矮人是否连续。解题思路： 目测（2 ≤ N ≤ 200 000, 2 ≤ M ≤ 200 000）就是线段树，维护区间最大值和最小值，找到最大值和最小值相减，如果长度...
2018-03-13 07:29:25
95
原创 贪心+结构体排序
A - Cleaning Shifts POJ - 2376 题目大意： 完全覆盖1-t所需要最小的奶牛数量。。。解题思路： 首先按开始时间从小到大排序，比如1肯定要在最前面。如果开始时间相同，就把结束时间大的放前面，因为要使奶牛数量最小。比如1-5，1-3，毫无疑问选择1-5。HDU...
2018-03-12 07:23:26
276
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人