Jove's Blog

题目链接：http://poj.org/problem?id=1028

1028的确是个水题，算法已经给出，仅要求你根据题意模拟浏览器的访问，前进，后退。
我查阅相关解题报告，感觉最好的思路就是STL中的stack，天然的浏览记录，第一次用stack，有点小激动。

其中，几个重要的函数：

ush()–将数据推入堆栈
pop()–推出堆栈
top()–查看堆栈最上方数据
empty()–检测堆栈是否为空

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

/*Problem: 1028		User: awq123
**Memory: 244K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <string>
#include <algorithm>
#include <stack>

using namespace std;

int main()
{
	stack<string> forward;
	stack<string> backward;
	string now="http://www.acm.org/",cmd;
	while(1)
	{
		cin>>cmd;
		if(cmd=="VISIT")
		{
			backward.push(now);
			cin>>now;
			cout<<now<<endl;
			while(!forward.empty()) forward.pop();
		}
		if(cmd=="BACK")
		{
			if(backward.empty())
				cout<<"Ignored"<<endl;
			else
			{
				forward.push(now);
				now=backward.top();
				cout<<now<<endl;
				backward.pop();
			}
		}
		if(cmd=="FORWARD")
		{
			if(forward.empty())
				cout<<"Ignored"<<endl;
			else
			{
				backward.push(now);
				now=forward.top();
				cout<<forward.top()<<endl;
				forward.pop();
			}
		}
		if (cmd=="QUIT")
			break;
	}

}

在没有用之前，我真的不会注意这，但是使用后你就不会忘记这，这就是vax一个强劲的vs插件。

Visual Assist X是一款非常好的Microsoft VisualStudio 2005和Visual Studio .NET插件，支持C/C＋＋，C＃，ASP，VisualBasic，Java和HTML等语言，能自动识别各种关键字、系统函数、成员变量、自动给出输入提示、自动更正大小写错误、自动标示错误等，有助于提高开发过程的自动化和开发效率。

我在网上收集了最新的10.6.1850破解版

首先运行安装文件，他会自动识别你的编译环境，然后安装破解补丁！

下载地址：jove_VAX_1850.rar

此软件可在下载中心下载！

题目链接：http://poj.org/problem?id=1017

这个题要求我们给1×1 2×2 3×3 4×4 5×5 6×6 六种包裹打包用最少的包裹，一个平面问题，我画图做的，在图中看比自己想快多了，后面会附加我做题的图，代码启发自某博客，加以研究。
装3×3时有其中可插入的2×2如图，1个3×3的，有5个2×2，其他的依次类推,
2个3×3可以放3个2×2,
3个3×3可以放1个2×2,
这样剩下的就是1×1的了
当然我门应该注意如果2×2或1×1多于间隙就要单独开箱来装了

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

/*Problem: 1017		User: awq123
**Memory: 172K		Time: 16MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include<stdio.h>
/*在linux下编译g++的iostream没有老式的输出*/
using namespace std;

int cc[4] = {0, 5, 3, 1};
/*装有3*3 的箱子可放2*2的包数 当放1个3*3可以放5个2*2 2个可放3个2*2*/
int a, b, c, d, e, f;
int num;

int main()
{
	while (scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e;, &f))
	{
		if (a==0 && b==0 && c==0 && d==0 && e==0 && f==0) break; 
			/* 4*4，5*5,6*6 的无疑每个都需要一个盒子 */
			num = d + e + f + (c+3)/4;/* (c+3)/4 是对于 3*3 的包需要的 6*6 大小的盒子数 */
		int aa, bb;
		bb = 5*d + cc[c%4];
		/* bb 是已有的包里能放多少个2*2的，每个放 4*4 的盒子还可以放 5 个 2*2的 */
		if (b > bb) 
			num += (b-bb+8)/9;
			/* 如果可装2*2的个数小于2*2的总个数新开箱子 每1～9 个开一个新箱子  */
		aa = num*36 - f*36 - e*25 - d*16 - c*9 - b*4;
		/* 总共剩下可以装1*1箱子的个数 */
		if (a>aa) 
			num += (a-aa+35)/36;
			/* 如果可装1*1的个数小于1*1的总个数新开箱子 每1～36开一个新箱子 */
		printf("%dn", num);
	}
return 0;
}

题目链接：http://poj.org/problem?id=1003

说实话，这个题目我看了半天，（不得不承认自己的英语水了点），网上都说这个是个水题，其实代码也不复杂，但是有些细节还是要注意的，题目大意可以理解成求1/2+1/3….1/x>=n的最小x值，我用最原始的方法做的，显然耗时有点多，看到别人0msAC还是很羡慕的，方法上还要优化啊
第一次超时代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

sum+=(1/i);


```第二次WA

```cpp
int i;
double  n=1,sum;
while(n!=0)
{
	cin>>n;
	for(i=2,sum=0;sum<n;i++)
	{
		sum+=(1.0/i);
	}
	cout<<i-2<<" card(s)"<<endl;
}


```完整代码如下：

```cpp
/*Problem: 1003		User: awq123
**Memory: 256K		Time: 16MS
**Language: C++		Result: Accepted
*/
#include <iostream>
using namespace std;
int main()
{
	int i;
	double  n,sum;
	cin>>n;
	while(n!=0)
	{
		for(i=2,sum=0;sum<n;i++)
		{
			sum+=(1.0/i);
		}
		cout<<i-2<<" card(s)"<<endl;
		cin>>n;
	}
return 0;	
}

题目链接：http://poj.org/problem?id=1833

下午研究了下1833，一个全排列问题，其中分析排列顺序并不容易，但是我们要感谢那些编写库函数的朋友，被我发现个全排列的函数next_permutation有的解释是这样的：

这是一个求一个排序的下一个排列的函数。如果要走遍所有的排列，你必须先排序。这是这两个函数使用需要注意的地方。
而其prev_permutation与之相反，是求一个排列的前一个排序。

这个题我原本的代码在vs10下运行正常，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int f[1028];
	int t;
	cin>>t;
	while(t--)
	{
		int n,k;
		cin>>n>>k;
		for(int i=0;i<n;i++)
			cin>>f[i];
		while(k--)
			next_permutation(f,f+n);
		cout<<f[0];
		for(int i=1;i<n;i++)
			cout<<" "<<f[i];
		cout<<endl;
	}
return0;
}

修改代码恢复老式输入输出结构代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/*Problem: 1833		User: awq123
**Memory: 176K		Time: 500MS
**Language: C++		Result: Accepted
*/
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int f[1028];
	int t;
	scanf("%d", &t;);
	while(t--)
	{
		int n,k;
		scanf("%d%d", &n;, &k;);
		for(int i=0;i<n;i++)
			scanf("%d", &f;[i]);
		while(k--)
			next_permutation(f,f+n);
		printf("%d", f[0]);
		for(int i=1;i<n;i++)
			printf(" %d", f[i]);
		printf("n");
	}
	return 0;
}

题目链接：http://poj.org/problem?id=2388

这个题目是基础排序的题目，主要利用数组的排序，我查阅相关资料，找到个数组排序的函数sort然而代码中的vector，维基里是这么解释的：

Vector 是一个动态数组（dynamic array）。在数据结构里，它被称之为容器（container），除此之外，其他则包括 set、map、…等等。由于它的实做是一个类模板，亦即泛型框架，所以它可以放置一般的数据型态，也可以放置用户自定义的数据型态，例如：它可以是一个放置整数（int）型态的 vector、也可以是一个放置字符串（char 或 string）型态的 vector、甚至可以放置用户自定类（user-defined class）的 vector。<
c++中灵活利用函数能使程序本身简洁度降到最低，也许poj应该禁用某些函数，让算法得到更大的利用

代码很简单多亏了sort函数，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/*Problem: 2388		User: awq123
**Memory: 296K		Time: 47MS
**Language: C++		Result: Accepted
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	int i, n;
	cin>>n;
	vector<int>num(n);
	for(i=0;i<n;i++)
		cin>>num[i];
	sort(num.begin(),num.end());
	cout<<num[n/2]<<endl; 
return 0;
}

才发现自己沉默的时候这么多愁善感。

今天一天不想说话，早上起来的时候，喉咙好疼，应该是扁桃体发炎了把，估计昨天晚上着凉了，早上朦胧之间听见彪起床的声音，其实那时我已经醒了，想想他也是去图书馆，我物理还有好多没看呢，昨天旧说要一块去的因为下雨就没去，就问他一块去把，当时喉咙还是好疼，不想说话。

早餐间，看到远处，一对穿情侣装的童鞋一块吃早餐在，羡慕不已，看他们的样子应该也是去图书馆的把，回想很多，原来我和小K也是这么约定的，不知怎么的突然觉得自己有点孤单，出了食堂门，跟彪说了句，想找个陪我学习的妹子，高中时和小K的日子还是很开心的，虽然那时我们还没有关系，但生活在忙碌紧张中的日子时充实的。大学的确是玩多了，自己总是莫名的感到彷徨，我也说不出来的那种感觉。

来到图书馆，不说人山人海，也算是座无虚席，好不容易还是找到了一个位置，但是坐的不怎么爽。

坐下静静的看了下书，我想把老师要求掌握的知识点都回顾下，如果不多顺便写下，休息间，撇见五楼大厅，每个人都是那副忙碌的样子，彪也不例外，想想自己以后，也许也会跟这群人一样，一样忙碌，一样充实，我们在楼梯口好多人上上下下，我还是太不专心了，有时闭上眼睛思考很多，想想刚才说得想找个妹子一块，笑了，至少我现在心里还是小K，也不可能去包容另外个女的把，也许我和她没有缘分，忘掉她也是时间的问题，但是既然现在还记得那就默默的珍惜把，如果有个女孩能让我动心，那时再谈这个问题把，永远的记忆给小K。

喉咙还是那么疼，到下午头也有点昏，在食堂吃了点饺子，把一碗饺子水都喝了，以前怎么没觉得热水这么舒服，饭间，没说话，也不想说话，彪也看出了我不舒服没说什么，他也算个不错的朋友了把，呵，慢慢的咳嗽也频繁了，没什么心思看书了，便决定回寝室休息会儿。

不知为什么，沉默间，我觉得自己眼睛更细的观察周围了，觉得自己仿佛能够看穿些什么，也许那些聋哑人就是这种感觉把，看到一棵树能想好多，说不清自己想什么，但是思绪飞逝，以前也有这样的感觉，高二那天自己也是头昏的不行一天趴着没说话，老师看我，同桌也就是解释了下，也就没什么了，沉默还是沉默，不想说话，然后自己变得很安静，小K一直说我不够沉稳，只有这个时候才觉得自己有那么一点沉稳，后来老段回忆说，我每次生病后就会静下心来，那次考试年级第8，不错的成绩。

自己很贪玩，自己知道，尤其遇到了高中那些特别的人，其实从他们身上学会了好多事，学会的彪说得无所谓，痞，也许那叫痞把，不过我更喜欢把他叫做自在，每次沉默间就会思考好多，不知道为什么，连逸凡都问我今天怎么了，怎么蔫了。还是不想说话，躺在床上，盖好毯子，浩浩睡一觉把，至少睡觉的时候很放松，他们说我总讲梦话，不知道是不是想太多的原因。

题目链接：http://poj.org/problem?id=1006

完成poj 1006，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <iostream>
using namespace std;
int main()
{
	int p,e,i,d,q;
	long int n,m=1;
	while(cin>>p>>e>>i>>d)
	{
		n=1;
		if(p!=-1||e!=-1||i!=-1||d!=-1)
		{
			while(!((n-p)%23==0&&(n-e)%28==0&&(n-i)%33==0))
				n++;
			q=(n-d)%21252;
			if(q<=0)
				q+=21252;
			cout<<"Case "<<m<<": the next triple peak occurs in "<<q<<" days."<<endl;
			m++;
		}
		else
			break;
	}
}

1
2
3

q=(n-d)%21252;

1
2
3
4

if(q<=0)
	q+=21252;

题目链接：http://poj.org/problem?id=1604

今天彪给我出了个小题，还是蛮有启发的。
这个题目如题就是简单的求n的阶乘的最后位非0数字，如果你还在想求出阶乘再算出最后一位，那么孩子你想太多了，n范围大些呢，题目中要求是n 小于 100000，这个已经彻底消灭了一个个试的心。
最开始的思路很简单,设一个循环变量从1-n,依次乘到累乘变量s中,只保留s的最后几位非零数字代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

/*错误算法，忽略5的倍数对结果可能带来的影响
*/
#include <iostream>
#include <iomanip>
using namespace std;
void main()
{
	long int n,m=1,i;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		m*=i;
		while(1)
		{
			if(m%10==0)
				m=m/10;
			else
			{
				m=m%10;
				break;
			}
		}
	}
	cout<<m;
}

稍作修改后，查阅poj发现正是是1604 ，顺便修改以完成题目，。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
	int n;
	while(cin>>n)
	{
		long int m=1,i;
		for(i=1;i<=n;i++)
		{
			m*=i;
			while(m%10==0)
				m=m/10;
			m=m%100000;
		}
		cout<<setw(5)<<n<<" -> "<<setw(1)<<m%10<<endl;
	}
}

关于Debug和Release之本质区别的讨论本文主要包含如下内容：

1. Debug 和 Release 编译方式的本质区别

2. 哪些情况下 Release 版会出错

3. 怎样“调试” Release 版的程序

一、Debug 和 Release 编译方式的本质区别

Debug 通常称为调试版本，它包含调试信息，并且不作任何优化，便于程序员调试程序。Release 称为发布版本，它往往是进行了各种优化，使得程序在代码大小和运行速度上都是最优的，以便用户很好地使用。

Debug 和 Release 的真正秘密，在于一组编译选项。下面列出了分别针对二者的选项（当然除此之外还有其他一些，如/Fd /Fo，但区别并不重要，通常他们也不会引起 Release 版错误，在此不讨论）

Debug 版本：

/MDd /MLd 或 /MTd 使用 Debug runtime library(调试版本的运行时刻函数库)

/Od 关闭优化开关

/D “_DEBUG” 相当于 #define _DEBUG,打开编译调试代码开关(主要针对assert函数)

/ZI 创建 Edit and continue(编辑继续)数据库，这样在调试过程中如果修改了源代码不需重新编译

/GZ 可以帮助捕获内存错误

/Gm 打开最小化重链接开关，减少链接时间

Release 版本：

/MD /ML 或 /MT 使用发布版本的运行时刻函数库

/O1 或 /O2 优化开关，使程序最小或最快

/D “NDEBUG” 关闭条件编译调试代码开关(即不编译assert函数)

/GF 合并重复的字符串，并将字符串常量放到只读内存，防止被修改

实际上，Debug 和 Release 并没有本质的界限，他们只是一组编译选项的集合，编译器只是按照预定的选项行动。事实上，我们甚至可以修改这些选项，从而得到优化过的调试版本或是带跟踪语句的发布版本。

二、哪些情况下 Release 版会出错

有了上面的介绍，我们再来逐个对照这些选项看看 Release 版错误是怎样产生的

1. Runtime Library：

2. 优化：这类错误主要有以下几种：

(1) 帧指针(Frame Pointer)省略（简称 FPO ）：在函数调用过程中，所有调用信息（返回地址、参数）以及自动变量都是放在栈中的。若函数的声明与实现不同（参数、返回值、调用方式），就会产生错误————但 Debug 方式下，栈的访问通过 EBP 寄存器保存的地址实现，如果没有发生数组越界之类的错误（或是越界“不多”），函数通常能正常执行；Release 方式下，优化会省略 EBP 栈基址指针，这样通过一个全局指针访问栈就会造成返回地址错误是程序崩溃。C++ 的强类型特性能检查出大多数这样的错误，但如果用了强制类型转换，就不行了。你可以在 Release 版本中强制加入 /Oy- 编译选项来关掉帧指针省略，以确定是否此类错误。

(2) volatile 型变量：volatile 告诉编译器该变量可能被程序之外的未知方式修改（如系统、其他进程和线程）。

(3) 变量优化：优化程序会根据变量的使用情况优化变量。例如，函数中有一个未被使用的变量，在 Debug 版中它有可能掩盖一个数组越界，而在 Release 版中，这个变量很可能被优化调，此时数组越界会破坏栈中有用的数据。当然，实际的情况会比这复杂得多。与此有关的错误有：

3. _DEBUG 与 NDEBUG ：当定义了 _DEBUG 时，assert() 函数会被编译，而 NDEBUG 时不被编译。除此之外，VC++中还有一系列断言宏。这包括：

ANSI C 断言 void assert(int expression );

C Runtime Lib 断言 _ASSERT( booleanExpression );

_ASSERTE( booleanExpression );

MFC 断言 ASSERT( booleanExpression );

VERIFY( booleanExpression );

ASSERT_VALID( pObject );

ASSERT_KINDOF( classname, pobject );

ATL 断言 ATLASSERT( booleanExpression );

此外，TRACE() 宏的编译也受 _DEBUG 控制。

4. /GZ 选项：这个选项会做以下这些事

(1) 初始化内存和变量。

(2) 通过函数指针调用函数时，会通过检查栈指针验证函数调用的匹配性。（防止原形不匹配）

(3) 函数返回前检查栈指针，确认未被修改.

三、怎样“调试” Release 版的程序

1. 前面已经提过，Debug 和 Release 只是一组编译选项的差别，实际上并没有什么定义能区分二者。我们可以修改 Release 版的编译选项来小错误范围。如上所述，可以把 Release 的选项逐个改为与之相对的 Debug 选项，如 /MD 改为 /MDd、/O1 改为 /Od，或运行时间优化改为程序大小优化。注意，一次只改一个选项，看改哪个选项时错误消失，再对应该选项相关的错误，针对性地查找。这些选项在 ProjectSettings… 中都可以直接通过列表选取，通常不要手动修改。由于以上的分析已相当全面，这个方法是最有效的。

2.你也可以像 Debug 一样调试你的 Release 版，只要加入调试符号。在 Project/Settings… 中，选中 Settings for “Win32 Release”，选中 C/C++ 标签，Category 选General，Debug Info 选 Program Database。再在 Link 标签 Project options 最后加上 “/OPT:REF” (引号不要输)。