HDOJ 2035 人见人爱A ^ B

突然想起还有一份杭电ACM的PPT没看，翻出来看了下~发觉蛮有意思的，就是内容少了点。。。基本上是提纲，该总结的都自己来吧。╮(￣▽￣")╭

题目很简单，但也蛮经典的算术题。
输入两个数A,B。输出A ^ B的最右三位数。

核心思路：求 A的B次方 模1000，只需要求 A%1000 的 B次方。B通过降幂二分加速。
比如：（1123）^ 6 = (1000 + 123) ^ 6
多项式展开后，决定结果最后三位的是123 ^ 6
然后123 ^ 6 = (123 ^ 3) ^ 2

version 1.0  纯暴力

#include<cstdio>
int main()
{
int a,b,sum;
while(scanf("%d%d",&a,&b) && a){
sum = a;
for(int i = 1;i < b;i ++){
sum *= a;
if(sum >= 1000)sum %= 1000;
}
printf("%d\n",sum);
}
return 0;
}



优化之后，通过二分加速，int范围内的大数都可以接受。
version 1.1 递归

关于import & package的应用与疑问

在《thinking in JAVA》第六章 访问控制权限 中，说到了package的用法。对于解决像System.out.print这种冗长的输出格式，也不失为一种好的解决办法。但是建立自己的类库，代码的可移植性也就要差点了。当然这个package也是鼓捣了好一阵才弄明白怎么用，囧

首先涉及到classpath的设置。安装JDK的时候会有设置classpath这一步。比如，classpath中存在“%java_home%\lib;"

import access.test.*
就会在classpath下寻找access]test 这个目录中的java源文件和class文件（也就是%java_home%\lib\access\test\ 这个目录）

个人感觉，import 和C++中的 using namespace 比较类似，反而不是属于include那一类。简单的说就是命名空间的划分引用。

也就是说，一般在类库中的文件，源代码开头（除注释）都是package 语句，用以将该java文件和class文件划分在指定的命名空间中。调用的时候就通过import语句导出。也就是说类库中java源文件中的package路径就是文件本身的路径?

其实一开始让我疑惑的是，一般我们会
import java.util.*
但是在我的classpath
.;%JAVA_HOME%\lib;%JAVA_HOME%\lib\dt.jar;%JAVA_HOME%\lib\tools.jar
搜寻路径中，没有java这个目录，而java\util\ 这个目录实际上存在于%JAVA_HOME%\src.zip 这个文件中打包保存。这个怎么解释呢？应该是JAVA路径支持压缩包

比如：
CLASSPATH：也指定一个路径列表，是用于搜索 Java 编译或者运行时需要用到的类。在 CLASSPATH 列表中除了可以包含路径外，还可以包含 .jar 文件。Java 查找类时会把这个 .jar 文件当作一个目录来进行查找。通常，我们需要把 JDK 安装路径下的 jre/lib/rt.jar (Linux: jre/lib/rt.jar) 包含在 CLASSPATH 中。

POJ 2247 humble number (DP)

这题第一感觉就是筛数法，可能是受前几天刚做的那题影响了。。。其实思路也没有太大问题，小数据的话还是可以的（虽然没优化过 = =）结果没想到题目的数据太大，堆溢出了 = =！所以就只好换一种思路吧。。。。
这题和ugly number 那题想法是可以完全一样的，还算蛮清晰，就是输出那里比较变态，估计坑了不少人。。。
网上看到有链表的做法，感觉上比这个要繁琐了，其实就是经典动规题。
核心思路就是用2,3,5,7和humble list中的数相乘，得出的数依然在list之内。
假设humble number集合开始只有{1}
2,3,5,7分别从集合中由小到大取数相乘后，
即2 * 1,3 * 1,5 * 1,7 * 1，min = 2，入队列{1,2}。
然后比较2 * 2,3 * 1，5 * 1,7 * 1，min = 3，入队列{1,2,3}。
.....


#include<cstdio>
int humble[6000];
int main(){
int t2,t3,t5,t7,p2,p3,p5,p7,i,min;
p2 = p3 = p5 = p7 = 1;
humble[1] = 1;
for(i = 1;i < 5843;i ++){
t2 = humble[p2] * 2;
t3 = humble[p3] * 3;
t5 = humble[p5] * 5;
t7 = humble[p7] * 7;
min = t2 < t3 ? t2 : t3;
min = min < t5 ? min : t5;
min = min < t7 ? min : t7;
humble[i+1] = min;
if(min == t2)p2 ++;
if(min == t3)p3 ++;
if(min == t5)p5 ++;
if(min == t7)p7 ++;
}
while(scanf("%d",&i) && i){
if(i % 10 == 1){
if(i % 100 == 11)printf("The %dth humble number is %d.\n",i,humble[i]);
else printf("The %dst humble number is %d.\n",i,humble[i]);
continue;
}
if(i % 10 == 2){
if(i % 100 == 12)printf("The %dth humble number is %d.\n",i,humble[i]);
else printf("The %dnd humble number is %d.\n",i,humble[i]);
continue;
}
if(i % 10 == 3){
if(i % 100 == 13)printf("The %dth humble number is %d.\n",i,humble[i]);
else printf("The %drd humble number is %d.\n",i,humble[i]);
continue;
}
else printf("The %dth humble number is %d.\n",i,humble[i]);
}
return 0;
}