UVaOJ

本题的目的是识别3000年前古埃及用到的6种象形文字，如图6-10所示。 图6-10 古代象形符号 每组数据包含一个H行W列的字符矩阵（H≤200，W≤50），每个字符为4个相邻像素点的 十六进制（例如，10011100对应的字符就是9c）。转化为二进制后1表示黑点，0表示白点。 输入满足： 不会出现上述6种符号之外的其他符号。 输入至少包含一个符号，且每个黑像素都属于一个符号。 每个符号都是一个四连块，并且不同符号不会相互接触，也不会相互包含。 如果两个黑像素有公共顶点，则它们一定有一个相同的相邻黑像素（有公共边）。 符号的形状一定和表6-9中的图形拓扑等价（可以随意拉伸但不能拉断）。 要求按照字典序输出所有符号。例如，图6-11中的输出应为AKW。 样例参见 https://www.udebug.com/UVa/1103 本家连接 分为以下几个步骤： 关键在于辨识每个图形中的空白四连块的数量。就是UVA 572 - Oil Deposits (油田) By SuCicada的升级版。 好就好在每个图形的白块数量不同，然而如何区分图形内的空白和图形外的空白是个问题。所以我在一开始就把外面的空白都涂黑了。 然后遍历，遍历到文字就将其当作油田求内部连通白块。 （最后的排序是手动实现的插入（:P） /* 1. 16进制 转 2进制 2. 从最外围开始融化 白纸 3. 遍历到文字黑色边缘, 4. 向内遍历找"油田", 即4连块 5. 计算每个文字的4连块数量 6. 结束文字们, 根据4连块数量映射文字, 排序 */ #include<iostream> #include<string> #include<algorithm> #include<cstring> using namespace std; /* 1. 16进制 转 2进制 2. 从最外围开始融化 白纸 3. 遍历到文字黑色边缘, 4. 向内遍历找"油田", 即4连块 5. 计算每个文字的4连块数量 6....

例题6-21 系统依赖（System Dependencies, ACM/ICPC World Finals 1997, UVa506） 软件组件之间可能会有依赖关系，例如，TELNET和FTP都依赖于TCP/IP。你的任务是 模拟安装和卸载软件组件的过程。首先是一些DEPEND指令，说明软件之间的依赖关系（保 证不存在循环依赖），然后是一些INSTALL、REMOVE和LIST指令，如表6-1所示。 表6-1 指令说明 指令 说明 DEPEND item1 item2 [item3 …] item1依赖组件item2, item3, … INSTALL item1 安装item1和它的依赖（已安装过的不用重新安装） REMOVE item1 卸载item1和它的依赖（如果某组件还被其他显式安装的组件所依赖，则不能卸载这个组件） LIST 输出所有已安装组件 在INSTALL指令中提到的组件称为显式安装，这些组件必须用REMOVE指令显式删除。 同样地，被这些显式安装组件所直接或间接依赖的其他组件也不能在REMOVE指令中删除。 每行指令包含不超过80个字符，所有组件名称都是大小写敏感的。指令名称均为大写字母。 Sample Input DEPEND TELNET TCPIP NETCARD DEPEND TCPIP NETCARD DEPEND DNS TCPIP NETCARD DEPEND BROWSER TCPIP HTML INSTALL NETCARD INSTALL TELNET INSTALL foo REMOVE NETCARD INSTALL BROWSER INSTALL DNS LIST REMOVE TELNET REMOVE NETCARD REMOVE DNS...

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=829&problem=1023&mosmsg=Submission+received+with+ID+20388214 A common typing error is to place the hands on the keyboard one row to the right of the correct position. So ‘Q’ is typed as ‘W’ and ‘J’ is typed as ‘K’ and so on. You are to decode a message typed in this manner. Input Input consists of several lines of text. Each line may contain digits, spaces, upper case letters (except Q, A, Z), or punctuation shown above [except back-quote (‘)]....

例题6-16 单词（Play On Words, UVa 10129） 输入n（n≤100000）个单词，是否可以把所有这些单词排成一个序列，使得每个单词的 第一个字母和上一个单词的最后一个字母相同（例如acm、malform、mouse）。每个单词最多包含1000个小写字母。输入中可以有重复单词。 Sample Input 3 2 acm ibm 3 acm malform mouse 2 ok ok Sample Output The door cannot be opened. Ordering is possible. The door cannot be opened. 本家链接 将一个单词看做是首字母到尾字母的一条路，所以这条路我们只关心头尾，即首尾两个字母，不关心中间字母。 所以我们可以构造一个图，26*26的图，有向的。其中的边即是一个单词。由此我们便无需关心重复以及首尾字母相同的具体单词了，只关心具有同样首尾的单词的数量。 所以这道题就成为了：构造了一个图，是否存在欧拉回路。 存在欧拉回路条件： 图连通 除了起点和终点，其余每个点的出入度都必须一样。 起点和终点的出入度之差为0或各为1。 用dfs判断连通，用数组记录各个点的出入度。 #include<iostream> #include<string> #include<cstring> using namespace std; /* x --> y */ int dict[33][33]; int inDegree[33]; int outDegree[33]; int N; int SUM = 26; int dfs(int w){ /* start at w */ int road = 0; for(int i=0;i<SUM;i++){ /* 找到了对应的尾字母，即存在一个单词，一条路 */ if(dict[w][i]==1){ dict[w][i] = 2; /* 走过了 */ road = 1; /* 路标记 */ dfs(i); /* 找下一个 */ } return road; } int main(){ int T; cin>>T; while(T--){ cin>>N; int n=N; memset(dict,0,sizeof(dict)); memset(inDegree,0,sizeof(inDegree)); memset(outDegree,0,sizeof(outDegree)); string s; while(n--){ cin>>s; int x = s[0]-'a'; int y = s[s....

两格子之间的距离 http://acm.hdu.edu.cn/showproblem.php?pid=1030 走一步判断一下 下一步走哪里 是走下面呢（前提要能走） 还是走左边 还是走右边 设定一个格子，代表当前走到的地方 如果能直接向下走，就向下走 不能的话： 如果终点在当前格子的哪一边（只看左右方向，不看上下），就走哪一边 #include<iostream> #include<cmath> using namespace std; // 同一行 相邻的能通过 // 上下行 上行的第奇数个能和下行中第偶数个过 //1 3 5 7 //1 2*1-1 2*n-1 //(1+ 2*n-1)*n/2 = int(a) //第 sqrt(a) +1 行 //第 a - sqrt(a)^2 个 // 向左走，向右走？ int which(int a){ int n = sqrt(a-1); int ge = a-n*n; n ++; return n; } int getmid(int a){ int n = which(a); return pow(n-1,2) + n; } int main(){ int a,b; while(cin>>a>>b){ if(a>b) a^=b^=a^=b; int go = a; int b_n = which(b);// 行 int b_mid = getmid(b); int go_mid; int go_n; int sum = 0; while(go !...

例题6-15 给任务排序（Ordering Tasks, UVa 10305） 假设有n个变量，还有m个二元组(u, v)，分别表示变量u小于v。那么，所有变量从小到 大排列起来应该是什么样子的呢？例如，有4个变量a, b, c, d，若已知a < b，c < b，d < c，则 这4个变量的排序可能是a < d < c < b。尽管还有其他可能（如d < a < c < b），你只需找出其 中一个即可。 Sample Input 5 4 1 2 2 3 1 3 1 5 0 0 Sample Output 1 4 2 5 3 本家连接 dfs(n) 从n开始找上级 循环找上级 如果没有上级，break 如果有上级， if 上级 is execute: continue else if 上级 not execute. then dfs(上级),...

习题3-9 子序列（All in All, UVa 10340） 输入两个字符串s和t，判断是否可以从t中删除0个或多个字符（其他字符顺序不变）， 得到字符串s。例如，abcde可以得到bce，但无法得到dc。 Sample Input sequence subsequence person compression VERDI vivaVittorioEmanueleReDiItalia caseDoesMatter CaseDoesMatter Sample Output Yes No Yes No https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=830&problem=1281&mosmsg=Submission+received+with+ID+20551262 循环大的 从第一位小的开始 判断是否匹配，若是小的下标+1，若非大的+1，继续循环。 #include<iostream> #include<string> using namespace std; int main() { string s,a; while(cin>>s>>a) { int sn=0; for(int i=0;i<a.size()&&sn<s.size();i++) { if(a[i]==s[sn]) { sn++; //cout<<sn<<"!!"<<endl; } } if(sn==s.size()) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; } //AC at 2017/12/30 （没想到居然一下就过了，总共十分钟？这还是在同一天的）

例题6-17 看图写树（Undraw the Trees, UVa 10562） 你的任务是将多叉树转化为括号表示法。如图6-16所示，每个结点用除了“-”、“|”和空格 的其他字符表示，每个非叶结点的正下方总会有一个“|”字符，然后下方是一排“-”字符，恰 好覆盖所有子结点的上方。单独的一行“#”为数据结束标记。 Sample Input 2 A | -------- B C D | | ----- - E F G # e | ---- f g # Sample Output (A(B()C(E()F())D(G()))) (e(f()g())) 本家地址 先记录树，然后从头开始递归遍历树，并且构造先序遍历字串。 非叶子结点字母下方必有竖线。竖线下方必有若干横线，横线下方必有若干字母，即子节点。 #include<iostream> #include<string> #include<cstdio> #include<cstring> using namespace std; char tree[222][222]; int isRightChar(char c){ return c && c!='-' && c!='|' && c!=' ' && c!='#'; } int loop(int x,int y){ cout<<tree[x][y]; cout<<"("; if(tree[x+1][y]!...

习题3-12 浮点数（Floating-Point Numbers, UVa11809） 计算机常用阶码-尾数的方法保存浮点数。如图3-9所示，如果阶码有6位，尾数有8位，可以表达的最大浮点数为0.1111111112×2 1111112。注意小数点后第一位必须为1，所以一共有9位小数。 图3-9 阶码-尾数保存浮点数 这个数换算成十进制之后就是0.9980468752^63=9.20535763834529410^18。你的任务是根据这个最大浮点数，求出阶码的位数E和尾数的位数M。输入格式为AeB，表示最大浮点数为A*10B。0< A<10，并且恰好包含15位有效数字。输 入结束标志为0e0。对于每组数据，输 出M和E。输入保证有唯一解，且0≤M≤9，1≤E≤30。在本题中，M+E+2不必为8的整数倍。 Sample Input 5.699141892149156e76 9.205357638345294e18 0e0 Sample Output 5 8 8 6 https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=830&problem=2909&mosmsg=Submission+received+with+ID+20702100 我们只要算：m*2^(2^n-1)=f *10^t (m是浮点数位，n是阶码位数，求f和t；) 而f=10^log10(f)：即左边=10^t1=10^(t+log10(f)); t1=log10(m*2^(2^n-1))=log10(m)+(2^n-1) *log10(2) t=(int)t1; f=10^(t1-t); 感谢参考来自http://blog.csdn.net/crazysillynerd/article/details/43339157 #include<iostream> #include<cstdio> #include<cmath> using namespace std; double flo[10][30]; int expstr[10][30]; int main() { int twoe; double twom; double temp; for(int i=0;i<10;i++) { twom=1-pow(2,-i-1); for(int j=0;j<30;j++) { twoe = pow(2,j+1)-1; temp = log10(twom)+twoe*log10(2); expstr[i][j]=temp; flo[i][j]=pow(10,(temp-expstr[i][j])); } } while(1) { double flo1; int exp1; char str[25]={0};//存输入的浮点数字符串 int iff=0; //输入浮点数 char c; for(int i=0;(c=getchar())!...

例题6-22 战场（Paintball, UVa 11853） 有一个1000×1000的正方形战场，战场西南角的坐标为(0,0)，西北角的坐标为(0,1000)。 战场上有n（0≤n≤1000）个敌人，第i个敌人的坐标为(xi ,yi )，攻击范围为ri。为了避开敌人的 攻击，在任意时刻，你与每个敌人的距离都必须严格大于它的攻击范围。你的任务是从战场 的西边（x=0的某个点）进入，东边（x=1000的某个点）离开。如果有多个位置可以进/出， 你应当求出最靠北的位置。输入每个敌人的xi、yi、ri，输出进入战场和离开战场的坐标。 Sample Input 3 500 500 499 0 0 999 1000 1000 200 Sample Output 0.00 1000.00 1000.00 800.00 本家地址 关键在于抓住问题的本质，即问题的核心，即问题去除了表面保护层之下的那个最纯粹的那个命脉。 初看，我们发现，这是要在坐标图上画圆啊。过分可怕。 但是我们鼓起勇气再细看问题： 求最靠上的进入战场和离开战场的坐标。 解剖一下： 能否离开 若能，最上 最左边进，最后边出。 然后我们随便画几个图来看看。 怎么样就不能离开： 当有一条敌人从最上一直连通到最下。 若能，最靠上的地方是哪里： 如果我们最左边进入的地方的下方有一条敌线一直连通到最上边。 那么这条敌线就把我们包住了。 所以 敌线（从上方延伸 and 延伸到左边），就不能被我们在其上方进入。 所以我们只要求敌线的连通性和敌线范围（从上方开始的）在最左边和最右边的最下方坐标即可。 #include<iostream> #include<map> #include<cmath> #include<cstring> #include<vector> #include<queue> #include<cstdio> using namespace std; /* 关键在于抓住问题的本质，即问题的核心，即问题去除了表面保护层之下的那个最纯粹的那个命脉。 初看，我们发现，这是要在坐标图上画圆啊。过分可怕。 但是我们鼓起勇气再细看问题： 求最靠上的进入战场和离开战场的坐标。 解剖一下： 1. 能否离开 2. 若能，最上 3....

例题5-5 集合栈计算机(The Set Stack Computer,ACM/ICPC NWERC 2006,UVa12096) 有一个专门为了集合运算而设计的“集合栈”计算机。该机器有一个初始为空的栈,并且 支持以下操作。 PUSH:空集“{}”入栈。 DUP:把当前栈顶元素复制一份后再入栈。 UNION:出栈两个集合,然后把二者的并集入栈。 INTERSECT:出栈两个集合,然后把二者的交集入栈。ADD:出栈两个集合,然后把先出栈的集合加入到后出栈的集合中,把结果入栈。 每次操作后,输出栈顶集合的大小(即元素个数)。例如,栈顶元素是A={{}, {{}}},下一个元素是B={{},{{{}}}},则: UNION操作将得到{{},{{}},{{{}}}},输出3。 INTERSECT操作将得到{{}},输出1。 ADD操作将得到{{},{{{}}},{{},{{}}}},输出3。 输入不超过2000个操作,并且保证操作均能顺利进行(不需要对空栈执行出栈操作)。 Sample Input 2 9 PUSH DUP ADD PUSH ADD DUP ADD DUP UNION 5 PUSH PUSH ADD PUSH INTERSECT Sample Output 0 0 1 0 1 1 2 2 2 *** 0 0 1 0 0 *** https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=835&problem=3248&mosmsg=Submission+received+with+ID+21273791 性质： １、set< int >　代表是集合 ２、idcache 是集合与其编号的映射，每一个集合都有唯一的编号。 ３、setcache是向量，即下标与其存的是集合的元素相映射。 ４、每一个集合都只在以上容器中存在一个。 ５、栈里存的只是集合的编号。 #include <iostream> #include <set> #include <map> #include <stack> #include <vector> using namespace std; map< set<int> ,int> idcache; //每一个集合对应一个编号 vector< set<int> > setcache; //每一个编号对应一个集合 int getid(set<int> s) { if(idcache....

例题6-18 雕塑（Sculpture, ACM/ICPC NWERC 2008, UVa12171） 某雕塑由n（n≤50）个边平行于坐标轴的长方体组成。每个长方体用6个整 数x0，y0，z0，x，y，z表示（均为1～500的整数），其中x0为长方体的顶点中x坐标的最小 值，x表示长方体在x方向的总长度。其他4个值类似定义。你的任务是统计这个雕像的体积 和表面积。注意，雕塑内部可能会有密闭的空间，其体积应计算在总体积中，但从“外部”看 不见的面不应计入表面积。雕塑可能会由多个连通块组成。 Sample Input 2 2 1 2 3 3 4 5 6 2 3 3 4 5 7 1 1 1 5 5 1 1 1 10 5 5 1 1 1 2 1 4 8 2 1 2 4 1 8 5 2 2 1 4 8 1 5 2 4 1 8 3 3 4 1 1 1...

例题6-7 树的层次遍历（Trees on the level, Duke 1993, UVa 122） 输入一棵二叉树，你的任务是按从上到下、从左到右的顺序输出各个结点的值。每个结 点都按照从根结点到它的移动序列给出（L表示左，R表示右）。在输入中，每个结点的左 括号和右括号之间没有空格，相邻结点之间用一个空格隔开。每棵树的输入用一对空括 号“()”结束（这对括号本身不代表一个结点），如图6-3所示。 图6-3 一棵二叉树 注意，如果从根到某个叶结点的路径上有的结点没有在输入中给出，或者给出超过一 次，应当输出-1。结点个数不超过256。 样例输入： (11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) () (3,L) (4,R) () 样例输出： 5 4 8 11 13 4 7 2 1 not complete 本家地址 祭出对象大法 #include<iostream> #include<sstream> #include<string> #include<cstring> #include<cstdio> #include<cstdlib> using namespace std; class Node{ public: int value; Node* left; Node* right; }; Node* queue[256]; void show(Node* root){ memset(queue,0,sizeof(queue)); int qbegin=0; int qend=0; int qlen = sizeof(queue)/sizeof(Node*); stringstream out; queue[qend] = root; qend = (qend+1) % qlen; while(qbegin!...

把前n（n≤10000）个整数顺次写在一起：123456789101112…数一数0～9各出现多少次 （输出10个整数，分别是0，1，…，9出现的次数）。 Sample Input 2 3 13 Sample Output 0 1 1 1 0 0 0 0 0 0 1 6 2 2 1 1 1 1 1 1 （注：输出的最后一个数后面没有空格） https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=830&problem=3666&mosmsg=Submission+received+with+ID+20469369 //判断一个数各个位的数字，存于一个数组中，倒的来循环也无妨 #include<iostream> #include<cstdio> using namespace std; int main() { int T; cin>>T; getchar(); while(T--) { int num[10]={0}; int N; cin>>N; getchar(); while(N--) { int ni=N+1; while(ni) { num[ni%10]++; ni/=10; } } for(int i=0;i<9;i++) cout<<num[i]<<" "; cout<<num[9]<<endl; } return 0; } //AC at 2017/12/10

正篇以及正确解题思路和代码参见 UVA 12333 - Revenge of Fibonacci (斐波那契的复仇) by SuCicada 此篇为后日谈 要说为什么专门开一篇来记录想法呢，主要是因为想说的太多了。首先从UVA的提交记录上来看，上一次答题是在足足1年之前了。 这么久以来都没有再好好做算法，感觉快要忘本了。而且出来之后脑子也不是那么灵光了，虽然更理性，但是却少了些抽象的想象力。 再说这道题，一开始我根本不知道什么字典序，完全是打表暴力比对的。把前40位算出来那里都是没错的。 但是之后我想的是：用map排个序，然后二分查找。但是这样会有问题，因为二分找到的可能并不是最小的，所以找到之后还需要分别找到同样匹配前缀的那一区域的数字，因为是map排过序的，所以他们都是挨着的。 但是之后在极端痛苦了两个晚上之后，我放弃了这种做法，经过测试计算，发现我电脑中g++在一秒钟可以进行4亿次运算，假设有5万个40位数字需要比对，4亿除以5万除以40 有20万呢，或者保险点我们取个1000。（一直到当时我都以为这道题的时间限制是1秒） 然后我就在死灰复燃的状态下在下2天晚上把位数比对写出了（暴力）。为了减少比对量，我打表了前3位，也就是记录下前三位的数字第一次出现的序数，而且这个序数是map中的序数，map中的序数和fibo的序数可是不同的。 而且map不能随机读取，怎么办，我又创造了两个数组专门存放键和值。 后来我还发现个位数的搜索起来比较慢，因为他们要暴力比对的数是最多的，所以我又用一个map来记录已经查找过的结果。 我真的是要疯，一直到昨天晚上我把这套模型整通。本地一跑，通过，time测下来 1.2秒，我巨喜。提交，time limit exceeded。把udebug上的样例全部跑了一遍，没有超过1.5秒的。我随机生成各种5万个数的组合，2秒之内绝对能过。 但是 time limit exceeded， time limit exceeded，time limit exceeded，time limit exceeded，time limit exceeded。 ”难道是表打的太小了？“我又将打表位数升到4，升到5。然而为什么更慢了。 那会已经3点钟了，我感到生命力的衰减，在极度无望的情况下，我打开百度，UVA 12333，我真特么被这道题23333了， 这道题考大数+字典树 我惊住，一个新的窗子仿佛打开了，一查，全懂了，完全懂了。我缩在床上颤抖不已，脑子瞬间就明白了我该怎么做，但是身体已经无法支撑下去，为了能保持住自己的生命力。我艰难的进入睡眠。 第二天我写，真的很快，因为我已经知道了，虽然遇到了oj离奇而严厉的 runtime error错误。但是我很冷静，因为我知道这个方法肯定是没错的，这条路一定是对的。就是这种知道目的的坚定。 当Accepted出现在屏幕上，我想哭了。太痛苦了，太刺激了，太疯狂了。再加上17个小时没有进食带来的虚弱感让我恍惚，感觉我活下来了。 劫后余生的感激之情。 而现在已经5点怅然若失感时不时在席卷我，跨时两个星期，4个夜晚的崩溃，20余小时的挣扎，20多次的错误。我太弱了，我为我的弱小感到伤心，但是我又为我的成功感到高兴。 算法拯救我，算法伤害我，算法摧残我，算法安慰我。 我时尝为我的自艾感到痛苦。 但是我害怕痛苦吗，不如说我正喜欢痛苦。 附赠更快的却更错的代码： #include<iostream> #include<algorithm> #include<iterator> #include<vector> #include<string> #include<cstdio> #include<iomanip> #include<map> #include<cmath> #include<cstring> using namespace std; vector<string> fibonacci(100005); map<string,int> fiboSorted; vector<string> fiboName(100005); vector<int> fiboIndex(100005); int limitSite = 52; string add(string a,string b){ int aLen = a....

合适的思路 大数加法 字典树 代码 注意点 附录 后日谈 习题5-15 Fibonacci的复仇（Revenge of Fibonacci, ACM/ICPC Shanghai 2011, UVa12333） Fibonacci数的定义为：F(0)=F(1)=1，然后从F(2)开始，F(i)=F(i-1)+F(i-2)。例如，前10 项Fibonacci数分别为1, 1, 2, 3, 5, 8, 13, 21, 34, 55…… 有一天晚上，你梦到了Fibonacci，它告诉你一个有趣的Fibonacci数。醒来以后，你只记 得了它的开头几个数字。你的任务是找出以它开头的最小Fibonacci数的序号。例如以12开头 的最小Fibonacci数是F(25)。输入不超过40个数字，输出满足条件的序号。 如果序号小于100000的Fibonacci数均不满足条件，输出-1。 提示：本题有一定效率要求。如果高精度代码比较慢，可能会超时。 原题链接 合适的思路 首先想我们该怎么样能匹配前缀，首先我们不知道完整的数字是什么，所以我们要先得到符合要求的数字数据集。 然后将这些数据集放入字典树中 所以我们要做的就是 使用大数加法技巧，计算前100000个fibonacci 将每一个fibo数存入字典树中 大数加法 首先先做大数加法，使用字符串存储数字，两个字符串（数字）从最后一位即个位开始一位一位加。 问题在于： 100000个fibo数字，到后期位数是相当恐怖的，测试时发现第10万个数字有足足2万多位。这会造成在运算时时间和空间的非常糟糕的消耗。 所以我们就可以遵从题意，只关心前40位，我们只截取每个数字的前面一部分做计算。这就要引出第2个和第3个问题。 如果我们使用40位，不论后面多少位，就把第40位当作个位。这会产生一个误差的问题。 比如两个数字 11001 和88999，如果我们只取他们的前2位算出来下一个数的前2位是99，但是实际上下一个数的前2位是10。这就是误差。 在解决第1个问题的时候，我们需要考虑数字进位的情况，因为我们只能看到数字的前一部分，不知道两个相加的数字是否位数相等，比如1234和345相加，假设取前2位，那么我们只能看到12和34，这样直接相加是不对的。 解决 问题:3：先解决位数问题，我们可以将位数记录在字符串中，比如加入一个最后一位专门用来放位数。但是这样我们只能放256个无符号数字（因为使用char型元素存储）。那么换个思路，因为我们的问题在于两个数字位数不等，而不是位数究竟多少，所以可以只记录位数的奇偶即可。 （另：其他办法，因为是Fibo数，位数不等的情况下，后一个数是大的数字，位数肯定多，而且第一位肯定是1，可以用这些关键点来解决） 问题:2：为了解决误差问题，我们就不能只选取前40位，那么应该选几位呢，经过测试发现最小能保证前40位没有问题的位数是52，测试方法见附录。 不过要是不能测试的时候可以以10位为单位扩大范围，反正50和60位的差距远比50和2万的差距小。 字典树 每一个结点中存有 从根节点到此结点的最小的Fibo序数，即最小前缀数字。 一个map，存有下一位的数字到下一位所在的结点的位置映射关系。 结点之间的关系如下图 在存储的时候，存入的字符串在经过每一个结点的时候，都要比一下这个结点中存储的minIndex（FIbo最小前缀序号），并将其替换成两者中更小的。 这样就能保证按照字典树的脉络寻找，寻找到的结点中的序号，一定是前缀数所在的最小的Fibo序号。 注意点 不知道现在的UVA 编译器是怎么回事，我定义的 int型返回值函数没有给返回值，返回判我 Runtime error。我一开始压根不明觉厉，一行一行注释，然后一次次提交看看哪部分代码没有才会不报 re，以此来判断问题出在哪部分。光是这样就提交了十几次。 我愿称之为绝活。 在 线 O J ，现 场 调 试。...

例题4-3 救济金发放（The Dole Queue, UVa 133） n(n<20)个人站成一圈，逆时针编号为1～n。有两个官员，A从1开始逆时针数，B从n开 始顺时针数。在每一轮中，官员A数k个就停下来，官员B数m个就停下来（注意有可能两个 官员停在同一个人上）。接下来被官员选中的人（1个或者2个）离开队伍。 输入n，k，m输出每轮里被选中的人的编号（如果有两个人，先输出被A选中的）。例 如，n=10，k=4，m=3，输出为4 8, 9 5, 3 1, 2 6, 10, 7。注意：输出的每个数应当恰好占3格。（即setw(3)） Sample Input 10 4 3 0 0 0 Sample Output ␣␣4␣␣8,␣␣9␣␣5,␣␣3␣␣1,␣␣2␣␣6,␣10,␣␣7 https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=832&page=show_problem&problem=69 有一个数组来表示队列里的人，然后分别用两个循环，从头和尾开始依次过，并且记录下每一轮最后的落脚点，在下一轮中就当做是起始点了。点出来的人的位置可以直接用0代替。 #include<iostream> #include<iomanip> using namespace std; int dole[25]; int n,a,b; int cycle(int j)//int n,int ab) { //int j=0; for(int i=0;i<a;i++) { do { j++; if(j==n) j=0; continue; } while(dole[j]==0); //j++; } return j; } int cycle2(int j)//int n,int b) { //int j=n-1; for(int i=0;i<b;i++) { do { j--; if(j<0) j=n-1; continue; } while(dole[j]==0); } //cout<<"j "<<j<<endl; return j; } int main() { while(cin>>n>>a>>b&&(n!...

例题4-1 古老的密码（Ancient Cipher, NEERC 2004, UVa1339） 给定两个长度相同且不超过100的字符串，判断是否能把其中一个字符串的各个字母重 排，然后对26个字母做一个一一映射，使得两个字符串相同。例如，JWPUDJSTVP重排后可 以得到WJDUPSJPVT，然后把每个字母映射到它前一个字母（B->A, C->B, …, Z->Y, A- Z），得到VICTORIOUS。输入两个字符串，输出YES或者NO。 Sample Input JWPUDJSTVP VICTORIOUS MAMA ROME HAHA HEHE AAA AAA NEERCISTHEBEST SECRETMESSAGES Sample Output YES NO YES YES NO https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=832&problem=4085&mosmsg=Submission+received+with+ID+20728592 //1、我们只需要分别记录两个字串里出现的各个字母的数量， //2、然后从小到大或从大到小排序， //3、之后进行比较，如果两个字串对应，那么他们的字母数量表相同下标的元素值（代表字母的数量）也应该相同。 #include<iostream> #include<string> using namespace std; void ssqrt(int *str) { //cout<<str<<endl; for(int i=0;i<26;i++) for(int j=i+1;j<26;j++) if(str[i]>str[j]) { int temp=str[i]; str[i]=str[j]; str[j]=temp; } //cout<<str<<endl; } int main() { string str,guess;//输入的两个字串 while(cin>>str>>guess) { int cha1[26]={0},cha2[26]={0};//分别记录两个字串里的各个字母的数量 for(int i=0;i<str....

习题3-7 DNA序列（DNA Consensus String, ACM/ICPC Seoul 2006, UVa1368） 输入m个长度均为n的DNA序列，求一个DNA序列，到所有序列的总Hamming距离尽量 小。两个等长字符串的Hamming距离等于字符不同的位置个数，例如，ACGT和GCGA的 Hamming距离为2（左数第1, 4个字符不同）。 输入整数m和n（4≤m≤50, 4≤n≤1000），以及m个长度为n的DNA序列（只包含字母 A，C，G，T），输出到m个序列的Hamming距离和最小的DNA序列和对应的距离。如有多 解，要求为字典序最小的解。例如，对于下面5个DNA序列，最优解为TAAGATAC。 TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT （汉明距离：算出 每列与 此列最多量的字符 不同的字符的个数 ，各个列相加） Sample Input 3 5 8 TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT 4 10 ACGTACGTAC CCGTACGTAG GCGTACGTAT TCGTACGTAA 6 10 ATGTTACCAT AAGTTACGAT AACAAAGCAA AAGTTACCTT AAGTTACCAA TACTTACCAA Sample Output TAAGATAC 7 ACGTACGTAA 6 AAGTTACCAA 12 https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=830&problem=4114&mosmsg=Submission+received+with+ID+20524214 //能解出来就是好的，有时候略微繁琐一些是在所难免的。 //It's not necessary to tack such a toxic attitude around that it's slightly difficult....

例题5-4 反片语（Ananagrams，Uva 156） 输入一些单词，找出所有满足如下条件的单词：该单词不能通过字母重排，得到输入文 本中的另外一个单词。 在判断是否满足条件时，字母不分大小写，但在输出时应保留输入中 的大小写，按字典序进行排列（所有大写字母在所有小写字母的前面）。 Sample Input ladder came tape soon leader acme RIDE lone Dreis peat ScAlE orb eye Rides dealer NotE derail LaCeS drIed noel dire Disk mace Rob dries # Sample Output Disk NotE derail drIed eye ladder soon https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=835&problem=92&mosmsg=Submission+received+with+ID+22713249 思路和书上的一样, 先把每次的单词变成小写, 然后将其存入map的键, 值就是原单词. 如果是重复的单词, 那么就把值变成空的. 最后判断 map 里每一个迭代对象的值是不是空就行了 将不是空的结果存入一个set, set自动排序, 然后再将set遍历输出即可 #include<iostream> #include<map> #include<string> #include<set> #include<algorithm> using namespace std; string lower(string s){ string re; for(int i=0;i<s....