清华机试（11）
考研机试解题报告（25）
题目1076：N的阶乘
时间限制：3 秒& 内存限制：128 兆&& 特殊判题：否& 提交：1266& 解决：351
题目描述：
&&&& 输入一个正整数N，输出N的阶乘。
&&& 正整数N(0&=N&=1000)
&&&& 输入可能包括多组数据，对于每一组输入数据，输出N的阶乘
样例输入：
样例输出：
//清华2006：题目1076：N的阶乘
//输出N的阶乘(0&=N&=1000) 即大数乘法
#include &fstream&
#include &iostream&
#include &memory.h&
int a[100000];
//a数组的实际占用长度
void mul(int *a, int b ){ // b 为乘数
int i, tmp, carry=0;
for( i=0; i& i++ ){
tmp = a[i] * b +
a[i] = tmp % 10000; //每个数组max=9999 运算中实际max=9999000 carry=999
carry = tmp / 10000;
if( carry!=0 ){
a[length] =
int main(){
int i, j, k,
//ifstream cin(&THU_1076.txt&);
while( cin && n ){
memset(a,0,sizeof(a));
length = 1;
for( i=2; i&=n; i++ ){
mul( a, i );
//逐级输出 调试用
//for( j=length-1; j&=0; j-- ){
// if( j!=length-1 ){
if( a[j]&10 )
cout && &000&;
else if( a[j]&100 )
cout && &00&;
else if( a[j]&1000 )
cout && &0&;
// cout && a[j];
//ofstream out(&THU_1076_output.txt&);
for( j=length-1; j&=0; j-- ){
if( j!=length-1 ){
if( a[j]&10 )
cout && &000&;
else if( a[j]&100 )
cout && &00&;
else if( a[j]&1000 )
cout && &0&;
cout && a[j];
题目1077：最大序列和
时间限制：1 秒& 内存限制：32 兆& 特殊判题：否& 提交：553& 解决：137
题目描述：
&&& 给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所有数的和为T的“序列和”。
&&& 对于S的所有非空连续子序列T，求最大的序列和。
&&& 变量条件：N为正整数，N≤1000000，结果序列和在范围（-2^63,2^63-1）以内。
&&& 第一行为一个正整数N，第二行为N个整数，表示序列中的数。
&&& 输入可能包括多组数据，对于每一组输入数据，
&&& 仅输出一个数，表示最大序列和。
样例输入：
&&& 1 5 -3 2 4
&&& 1 -2 3 4 -10 6
&&& -3 -1 -2 -5
样例输出：
各种情况都要考虑到啊 包括单个输入数据可能是大数 超出int范围
//清华2006：题目1077：最大序列和
//求给定序列的最大非空连续子序列和
//N为正整数，N≤1000000，结果序列和在范围（-2^63,2^63-1）以内。
#include &fstream&
#include &iostream&
#define INT long long
int main(){
INT temp, sum,
ifstream cin(&THU_1077.txt&);
while( cin && n ){
for( i=0; i&n; i++ ){
if( i == 0 ){
if( temp & 0 )
if( temp & sum )
cout && sum &&
system(&pause&);
题目1078：二叉树遍历
时间限制：1 秒& 内存限制：32 兆& 特殊判题：否& 提交：159& 解决：109
题目描述：
&&& 二叉树的前序、中序、后序遍历的定义：
&&& 前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；
&&& 中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；
&&& 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
&&& 给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。
&&& 两个字符串，其长度n均小于等于26。
&&& 第一行为前序遍历，第二行为中序遍历。
&&& 二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。
&&& 输入样例可能有多组，对于每组测试样例，
&&& 输出一行，为后序遍历的字符串。
样例输入：
&&& FDXEAG
&&& XDEFAG
样例输出：
&&& XEDGAF
因为二叉树遍历几乎不会 所以参考了别人的程序 以后有时间写个自己的非递归版吧
//清华2006：题目1078：二叉树遍历
//两个字符串，其长度n均小于等于26。 第一行为前序遍历，第二行为中序遍历。
//二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。
//输出后序遍历的字符串。
#include &fstream&
#include &string&
#include &iostream&
struct BiTree{
BiTree* process( string S, string T ){
if( S.empty() )
return NULL;
int mark = T.find(S[0]); //t[S[0]-64];
BiTree *b = new BiTree(); //b=binary tree
b-&a = S[0];
b-&l = process( S.substr(1,mark), T.substr(0,mark) );
b-&r = process( S.substr(mark+1,S.size()-mark-1),
T.substr(mark+1,T.size()-mark-1) );
void postTraverse( BiTree* b ){
if( b != NULL ){
if( b-&l != NULL) postTraverse(b-&l);
if( b-&r != NULL) postTraverse(b-&r);
cout && b-&a;
int main(){
string S, T; //preorder inorder postorder
ifstream cin(&THU_1078.txt&);
while( cin && S && T ){
BiTree *B = process( S, T );
postTraverse( B );
system(&pause&);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：106407次
积分：1513
积分：1513
排名：千里之外
原创：43篇
转载：13篇
(1)(1)(1)(2)(1)(1)(4)(1)(1)(1)(3)(20)(19)
(window.slotbydup = window.slotbydup || []).push({
id: '4740881',
container: s,
size: '200,200',
display: 'inlay-fix'题目17(0019)：魔术对；推荐者：王知昆；可以证明：对于任何的整数X和Y，如果5X+4Y能；对于给定的N，和整数对(A0,B0)，找出所有的；输入；每个输入包含三个正整数N,A0和B0(N,A0,；第一行输出整数对(A,B)的数目，以后每一行输出；样例输入312；样例输出3001221；【提示】本题需要一些数论知识，大家可以看看何林同；第26页；题目18
题目17(0019)：魔术对 推荐者：王知昆
可以证明：对于任何的整数X和Y，如果5X+4Y能被23整除，那么3X+7Y一定也能被23整除。
对于给定的N，和整数对(A0, B0)，找出所有的整数对 (A, B)使得对于任何的整数X 和Y，如果A0X+B0Y 能被N整除，AX+BY 都能被N整除 (0<=A,B<N)。
输入 每个输入包含三个正整数 N, A0 和 B0 (N,A0,B0<=10000)。 输出 第一行输出整数对(A, B)的数目，以后每一行输出一个整数对。整数对按A从小到大排序，A相同时按B排序. 样例输入 3 1 2
样例输出 3
0 0 1 2 2 1
【提示】本题需要一些数论知识，大家可以看看何林同学的解题报告。
题目18(0036)：绿色游戏 推荐者：金恺
“Green游戏”是两个人玩的游戏――Ann和Billy说。他们的任务是移动板子上的兵。板子的一些区域是绿色的，余下的是白色的。所有的区域都被区间1..a+b中所有的整数标号。用1 到a的整数所标号的区域属于Ann，而标号为a+1到a+b的区域属于Billy。 每个区域都有一些后继者，包含一个兵能从这个区域通过一步到达的区域。这些后继者符合下面的条件：Ann的区域的后继者属于Billy，反之亦然。所有的区域都有后继者，这样永远可以移动。 游戏开始的我们放一个兵在一个随意选择的区域P，然后游戏者轮流从他们的区域到任何这个区域的后继者（我们知道它属于对手）。游戏从开始区域P的拥有者开始；结束于当兵第二次到同一块区域时，该区域认为是Q区域。如果在一系列移动后，兵从区域Q再次到区域Q，至少有一次放在绿区域，Ann赢这场游戏，否则Billy赢。如果开始区域是P，无论Billy怎么动，Ann总能保证从这个区域开始的游戏他能赢，那么我们说Ann有一个在给定开始区域为P时赢得这场游戏的策略。
任务： 1． 从文件GRA.IN中读入板子的描述； 2． 计算Ann有取胜策略的开始区域； 3． 在文件GRA.OUT中输出结果，输出所有解。
输入： 在文件GRA.IN的第一行有两个正整数a,b ――属于Ann的区域数，属于Billy的区域数。整数a,b满足条件：1≤a+b≤3000。下面的a+b行是描述板子的：首先是属于Ann区域的描述，然后是属于Billy的。第i+1行，1≤i≤a+b，由整数Z、K开始，它们意味着区域i的颜色（0表示白色，1表示绿色）和这个区域的后继者的数目。然后K个整数将会写下来（1≤K≤a+b）（仍然在同一行），它们指出第i个区域的后继者的数字。这些数字由空格隔开。板子上的绿色区域不超过100。板上所有区域的后继者不超过30000。
输出： 文件GRA.OUT的第一行应包含一个整数I，它指出Ann有取胜策略的区域的数目。下面I行包含以上升顺序写出的区域标号――每个数写一行。
样例输入 样例输出 5 3 0 2 6 7 0 3 6 7 8 0 1 8 1 1 7 1 1 8 1 2 1 2 0 2 1 2 0 2 3 4 5 1 2 4 6 7
第27页 【提示】不错的博弈题目，可以用图论方法来分析。大家可以看看上届集训队员的解题报告。 第28页
题目19(0040)：跳跃 推荐者：张宁
“跳跃”是一个棋盘游戏，在一个无限大的带状方格上进行。棋盘既没有左边界也没有右边界。在棋盘上放着有限的棋子（一格上可以有多个棋子）。我们假定最左非空的方格被标号为0。右边的方格被表示成连续的自然数1, 2, 3, ...，左边的方格被表示成负整数：-1, -2, -3, ...。棋盘上棋子的放置方式被描述为以下方式：我们将给出每一个至少有一个棋子的方格的标号以及方格上棋子的个数。有两种移动方式可以改变棋子的放置方式：右跳与左跳。右跳有以下步骤，从棋盘上移走两个棋子：一个从方格p，另一个从方格p+1，并且在方格p+2上放上一个棋子。左跳有以下步骤，从方格p+2移走一个棋子，并且在棋盘上放置两个棋子：一个放在方格p+1上，另一个放在方格p上。我们将一个最终状态定义为：两个相邻方格至多只有一个棋子。对于每一个棋盘放置方式可以通过有限步来达到一种最终状态，并且只有一种最终状态。
任务 写一个程序： ? 从输入文件SKO.IN 中读入棋盘初始状态的描述 ? 找出所给初始状态可以达到的最终状态，并且将最终状态的描述输出到输出文件SKO.OUT。
输入 在输入文件SKO.IN的第一行有一个正整数n，1 <= n <= 10000，表示非空方格的数目。在接下来的每一行中有两个整数。第一个是方格的标号，第二个是方格上棋子数目。描述以方格标号的升序顺序给出。其中最大的方格标号不超过10000，一个方格上棋子的个数不超过。
输出 在输出文件SKO.OUT的第一行描述所给初始状态所能达到的最终状态。即在这一行中需要包含最终状态非空的方格的标号（以升序给出）。所有数字以一个空格隔开。
样例输入 2 0 5 3 3
样例输出 -4 -1 1 3 5
【提示】本题和Fibonacci数列有关，大家能看出来么？ 第29页
题目20(0041)：装容器 推荐者：张宁
一个公司生产的产品被装进圆柱型的盒子。所有的盒子有着同样的底部。盒子的高度是2的幂次，等于2i (i=0,1,2,…)，指数i被称为盒子的大小。所有的盒子都装着同样的货物，但是它们的价值可能不同。早期生产的货物要便宜些。管理者决定，将最早生产的货物(最便宜)最先出售。在仓库中货物被送进容器中。容器同样也是圆柱型。每个容器的直径要比盒子稍大一些，所以盒子可以容易地放进容器中。容器的高度也是2的幂次。指数被称为容器的大小。为了安全地运送容器，容器必须紧紧地装满盒子，就是说被装入容器的盒子的高度总和应等于容器的高度。一些容器已经被送到了仓库。检查是否可能将容器用盒子装满，如果可能的话，求出被装进容器的货物的价值和的最小值。
例子 仓库中有5个盒子。它们的大小及价值给出如下：1 3；1 2；3 5；2 1；1 4。 两个容器大小分别为1和2可以被两个盒子填满可能得到的价值总和为3，4或5，或者被三个盒子填满而得到总价值9。大小为5的容器不可能被这些盒子填满。
任务 写一个程序，读取仓库中盒子的描述(大小，价值)，和容器的描述(大小，数量)，并检查所有的容器是否能被仓库中的盒子装满，如果可以，则计算出所有货物价值总和的最小值。
输入 输入文件PAK.IN的第一行有一个整数n，1<=n<=10000，表示仓库中盒子的个数。在接下来的n行中，每行有两个非负整数，中间有一个空格。两个数字描述了一个盒子。第一个数字表示盒子的大小，第二个数字表示盒子中货物的价值。盒子的大小不会超过1000，并且价值不会超过10000。接下来的一行有一个正整数q，表示不同大小的容器的种类数目。在接下来的q行中，每行有两个正整数，中间有一个空格。第一个整数表示容器的大小，第二个整数表示这种大小的容器的数目。容器的总数不超过5000，每个容器的大小不超过1000。
输出 如果不可能将所有的容器用所给出的盒子装满则输出一个单词NIE (波兰语中没有的意思) 如果可以将所有的容器用所给出的盒子装满则输出所有被装入的货物的总价值的最小值。
样例输入 样例输出 5 3 1 3 1 2 3 5 2 1 1 4 2 1 1 2 1 【提示】本题可以贪心。 第30页 三亿文库包含各类专业文献、外语学习资料、幼儿教育、小学教育、文学作品欣赏、中学教育、高等教育、302003集训队100道讨论题等内容。　
　2003年中国国家集训队测试_高三数学_数学_高中教育_...(黄玉民供题) 2003 年中国国家队培训 第一套 1....17. 考虑直角坐标平面上由 100 个点组成的集合 M... 　2003年物理奥赛集训队考试题_学习总结_总结/汇报_实用文档。2003年物理奥赛集训...实验试题 试题一: 实验基础知识 1.(1)指出以下数据各有几位有效数字: 0.100... 　2003年物理奥赛集训队考试题2003年物理奥赛集训队考试题隐藏&& 第27 届全国中学生物理竞赛决赛试题
使用一键分享,轻松赚取财富值, 了解详... 　京翰教育中心
2003 年 IMO 中国国家集训队选拔考试试题( 8:00―12:30) 一、在锐角△ABC 中,AD 是∠A 的内角平分线,点... 　4页 4下载券 浅析一道竞赛集训队试题... 暂无评价 2页 免费 ...对于 100%的数据 1≤n≤20000,1≤m≤50,1≤C≤2000。对于满足 2≤i ≤n... 　2003年IMO中国国家集训队选拔考试试题_学科竞赛_小学教育_教育专区。IMO中国国家集训队选拔考试试题2003 年 IMO 中国国家集训队选拔考试试题( 8:00―12... 　蓝天小学04贡献于 0.0分 (0人评价)暂无用户评价 我要评价 ...一年级集训队每周习题(1) 暂无评价|0人阅读|0次下载|举报文档 每周习题: 第... 　历年国家集训队论文题目_法律资料_人文社科_专业资料...动态规划的深入讨论 解决空间规模问题的几种常用的...2003 年方奇 高正宇 何林 侯启明 姜尚仆 金恺 ...03 2014 档案
摘要: 题目描述：在初试即将开始的最后一段日子里，laxtc重点练习了英语阅读的第二部分，他发现了一个有意思的情况。这部分的试题最终的答案总是如下形式的：1.A;2.C;3.D;4.E;5.F。即共有六个空格，每个空格填入一个相应的字母代表这个空格他所选择的答案，且空格中的字母不存在重复。若每个空格选择的答案都是严格递增的，则laxtc认为这个答案是和谐的，如1.A;2.C;3.D;4.E;5.F;反之，若答案中存在不递增的情况，则他认为这组答案是不和谐的，如1.A;2.C;3.B;4.E;5.F;laxtc总是希望他所选择的答案是和谐的。由于laxtc的英语并不怎么好，所以他也经常会空着一些空格，如
SangS 阅读(324) |
摘要: 题目描述：给定一个数组，判断数组内是否存在一个连续区间，使其和恰好等于给定整数k。输入：输入包含多组测试用例，每组测试用例由一个整数n(1#include #includeclass Node {public: int i, Node(int _i, int _di):i(_i), di(_di) { } Node() { Node(0, 0); } bool operatordi == ths.di) return this-&i di &1; if(nodes[mid].di &1; if(nodes[mid].di hi
SangS 阅读(621) |
摘要: 题目描述：如图，给定任意时刻，求时针和分针的夹角(劣弧所对应的角)。输入：输入包含多组测试数据，每组测试数据由一个按hh:mm表示的时刻组成。输出：对于每组测试数据，输出一个浮点数，代表时针和分针的夹角（劣弧对应的角），用角度表示，结果保留两位小数。样例输入：03:0014:45样例输出：90.00172.50总结:1. 不要忘了, 分针的角度可以由分直接转换, 而时针则需要考虑分代码:#include #include #include #include #includechar time1[20];double timeToDegree(char
SangS 阅读(243) |
摘要: Problem DescriptionMy name is Hu Bayi, robing an ancient tomb in Tibet. The tomb consists of N rooms (numbered from 1 to N) which are connected by some roads (pass each road should cost some time). There is exactly one route between any two rooms, and each room contains some treasures. Now I am loca
SangS 阅读(130) |
摘要: DescriptionEvery year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at the end,Lunits away from the start (1 ≤L≤ 1,000,000,0
SangS 阅读(62) |
摘要: DescriptionFarmer John is an astounding accounting wizard and has realized he might run out of money to run the farm. He has already calculated and recorded the exact amount of money (1 ≤moneyi≤ 10,000) that he will need to spend each day over the nextN(1 ≤N≤ 100,000) days.FJ wants to create a budge
SangS 阅读(104) |
摘要: 题目描述：为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。请问：你用有限的资金最多能采购多少公斤粮食呢？思路裸多重背包, 本想练练倍增优化的, AC 后又没动力了代码#include #include #includeint weight[222];int bags [222];int money [222];int dp [222];int main() { scanf(&%d&, &t);
SangS 阅读(60) |
摘要: 题目描述：又到毕业季，很多大公司来学校招聘，招聘会分散在不同时间段，小明想知道自己最多能完整的参加多少个招聘会(参加一个招聘会的时候不能中断或离开)。思路算法导论贪心算法章节原题, 编程之美上也有类似题目.这种招聘会还比较简单, 招聘会本身没有权值, 假如考虑权值, 题目就变成动态规划了先对招聘会按照截止时间排序, 然后按照截止时间选取具体哪场招聘会, 时间复杂度为 O(nlogn)代码#include #include #include #includeclass Meeting {public: int st, Meeting(...
SangS 阅读(318) |
摘要: 题目描述：在一个无权图中，两个节点间的最短距离可以看成从一个节点出发到达另一个节点至少需要经过的边的个数。同时，任意两个节点间的最短路径可能有多条，使得从一个节点出发可以有多条最短路径可以选择，并且沿着这些路径到达目标节点所经过的边的个数都是一样的。但是在图中有那么一些特殊的节点，如果去除这些点，那么从某个初始节点到某个终止节点的最短路径长度要么变长，要么这两个节点变得不连通。这些点被称为最短路径上的关键点。现给定一个无权图，以及起始节点和终止节点，要求输出该图上，这对节点间最短路径上的关键点数目。思路1. 起初把题目想简单了, 以为一遍 BFS 就能得到正解, 用案例跑了下没报错就直接提交了
SangS 阅读(193) |
摘要: 题目描述：大家都知道在dota游戏中，装备是对于英雄来说十分重要的要素。英雄们不仅可以购买单个的装备，甚至某些特定的装备组合能够合成更强的装备。为了简化问题，我们将每个装备对于英雄的功能抽象为一个整数：价值。同时，如上所说，一些特定的装备可以用来合成更强的装备，玩家会因此获得除原装备价值外额外的价值。给定玩家现有的金钱数，每个装备的价格和其对应的价值，以及装备合成的信息。输出，其能获得的最大价值数。注意：每件装备只能参与合成一件合成装备（即原装备参与合成后得到合成后的新装备，原装备消失），除非一次购买多个该种装备。思路1. 刚开始没看懂题目, 还以为是有依赖的背包问题, 后来看了解题报告才明白
SangS 阅读(88) |
摘要: 题目描述：给定一个m*m的矩阵，矩阵中每个数字都是整数。在该矩阵中找到一个大小为n*n的子矩阵，使该子矩阵中的所有元素和最小。输出该最小元素和。思路1. 简单版的最小矩阵, 矩阵被限定在正方形2. 对于子问题的求解, 几乎算不上是动态规划了, 只能说是一道模拟题3. 一个游标, 遍历第 n~m 行, 对每一行, 利用单调队列计算矩阵的和, 时间复杂度为 o(m*m)代码#include #include #includeint matrix[200][200];int line[200];int calOneLine(int m, int n) { .
SangS 阅读(105) |
摘要: Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为，空间复杂度为。原理Floyd-Warshall算法的原理是动态规划。设为从到的只以集合中的节点为中间节点的最短路径的长度。若最短路径经过点k，则；若最短路径不经过点k，则。因此，。在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。（见下面的算法描述）算法描述Floyd-Warshall算法的描述如下：for k ← 1 to
SangS 阅读(112) |
摘要: 题目描述：为了加快城市之间的通行和物资流动速度，A国政府决定在其境内的N个大中型城市之间，增加修建K条公路。已知这N个城市中的任意两个都能相互连通，且已知其最短的路径长度。为了时刻监测修建新路对A国城市的影响，特任命你为观察员，负责在每修建完一条公路之后，就向该国领导汇报当前N个城市间的最短路之和。思路1. 这道题目是 floyd 算法的变形, 题目已给出任意两个城市之间的最短距离, 每次增加一条道路, 求解增加这条道路后各个城市之间的最短路径之和减小到多少2. floyd 算法描述如下Floyd-Warshall算法的原理是动态规划设为从到的只以集合中的节点为中间节点的最短路径的长度。若最短
SangS 阅读(174) |
摘要: 题目描述： Every positive number can be presented by the exponential form.For example, 137 = 2^7 + 2^3 + 2^0。 Let&#39;s present a^b by the form a(b).Then 137 is presented by 2(7)+2(3)+2(0). Since 7 = 2^2 + 2 + 2^0 and 3 = 2 + 2^0 , 137 is finally presented by 2(2(2)+2 +2(0))+2(2+2(0))+2(0). Given a posit
SangS 阅读(103) |
摘要: 题目描述：哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和思路1. 构建哈夫曼树然后 topDown 遍历即可2. 也可以不显式的创建树. 所有树叶点的和即为所求(根节点以外)代码 STL priority_queue 自定类型不会用#include #include #includeclass Node {public: Node *left, * Node(int _value...
SangS 阅读(92) |
摘要: 总结1. Objects in if you want to modify an object, you need to:a. make a copy of the object from the setb. modify the copyc. remove the original object from the object, andd. insert the copy into the set2. Each associative container is parameterized on Key and an ordering relation
SangS 阅读(49) |
摘要: 题目描述： 有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值 如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可思路1. 朴素背包问题2. 假设 dp[i][j] 表示前 i 件物品拼成 j 分的最少邮票数dp[i][j] = min(dp[i-1][j], dp[i-1][j-value[i]]+1)3. 转化成一维背包 dp[v] = min(dp[v], dp[v-value[i]]+1)代码 未通过九度测试#include #include #includeconst int INF ..
SangS 阅读(65) |
摘要: 目的：将中缀表达式（即标准形式的表达式）转换为后缀式。例子：a+b*c+(d*e+f)*g转换成abc*+de*f+g*+转换原则1. 遇到操作数, 直接输出2. 操作符的优先级为 () 最大, * / 次之, +- 最小. 遇到操作符后, 假如操作符堆栈为空, 则直接压入操作符, 否则判断当前操作符与栈顶操作符的优先关系, 假如栈顶操作符的优先级大于 等于当前操作符的优先级, 那么弹出栈顶操作符, 持续弹出, 直到栈顶操作符优先级小于当前操作符优先级或栈为空. 最后将当前操作符入栈3. 如果遇到右括号, 那么将栈顶操作符弹出, 持续弹出直到遇到左括号, 左括号弹出但不输出4. 表达式读入完毕
SangS 阅读(1963) |
摘要: 题目描述：计算机学院的男生和女生共n个人要坐成一排玩游戏，因为计算机的女生都非常害羞，男生又很主动，所以活动的组织者要求在任何时候，一个女生的左边或者右边至少有一个女生，即每个女生均不会只与男生相邻。现在活动的组织者想知道，共有多少种可选的座位方案。例如当n为4时，共有女女女女, 女女女男, 男女女女, 女女男男, 男女女男, 男男女女, 男男男男7种。思路1. 读完题, 感觉这是道 DP 题2. 前几天做了一道统计括号数的题目, 和此题比较类似3. dp[i][j] 表示前 i 个人中有 j 个女生的方案数, 那么状态转移方程就能写为 dp[i][j] = dp[i-1][j] (最后一位.
SangS 阅读(125) |
摘要: 题目描述：有如下图半价为R的圆形蛋糕，被切一刀后（图中红色直线），分成两个部分（黄色和绿色），已知其比例为r，求刀痕长度（图中红色直线）。思路1. 画个图比划比划, 可以看出是道数学题2. 将刀痕的长度设成 l, 就能建立等式, 接下来就是求 l 了3. 写成等式后需要以编程的角度出发求解未知数 l, 很自然就能联想到二分法搜索, 但是需要从数学的角度去证明 L 在区间 (0, R) 是单调的4. 再看图, 发现不需要求导数证明单调, L 越大黄色部分越大, L 越小黄色部分越小, 单调性是 straight forward5. 对 double 进行二分搜索还是第一次做, 二分后对 low,
SangS 阅读(136) |
摘要: 题目描述：编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。例如如下的先序遍历字符串：ABC##DE#G##F###其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。思路1. 想了半天, 写不出递归函数, 倒是基于堆栈的循环方法简单的多代码#include #include #include #include #includeclass Node {public: Node *left, * Node(char...
SangS 阅读(149) |
摘要: 题目描述： 二叉排序树，也称为二叉查找树。可以是一颗空树，也可以是一颗具有如下特性的非空二叉树： 1. 若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值； 2. 若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值； 3. 左、右子树本身也是一颗二叉排序树。 现在给你N个关键字值各不相同的节点，要求你按顺序插入一个初始为空树的二叉排序树中，每次插入后成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。思路1. 根据数组构建二叉搜索树代码#include #includeclass Node {public: .
SangS 阅读(475) |
摘要: 题目描述：在组合数学中，我们学过排列数。从n个不同元素中取出m（m#includeint five[20];void init() { int tmp = 2, i = 0; while(tmp = five[i]; i ++) { cnt += x/five[i]; }}int main() { int n, init(); while(scanf(&%d%d&, &n, &m) != EOF && n != 0) { int cnt = 0; ...
SangS 阅读(117) |
摘要: 题目描述：给出n个正整数，任取两个数分别作为分子和分母组成最简真分数，编程求共有几个这样的组合。思路1. 题目考察的是 GCD代码#include #include #includeint numbers[700];int gcd(int x, int y) { if(x == 1 || y == 1) return 1; if(x == y) if(x & y) swap(x, y); if(x&1 == 1) { if(y&1 == 1) ...
SangS 阅读(283) |
摘要: 题目描述：Given any string of N (&=5) characters, you are asked to form the characters into the shape of U. For example, &helloworld& can be printed as:hde ll rlowoThat is, the characters must be printed in the original order, starting top-down from the left vertical line with n1 characters,
SangS 阅读(210) |
摘要: 题目描述：玛雅人有一种密码，如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串，（2=#include #include #include #include #includeint N;bool visited[1600000];bool match(const string &str1) { for(int i = 0; i & memset(visited, 0, sizeof(visited)); record.pu...
SangS 阅读(1269) |
摘要: 题目描述：一个数的序列bi，当b1 #includeint dp[1001];int val[1001];int main() { while(scanf(&%d&, &n) != EOF ) { for(int i = 0; i = val[i]) dp[i] = max(dp[i], dp[j]+val[i]); } } int resval = 0; for(int i = 0; i & i ++...
SangS 阅读(182) |
摘要: 题目描述： 对于一副扑克牌，我们有多种不同的洗牌方式。一种方法是从中间某个位置分成两半，然后相交换，我们称之为移位（shift）。比如原来的次序是123456，从第4个位置交换，结果就是561234。这个方式其实就是数组的循环移位，为了多次进行这个操作，必须使用一种尽可能快的方法来编程实现。在本题目中，还引入另外一种洗牌方式，就是把前一半（如果总数是奇数，就是(n-1)/2）牌翻转过来，这种操作称之为翻转（flip）。在前面shift操作的结果上进行flip，结果就是165234。当然，如果是实际的扑克牌，直接翻转会造成正反面混在一起的，我们就不管那么多了。 给定n张牌，初始次序为从1到n，经
SangS 阅读(87) |
摘要: 题目描述：给定正整数N，函数F(N)表示小于等于N的自然数中1和2的个数之和，例如：1,2,3,4,5,6,7,8,9,10序列中1和2的个数之和为3，因此F(10)=3。输入N，求F(N)的值，1=&N&=10^100(10的100次方)若F(N)很大，则求F(N)mod 20123 的值。思路1. 剑指 offer 例题.2. 这题需要对数组求摸, 就懒得做了
SangS 阅读(83) |
摘要: 题目描述：给定n个物品的重量和两艘载重量分别为c1和c2的船，问能否用这两艘船装下所有的物品。思路1. 朴素背包问题2. 有几个细节要好好把握 (1) 在读入物品重量时顺带统计物品的最大值和总重量 (2) 对载重量较小的船计算dp3. 一维 dp, dp[i] 表示总物品重量为 i 时的最大价值, 因此 dp[i] 是不连续的, 统计结果时需要遍历 dp. 而二维 dp[][] 则可以填满矩阵代码 未通过九度测试#include #include #includeint n, c1, c2;int wet[200];int dp[10000];int
SangS 阅读(62) |
摘要: Leetcode 原题.这里 N 最大会取到 13, TLE 了代码#include #includebool chess[15][15];void dfs(int depth) { if(depth == n) { cnt ++; } for(int i = 0; i = 0; j --) { if(chess[j][i]) { qualify = ...
SangS 阅读(89) |
摘要: 题目描述：给定一个n*n的矩阵，求该矩阵的k次幂，即P^k思路1. 和求解整数幂的思路相同, 使用分治策略, 代码的框架是int pow(a, b) { c = pow(a, b/2) c*= if(b 为奇数) c *= return c}2. 这道题求的是矩阵, 上面的框架不太好用, 毕竟返回一个矩阵是有点不靠谱. 既然显式的返回矩阵不行, 那就玩个把戏, 隐式返回.将矩阵设置为全局变量, 使得递归函数里对矩阵的操作全局有效, 就不需要显式返回矩阵了3. 尝试仅使用两个矩阵得出结果, 但失败了, 计算矩阵乘法, 至少需要三个矩阵的空间吧代码#include #in...
SangS 阅读(119) |
摘要: 题目描述：在印刷术发明之前，复制一本书是一个很困难的工作，工作量很大，而且需要大家的积极配合来抄写一本书，团队合作能力很重要。当时都是通过招募抄写员来进行书本的录入和复制工作的, 假设现在要抄写m本书，编号为1,2,3...m, 每本书有1#includeint m,k;int books[600];int main() { scanf(&%d&, &n); for(int i = 0; i & 1; int cnt = 1, sum = 0; for(int i = 0; i...
SangS 阅读(486) |
摘要: 题目描述：小明每天都在开源社区上做项目，假设每天他都有很多项目可以选，其中每个项目都有一个开始时间和截止时间，假设做完每个项目后，拿到报酬都是不同的。由于小明马上就要硕士毕业了，面临着买房、买车、给女友买各种包包的鸭梨，但是他的钱包却空空如也，他需要足够的money来充实钱包。万能的网友麻烦你来帮帮小明，如何在最短时间内安排自己手中的项目才能保证赚钱最多（注意：做项目的时候，项目不能并行，即两个项目之间不能有时间重叠，但是一个项目刚结束，就可以立即做另一个项目，即项目起止时间点可以重叠）。思路1. 一道任务调度题, 为此专门翻了下算法导论, 回顾了上面那道贪心可解的调度题目. 那道题目给定任务
SangS 阅读(126) |
摘要: 题目描述：现在有一个序列123......N，其中N介于3和15之间，要求在序列之间加入+、-或者空格，使得该序列组成的数学表达式的运算结果为0。思路1. 枚举运算符, 时间复杂度为 o(3^15)2. 1_2 是 12, 10_11 是 1011, WA了很多次3. 一个简单的计算器做了一下午, 思路忘了. 要注意案例, 1+2_3, 1+2_3-44. 下次要把中序表达式转后序表达式的算法实现以下5. 使用了 STL, 超时了. 当然不需要使用 STL 也能做出来代码#include #include #include #include #include using namespace s
SangS 阅读(132) |
摘要: 题目描述：在一个M * N的矩阵中，所有的元素只有0和1，从这个矩阵中找出一个面积最大的全1子矩阵，所谓最大是指元素1的个数最多Leetcode 原题, 没有案例就是跪, WA 到没脾气代码 未通过九度测试#include #include #include #include #includeint m,int matrix[];int rectangle[1001];int largestHis() { int global = 0; for(int i = 0; i & i...
SangS 阅读(256) |
摘要: 题目描述：在读高中的时候，每天早上学校都要组织全校的师生进行跑步来锻炼身体，每当出操令吹响时，大家就开始往楼下跑了，然后身高矮的排在队伍的前面，身高较高的就要排在队尾。突然，有一天出操负责人想了一个主意，想要变换一下队形，就是当大家都从楼上跑下来后，所有的学生都随机地占在一排，然后出操负责人从队伍中抽取出一部分学生，使得队伍中剩余的学生的身高从前往后看，是一个先升高后下降的“山峰”形状。据说这样的形状能够给大家带来好运，祝愿大家在学习的道路上勇攀高峰。(注，山峰只有一边也符合条件，如1,1、2,2、1均符合条件)思路1. 这道题我还蛮想总结一下, 因为与之类似的一道题 Candy 当时就把我做
SangS 阅读(165) |
摘要: 题目描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。思路1. 最初的想法是比较两个数时, 较短的数末尾补最后一个数, 比如 233, 23 -& 233, 233. 然后判断会变得比较复杂2. 正好昨晚和室友闲聊, 谈到说到这道题, 才知道末尾补第一个数才是正解. 233, 23 -& 233, 2323. 剑指 offer 上的解法更是简单粗暴, 直接将两个数拼出来看看就得了. 233, 23 -& 2. 看完剑指 o
SangS 阅读(1199) |
摘要: 题目描述：输入一个二叉树，输出其镜像。思路1. 二叉树镜像的判定, 镜像树的建立是类似的题目.2. 代码的框架是 func(root1, root2). 函数体内部是 func(root1-&left, root-&right), func(root-&left, root-&right)3. 建立的方法都是 bottomUp, 这个过程可以通过 func 的返回实现, 也可以通过参数实现.代码 未通过九度测试, 以后再改吧#include #include #include #include #includechar arr[
SangS 阅读(21) |
摘要: 题目描述：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。总结剑指 offer 原题, 要注意负数移位是永远到不了 0 的代码#include #includeint count1(int x) { int cnt = 0; while(x != 0) { x = x&(x-1); cnt ++; }}int main() { //freopen(&testcase.txt&, &r&, stdin); while(scanf(&...
SangS 阅读(175) |
摘要: 题目描述：回文串就是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。回文子串，顾名思义，即字符串中满足回文性质的子串。给出一个只由小写英文字符a,b,c...x,y,z组成的字符串，请输出其中最长的回文子串的长度。思路1. 使用枚举法判断, 时间复杂度会到 o(n^3)2. 动规的记忆化搜索, 时间复杂度会降到 o(n^2)3. leetcode 给出了一个算法, 将时间复杂度降低到 o(n)代码#include #include #includechar ori[200010];char ist[500020];int
SangS 阅读(133) |
摘要: 总结1. getline(cin, string)2. getline 不能和 scanf 联合使用. 联合使用的话, 一个数会被读入多次题目描述：小明手中有很多字符串卡片，每个字符串中都包含有多个连续的空格，而且这些卡片在印刷的过程中将字符串的每个子串都打印反了，现在麻烦你帮小明将这些字符串中的子串修正过来，同时为了使卡片美观，压缩其中的连续空格为1个。思路1. 题目本身并没有什么难度, 主要是看懂题. 题目要求的是压缩空格, 不是删除空格. WA 了很多次代码#include #include #include #include #includec
SangS 阅读(103) |
摘要: 题目描述：假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友...），则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。假如：n = 5 ， m = 3 ， r = {{1 , 2} , {2 , 3} , {4 , 5}}，表示有5个人，1和2是好友，2和3是好友，4和5是好友，则1、2、3属于一个朋友圈，4、5属于另一个朋友圈，结果为2个朋友圈。思路1. 裸的并查集, 回顾下并查集的知识2. 并查集主要有两个操作, 一个是 merge, 一个是 find. find 用于找到一个集合的标志, merge 用于合并两个集合. 在实
SangS 阅读(373) |
摘要: 题目描述：给定一个由N个整数元素组成的数组arr，数组中有正数也有负数，这个数组不是一般的数组，其首尾是相连的。数组中一个或多个连续元素可以组成一个子数组，其中存在这样的子数组arr[i],…arr[n-1],arr[0],…,arr[j]，现在请你这个ACM_Lover用一个最高效的方法帮忙找出所有连续子数组和的最大值（如果数组中的元素全部为负数，则最大和为0，即一个也没有选）思路1. 本以为这题与 Leetcode 上 Gas Station 一样, 提交之后也能通过 2 个 case, 但最终通过一组数据 (2 1 -3 2) 决定了 Gas Station 的做法不正确2. 分两种情况
SangS 阅读(609) |
摘要: 题目描述：现在有一个8*8的棋盘，上面放着64个不同价值的礼物，每个小的棋盘上面放置一个礼物（礼物的价值大于0小于100），一个人初始位置在棋盘的左上角，每次他只能向下或向右移动一步，并拿走对应棋盘上的礼物，结束位置在棋盘的右下角。从棋盘的左上角移动到右下角的时候的，每次他只能向下或向右移动一步，并拿走对应棋盘上的礼物，但是拿到的所有的礼物的价值之和不大于一个限定值limit，请设计一个算法请实现，使其能够获得不超过限制值limit的最大价值的礼物。思路1. 在棋盘问题的基础上加了一个限制, 礼物数不能超过 limit2. 这个限制使得状态转移方程需要进行一下变形3. dp[i][j][k]
SangS 阅读(329) |
摘要: 题目描述：小虎是游戏中的一个国王，在他管理的国家中发行了很多不同面额的纸币，用这些纸币进行任意的组合可以在游戏中购买各种装备来提升自己。有一天，他突然很想知道这些纸币的组合不能表示的最小面额是多少，请聪明的你来帮助小虎来解决这个财政问题吧思路1. 面值最小额度, 枚举的话时间复杂度为 o(n^3). 但思考一下就会发现其实这是背包问题恰好装满的变形题2. 背包问题恰好装满是在朴素背包问题的基础上初始化 dp[0] = 0, dp[i] = 负无穷. 这样就会使得不能恰好装满的容量都是负无穷3. 下面的代码设置的是 int dp[], 其实设置成 bool dp[] 也是可以的代码#includ
SangS 阅读(111) |
摘要: 题目描述：最长不重复子串就是从一个字符串中找到一个连续子串，该子串中任何两个字符都不能相同，且该子串的长度是最大的。思路Leetcode 原题设置两个游标, 右边游标向右走, 出现重复字符时, 左边的游标向右走代码#include #include #includeint myHash[30];char arr[10010];int main() { while(scanf(&%s&, arr) != EOF) { memset(myHash, 0, sizeof(myHash)); int len = str...
SangS 阅读(209) |
摘要: 题目描述：现在有一个8*8的棋盘，上面放着64个价值不等的礼物，每个小的棋盘上面放置一个礼物（礼物的价值大于0小于1000），一个人的初始位置在棋盘的左上角，每次他只能向下或向右移动一步，并拿走对应棋盘上的礼物，结束位置在棋盘的右下角，请设计一个算法使其能够获得最大价值的礼物。思路Leetcode 原题dp[i][j] 表示 在第 (i,j) 个格子上能够获得的最大价值的礼物状态转移方程为dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + matrix[i][j]这题不应该再贴上, 不过上次做括号匹配没构造出状态转移方程, 那题与此题思路是类似的状态方程的求解,
SangS 阅读(151) |
摘要: 总结1. 更新动规矩阵时, 不要 push 更新, 要用 pull更新. push 更新容易让逻辑出问题, 自己卡了很久, 改用 pull 就变得很顺利了2. acm 题, 空间至多是百万, 再网上就会超的3. 曾做过一道题, 和这个类似. 好像是背包问题的一个变形把, 核心都是降维. 降维的过程又是一道动规题目题目描述：给定一个大小为n的数组，数组的元素a[i]代表第i天的股票价格设计一个算法，计算在最多允许买卖k次（一买一卖记为一次）的条件下的最大收益需要注意的是，你不能同时拥有两份股票。也就是说在下次买入前，你必须把手头上原有的股票先卖掉思路1. 假设 dp[i][j] 表示前 i 天,
SangS 阅读(628) |
摘要: 题目描述：给定一个整型数组， 求这个数组的最长严格递增子序列的长度。 譬如序列1 2 2 4 3 的最长严格递增子序列为1，2，4或1，2，3.他们的长度为3。思路1. 朴素求解 LIS, 没什么可说的2. 又涉及到二分查找, 这次找的是大于等于 target 的最小值. = 时直接返回, 这就简单了. low & high 时, 返回 low, 因为上一轮比较, mid #includeint arr[100010];int record[100010];int search(int x, int low, int high) { if(low
SangS 阅读(75) |
摘要: 题目描述：给定两个整型数组A和B。我们将A和B中的元素两两相加可以得到数组C。譬如A为[1,2]，B为[3,4].那么由A和B中的元素两两相加得到的数组C为[4,5,5,6]。现在给你数组A和B，求由A和B两两相加得到的数组C中，第K小的数字。思路1. 多年前第一次搞这道题就没弄出来, 今天是大概记得做法, 不过 failed again, 总结起来, 仍然是没有意识到 int 的特殊性, 即 (int+int)/2 得到的仍然是 int2. 涉及到二分查找, 用我以前总结的步骤来做, 非常顺利. 核心就是 mid = target, high = mid-1, 尝试向左. 最后返回的应该是
SangS 阅读(295) |
摘要: 题目描述：给定一棵无向树， 我们选择不同的节点作为根节点时，可以得到不同的高度（即树根节点到叶子节点距离的最大值）， 现在求这棵树可能的最低高度。思路1. 刚开始题目都没看懂. 树的高度, 指的是根节点到叶节点的最大值, 我们要做的是找到最大值中的最小值2. 查了下资料, 发现这道题是裸求树的直径3. 树的直径可以用动规求解, 但基本的求法是用两次 BFS(DFS)4. BFS 的求解过程为, (1) 从任意节点 u 出发, 找到其能够达到的最远的节点 v (2) 再从 v 出发, 找到其能够达到的最远的节点 o (3) v,o 之间的距离就是树的直径 (4) 直径的一半就是所要求的高度证明
SangS 阅读(491) |
摘要: 题目代码#include #includeint candys[100010];int left1[100010];int right1[100010];int main() { //freopen(&testcase.txt&, &r&, stdin); while(scanf(&%d&, &n) != EOF) { for(int i = 0; i candys[i-1]) left1[i] = left1[i-1] +1; else ...
SangS 阅读(44) |
摘要: 题目描述：给定两个正整数a，b（1#include #includeint gcd(int x, int y) { if(x == 1 || y == 1) return 1; if(x == y) if(y & x) swap(x,y); if((x&1) && (y&1)) { return gcd(x-y, y); }else if((x&1) &&(!(y&1))) { return gcd(x, y/2); }else...
SangS 阅读(64) |
摘要: 题目描述：已知有面值为1元，2元，5元，10元，20元，50元，100元的货币若干（可认为无穷多），需支付价格为x的物品，并需要恰好支付，即没有找零产生。求，至少需要几张货币才能完成支付。如，若支付价格为12元的物品，最少需要一张10元和一张2元，即两张货币就可完成支付。思路1. 先用完全背包的思想考虑了一下, 甚至还计算2^40 个 int 相当于多大空间2. 然后考虑到一个优化, 100 元以上的直接用 100 付就好了嘛, 然后... 这又是道水题代码#include #includeint money[10]; void init() { ..
SangS 阅读(77) |
摘要: 题目描述：输入一个N（N#include #include vector matrix[12]; void dfs(int i, int n) { if(i == n-1) int maxVal = matrix[i][i], maxLine = for(int j = i+1; j & j++) { if(maxVal & matrix[j][i]) { maxVal = matrix[j][i]; maxLine = ...
SangS 阅读(43) |
摘要: 题目给定一个有向图, 判断其是否是一棵树要求 (1) 除了根节点外, 每个节点只有唯一的前驱 (2) 从根节点出发, 到任何节点有且只有一条路径思路1. 要求(1) 可以通过记录每个节点的前驱决定, (2) 可以从根节点 dfs, 搜不到的点不是树, 搜到的点在(1)符合条件的情况下, 只有一条路径2. 具体实现的话可以用 map[node*, node*]3. 最终使用的并查集, 使用并查集的过程要注意几个判断条件3.1　(1, 2) (2, 1) 不是树, 判断条件是 if(ed == find(st)) 假如经过寻找, 一个节点的父亲还是他自己, 说明出现了环3.2 一个节点不能被...
SangS 阅读(42) |
摘要: 题目描述：给定平面上的n个点，任意做一条直线，求至多能有几个点恰好落在直线上。思路1. Leetcode 上原题. 解法是先确定一个点, 然后计算其他点相对于这个点的斜率2. 这道题需要注意多点重合, 斜率为无穷大的情况代码 未通过九度测试#include #include #includeint xs[200], ys[200];int main() {freopen(&testcase.txt&, &r&, stdin); int pointnum, x, while(scanf(&%d&qu
SangS 阅读(78) |
摘要: 题目描述：给定一个初始为空的栈，和n个操作组成的操作序列，每个操作只可能是出栈或者入栈。要求在操作序列的执行过程中不会出现非法的操作，即不会在空栈时执行出栈操作，同时保证当操作序列完成后，栈恰好为一个空栈。求符合条件的操作序列种类。例如，4个操作组成的操作序列符合条件的如下：入栈，出栈，入栈，出栈入栈，入栈，出栈，出栈共2种。思路1. Leetcode 上有道类似的题目, 那道题求得是括号的总类, 当初用的是搜索法2. 搜索法超时, 分治法没想起什么好办法, 动规没头绪3. dp[i][j] (i&=j) 表示入栈 i 次出栈 j 次 的种类数4. dp[i][j] = dp[i-1][
SangS 阅读(196) |
摘要: 题目根据手机按键上的对应关系将字母转成数字, 简单模拟题总结1. scanf(&%s&, input); 不需要加上 &2. 字符串的终结符是 &#39;\0&#39;3. scanf 和 printf 打印的都是 char*, 不能是 int*代码#include #include #includeint map[50];void init() { for(int i = 0; i & 18; i ++) { map[i] = i/3 + 2; } map[18] = 7; for(int i = 19; i &lt
SangS 阅读(25) |