- 博客(36)
- 收藏
- 关注
RSS订阅
原创 深搜与广搜
深搜深搜是一种一条路走到黑，碰壁就倒退的算法。运用递归思想，如果到了不符合条件的节点就撤回一步，然后再选择另一条路走下去。如果这个节点的所有路径都走完了，再撤回一步。//最简单的模板int x[4]={0,1,0,-1};int y[4]={1,0,-1,0};//上下左右四个方向走。也可以八个方向，这里我就不写了。void dfs(int fx,int fy){//fx，fy是现在的...
2019-02-23 20:38:39
342
原创 RMQ问题
题目：忠诚解题思路代码里有代码#include <iostream>#include <cmath>//cmath库下有log()和log2()等#include <algorithm>//algorithm用来做max(),min()using namespace std;int a[100010];int dp[100010][30];//...
2019-02-10 10:30:46
154
原创 FBI树
题目描述我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2^N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：T的根结点为R，其类型与串S的类型相同；若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S...
2019-02-04 13:33:04
330
原创 新二叉树
题目描述输入一串二叉树，用遍历前序打出。输入格式：第一行为二叉树的节点数n。(n≤26)后面n行，每一个字母为节点，后两个字母分别为其左右儿子。空节点用*表示输出格式：前序排列的二叉树输入样例1：6abcbdicj*d**i**j**输出样例1：abdicj解题思路也是直接上代码。代码#include <iostream>#include &...
2019-02-04 13:32:07
481
原创 求先序排列
题目描述给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度≤8。输入格式：2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。输出格式：1行，表示一棵二叉树的先序。输入样例1：BADCBDCA输出样例1：ABCD解题思路就是一个先中后序遍历的问题，看代码吧，有标注示。代码#include <iostream>...
2019-01-05 15:19:59
1731
1
原创 USACO Prime Cryptarithm 牛式
题目描述农夫约翰的奶牛不停地从他的农场中逃出来，导致了很多损害。为了防止它们再逃出来，他买了一只很大的号码锁以防止奶牛们打开牧场的门。农夫约翰知道他的奶牛很聪明，所以他希望确保它们不会在简单地试了很多不同的号码组合之后就能轻易开锁。锁上有三个转盘，每个上面有数字1…N (1 <= N <= 100)，因为转盘是圆的，所以1和N是相邻的。有两种能开锁的号码组合，一种是农夫约翰设定的，...
2018-12-16 15:13:08
130
原创 树状数组（区间修改单点查询）洛谷：树状数组2
模版和单点修改区间查询差不多树状数组（单点修改区间查询）https://blog.csdn.net/johnwayne0317/article/details/84927585然后用到了差分数组https://blog.csdn.net/johnwayne0317/article/details/84928568代码#include <bits/stdc++.h>us...
2018-12-16 14:49:21
216
原创 USACO Barn Repair 修理牛棚
题目描述在一个夜黑风高,下着暴风雨的夜晚,farmer John的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假，所以牛棚没有住满。 牛棚一个紧挨着另一个被排成一行，牛就住在里面过夜。 有些牛棚里有牛，有些没有。 所有的牛棚有相同的宽度。 自门遗失以后,farmer John必须尽快在牛棚之前竖立起新的木板。 他的新木材供应商将会供应他任何他想要的长度,但是吝啬的供应商只能提供有限数目的木板。 f...
2018-12-15 21:57:27
184
原创 结构体排序
结构体排序是一个非常重要的语句，不会的话有些题目要超级复杂的方式才能做。什么时候使用？如果要把两个数组以其中一个数组的形式排列例如：价格供应量520940310880630现在要变为价格供应量310520630880940怎么用？伪代码#inclu
2018-12-13 22:04:44
967
7
原创 USACO mixing milk 混合牛奶
题目描述由于乳制品产业利润很低，所以降低原材料（牛奶）价格就变得十分重要。帮助Marry乳业找到最优的牛奶采购方案。Marry乳业从一些奶农手中采购牛奶，并且每一位奶农为乳制品加工企业提供的价格是不同的。此外，就像每头奶牛每天只能挤出固定数量的奶，每位奶农每天能提供的牛奶数量是一定的。每天Marry乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。给出Marry乳业每天对牛奶...
2018-12-13 21:52:45
356
原创 USACO dual palindromic 双重回文数
题目描述如果一个数从左往右读和从右往左读都是一样，那么这个数就叫做“回文数”。例如，12321就是一个回文数，而77778就不是。当然，回文数的首和尾都应是非零的，因此0220就不是回文数。事实上，有一些数（如21），在十进制时不是回文数，但在其它进制（如二进制时为10101）时就是回文数。编一个程序，从文件读入两个十进制数N (1 &lt;= N &lt;= 15)S (0 &lt; S ...
2018-12-12 22:09:48
255
原创 进制转换
int a[100]//数组无法返回数组void change(int n){ int cnt=0; while(n!=0){ a[cnt]=n%jin; n/=jin; cnt++; } return ;}
2018-12-12 21:57:27
134
原创 USACO palindromic squares 回文数平方
题目描述回文数是指从左向右念和从右向左念都一样的数。如12321就是一个典型的回文数。给定一个进制B(2&amp;lt;=B&amp;lt;=20,由十进制表示)，输出所有的大于等于1小于等于300（十进制下）且它的平方用B进制表示时是回文数的数。用’A’,’B’……表示10，11等等输入格式：共一行，一个单独的整数B(B用十进制表示)。输出格式：每行两个B进制的符合要求的数字，第二个数是第一个数的平...
2018-12-12 21:26:27
168
原创 单向链表与双向链表
单向链表单向链表的特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；列表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向NULL的指针。双向链表双向链表的每个数据结点中都有两个指针，分别指向前面的rlink和后面的lli...
2018-12-09 20:35:58
2917
原创 USACO namenum 命名那个数字
中文版题目：https://www.luogu.org/problemnew/show/P3864虽然翻译得不太好，但是将就着看吧。解题思路这道题有点坑，有两种解题方式（一种简单，一种难）：第一种（简单）：把名字化为数字。第二种（困难）：把数字化为名字。我最开始尝试的是第二种，写了半个小时想不出来，就果断放弃用第一种做。然后就做出来了代码...
2018-12-09 20:24:35
301
原创 前缀和
编号a1234567891011121314151617b10111213现在要从a数组中截取b数组知道b的和1000000次，而且不能够直接记下b数组的值，要一次一次算，怎么快速求？这样看也许看不出什么，但是我再画一幅图你就明白了编号...
2018-12-09 16:02:55
1376
原创 差分数组
现在有数组a[7]int a[7];a[0]=1;a[1]=2;a[2]=4;a[3]=5;a[4]=12a[5]=34;a[6]=123;a[7]=3;如果要把a[0]-a[4]都加一，最朴素的方法就是a[0]++;a[1]++;a[2]++;a[3]++;a[4]++;时间复杂度为O(n)打字打着都很费力。。。但是如果先有一个神奇的差分数组d[7]，就...
2018-12-09 15:36:53
2448
3
原创 树状数组（单点修改区间查询）
lowbit（重要！）lowbit是用来取出二进制中最低位数的1所代表的二进制的值。只需要记下代码就行了int lowbit(int x){ return x&amp;amp;(-x);}add单点修改前缀和将一个树的最子节点修改，则其父节点也需要更改，父父节点也需要修改。x=x+lowbit(x)就是用来取出其父节点的。void add(int x,int k){ while(x&amp;...
2018-12-09 13:59:35
897
原创 USACO transformations 方块转换
题目描述一块N x N（1&lt;=N&lt;=10）正方形的黑白瓦片的图案要被转换成新的正方形图案。写一个程序来找出将原始图案按照以下列转换方法转换成新图案的最小方式：1：转90度：图案按顺时针转90度。2：转180度：图案按顺时针转180度。3：转270度：图案按顺时针转270度。4：反射：图案在水平方向翻转（以中央铅垂线为中心形成原图案的镜像）。5：组合：图案在水平方向翻转，然后...
2018-12-03 12:47:58
452
原创 USACO milking cows 挤牛奶
QuestionThree farmers rise at 5 am each morning and head for the barn to milk three cows. The first farmer begins milking his cow at time 300 (measured in seconds after 5 am) and ends at time 1000. T...
2018-12-02 12:32:35
662
原创 USACO broken necklace 破碎的项链
QUESTIONYou have a necklace of N red, white, or blue beads (3&lt;=N&lt;=350) some of which are red, others blue, and others white, arranged at random. Here are two examples for n=29: 1 2 ...
2018-12-01 19:27:36
335
原创 noip第四弹 判断语句
有两种判断语句 if 判断和 switch 判断if判断是一个简单明了的语句。但是学习它之前先要学会几个逻辑运算符==等于——就是等于，为了和赋值的 ‘=’ 区分开来，就创立了它 eg：a==b a等于b!=不等于——（!）在C++和C语言中就是不的意思 eg：n!=1 n不等于1&&与——并且的意思，需要同时成立 eg：if(a==1&am...
2018-11-27 22:20:41
81
原创 2009 junior T2 分数线划定
题目描述世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%划定，即如果计划录取m名志愿者，则面试分数线为排名第m×150%（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。现在就请你编写程序划定面试分数线，并输出所有进入面试...
2018-11-26 12:50:29
161
原创 noip第三弹 循环语句
循环语句包括for循环和while循环。其中两个可以互相转换。while循环最简单的while(1)即为无限循环#include &amp;lt;iostream&amp;gt;using namespace std;int main(){while(1){//其中在计算机中 1 即为真， 0 即为假。真就是做的意思，假就是不做的意思。printf(&quot;hello world\n&quot;);}re
2018-11-25 21:09:37
299
原创 2009 junior T1 多项式输出 题解
题目描述一元 n 次多项式可用如下的表达式表示：其中，aixi称为 i 次项，ai 称为 i 次项的系数。给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：1.多项式中自变量为 x，从左到右按照次数递减顺序给出多项式。2.多项式中只包含系数不为 0 的项。3.如果多项式 n 次项系数为正，则多项式开头不出现“+”号，如果多项式 n 次项系数为负，则多项式以“-”...
2018-11-24 22:03:15
404
原创 2010 junior T1 数字统计 题解
题目描述请统计某个给定范围[L, R]的所有整数中，数字2出现的次数。比如给定范围[2, 22]，数字2在数2中出现了11次，在数 12中出现 1 次，在数20中出现1次，在数21中出现1次，在数22中出现2次，所以数字22在该范围内一共出现了6次。输入格式：22个正整数L和R，之间用一个空格隔开。输出格式：数字2出现的次数。输入样例1：2 22输出样例1：6输入样例2：2...
2018-11-23 12:54:56
308
原创 2011 junior T1 数字反转 题解
题目描述给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2）。输入格式：一个整数 N输出格式：一个整数，表示反转后的新数。输入样例1：123输出样例1：321输入样例2：-380输出样例2：-83【数据范围】−1,000,000,000≤N≤1,000,000,00...
2018-11-21 16:36:03
210
原创 2012 junior T1 质因数分解 题解
题目描述已知正整数n是两个不同的质数的乘积，试求出两者中较大的那个质数。输入格式：一个正整数n。输出格式：一个正整数p，即较大的那个质数。输入样例1：21输出样例1：7【样例说明】n≤2×10^9解题思路是质数的话只需要从2开始一个一个试过去，是n的因数就停止。这个答案p1肯定是较小的那个。只需要用n/p1就可以得出p了代码#include &amp;amp;lt;iostream&amp;amp;...
2018-11-21 16:13:23
266
原创 2013 junior T1 计数问题 题解
题目描述试计算在区间 11 到 n n的所有整数中，数字 x(0 ≤ x ≤ 9)x(0≤x≤9)共出现了多少次？例如，在 11到 11 11中，即在 1,2,3,4,5,6,7,8,9,10,111,2,3,4,5,6,7,8,9,10,11 中，数字 11 出现了 44 次。输入格式：22个整数n,xn,x，之间用一个空格隔开。输出格式：11个整数，表示xx出现的次数。输入样例#1...
2018-11-21 15:56:25
201
原创 2014 junior T1 珠心算测试 题解
题目描述珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？最近老师出了一些测验题，请你帮忙求出答案。(本题目为201...
2018-11-21 12:54:03
320
原创 2015 junior T1 金币 题解
题目描述国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续N+1N+1天里，每天收到N+1N+1枚金币。请计算在前KK天里，骑士一共获得了多少金币。输...
2018-11-21 12:42:04
554
原创 2016 junior T1 买铅笔 题解
题目描述P老师需要去商店买n支铅笔作为小朋友们参加NOIP的礼物。她发现商店一共有3种包装的铅笔，不同包装内的铅笔数量有可能不同，价格也有可能不同。为了公平起 见，P老师决定只买同一种包装的铅笔。商店不允许将铅笔的包装拆开，因此P老师可能需要购买超过n支铅笔才够给小朋 友们发礼物。现在P老师想知道，在商店每种包装的数量都足够的情况下，要买够至少n支铅笔最少需要花费多少钱。输入输出格式输入格...
2018-11-20 21:51:42
470
原创 2017 junior T1 成绩 题解
这道题非常水，不需要任何算法，考察你会不会编程。#include &amp;amp;amp;amp;amp;lt;bits/stdc++.h&amp;amp;amp;amp;amp;gt;using namespace std;int main(){ int a,b,c; cin&amp;amp;amp;amp;amp;gt;&amp;amp;amp;amp;amp;gt;a&amp;amp;amp;amp;
2018-11-20 21:40:47
391
原创 noip第二弹 输入输出
第二弹 输入输出1.scanfscanf是一种较为快速的输入语句，但是对于cout较为难写#include &amp;amp;amp;amp;amp;amp;lt;bits/stdc++.h&amp;amp;amp;amp;amp;amp;gt;using namespace std;int main(){int a;scanf(&amp;amp;amp;amp;amp;quot;%d&amp;amp;amp;amp
2018-11-10 14:47:59
634
原创 noip第一弹 为了不爆零
C++第一弹 为了不爆零1. 库C++的库数之不尽，但你在noip比赛中只需要使用#include &amp;amp;lt;bits/stdc++.h&amp;amp;gt;就可以了。2. using namespace std;如果你是一个C++选手而不是C语言选手，using namespace std;是一定要写的。不然的话 cin 和 cout 等基础语句是会报错的。3. 主函数主函数是...
2018-11-08 22:16:59
416
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人