存档

2010年11月 的存档

USACO Barn Repair

2010年11月30日 5 条评论

贪心问题。首先可以按照stall的编号从小到大排序,然后计算每个stall编号之见的距离,再按照距离从大到小排序(也可以从小到大,反正排序就行了),然后找出M-1个最大的距离,这些都是分隔段,其他的stall都是应该被覆盖的。
比如,1 3 9,给一个board的话,肯定是全部覆盖;如果能给两个board,则是一个覆盖1,2,3;另一个覆盖9。题目大概就是这个意思:

/*
ID:stackex1
LANG:C
PROG:barn1
*/
#include <stdio.h>
[……]

继续阅读

分类: USACO题解 标签: ,

USACO Prime Cryptarithm

2010年11月30日 没有评论

先产生所有能的三位数和两位数,然后两层循环枚举所有可能的情况,判断是否符合条件即可。
/*
ID:stackex1
LANG:C
PROG:crypt1
*/
#include <stdio.h>

int checkok(int num, int digit[], int n)
{
int i;
if(!(num >= 100 && num <= 999))
return 0;
while(num)
{
[……]

继续阅读

分类: USACO题解 标签: ,

error:no type named iterator_category in struct

2010年11月29日 没有评论

又一个非常非常诡异的一个编译错误。当我第一次遇到这个错误的时候头都晕了。还是先把代码贴上来吧:
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

typedef struct TagPoint
{
int x, y;
}Point;

inline double distance(const Point& a, const [……]

继续阅读

分类: C++编程 标签: , ,

POJ 2420 A Star not a Tree? 多边形费马点

2010年11月29日 没有评论

POJ 2420 A Star not a Tree?实际上就是求平面内多边形的费马点问题,只不过这里要的不是点,而是最短距离。这里使用模拟退火的方法来逼近费马点。所谓费马点就是指满足这样条件的一个点:这个点到多边形所有定点的距离和最短。
平面上三角形的费马点有如下性质:

  1. 若三角形ABC的3个内角均小于120°,那么3条距离连线正好平分费马点所在的周角。
  2. 若三角形有一内角不小于120度,则此钝角的顶点就是距离和最小的点。

这次福州赛区考了个四边形的费马点,但是我们悲剧的卡在了Wron[……]

继续阅读

error C2723:’virtual’ storage-class specifier illegal

2010年11月28日 没有评论

错误全称:error C2723: 'funname' : 'virtual' storage-class specifier illegal on function definition。
错误原因:C++类头文件中使用了virtual声明静态方法,在Cpp源文件中定义该静态函数时再次使用了virtual修饰。
解决方案:Cpp源文件定义静态成员函数时不再需要virtual修饰。或者定义直接放在h头文件中。
在写简单工厂模式中遇到了这个问题,因为产品类要实现多态[……]

继续阅读

error C2724:’static’ should not be used on member functions

2010年11月28日 1 条评论

错误全称:error C2724 : 'funname' : 'static' should not be used on member functions defined at file scope。
错误原因:C++类头文件中使用了static声明静态方法,在Cpp源文件中定义该静态函数时再次使用了static修饰。
解决方案:Cpp源文件定义静态成员函数时不再需要static修饰。或者定义直接放在h头文件中。
在写简单工厂模式中遇到了这个问题,因为Facto[……]

继续阅读

USACO Calf Flac

2010年11月28日 2 条评论

USACO Calf Flac又是一个回文数问题。因为数据量不是非常大,所以这里采用暴力枚举。即枚举所有可能的中心节点,往后依次求得以此节点为中心节点的最大回文传长度。
这样做需要注意一个对称问题存在两种情况,如长度为奇数的AABBXBBAA;长度为偶数的AABBBBAA;两种情况都要考虑到。这样之后,只要简单处理一下字符串问题即可。
/*
ID:stackex1
LANG:C
PROG:calfflac
*/
#include <stdio.h>
#include[……]

继续阅读

USACO Mixing Milk

2010年11月28日 没有评论

USACO Mixing Milk简单的贪心问题,按照单价从小到大排序,然后对Farmers的牛奶一个一个的进行收购,知道已经买到了所有Milk。代码如下:
/*
ID:stackex1
LANG:C
PROG:milk
*/
#include <stdio.h>
#include <stdlib.h>

#define MAX_NUM 5010

typedef struct TagNode
{
int price;
int amou[……]

继续阅读

USACO Dual Palindromes

2010年11月28日 没有评论

USACO Dual Palindromes又是一个进制转换和回文数判断相关的题目,跟上一个题目“USACO Palindromic Squares”类似,可以重用一下上一个题目的代码:
/*
ID:stackex1
LANG:C
PROG:dualpal
*/
#include <stdio.h>
#include <string.h>

void num2str(int num, char *s, int base)
{[……]

继续阅读

USACO Palindromic Squares

2010年11月28日 没有评论

USACO Palindromic Squares属于回文数判断与进制转换问题。在Windows下有一个itoa函数,可以方便的将10进制数转换成2到36进制字符串,但是很遗憾GCC里面没有这个函数。于是就自己来写一个通用的转换函数吧。同样是通过一个map数组,可以方便的实现进制的转换,具体请参考下面代码中的num2str函数。
/*
ID:stackex1
LANG:C
PROG:palsquare
*/
#include <stdio.h>
#include &[……]

继续阅读