8634 字符菱形
时间限制:500MS 内存限制:1000K 提交次数:0 通过次数:0
题型: 编程题 语言: 无限制
Description
zayhero 在印度比赛时的纪念品是一幅精致的竹叶画。他在看其他选手的竹叶画时发现其中一幅是以字符 菱形为基础画出来的。下图就是半径为1---5 时的字符菱形。
那幅画的构图，就是将很多个半径为10 的字符菱形不断延伸画成。由于这种图案包含了太多字符，所以 zayhero 觉得很混乱，为了理清思路，他需要知道画面上的字符分别有多少个。但由于画面太大了，所以 他每次只能看到画面的一部分，假设这个部分是一个矩形，请计算该矩形内部某种字符的个数。 在下面的图中，黄色部分的左上角为(13, 12)，右下角为(53, 25)，这个区域内没有字符a，但有12 个字 符e，49 个字符i，58 个字符j。
Input
第一行，一个整数T (T <= 500)，为测试数据组数。 之后2T 行，每2 行表示一组测试数据。每组数据 第一行，一个字符ch，表示需要计算个数的字符种类(a <= ch <= j)。 第二行，四个整数X1，Y1，X2，Y2，(1<=X1 <= X2<=50000，1<=Y1 <= Y2<=50000)，表示询问 的矩阵的范围，其中(X1，Y1)为矩形左上角，(X2，Y2)为右下角。 请注意，在本问题中，原点在左上角，而非一般的左下角。
Output
每组数据输出一行，输出需要计算的字符个数，具体格式见sample。
Sample Input
8 j 1 1 19 19 a 1 1 1 1 a 13 12 53 25 e 13 12 53 25 i 13 12 53 25 j 13 12 53 25 f 13 23 33 333 g 2 2 100 100
Sample Output
Case 1: 36 Case 2: 0 Case 3: 0 Case 4: 12 Case 5: 49 Case 6: 58 Case 7: 397 Case 8: 630
Hint
Source
Zayhero
Provider
admin
#include<stdio.h> #include<string.h> int main() { int alpha[22][22], word[10]; int x1, y1, x2, y2, k1, k2, i, j, t, T, cnt, x, y, m, n, max, nflag, mflag, n1; char temp, ch; // 构造字符菱形 memset(alpha, 1, sizeof(alpha)); memset(word, 0, sizeof(word)); for(i=1; i<20; ++i) { k1 = i>10? i%10 : 10 - i; for(j=k1+1; j<=19-k1; ++j) { k2 = j>10? j-19 : 1-j; t = i>10? k2+i-10 : k2+10-i; alpha[i][j] = t; word['j'+t-97]++; } } // 构造完成 scanf("%d", &T); t = T; while(T--) { getchar(); scanf("%c", &ch); scanf("%d%d%d%d", &x1, &y1, &x2, &y2); if(x1 > x2) {x1 ^= x2; x2 ^= x1; x1 ^= x2;} if(y1 > y2) {y1 ^= y2; y2 ^= y1; y1 ^= y2;} cnt = nflag = mflag = 0; k2 = 0; if((n = (y2-y1+1)/19) > 0) nflag = 1; if((m = (x2-x1+1)/19) > 0) mflag = 1; if(mflag && nflag) { cnt = n*m*word[ch-97]; n = (y2-y1+1)%19, m = (x2-x1+1)%19; k2 = 0; for(i=y2-n+1; i<=y2; ++i) for(j=1; j<20; ++j) if((k1 = alpha[i%19? i%19 : 19][j]) <= 0 && ch == 'j'+ k1) k2++; n1 = (x2-x1+1)/19; cnt = cnt + n1*k2; /* for(i=y2-n+1; i<=y2; ++i) for(j=x1; j<=x2; ++j) //这里要超时 { x = i%19? i%19 : 19; y = j%19? j%19 : 19; if((k1 = alpha[x][y]) <= 0 && ch == 'j'+ k1) ++cnt; } */ k2 = 0; for(i=1; i<20; ++i) for(j=x2-m+1; j<=x2; ++j) if((k1 = alpha[i][j%19? j%19 : 19]) <= 0 && ch == 'j'+ k1) k2++; n1 = (y2-y1+1)/19; cnt = cnt + n1*k2; /* for(j=x2-m+1; j<=x2; ++j) for(i=y1; i<=y2; ++i) //这里要超时 { x = i%19? i%19 : 19; y = j%19? j%19 : 19; if((k1 = alpha[x][y]) <= 0 && ch == 'j'+ k1) ++cnt; } */ for(i=y2-n+1; i<=y2; ++i) for(j=x2-m+1; j<=x2; ++j) { x = i%19? i%19 : 19; y = j%19? j%19 : 19; if((k1 = alpha[x][y]) <= 0 && ch == 'j'+ k1) ++cnt; } } else if(!mflag && !nflag) { for(i=y1; i<=y2; ++i) for(j=x1; j<=x2; ++j) { x = i%19? i%19 : 19; y = j%19? j%19 : 19; if((k1 = alpha[x][y]) <= 0 && ch == 'j'+ k1) ++cnt; } } else { if(nflag) { k2 = 0; for(i=1; i<20; ++i) for(j=x1; j<=x2; ++j) if((k1 = alpha[i][j%19? j%19 : 19]) <= 0 && ch == 'j'+ k1) k2++; n1 = (y2-y1+1)/19; cnt = cnt + n1*k2; n = (y2-y1+1)%19; for(i=y2-n+1; i<=y2; ++i) for(j=x1; j<=x2; ++j) if((k1 = alpha[i%19? i%19 : 19][j%19? j%19 : 19]) <= 0 && ch == 'j'+ k1) cnt++; } if(mflag) { k2 = 0; for(i=y1; i<=y2; ++i) for(j=1; j<20; ++j) if((k1 = alpha[i%19? i%19 : 19][j]) <= 0 && ch == 'j'+ k1) k2++; n1 = (x2-x1+1)/19; cnt = cnt + n1*k2; m = (x2-x1+1)%19; for(i=y1; i<=y2; ++i) for(j=x2-m+1; j<=x2; ++j) if((k1 = alpha[i%19? i%19 : 19][j%19? j%19 : 19]) <= 0 && ch == 'j'+ k1) cnt++; } } printf("Case %d: %d\n", t-T, cnt); } return 0; }
解题报告：
之前有编写菱形的经验，原本以为只是找输出如图菱形的规律需要消耗大部分的时间，刚输出完整的菱形时松了一口气，觉得接下来就容易处理多了
根据题目意思，输入坐标，然后充分利用求模遍历就行了，检验没错后提交，超时？？ 下来输入测试数据1 1 50000 50000 老半天才出来，看了一下这时判断字符的次数达到50000*50000，后来率先就改了菱形的构造函数，处理掉了一些不必要的判断和循环，（必须小心翼翼的，错了一个你不知道影响有多大！……）我想主要不是在这里啊，问题是遍历这里啊，后来想到干脆将一个菱形中所有出现的字符（毕竟只有a~j)个数都存储起来words，为了是看后面整个坐标划成的区域（矩形S）中有几个如此的菱形n， 然后先确定整的总数cnt = n*words； 而接下来的就处理剩余的部分：
图1 图2
蓝色的部分为n = 2 此时剩余蓝色线条圈住的空白，而我再次超时的做法是：
分别直接处理红色和黄色的部分，最后减去重叠部分（浅绿），此时输入1 1 50000 50000 并没有等很久才出现结果，但提交还是WA，下来分析原因还是发现不够简，尽管处理了整块的部分，但（y2-y1）和 （x2-x1)还可以很大的，最大可以达到2*50000*18， 此时应该再处理。
图3 图4
图5
情况一：（连接图1图2得到的图3）
先计算黑色的圈子里有几个所需要的字符，这时用不到word统计出来的数据，需在构造菱形时的数组里存储相应的字符，从而可以拿到现在来统计，然后计算有多少个这样的块m，比如所说这里在右边的竖直方向上有2块（下面的红色那块不算，因为大家的长和宽都不相同，尽管这里看上去相同，但实质上是由（x2-x1)%19 和 (y2-y1)%19 决定的）。
在水平方向上也这样处理，这时会剩下浅绿色的那块未计算，这块的长和宽分别是（x2-x1)%19 和 (y2-y1)%19 （那条是长那条是宽由自己决定）计算此块内所需统计的字符后加到总数中。
情况二：（图4）
（y2-y1) 异或 （x2-x1)超出了19，假设（x2-x1)>19这时跟处理上面的黑色那块一样，先计有在n=（x2-x1)/19， 然后得到（x2-x1)%19 和 （y2-y1) 围成的矩形中有多少个所需统计的字符，再与n相乘，而剩下的跟处理上图的浅绿色方块一样。
情况三：（图5）
这种情况最简单，直接计算围城的矩形里有多少需要统计的字符，但还是要对坐标求模计算。
个人情况：
花的事件可谓是不少啊，最后处理超时时，思维混乱了一个晚上，从下午7点到晚上1点多，好像时间都花在上面了，#￥&#@&&…… 但还比不上早上上课时用笔画图分情况思考，
而回来写代码的时候，在很多的复制过程中还是将 i 用成了j， 比如说： k1 = alpha[ij%19? j%19 : 19][j%19? j%19 : 19] 又不得不调试了一番……
思维能力自己感觉比别人欠缺了不少啊，严谨和周密、细心永远不能少！！！！！！
