UVaOJ

例题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!...

习题4-3 黑白棋（Othello, ACM/ICPC World Finals 1992, UVa220） 你的任务是模拟黑白棋游戏的进程。黑白棋的规则为：黑白双方轮流放棋子，每次必须 让新放的棋子“夹住”至少一枚对方棋子，然后把所有被新放棋子“夹住”的对方棋子替换成己 方棋子。一段连续（横、竖或者斜向）的同色棋子被“夹住”的条件是两端都是对方棋子（不 能是空位）。如图4-6（a）所示，白棋有6个合法操作，分别为(2,3),(3,3),(3,5), (6,2),(7,3), (7,4)。选择在(7,3)放白棋后变成如图4-6（b）所示效果（注意有竖向和斜向的共两枚黑棋变 白）。注意(4,6)的黑色棋子虽然被夹住，但不是被新放的棋子夹住，因此不变白。 （a） （b） 图4-6 黑白棋 输入一个8*8的棋盘以及当前下一次操作的游戏者，处理3种指令： L指令打印所有合法操作，按照从上到下，从左到右的顺序排列（没有合法操作时输出No legal move）。 Mrc指令放一枚棋子在(r,c)。如果当前游戏者没有合法操作，则是先切换游戏者再操作。输入保证这个操作是合法的。输出操作完毕后黑白方的棋子总数。 Q指令退出游戏，并打印当前棋盘（格式同输入）。 Sample Input 2 -——- -——- -——- —WB— -–BW— -——- -——- -——- W L M35 L Q WWWWB— WWWB—- WWB—– WB—— -——- -——- -——- -——- B L M25 L Q Sample Output (3,5) (4,6) (5,3) (6,4) Black - 1 White - 4 (3,4) (3,6) (5,6) -——-...

例题5-12 城市正视图（Urban Elevations, ACM/ICPC World Finals 1992, UVa221） 如图5-4所示，有n（n≤100）个建筑物。左侧是俯视图（左上角为建筑物编号，右下角 为高度），右侧是从南向北看的正视图。 图5-4 建筑俯视图与正视图 输入每个建筑物左下角坐标（即x、y坐标的最小值）、宽度（即x方向的长度）、深度 （即y方向的长度）和高度（以上数据均为实数），输出正视图中能看到的所有建筑物，按 照左下角x坐标从小到大进行排序。左下角x坐标相同时，按y坐标从小到大排序。 输入保证不同的x坐标不会很接近（即任意两个x坐标要么完全相同，要么差别足够大， 不会引起精度问题）。 Sample Input 14 160 0 30 60 30 125 0 32 28 60 95 0 27 28 40 70 35 19 55 90 0 0 60 35 80 0 40 29 20 60 35 40 25 45 80 0 67 25 20 50 0 92 90 20 80 95 38 55 12 50...

习题3-5 谜题（Puzzle, ACM/ICPC World Finals 1993, UVa227） 有一个5*5的网格，其中恰好有一个格子是空的，其他格子各有一个字母。一共有4种指 令：A, B, L, R，分别表示把空格上、下、左、右的相邻字母移到空格中。输入初始网格和指 令序列（以数字0结束），输出指令执行完毕后的网格。如果有非法指令，应输出“This puzzle has no final configuration. 还有：输入的迷宫以大写 Z 结束。输出的行与行间要有一行空行 Sample Input TRGSJ XDOKI M VLN WPABE UQHCF ARRBBL0 ABCDE FGHIJ KLMNO PQRS TUVWX AAA LLLL0 ABCDE FGHIJ KLMNO PQRS TUVWX AAAAABBRRRLL0 Z Sample Output Puzzle #1: T R G S J X O K L I M D V B N W P A E U Q H C F...

习题3-6 纵横字谜的答案（Crossword Answers, ACM/ICPC World Finals 1994, UVa232） 输入一个r行c列（1≤r，c≤10）的网格，黑格用“*”表示，每个白格都填有一个字母。如 果一个白格的左边相邻位置或者上边相邻位置没有白格（可能是黑格，也可能出了网格边 界），则称这个白格是一个起始格。 首先把所有起始格按照从上到下、从左到右的顺序编号为1, 2, 3,…，如图所示。 接下来要找出所有横向单词（Across）。这些单词必须从一个起始格开始，向右延伸到 一个黑格的左边或者整个网格的最右列。最后找出所有竖向单词（Down）。这些单词必须 从一个起始格开始，向下延伸到一个黑格的上边或者整个网格的最下行。 输出时每两行之间有空行 Sample Input 2 2 AT O 6 7 AIMDEN MEONE UPONTO SOERIN SAOR* IES*DEA 0 Sample Output puzzle #1: Across 1.AT 3.O Down 1.A 2.TO puzzle #2: Across 1.AIM 4.DEN 7.ME 8.ONE 9.UPON 11.TO 12.SO 13.ERIN 15.SA 17.OR 18.IES 19.DEA Down 1.A 2.IMPOSE 3.MEO 4.DO 5.ENTIRE 6.NEON 9.US 10.NE 14.ROD 16.AS...

习题4-4 骰子涂色（Cube painting, UVa 253） 输入两个骰子，判断二者是否等价。每个骰子用6个字母表示，如图4-7所示。 图4-7 骰子涂色 例如rbgggr和rggbgr分别表示如图4-8所示的两个骰子。二者是等价的，因为图4-8（a） 所示的骰子沿着竖直轴旋转90°之后就可以得到图4-8（b）所示的骰子。 （a） （b） 图4-8 旋转前后的两个骰子 . Sample Input rbgggrrggbgr rrrbbbrrbbbr rbgrbgrrrrrg Sample Output TRUE FALSE FALSE 思路：暴力枚举，将一个骰子的所有姿态都列出来， 1、注意第一个图上的数字，那个是记录骰子面的顺序 2、先找最上面的，也就是1的位置，能排列6种（1，2，3，4，5，6） 3、然后找到了上面也就找到了与其相对的面，就是下面，就是字串中第六个元素。这个不会额外记录，因为有上就有下了。 4、然后就是中间四个的排列了，很显然，4种。 5、然后我们变换第二个骰子，看看它在这24种情况中，有没有一种的情况和第一个骰子的记录是相同的。（比较字串即可） 6、请注意骰子面的转换是否正确，虽然这个逻辑简单，但是容易写错，要好好检查，我就因为写错下标错了两次。 #include<iostream> #include<string> using namespace std; /* 1 3 2 4 5 1在顶上 6 2 3 6 4 1 2在顶上 5 3 5 6 2 1 3在顶上 4 4 2 6 5 1 4在顶上 3 5 4 6 3 1 5在顶上 2 6 3 5 4 2 6在顶上 1 */ string s1,s2;//记录两个骰子的字符串 int str_equal(string a,char s1,char s2,char s3,char s4,char s5,char s6)//比较两个字串相等吗 { string b="0000000"; b[1]=s1; b[2]=s2; b[3]=s3; b[4]=s4; b[5]=s5; b[6]=s6; //cout<<b....

例题6-11 四分树（Quadtrees, UVa 297） 如图6-8所示，可以用四分树来表示一个黑白图像，方法是用根结点表示整幅图像，然 后把行列各分成两等分，按照图中的方式编号，从左到右对应4个子结点。如果某子结点对 应的区域全黑或者全白，则直接用一个黑结点或者白结点表示；如果既有黑又有白，则用一 个灰结点表示，并且为这个区域递归建树。 图6-8 四分树 给出两棵四分树的先序遍历，求二者合并之后（黑色部分合并）黑色像素的个数。p表 示中间结点，f表示黑色（full），e表示白色（empty）。 样例输入： 3 ppeeefpffeefe pefepeefe peeef peefe peeef peepefefe 样例输出： There are 640 black pixels. There are 512 black pixels. There are 384 black pixels. 本家 构造32*32的矩阵，构建树木的时候同时给矩阵染色，由于黑色会覆盖，所以也不怕树木之间的冲突。然后最后刷一下矩阵，看看有多少个黑块块就行（即数字为1） #include<iostream> #include<string> #include<cmath> using namespace std; /* 共5+1层 32*32=4^5 */ int SIDE_LENGTH = 32; int quad[100][100]; int sum = 0; /* f > p > e */ void build(int side,int x,int y){ char c; cin>>c; if(c=='p'){ for(int xi=0;xi<=1;xi++){ for(int yi=0;yi<=1;yi++){ int nextSide = side / 2; int xx = x+nextSide*xi; int yy = y+nextSide*yi; build(nextSide,xx,yy); } } }else if(c=='f'){ /* fill $quad from $begin to $end */ for(int xi=x;xi<x+side;xi++){ for(int yi=y;yi<y+side;yi++){ if(quad[xi][yi]==0){ sum++; quad[xi][yi] = 1; } } } } } int main(){ int T; cin>>T; while(T--){ // memset(quad,0,SIDE_LENGTH*SIDE_LENGTH*sizeof(int)); for(int i=0;i<SIDE_LENGTH;i++){ for(int j=0;j<SIDE_LENGTH;j++){ quad[i][j]=0; } } sum = 0; for(int i=0;i<2;i++){ build(SIDE_LENGTH,0,0); } cout<<"There are "<<sum<<" black pixels....