题目链接：http://poj.org/problem?id=3507
简单题，六个分数去掉一个最高分，去掉一个最低分，然后取平均值，然而这题的难点在于输出要求：
(without unnecessary decimal points and/or zeros.)
也就是输出浮点数，但不输出多余的0，其实要是用printf输出，我觉得很麻烦，还要判断这那的，不过C++中cout对浮点的输出会自动优化这些，嘿嘿，又偷懒了！
代码如下：
1 | /*Problem: 3507 User: awq123 |
题目链接：http://poj.org/problem?id=3438
题目是一种压缩算法，比如11111是5个1就写成51，222333是3个2和3个3写成3233。依次类推。利用计数记录下相连的数的个数，当不连续的时候输出，不过这个题我的方法，循环完后还要输出漏掉的一次！
代码如下：
1 | /*Problem: 3438 User: awq123 |
题目链接：http://poj.org/problem?id=3325
题目很简单，去掉一个最高分，去掉一个最低分，求平均分，小日本的题目还是很简单的！
1 | /*Problem: 3325 User: awq123 |
题目链接：http://poj.org/problem?id=2181
题目给你一些数，让你找出一个子序列，子序列计算的规则是：奇数位相加偶数位相减。要求这个子序列计算的值最大为多少！
也就是总数+奇数位-偶数位的子串；
先开始没什么思路，查阅了下解体报告，发现，我们只要找比相邻都高的数为奇数位，比相邻都底的数做偶数位就可能得到最大的值！
代码如下
1 | /*Problem: 2181 User: awq123 |
题目链接：http://poj.org/problem?id=1958
题目是一个变相的汉诺塔，问4个塔至少移动多少步！
先开始没看题以为就是普通汉诺塔，然后WA了半天才发现，本来汉诺塔我们可以套用公式，但4塔的我就没办法了！多塔问题，参考了维基百科
其中这样描述的：
令f(n,k)为在有k个柱子时，移动n个圆盘到另一柱子上需要的步数，则：
对于任何移动方法，必定会先将m(1<=m<=n-1)个圆盘移动到一个中间柱子上，再将第n到第n-m个圆盘通过剩下的k-1个柱子移到目标柱子上，最后将m个在中间柱子上的圆盘移动到目标柱子上。这样所需的操作步数为2f(m,k) + f(n − m,k − 1)。
进行最优化，易得: 
这个递归公式适用于大于3的所有情况，但是我们只考虑4的情况，也就修改了下，具体见代码！
代码如下：
1 | /*Problem: 1958 User: awq123 |
题目链接：http://poj.org/problem?id=1579
题目没什么好说的，给出了递归算法，但是单纯模拟题意，你会发现递归过多，严重超时。这里我们利用DP里的记忆搜索，开一个数组记录已经求出的值，减少递归的计算次数，单纯优化运行速度，对于这样的题OJ系统的数据是不可想象的，就算你的能运行，在OJ系统里的数据也过不了！
代码如下：
1 | /*Problem: 1579 User: awq123 |
题目链接：http://poj.org/problem?id=3302
解释下题目，问是否能在一个字符串正顺序，或者逆顺序中，删除一些字母组成另一个字符串。
注意：正序是以’\0’逆序则要以第一个字母的前面一位结束
代码如下：
1 | /*Problem: 3302 User: awq123 |
题目链接：http://poj.org/problem?id=3219
题意简单，求C(n，k)的奇偶性，
我的方法不简单，但分析简单，不过今天还看到个大神的分析，让我很是佩服
我门知道C(n，k)=n!/k!/(n-k)!那么就通过分析这三项的2的阶数来分析C(n，k)的2的阶数，也就是n!的阶数<=k!的阶数+(n-k)!阶数，则为奇数。
其中n!的2的阶数求解的方法为n/2+n/4+n/8….我就是用的这个方法，
1 | int y(int d) |
1 | int y(int d) |
::cpp
/*Problem: 3219 User: awq123
**Memory: 244K Time: 32MS
**Language: C++ Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int y(int d)
{
int s=0;
for(int i=2;d/i;i*=2)
s+=d/i;
return s;
}
int main()
{
int n,k;
while (cin>>n>>k)
{
if(k>n-k)
k=n-k;
if(y(n)<=y(n-k)+y(k))
cout<<1<<endl;
else
cout<<0<<endl;
}
}
这个题还见到了一种大神的做法
1 |
|
题目链接：http://poj.org/problem?id=1006
解释下题意，Snoopy想问下，若有n枚硬币，这n枚硬币的初始状态是任意的，则至少需要翻转几次，才能保证对于任何一种初始状态而言，都能变成n枚硬币全为正或全为反。
分析：
1：若为偶数
那么正反数目就有奇奇和偶偶两种情况，很明显奇数的翻转不适合偶数，偶数的翻转不适合奇数
例如： ○○●●●● 则翻转 2,4,6,8……次均可。
例如： ○○○○○● 则翻转 1,3（先将●翻为○，再将任一个○翻两下）,5,7……次均可。
2：若为奇数
若所有硬币一开始就同一面向上那么翻转次数一定为偶数，那么对于其他情况，我们必须翻转偶数面来完成目标
例如： ○○○○●●● 则翻转4,6,8,10……次均可，其中最小为4。要保证对7枚硬币的任意初始状态都可行，则最小应为 7-1=6
这样我们就能推出，至少应该翻转n-1次
代码如下：
1 | /*Problem: 3210 User: awq123 |
题目链接：http://poj.org/problem?id=2386
题目问，一共有几块池塘，8方向相连就算一块！
简单DFS，我用used数组记录每一块，若发现新的一块就编号，然后从这个点开始8方向深搜，有相连还没编号的一起编上号，看左后一共编了几个号！
代码如下：
1 | /*Problem: 2386 User: awq123 |