正篇以及正确解题思路和代码参见 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....

例题6-19 自组合（Self-Assembly, ACM/ICPC World Finals 2013, UVa 1572） 有n（n≤40000）种边上带标号的正方形。每条边上的标号要么为一个大写字母后面跟着一个加号或减号，要么为数字00。当且仅当两条边的字母相同且符号相反时，两条边能拼在一起（00不能和任何边拼在一起，包括另一条标号为00的边）。 假设输入的每种正方形都有无穷多种，而且可以旋转和翻转，你的任务是判断能否组成一个无限大的结构。每条边要么悬空（不和任何边相邻），要么和一个上述可拼接的边相邻。如图6-17（a）所示是3个正方形，图6-17（b）所示边是它们组成的一个合法结构（但大小有限）。 Sample Input 3 A+00A+A+ 00B+D+A- B-C+00C+ 1 K+K-Q+Q Sample Output bounded unbounded 本家地址 提炼一下关键点：一共53种符号。方块数目很大，构造传统二维图会过大而超时。方块内部符号已知连通性。求方块间符号连通性。 可以抽象为52个点（00去掉），已知连通性（方块内部，不互补符号），互补符号可连通，当一段方块能够重复连接，即能够无限，即在可能的通路中求是否存在环路。 所以解决方案：使用dfs的方式，从一个符号开始，然后循环找方块内部的道路，找到之后，再递归走向下一个与其互补的符号。然后记录每一次递归通过的符号，即结点，当某一次递归走到了已经走过的符号结点上，那么就存在重复道路，即环路了。 具体看注释 #include<iostream> #include<string> #include<cstring> using namespace std; /* x -> y : inner */ /* y -> x : outer( + -) */ // /* A+B+C+D+...A-B-C-D- */ /* A+A-B+B-C+C-D+D-... */ int table[55][55]; /* 1: can go 2: has gone 用于减少计算数 */ int look[55]; /* 作为标记，锁一类。作为当前一次dfs中,这个点是否已经走过了 用于判断环路存在 */ int run[55]; int getIndex(char a,char b){ return (a-'A')*2 + (b=='-'?...

长度为n的环状串有n种表示法，分别为从某 个位置开始顺时针得到。例如，图3-4的环状串 有10种表示： CGAGTCAGCT，GAGTCAGCTC，AGTCAGCTCG等。在这些表示法中，字典序最小的称 为"最小表示"。 输入一个长度为n（n≤100）的环状DNA串（只包含A、C、G、T这4种字符）的一种表 示法，你的任务是输出该环状串的最小表示。例如，CTCC的最小表示是 CCCT，CGAGTCAGCT的最小表示为AGCTCGAGTC。 Sample Input 2 CGAGTCAGCT CTCC Sample Output AGCTCGAGTC CCCT https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=829&page=show_problem&problem=4459 #include<iostream> #include<string> #include<cstdio> #include<string.h> using namespace std; int const N = 100; //比较从be1,和从be2开始的字串哪一个更小 int com(char *s,int be1,int be2) { int sl=strlen(s); for(int i=0;i<sl;i++) { //cout<<endl<<(be1+i)%N<<endl; //cout<<s[(be1+i)%N]<<"_"<<s[(be2+i)%N]<<endl; if(s[(be1+i)%sl]>s[(be2+i)%sl]) return be2; if(s[(be1+i)%sl]<s[(be2+i)%sl]) return be1; } return be1; } char s[N+5]; int main() { // char acgt[4]="ACGT"; int T=1; cin>>T; while(T--) { scanf("%s",s); int j=0; int be1=0,be2; for(int i=0;i<strlen(s);i++)//找最小的首字符给be1 { if(s[i]<s[be1]) { be1=i; } } //cout<<be1<<endl; for(int i=0;i<strlen(s);i++)//在最小的首字符中 找最小的字串 { if(s[i]==s[be1]) { if(com(s,be1,i)==i) be1=i; } } for(int i=0;i<strlen(s);i++) cout<<s[(be1+i)%strlen(s)]; cout<<endl; } return 0; } ACat2017/12/9

给出一个由O和X组成的串（长度为1～80），统计得分。每个O的得分为目前连续出现 的O的个数，X的得分为0。例如，OOXXOXXOOO的得分为1+2+0+0+1+0+0+1+2+3。 Sample Input 5 OOXXOXXOOO OOXXOOXXOO OXOXOXOXOXOXOX OOOOOOOOOO OOOOXOOOOXOOOOX Sample Output 10 9 7 55 30 https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=830&problem=4460&mosmsg=Submission+received+with+ID+20465648 #include<iostream> #include<cstdio> using namespace std; int main() { int T; cin>>T; getchar(); while(T--) { int sum=0; int o=1; int c; while((c=getchar())!='\n') { if(c=='O') { sum+=o; o++; } if(c=='X') { o=1; } } cout<<sum<<endl; } return 0; } //AC at 2017/12/9

给出一种物质的分子式（不带括号），求分子量。本题中的分子式只包含4种原子，分 别为C, H, O, N，原子量分别为12.01, 1.008, 16.00, 14.01（单位：g/mol）。例如，C6H5OH的 分子量为94.108g/mol。 Sample Input 4 C C6H5OH NH2CH2COOH C12H22O11 Sample Output 12.010 94.108 75.070 342.296 https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=830&problem=4461&mosmsg=Submission+received+with+ID+20466109 //通过判断下一个字符的类型来执行上一个原子的量计算 #include<iostream> #include<cstdio> #include<cctype> using namespace std; int main()//两个变量，一个存原子量，一个存后面的数字 { int T; cin>>T; getchar(); while(T--) { int c; double sum=0,mol=0; int num=0; while((c=getchar())!='\n') { if(isdigit(c)) { num=num*10+c-'0'; //sum+=mol*(c-'0'); //num=1; } else { if(num) { sum+=mol*num;//加前一个原子*数量 mol=num=0; } else { sum+=mol;//加前一个原子 } switch(c) { case 'C':mol=12.01;break; case 'H':mol=1....

习题3-10 盒子（Box, ACM/ICPC NEERC 2004, UVa1587） 给定6个矩形的长和宽wi和hi（1≤wi，hi≤1000），判断它们能否构成长方体的6个面。 Sample Input 1345 2584 2584 683 2584 1345 683 1345 683 1345 2584 683 1234 4567 1234 4567 4567 4321 4322 4567 4321 1234 4321 1234 Sample Output POSSIBLE IMPOSSIBLE https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=830&problem=4462&mosmsg=Submission+received+with+ID+20554313 1、因为长方体都有三组含四条的边，我们先将三条不同的边长度用一个数组存起，在用一个数组存各个边在六组数据中分别出现的次数。 2、输入的同时来进行存边，并记录下出现的正方形的个数（即输入的两条边相等）。 3、六组输入完成后，判断是否属于以下情况 （1）a 4 , b 4 ,c 4 ,正方面 0 （2）a 8 , b 4 ,c 0 ,正方面 2 （3）a 12 , b 0 ,c 0 ,正方面 6 （a 4：a长度的边有4条）...

习题3-11 换低挡装置（Kickdown, ACM/ICPC NEERC 2006, UVa1588） 给出两个长度分别为n1，n2（n1，n2≤100）且每列高度只为1或2的长条。需要将它们放 入一个高度为3的容器（如图3-8所示），问能够容纳它们的最短容器长度。 Sample Input 2112112112 2212112 12121212 21212121 2211221122 21212 Sample Output 10 8 15 https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=830&problem=4463&mosmsg=Submission+received+with+ID+20560401 用两个字符串数组分别存这两个块，一块作为不动的，另一块在其上移动，判断当前移动到的位置是不是和下块契合（用循环依次比较各个位置），若不是则继续移动到下一位。 需要注意的是，最短的契合方案有可能你漏想了，下面一共是三种可能的情况。所以我用一个函数来将两个块换了位置后又移动了一次。 //三种情况：bbbbb aa (|a|:ab重叠 //1.短块在长块里(bb|aa|b) //2.短块头在长块里（外），短块尾巴超出长块尾(bbbb|a|a) //3.长块头在短块尾（外），长块尾巴超出短块尾(a|a|bbbb) //不要忘记第三种情况，有时最短空间就是出自3 #include<iostream> #include<cstring> using namespace std; const int N = 100; //int kick1[N+5],kick2[N+5]; int kickdown(string k1,string k2)//定k1，移k2 { //cout<<k1.size()<<" "<<k2.size()<<endl; for(int i=0;i<k1.size();i++) { int ii=i,j=0;//i就是大小块契合的那一位 //cout<<ii<<" "<<j<<endl; while((k1[ii]-'0'+k2[j]-'0')<=3&&(j<k2.size()&&ii<k1.size()))//若当前位不匹配则进行for到下一位 { //cout<<"k1 ii "<<ii<<" "<<k1[ii]<<" | k2 j"<<j<<" "<<k2[j]<<endl; ii++; j++; } if(j==k2....

习题4-1 象棋（Xiangqi, ACM/ICPC Fuzhou 2011, UVa1589） 考虑一个象棋残局，其中红方有n（2≤n≤7）个棋子，黑方只有一个将。红方除了有一个 帅（G）之外还有3种可能的棋子：车（R），马（H），炮（C），并且需要考虑“蹩马 腿”（如图4-4所示）与将和帅不能照面（将、帅如果同在一条直线上，中间又不隔着任何棋 子的情况下，走子的一方获胜）的规则。 输入所有棋子的位置，保证局面合法并且红方已经将军。你的任务是判断红方是否已经 把黑方将死。 Sample Input 2 1 4 G 10 5 R 6 4 3 1 5 H 4 5 G 10 5 C 7 5 0 0 0 Sample Output YES NO https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=833&problem=4464&mosmsg=Submission+received+with+ID+20833399 注意： 输入的第一行第一个为红子的数量，后两个是黑将的位置。接下来的是红子类型和位置。 思路： 1、黑将有四种走法，即上下左右。我们只要判断 是否这四种走法中合理的都是死路 即可判断将是否被将死 。 2、先判断是否当前的黑将走子的位置是否合理，即当前的将子有没有超出九宫格。 3、对于车炮帅的将军，我们可以一起判断，先从将的位置开始，依次往一条路过，比如从（1，4）向（10，4）竖的过， （1）如果路上遇到车或帅，那么就是将军了。 （2）若是非车帅的子，就计数加一。（比如我用c_iff变量记录目前非车帅的子数量）。 （3）若是炮，判断炮前是否有一个子（c_iff的值是不是一），若是，将军 。 （4）关于如何将“顺次从黑将开始分别左一行，右一行，上一列，下一列遍历格子上的子”放在一个循环条件里，见代码，我是将本应四个循环的条件写在一个循环体里用 if 处理了 4、关于马的将军，我们可以单独判断。看图,(x,y)位置为黑将，黑框位置为蹩马腿，如果此处没有子那么与其相邻的两个位置上有马的话就可以将军了。 这里的技巧1：两层循环过完四个方向，见代码 技巧2：黑框位置：（x+i，y+j），与其相邻的马（x+i+i，y+j）和（x+i，y+j+j） 5、注意：还有一点陷阱，我们还要考虑一开始黑将就和红帅对面，那样的话黑将就可以直接击杀红帅。样例： 2 1 5 G 10 5...

习题4-5 IP网络（IP Networks, ACM/ICPC NEERC 2005, UVa1590） 可以用一个网络地址和一个子网掩码描述一个子网（即连续的IP地址范围）。其中子网 掩码包含32个二进制位，前32-n位为1，后n位为0，网络地址的前32-n位任意，后n位为0。 所有前32-n位和网络地址相同的IP都属于此网络。 例如，网络地址为194.85.160.176（二进制为11000010|01010101|10100000|10110000）， 子网掩码为255.255.255.248（二进制为11111111|11111111|11111111|11111000），则该子网 的IP地址范围是194.85.160.176～194.85.160.183。输入一些IP地址，求最小的网络（即包含IP 地址最少的网络），包含所有这些输入地址。 例如，若输入3个IP地址：194.85.160.177、194.85.160.183和194.85.160.178，包含上述3 个地址的最小网络的网络地址为194.85.160.176，子网掩码为255.255.255.248。 Sample Input 3 194.85.160.177 194.85.160.183 194.85.160.178 Sample Output 194.85.160.176 255.255.255.248 【注意：他可能有很多组输入，而每组输出之间没有空行】 https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=833&problem=4465&mosmsg=Submission+received+with+ID+21184770 思路： 1、先将所有ip存起来，用数组或容器什么的。 2、转换二进制 3、从第一位开始，诸位比较所有的ip在这一位上的数字一样否 4、判断出最小网络位数，即掩码为1的位数。 5、转换十进制 （我用来存二进制的ip用的是string） （用了下vector，当然也可以用数组存，一个32*1000的数组） /* 110000100101010110100000_10110001 110000100101010110100000_10110111 110000100101010110100000_10110010 11000010010101011010000010110000 11111111111111111111111111111000 */ //特殊情况：只输入一个IP地址，这时掩码应该32位1 #include<iostream> #include<stack> #include<string> #include<vector> #include<cmath> #include<cstdio> using namespace std; string binary(int dec) { string str="00000000"; stack<int> s; int bin=0; for(int i=7;i>=0;i--) { //s.push(dec%2); str[i]=dec%2+'0'; dec /= 2; } // while(!...

例题5-9 数据库（Database，ACM/ICPC NEERC 2009，UVa1592） 输入一个n行m列的数据库（1≤n≤10000，1≤i≤10），是否存在两个不同行r1，r2和两个 不同列c1，c2，使得这两行和这两列相同（即（r1，c1）和（r2，c1）相同，（r1，c2）和 （r2，c2）相同）。例如，对于如图5-3所示的数据库，第2、3行和第2、3列满足要求。 Sample Input 3 3 How to compete in ACM ICPC,Peter,peter@neerc.ifmo.ru How to win ACM ICPC,Michael,michael@neerc.ifmo.ru Notes from ACM ICPC champion,Michael,michael@neerc.ifmo.ru 2 3 1,Peter,peter@neerc.ifmo.ru 2,Michael,michael@neerc.ifmo.ru Sample Output NO 2 3 2 3 YES 本家地址 设计存储的结构 [ { (c1.value, c2.value) -> r0.index } ] 列表中存储每一行中列列的组合（map存储）。列表的大小会是数据库的列*(列-1)/2。map的键是一个存有2个元素的列表（列表中存的是列值），map的值是对应的行下标。map的大小为总行数。 存储： 我们在存储时，针对每一行进行列的两两组合，然后对每一个组合在当前列组合下标中进行map查找，如果总排列数过完之后，有2个map匹配项，那我们就找到了。 在这里也用到了字符串索引存储的方式。类比指针，我们对每一个字符串给定一个编号，然后存在数据库中的就只是这个编号，而不用存字符串，节省了很大空间。 #include<iostream> #include<map> #include<string> #include<vector> #include<cstring> #include<cstdio> #include<set> using namespace std; /* [ { (c1.value, c2.value) -> r0....

例题6-20 理想路径（Ideal Path, NEERC 2010, UVa1599） 给一个n个点m条边（2≤n≤100000，1≤m≤200000）的无向图，每条边上都涂有一种颜 色。求从结点1到结点n的一条路径，使得经过的边数尽量少，在此前提下，经过边的颜色序 列的字典序最小。一对结点间可能有多条边，一条边可能连接两个相同结点。输入保证结点 1可以达到结点n。颜色为1～10 9的整数。 Sample Input 4 6 1 2 1 1 3 2 3 4 3 2 3 1 2 4 4 3 1 1 Sample Output 2 1 3 本家链接 先找最短路：倒序从终点bfs找。 - 在此认为倒序和正序效果一样。只是某些处理逻辑相反。 bfs之后，可能存在多条最短路，所以再需要一次bfs，来选出颜色最小的路。 降低时间的注意点： 选择合适的数据结构存储图。 一开始使用了map作为存储图的结构，后来在遍历过程中实在比vector慢了太多。 使用标记记录走过的结点，减少bfs重复计算。 对了2:00 - 2:30 期间uva oj 判题特别慢特别慢。尽量避开。 #include<iostream> #include<vector> #include<map> #include<queue> #include<cmath> #include<cstring> #include<set> using namespace std; #define mapiter map<int,int>::iterator const int MAX_N = 100005; /* 先找最短路：倒序从终点bfs找。 - 在此认为倒序和正序效果一样。只是某些处理逻辑相反。 bfs之后，可能存在多条最短路，所以再需要一次bfs，来选出颜色最小的路。 一开始使用了map作为存储图的结构，后来在遍历过程中实在比vector慢了太多。 */ /* a->b map[a][b] == color */ class Node{ public: int next; int color; }; // map<int,int> door[MAX_N]; vector<Node> door[MAX_N]; /* 存储无向图，因为结点太多了 */ int book[MAX_N]; /* 记录每个点距离终点`的最小距离 */ int visit[MAX_N]; /* 记录走过的点 */ int big = (1L<<31)-1; int res[MAX_N]; int N,M; /* n下各点 到n 的距离取最短+1 door[a][b] a -> b log[b] = min(log[b], log[a]+1) */ void bfs(){ queue<int> tmp; tmp....

习题4-2 正方形（Squares, ACM/ICPC World Finals 1990, UVa201） 有n行n列（2≤n≤9）的小黑点，还有m条线段连接其中的一些黑点。统计这些线段连成 了多少个正方形（每种边长分别统计）。 行从上到下编号为1～n，列从左到右编号为1～n。边用H i j和V i j表示，分别代表边 (i,j)-(i,j+1)和(i,j)-(i+1,j)。如图4-5所示最左边的线段用V 1 1表示。图中包含两个边长为1的正 方形和一个边长为2的正方形。 Sample Input 4 16 H 1 1 H 1 3 H 2 1 H 2 2 H 2 3 H 3 2 H 4 2 H 4 3 V 1 1 V 2 1 V 2 2 V 2 3 V 3 2 V 4 1 V 4 2 V 4 3...

习题3-8 循环小数（Repeating Decimals, ACM/ICPC World Finals 1990, UVa202） 输入整数a和b（0≤a≤3000，1≤b≤3000），输出a/b的循环小数表示以及循环节长度。例 如a=5，b=43，小数表示为0.(116279069767441860465)，循环节长度为21。 注意：有些即便是原题也可能没用看清的要求 （如果小数位大于50括号里显示到50个小数位即可，后面加…） （但是输出的小数位要是确实的位数，即便几百几千） https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=830&problem=138&mosmsg=Submission+received+with+ID+20551105 Sample Input 76 25 5 43 1 397 Sample Output 76/25 = 3.04(0) 1 = number of digits in repeating cycle 5/43 = 0.(116279069767441860465) 21 = number of digits in repeating cycle 1/397 = 0.(00251889168765743073047858942065491183879093198992…) 99 = number of digits in repeating cycle （ps：这个案例的99就很是误导人） 思路：从手算的除法公式下手，每一次的被除数都是 上一个被除数 – 上一位商*除数，而我们只要找到从哪里开始的被除数和之前的某一个被除数一样，那么从这一位便开始循环；如果不懂，看下面的例子：2/3 0.6 6 // 3|2.0 //一开始不够除，补零 1.8 //28 = 4（商）* 7（除数） 2 0 //20 = (30（被除数）- 4（商）* 7（除数）)*10 //开始循环 //同时我们发现 这里的被除数20 和第二行的被除数20 一样， 如果还不懂，亲自写一下除法运算，真的可以秒懂。...

例题6-1 并行程序模拟（ Concurrency Simulator, ACM/ICPC World Finals 1991, UVa210） 你的任务是模拟n个程序（ 按输入顺序编号为1～ n） 的并行执行。 每个程序包含不超过 25条语句， 格式一共有5种： var = constant（ 赋值） ； print var（ 打印） ； lock； unlock； end。 变量用单个小写字母表示， 初始为0， 为所有程序公有（ 因此在一个程序里对某个变量 赋值可能会影响另一个程序） 。 常数是小于100的非负整数。 每个时刻只能有一个程序处于运行态， 其他程序均处于等待态。 上述5种语句分别需 要t1、 t2、 t3、 t4、 t5单位时间。 运行态的程序每次最多运行Q个单位时间（ 称为配额） 。 当 一个程序的配额用完之后， 把当前语句（ 如果存在） 执行完之后该程序会被插入一个等待队 列中， 然后处理器从队首取出一个程序继续执行。 初始等待队列包含按输入顺序排列的各个 程序， 但由于lock/unlock语句的出现， 这个顺序可能会改变。 lock的作用是申请对所有变量的独占访问。 lock和unlock总是成对出现， 并且不会嵌套。 lock总是在unlock的前面。 当一个程序成功执行完lock指令之后， 其他程序一旦试图执行lock 指令， 就会马上被放到一个所谓的阻止队列的尾部（ 没有用完的配额就浪费了） 。 当unlock 执行完毕后， 阻止队列的第一个程序进入等待队列的首部。...

例题4-4 信息解码（Message Decoding, ACM/ICPC World Finals 1991, UVa 213） 考虑下面的01串序列： 0, 00, 01, 10, 000, 001, 010, 011, 100, 101, 110, 0000, 0001, …, 1101, 1110, 00000, … 首先是长度为1的串，然后是长度为2的串，依此类推。如果看成二进制，相同长度的后 一个串等于前一个串加1。注意上述序列中不存在全为1的串。 你的任务是编写一个解码程序。首先输入一个编码头（例如AB#TANCnrtXc），则上述 序列的每个串依次对应编码头的每个字符。例如，0对应A，00对应B，01对应#，…，110对 应X，0000对应c。接下来是编码文本（可能由多行组成，你应当把它们拼成一个长长的01 串）。编码文本由多个小节组成，每个小节的前3个数字代表小节中每个编码的长度（用二 进制表示，例如010代表长度为2），然后是各个字符的编码，以全1结束（例如，编码长度 为2的小节以11结束）。编码文本以编码长度为000的小节结束。 例如，编码头为$#\，编码文本为0100000101101100011100101000，应这样解码： 010(编码长度为2)00(#)00(#)10(*)11(小节结束)011(编码长度为3)000()111(小节结束)001(编码 长度为1)0($)1(小节结束)000(编码结束)。 Sample input TNM AEIOU 0010101100011 1010001001110110011 11000 $# 0100000101101100011100101000 Sample output TAN ME ##*$ https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=832&problem=149&mosmsg=Submission+received+with+ID+20759428 /* 1、先接收字符串，因为有空格，所以我用了getline，因为我用string 2、然后我们将输入的字符串存入code这个二维数组里，code[i][j]中i代表二进制码的位数，j代表当前01码的十进制数。以此我们每次循环的j小于2^i-i即可。 3、然后我们用循环，先将三位的二进制数传入bin_dec()函数，来得出接下来代表一个字符的二进制码的位数。 4、contra()函数是用来进行每一组相同码长的字符的输出。 （1）其思路是用一个变量记录当前bcode（01码字符串）读到哪个位了。 （2）然后循环将之后的len位二进制变成一个整数，传入bin_dec()函数得出其代表的十进制数，而这个十进制数也是code数组的第二维的下标。 5、还有一点，因为二进制码在输入的过程中并不一定是在同一行,所以我用了：当前下标+要接受的码长 和 当前的01码字符串长度来进行比较，若大则接收新的一行字符串，再加到原先01码字符串后面。（！注意这里用的是while循环而不是单一次的if判断，是因为可能接收一次字串后也依然不够码长，所以要一直接收到足够长为止。）*/ #include<iostream> #include<cmath> #include<string> #include<cstring> using namespace std; char code[7][1<<7];//长度，值，来存字符 int bin_dec(int b)//二进制转十进制 { int dec=0; for(int i=0;b!...