博文
关于结构体的大小(#pragma pack())(2008-10-01 15:52:00)
摘要：经常会遇到要求sizeof(struct)的问题，由于要涉及到字节对齐的问题，而且不同平台结果也有所不同，所以，现对vc下的字节对齐总结一下：
struct test...{
double m4; char m1； int m3;}
在默认情况下，VC规定各成员变量存放的起始地址相对于结构的起始地址的偏移量必须为该变量的类型所占用的字节数的倍数。下面列出常用类型的对齐方式(vc6.0,32位系统)。类型 对齐方式（变量存放的起始地址相对于结构的起始地址的偏移量）Char 偏移量必须为sizeof(char)即1的倍数Short 偏移量必须为sizeof(short)即2的倍数int 偏移量必须为sizeof(int)即4的倍数float 偏移量必须为sizeof(float)即4的倍数double 偏移量必须为sizeof(double)即8的倍数各成员变量在存放的时候根据在结构中出现的顺序依次申请空间，同时按照上面的对齐方式调整位置，空缺的字节VC会自动填充。同时VC为了确保结构的大小为结构的字节边界数（即该结构中占用最大空间的类型所占用的字节数）的倍数，所以在为最后一个成员变量申请空间后，还会根据需要自动填充空缺的字节。为上面的结构分配空间的时候，VC根据成员变量出现的顺序和对齐方式，先为第一个成员dda1分配空间，其起始地址跟结构的起始地址相同（刚好偏移量0刚好为sizeof(double)的倍数），该成员变量占用sizeof(double)=8个字节；接下来为第二个成员dda分配空间，这时下一个可以分配的地址对于结构的起始地址的偏移量为8，是sizeof(char)的倍数，所以把dda存放在偏移量为8的地方满足对齐方式，该成员变量占用 sizeof(char)=1个字节；接下来为第三个成员type分配空间，这时下一个可以分配的地址对于结构的起始地址的偏移量为9，不是sizeof (int)=4的倍数，为了满足对齐方式对偏移量的约束问题，VC自动填充3个字节（这三个字节没有放什么东西），这时下一个可以分配的地址对于结构的起始地址的偏移量为12，刚好是sizeof(int)
=4的倍数，所以把type存放在......
文本压缩问题(2008-09-09 14:17:00)
摘要：#include<iostream>#include<fstream>#include<stdio.h>#include<string>#define MAX 10000using namespace std;ifstream filein("COMPRE5.DAT");ofstream fileout("comper5.out");string s[1000];int s1[1000];
int len,map[10000],fk;string doc;
void del(string a,int n){ string b(a,n,a.length()); doc=b;}
void workout(){ int i,j; for(i=1;i<=len;i++) map[i]=MAX; map[0]=0; j=0; while(doc.length()>0) { for(i=0;i<fk;i++) { int n=s[i].length(); string b(doc,0,n); if(s[i]==b) { if(map[j]+s1[i]<map[j+s[i].length()]) map[j+s[i].length()]=map[j]+s1[i]; } } del(doc,1); j++; }}int main(){ int N,i; string temp; filein>>N; filein>>temp; fk=0; while(N>0) { &nb......
Employment Planning(hdu1158)(2008-08-18 15:43:00)
摘要：Employment PlanningTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 606 Accepted Submission(s): 184
Problem Description
A project manager wants to determine the number of the workers needed in every month. He does know the minimal number of the workers needed in each month. When he hires or fires a worker, there will be some extra cost. Once a worker is hired, he will get the salary even if he is not working. The manager knows the costs of hiring a worker, firing a worker, and the salary of a worker. Then the manager will confront such a problem: how many workers he will hire or fire each month in order to keep the lowest total cost of the project.
Input
The input may contain several data sets. Each data set contains three lines. First line contains the months of the project planed to use which is no more than 12. The second line contains the cost of hiring a worker, the amoun......
Domino Art(2008-08-17 10:12:00)
摘要：
Domino Art
Time Limit: 10000ms, Special Time Limit:25000ms, Memory Limit:65536KB
Total submit users: 4, Accepted users: 2
Problem 11223 : No special judgement
Problem description
Lawliet is a very intelligent person, he is often seen solving puzzles or painting beautiful landscapes, in his new challenge he is trying to make some art with dominoes, he will draw a figure on a rectangular grid consisting of 1x1 squares by marking some of these squares, after that he will try to cover the marked squares with dominoes. As you probably know dominoes consist of pieces of size 2x1, for simplicity we assume that the dominoes can only be put horizontally or vertically and that you have an unlimited amount of dominoes available. The cover has to be perfect, meaning that the dominoes must cover only the marked positions and the dominoes must cover all of them, also all the dominoes must lie strictly inside the rectangular grid. Below are shown two examples of possible......
Nim游戏(2008-08-16 17:55:00)
摘要：Nim游戏
Nim游戏是博弈论中最经典的模型（之一？），它又有着十分简单的规则和无比优美的结论Nim游戏是组合游戏(Combinatorial Games)的一种，准确来说，属于“Impartial Combinatorial Games”（以下简称ICG）。满足以下条件的游戏是ICG（可能不太严谨）：1、有两名选手；2、两名选手交替对游戏进行移动(move)，每次一步，选手可以在（一般而言）有限的合法移动集合中任选一种进行移动；3、对于游戏的任何一种可能的局面，合法的移动集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素； 4、如果轮到某名选手移动，且这个局面的合法的移动集合为空（也就是说此时无法进行移动），则这名选手负。根据这个定义，很多日常的游戏并非ICG。例如象棋就不满足条件3，因为红方只能移动红子，黑方只能移动黑子，合法的移动集合取决于轮到哪名选手操作。通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。这游戏看上去有点复杂，先从简单情况开始研究吧。如果轮到你的时候，只剩下一堆石子，那么此时的必胜策略肯定是把这堆石子全部拿完一颗也不给对手剩，然后对手就输了。如果剩下两堆不相等的石子，必胜策略是通过取多的一堆的石子将两堆石子变得相等，以后如果对手在某一堆里拿若干颗，你就可以在另一堆中拿同样多的颗数，直至胜利。如果你面对的是两堆相等的石子，那么此时你是没有任何必胜策略的，反而对手可以遵循上面的策略保证必胜。如果是三堆石子……好像已经很难分析了，看来我们必须要借助一些其它好用的（最好是程式化的）分析方法了，或者说，我们最好能够设计出一种在有必胜策略时就能找到必胜策略的算法。定义P-position和N-position，其中P代表Previous，N代表Next。直观的说，上一次move的人有必胜策略的局面是P-position，也就是“后手可保证必胜”或者“先手必败”，现在轮到move的人有必胜策略的局面是N-position，也就是“先手可保证必胜”。更严谨的定义是：1.无法进行任何移动的局面（也就是terminal pos......
Sudoku Killer(HDU1426)(2008-08-15 13:09:00)
摘要：
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 283 Accepted Submission(s): 76
Problem Description
自从2006年3月10日至11日的首届数独世界锦标赛以后，数独这项游戏越来越受到人们的喜爱和重视。据说，在2008北京奥运会上，会将数独列为一个单独的项目进行比赛，冠军将有可能获得的一份巨大的奖品———HDU免费七日游外加lcy亲笔签名以及同hdu acm team合影留念的机会。所以全球人民前仆后继，为了奖品日夜训练茶饭不思。当然也包括初学者linle，不过他太笨了又没有多少耐性，只能做做最最基本的数独题，不过他还是想得到那些奖品，你能帮帮他吗？你只要把答案告诉他就可以，不用教他是怎么做的。数独游戏的规则是这样的：在一个9x9的方格中，你需要把数字1-9填写到空格当中，并且使方格的每一行和每一列中都包含1-9这九个数字。同时还要保证，空格中用粗线划分成9个3x3的方格也同时包含1-9这九个数字。比如有这样一个题，大家可以仔细观察一下，在这里面每行、每列，以及每个3x3的方格都包含1-9这九个数字。例题：答案：
Input
本题包含多组测试，每组之间由一个空行隔开。每组测试会给你一个 9*9 的矩阵，同一行相邻的两个元素用一个空格分开。其中1-9代表该位置的已经填好的数，问号（?）表示需要你填的数。
Output
对于每组测试，请输出它的解，同一行相邻的两个数用一个空格分开。两组解之间要一个空行。对于每组测试数据保证它有且只有一个解。
Sample Input
7 1 2 ? 6 ? 3 5 8
? 6 5 2 ? 7 1 ? 4
? ? 8 5 1 3 6 7 2
9 2 4 ? 5 6 ? 3 7
5 ? 6 ? ? ? 2 4 1
1 ? 3 7 2 ? 9 ? 5
? ? 1 9 7 5 4 8 6
6 ? 7 8 3 ? 5 1 9
8 5 9 ? 4 ? ? 2 3
&......
Oil Deposits(2008-08-13 14:59:00)
摘要：
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 22 Accepted Submission(s) : 9
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.
Input
The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns ......
哈密顿绕行世界问题(2008-08-13 14:56:00)
摘要：
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 8 Accepted Submission(s) : 4
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
一个规则的实心十二面体，它的 20个顶点标出世界著名的20个城市，你从一个城市出发经过每个城市刚好一次后回到出发的城市。
Input
前20行的第i行有3个数,表示与第i个城市相邻的3个城市.第20行以后每行有1个数m,m<=20,m>=1.m=0退出.
Output
输出从第m个城市出发经过每个城市1次又回到m的所有路线,如有多条路线,按字典序输出,每行1条路线.每行首先输出是第几条路线.然后个一个: 后列出经过的城市.参看Sample output
Sample Input
2 5 20
1 3 12
2 4 10
3 5 8
1 4 6
5 7 19
6 8 17
4 7 9
8 10 16
3 9 11
10 12 15
2 11 13
12 14 20
13 15 18
11 14 16
9 15 17
7 16 18
14 17 19
6 18 20
1 13 19
5
0
Sample Output
1: 5 1 2 3 4 8 7 17 18 14 15 16 9 10 11 12 13 20 19 6 5
2: 5 1 2 3 4 8 9 10 11 12 13 20 19 18 14 15 16 17 7 6 5
3: 5 1 2 3 10 9 16 17 18 14 15 11 12 13 20 19 6 7 8 4 5
4: 5 1 2 3 10 11 12 13 20 19 6 7 17 18 14 15 16 9 8 4 5
5: 5 1 2 12 11 10 3 4 8 9 16 15 14 13 20 19 18 17 7 6 5
6: 5 ......
【回文数(二)】(2008-08-12 20:31:00)
摘要：Time Limit:1000MS Memory Limit:1000KTotal Submit:36 Accepted:10
Description
若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。 例如：给定一个10进制数56，将56加65（即把56从右向左读），得到121是一个回文数。 又如：对于10进制数87： STEP1：87+78 = 165 STEP2：165+561 = 726 STEP3：726+627 = 1353 STEP4：1353+3531 = 4884 在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。 写一个程序，给定一个N（2<=N<=16）进制数M，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!”
Input
共两行 第一行为进制数N（2<=N<=16） 第二行为N进制数M（0<=M<=maxlongint）
Output
共一行，为“STEP=经过的步数”或“Impossible!”
Sample Input
9
87
Sample Output
STEP=6
Source
NOIP1999
#include<stdio.h>
#include<string.h>
char a[10000],b[10000],c[10000];
void f(int N) //N ????????
{
int temp,cout=0;
int aa,bb,i;
int ai=strlen(a);
int bi=strlen(b);
int ci1=ai>bi?ai-1:bi-1;
int ci2=ci1;
c[ci1+1]='\0';
cout = 0;
while(ai>0&&bi>0)
{
if(a[ai-1]>='A')
aa=a[ai-1]-55;
else aa=a[ai-1]-'0';
ai--;
if......
【检查金币】(2008-08-12 20:30:00)
摘要：
Time Limit:1000MS Memory Limit:65536KTotal Submit:26 Accepted:20
Description
ACM公司生产金币的设备出了问题，使得最近生产的10批金币的重量出现了波动：本来金币的标准重量是10克，但现在有的可能是11克，有的可能9克，也有可能是10克。 现在只知道同一批金币的重量是相同的，你的任务是要把每批的单枚金币的重量找出来。 你的设备有一个电子秤，但只允许称量一次！ 你从第1批中取1枚金币，第2批取3枚，...第i批取3^(i−1)枚...，第10批取3^9枚，总共29524枚。将这29524枚金币放在电子秤上，得到了总重量，就交给你的程序去！
Input
有多个测试序列，每个测试序列一行，包含一个6位的正整数W(265716≤W≤324764)，表示29524枚金币的总重量。
Output
每个测试序列输出一行，包含10个用空格分开的正整数，分别表示10批金币的单枚重量，注意行尾没有空格。
Sample Input
265716
324764
295240
Sample Output
9 9 9 9 9 9 9 9 9 9
11 11 11 11 11 11 11 11 11 11
10 10 10 10 10 10 10 10 10 10
Hint
ＤＦＳ
Source
HUNAN UNIVERSITY ACM/ICPC Judge Online
#include<stdio.h>#include<math.h>int a[60000][10];int b[10];#define MIN 265716int main(){ int n,i,j,min,k,total; for(i=0;i<10;i++) a[0][i]=9; for(i=0;i<10;i++) b[i]=(int)pow(3,i); for(i=1;i<=59048;i++) { total=i+MIN; min=MIN; for(k=0;k<10;k++) a[i][k]=9; for(j=9;j>=0;j--) { if(......