今天小组的群里讨论了关于对齐规则的问题，刚好是我不大熟悉的部分，所以收集了一些资料整理如下：内存对齐规则：1）数据成员对齐规则：结构(struct)(或联合(union))的数据成员，第一个数据成员放在offset为0的地方，以后每个数据成员存储的起始位置要从该成员大小的整数倍开始简单的说就是这样：Char 偏移量必须为sizeof(char)即1的倍数int 偏移量必须为sizeof(int)即4的倍数float 偏移量必须为sizeof(float)即4的倍数double 偏移量必须为sizeof(double)即8的倍数Short 偏移量必须为sizeof(short)即2的倍数举个例子来说明一下：struct name1{ char str; //在0偏移处存放，占1字节 short x; //原本应在第二个字节处存放（偏移量为1），但是偏移量应为2的整数倍，所以应该加1， //在第三个字节处存放（偏移量为2） int num; } sizeof(struct name1) = 1 + 1 + 2 + 4 = 8 struct name2{ char str; int num; //存放int型，偏移量应为4的倍数，故应在存放了一个字节的char型数据后，再偏移3个字节， //存放int型数据 sh ...继续阅读 (16)

刻苦的训练我打算最后稍微提一下。主要说后者：什么是有效地训练？我想说下我的理解。很多ACMer入门的时候，都被告知：要多做题，做个500多道就变牛了。其实，这既不是充分条件、也不会是必要条件。我觉得一般情况下，对于我们普通学校的大学生，各方面能力的差距不会太大，在这种情况下，训练和学习的方法尤为重要。其实，500题仅仅是一个标志，而且仅仅表示你做ACM-ICPC有一定的时间，我们训练的目的是什么？我觉得有四点1、提高编程能力2、学习算法，（读书，读论文，包括做一些题目验证）3、准备好面临将到来的挑战（熟悉题型，调整心态）4、启发思维。这里四个目的，从训练的角度上，重要性逐次递减；为什么呢？因为前面的因素是后面的基础。而是后面的目的，想达成越为不易。我觉得前3者能保证你ac掉你能做的题，即使难题始终不会做，也可以ac掉中等偏难的题目。而需要一定思维难度的题，要以前三者为基础而且属于训练的后期，中期只能作为偶尔调节。当然，我思维也烂得要死，对这点没什么发言权，大家可以鄙视我。我这里想主要说下第2点。对于算法，我发现，很多我们这样的弱校ACMer选手没有侧重好算法的学习。下面要讲的几点，可能都很老套，但我想以035对比我自己的例子给大家做说明。<1>算法学习是ACM比赛所要推广或者要提倡的一个方面记得曾经路过某人的blog，上面说他作比赛的时候遇到了一个dijkstra，他没做出来，然后 ...继续阅读 (27)

题意简述这题是POJ-2996的逆过程。给出棋盘描述，要求打印出棋盘。具体的描述和棋盘格式见POJ-2996。算法分析这个比2996简单。也是直接模拟。开一个二维数组存储8*8棋盘，读入一行后按","拆分，判断是3位还是2位，三位的话按第二三位定位点并存储第一位字符（注意根据黑白区分大小写），二位的话存储P。最后按指定格式输出即可。Problem Status: AC。时间0ms，内存388k程序样例#include#includevoid output(char a[8][8]) { int i,j; printf("+---+---+---+---+---+---+---+---+n"); for(i=0;i<8;i++) { printf("|"); for(j=0;j<8;j++) { if(a[i][j]==' ') if((i+j)%2==0) printf("...|"); else printf("::: |"); else if((i+j)%2==0) printf(".%c.|",a[i][j]); else ...继续阅读 (6)

题意简述将一个棋盘翻译为文字表达。如下：大写字母表示白方，小写表示黑方。输出时按照KQRBNP的顺序;棋盘格子编号的表示：从下往上是1～8,从左往右是a~h。遇到相同棋子，白方表示时按从下往上从左往右的顺序，黑方按从上往下从左往右的顺序。输出格式：White: Ke1,Qd1,Ra1,Rh1,Bc1,Bf1,Nb1,a2,c2,d2,f2,g2,h2,a3,e4 Black: Ke8,Qd8,Ra8,Rh8,Bc8,Ng8,Nc6,a7,b7,c7,d7,e7,f7,h7,h6算法分析直接模拟。分行读入棋盘，分析该行字母，将对应坐标记录。此处忽略黑白相同棋子从上往下和从下往上的区别，只需满足从上往下从左往右。输出时黑子按存储的顺序输出即可，白子输出相同棋子时判断，若有相同棋子则先输出行数大的。具体实现见代码。Problem Status: AC。时间0ms，内存388k——————————————————————分割线——————————————————————注意棋子是有规律的，最多16个，但可以不全出现。KQ各一个，RBN最多两个，P8个。程序样例#includevoid outputb(int a[16][2]) { int i; if (a[0][0]) printf("K%c%d",'a'+a[0][1]-1,9-a[0][0]); if (a[1 ...继续阅读 (9)

题意简述一个机器人从指定位置进入一个每格都指向一个确定方向的矩阵。它会顺着格子给定的方向运动。若机器人能走出矩阵，则输出其经过的格子数量。若机器人会陷入一个环，则输出经过多少格后，机器人进入了一个格数为多少的环。算法分析与POJ-2632类似。直接模拟。建立一个等大的累加矩阵，存储机器人经过的次数。当机器人碰墙时则认为机器人走出矩阵。计算此时累加矩阵内1的个数。即为经过格子数量。当机器人到达的点的累加值已经达到2，则说明机器人已经过一个环两次。此时计算累加矩阵内1的个数，即进入环前经过的格子数；计算矩阵内2的个数，即环所占格子数。Problem Status: AC。时间0ms，内存120k——————————————————————分割线——————————————————————优化：没想到。POJ排名第一仍然是0ms 4k的恐怖数据……程序样例#includevoid out(int map[][20],int n,int r,int c) { int i,j,ans1=0,ans2=0; for(i=0;i=0&&pos;[0]=0&&pos;[1] ...继续阅读 (21)

题意简述给定A*B的格子，放入N个机器人，每个机器人初始位置及朝向给定。给定M条指令。指令类型有三种：1、L：左转90°      2、R：右转90°       3、F：前进一格问执行指令过程中机器人是否发生碰撞，碰撞包括碰墙或碰其他机器人。安全执行完所有指令输出OK。（程序只需输出发生的第一次碰撞）算法分析模拟法。一条一条指令执行。指令执行过程把一条指令重复几遍拆分成几条指令来执行。每执行一条判断是否发生碰撞。若发生碰撞则标记位记0并输出。注意还需继续读取剩余输入。Problem Status: AC。时间0ms，内存156k——————————————————————分割线——————————————————————TIPS：机器人方向用0~3 四个数字表示四个朝向。转向时自增或自减即可。注意处理转后方向变为负值的情况。——————————————————————分割线——————————————————————优化：POJ最高成绩：内存4k 时间0ms……我现在开始怀疑内存占用和编译器有关系了……太诡异了……程序样例#includeint main() { int k,a,b,n,m,i,j,num,rep,rect[100][100],robot[100][3]; int flag; char c; for(scanf("%d",&k;); ...继续阅读 (10)

题意简述字符串s仅由括号构成（e.g.“(((()()())))”）。它可以用以下两种形式编码：1、P编码： 记录每个右括号前有几个左括号。例如：上面的S串可被表示为：4 5 6 6 6 6；2、W编码： 记录每对对应的左右括号之间有几个右括号。例如：上面的S串可被表示为：1 1 1 4 5 6给定测试组数t(1 <= t <= 10)，输入每组的右括号数量，和该串的P编码。输出该串的W编码。算法分析直接模拟。从读入的P编码中还原原串（我直接还原为01串，0为左括号1为右括号）。建一个栈。从头向后扫描还原的串。遇到左括号则压入栈内，遇到右括号则出栈，记录下该对左右括号的位置。扫描每对左右括号间有多少个右括号。输出结果。Problem Status: AC。时间0ms，内存120k——————————————————————分割线——————————————————————优化：该题POJ排名第一的成绩，耗时0ms，内存0k……太恐怖了……想不到这么神奇的算法……程序样例#includeint main() { int t,i,j,n[20][2],p=0,s[50]={0},tem,stack[50],ans; scanf("%d",&i;); for(;i>0;i--) { scanf("%d%d",&t;,&n;[0][0]); ...继续阅读 (16)

先让我吐槽一下…这题的题目真的不愧于“POJ最大的纸老虎”的称号啊！我用有道来来回回看了N遍愣是看不懂…最后百度了一下才知道它到底在说什么…题意简述MS公司的财务每月有盈利或赤字两种可能，若盈利则必盈利s元，若亏损则必亏损d元。已知1999年1~5月，2~6月，3~7月……8~12月，每五个月MS公司财务累计均为赤字。问1999年全年MS公司是否可能盈利？若能盈利则输出最大盈利，若不能盈利则输出“Deficit”。输入数据有多组。每行一组。算法分析贪心。易证得全年盈利只与12个月中盈利月总数和亏损月总数相关，与各月具体盈利或亏损无关。分析可知，欲满足每5个月总和为亏损，全年又必须盈利，则需要令每五个月内的亏损尽可能少。又为了尽可能多的让亏损月份可以在其他区间中共享，令5个月中的亏损月后置，盈利月前置。1~5月中盈利亏损分部仅有以下几种可能：ssssdsssddssdddsdddd确定第一个月的分部后，后面月份可以根据【统计亏损月份数量是否足够，不足则在末尾补上】的策略推出。只需按亏损月数递增的顺序扫描上述四种方案，直到能使5个月总和为亏损则停止。由选定的方案即可确定全年12个月方案。则可求出全年是否盈利。若全年财务为负值则不可盈利。（因ddddd的情况为全年亏损，明显无法盈利，故不用考虑。若遇到四个月亏损一个月盈利仍无法使5个月总和为负，则直接输出Deficit）根据前五个月可推出 ...继续阅读 (14)

题意简述设k^n=p，给定n与p（1<=n<= 200, 1<=p<10^101），求k。输入数据保证存在k且1<=k<=10^9。算法分析这题乍看是用高精度，可是考虑到1s出解的时间限制，和数据规模，联想到神奇的double类型，就通啦~这个数据规模，用double是完全存的下的。只需考虑如何求方根。一种显而易见的方法：k=pow(p,1/n)。这种方法直接就可以AC啦。Problem Status: AC。时间0ms，内存136k——————————————————————分割线——————————————————————不过如果考虑不允许使用pow函数呢？我们知道，k=p开n次方根。即：k=(e^(ln p))^(1/n)即：k=e^(ln(p)/n)所以也可以直接写成：k=exp(log(p)/n)——————————————————————分割线——————————————————————如果考虑不使用math库呢？在1s的情况下，二分法也好像会TLE。没有想到更好的解决方法。——————————————————————分割线——————————————————————TIPS:题目中并没有说明如何判断停止读入数据。数据又有多组。这种情况直接用while(1)会出现OLE的情况。（人生中第一次看到神奇的OLE啊~）可以使用：while(scanf("%lf%lf",&n; ...继续阅读 (16)

题意简述如图所示，x轴上方有n（1≤n≤1000）个岛屿（坐标均为整数），在x轴上可以放置覆盖半径为d（整数）的雷达。问最少放置多少个雷达能够覆盖所有岛屿？如果无法全部覆盖则输出-1。算法分析这道题折磨了我好几天，一直WA一直WA…本来觉得没多难都被WA崩溃了…好了不扯了进正题。首先分析无解的情况。容易得到：当且仅当某一岛屿的纵坐标大于雷达半径时，此组数据无解。 这个可以在读入时直接判断。需要注意的是，即便已经得到无解结论，也应等所有数据输入完毕再输出-1。接下来就是求解过程了。这题用贪心。但刚拿到手时，由于思考的局限性给出了错误的贪心策略。导致WA了好几次…（血泪史啊！T.T）下面先说错误的：错误贪心策略：所有岛屿按照横坐标从小到大排序。若横坐标相等则按纵坐标从大到小排序。首先利用第一个岛屿坐标，选择能够覆盖住它的，在它右侧距离最远的x轴上的点，放下第一个雷达。（位置可由勾股确定）。如图所示：橘色为雷达位置。扫描下一个点，如果在当前雷达覆盖范围内则继续向后扫描，否则以该点坐标为基准，依照步骤2中方法确立一个新雷达位置。直到所有岛屿被覆盖。这个贪心策略至少我当时完全没有想到任何破绽…可是一直WA一直WA…直到学长给了这样一组数据：其中雷达半径为5。这组数据只需在（1,0）放置一个雷达即可。但按照上面的策略，则需放置两个雷达。分别在（1,0）和（3,0）。这让我相当郁闷……最后无奈上 ...继续阅读 (13)

题意简述4*4矩阵，填充+或-，改变某格符号将同时改变当前行和列所有的格的符号。求最少经过多少次转换能使所有符号变为-，并输出任一种可行方案。算法分析本题与POJ-1753基本没有区别。仅仅换了壳，增加了输出一种可行方案。【POJ-1753解题报告 传送门】在POJ-1753的基础上，DFS同时用一个16个一维01数组记录当前的转换方案。与当前最优解比较时，如果更优则替换已记录的最优方案。Problem Status: AC。时间875ms，内存388k——————————————————————分割线——————————————————————优化：1、与POJ-1753一样可以使用一个int型代替一维01数组，用位运算实现转换。（还没试，改天再说…）2、在评测记录里看到一个内存16K，时间0ms的记录…估计和POJ-1753一样用了某种神奇的枚举…如果找到了代码或者算法会更新上来~程序样例#includeint finish(int s[]) { int i; for(i=0;i<16;i++) if (s[i]==0) return 0; return 1; } void change(int s[],int pos) { int i; if (s[pos]==1) s[pos]=0; else s[pos]=1; ...继续阅读 (8)

题意简述4*4的格子放有黑白两面的棋子16个，翻转任一棋子会使其上下左右棋子一同翻转。给定初始状态，求达到所有棋子全黑或全白的最少翻转次数。如果无解，输出Impossible。POJ1753附图算法分析首先容易证明：1、翻转棋盘上任意个棋子，棋盘达到的状态与各棋子被翻转的先后顺序无关。2、对每个棋子进行2次及以上的翻转没有意义。∵ 偶数次翻转结果与不翻转相同，奇数次翻转结果与翻转1次相同。于是问题被简化为：棋盘上部分棋子经过1次翻转，能使棋盘达到全黑或全白状态。求所需翻转棋子的最少数目。因为一共只有16个棋子，故只有2^16种可能。——————————————————————分割线——————————————————————具体算法：DFS。输入时将数据转化为1维01数组。dfs(array,position,step,answer)四个形参，array传递数组，position传递当前位置，step传递深度（也即翻转个数），ans传递当前最优答案。深搜时先判断当前状态是否满足条件，满足则和当前答案对比，若更优则替换。返回。若深度超出16也返回。改变当前位置，以及上下左右共5个点状态。dfs(array,position+1,step+1,answer)。回溯。只需再次改变5个点状态即可。dfs(array,position+1,step,answer)。Problem Statu ...继续阅读 (6)