Question

Float Point Error,题目见http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1961

我的解答如下：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
using namespace std;
// 用于存储stack[i]中从下标x到y的和的结构，i = 1，2，3...n
typedef struct {
long x;
long y;
long value;
} Sum;
// 题目所规定的栈数的上限
const int maxNumber = 1000;
// 用于存储每个栈的大小，为了方便从1开始使用，故多申请了一个
long stackSize[maxNumber+1];
// 采用分离链接法的哈希表，存储在递归过程中所计算的stack[i]从下标x到y的和，以缩
// 短计算时间，栈序号直接作为哈希表的存储位置
list<Sum> solveCache[maxNumber+1];
// 递归解决，即要计算stack[n]中从x到y的和，则计算stack[n-1]中从x对应位置nx到y对应
// 位置ny的和，依次类推，同时将每次的计算结果保存在哈希表中以防止重复计算，从而
// 加快计算速度
static long solve(long x, long y, int n);
int main(void)
{
int number;
long x, y;
// 输入栈的数目
scanf("%d", &number);
while (number) {
// 在计算开始前将用于存储栈大小的数组以及哈希表清空
memset(stackSize, 0, sizeof(stackSize));
for (int i = 1; i <= number; i++)
solveCache[i].clear();
// 输入每个栈的大小
for (int i = 1; i <= number; i++)
scanf("%ld", &stackSize[i]);
// 输入所求和的下标
scanf("%ld%ld", &x, &y);
// 调用solve函数递归进行求解
printf("%ld\n", solve(x, y, number));
// 输入下一组数据
scanf("%d", &number);
}
}
static long solve(long x, long y, int n)
{
// 如果所求问题已被计算过，则直接从哈希表中读取计算结果
list<Sum>::iterator cur = solveCache[n].begin();
while (cur != solveCache[n].end()) {
if (cur->x == x && cur->y == y)
return cur->value;
cur++;
}
// 如果未被计算过，则分情况进行计算
// 如果在stack[1]中求和，则直接进行计算即可
if (n == 1) {
Sum sum = {x, y, (x+y)*(y-x+1)/2};
solveCache[n].push_back(sum);
return sum.value;
}

// 如果栈序号大于1，则计算下标x、y在前一个栈中所对应的下标nx、ny
// 根据y - x 是否等于nx - ny来分别进行计算
long nx, ny;
// count the responsing index nx, ny in stack n-1
if (x % stackSize[n-1] == 0)
nx = 1;
else
nx = stackSize[n-1] - x % stackSize[n-1] + 1;
if (y % stackSize[n-1] == 0)
ny = 1;
else
ny = stackSize[n-1] - y % stackSize[n-1] + 1;

if (y - x == nx - ny) {
Sum sum = {x, y, solve(ny, nx, n-1)};
solveCache[n].push_back(sum);
return sum.value;
}
else {
if (y - x + 1 > stackSize[n-1] - (ny - nx) + 1) {
Sum sum;
sum.x = x;
sum.y = y;
sum.value = solve(1, nx, n-1) + solve(ny, stackSize[n-1], n-1)
+ solve(1, stackSize[n-1], n-1) * ((y - x + 1) / stackSize[n-1]);
solveCache[n].push_back(sum);
return sum.value;
}
else {
Sum sum = {x, y, solve(1, nx, n-1) + solve(ny, stackSize[n-1], n-1)};
solveCache[n].push_back(sum);
return sum.value;
}
}
}

Answer 1

【分析】
/*
根据Polya定理,这道题可以按照如下思路进行求解:
第一:找出可以对正多边形采取的旋转或者翻转方案(即对多边形顶点的置换),
以这些方案作为元素构成一个置换群;
第二:对置换群中的每个元素,即某一个特定的置换,找到其循环数;
第三:根据Polya定理进行计算.对于有s个顶点的正多边形,共有2s种置换
其中s种为旋转,s种为翻转
旋转部分:
第i种旋转为在原多边形的基础上旋转i格,
该置换的循环数为gcd(s,i),i=0,1,...,n-1
翻转部分:
对于正(2k)边形,有一半置换是有k个2-循环,
另一半置换是有2个1-循环,k-1个2-循环;
对于正(2k+1)边形,每个置换都是有1个1-循环,k个2-循环
其中"i-循环"
表示循环节的长度为i
*/

【C/C++源代码】
#include<cstdio>
#include<cmath>
int
gcd(int a,int b)
{
int c;
if(a<b)
{

c=a;a=b;b=c;
}
if(a%b==0) return b;
else return
gcd(b,a%b);
}
int main()
{
int c,s,i,j,t,x;

while(scanf("%d%d",&c,&s)&&c+s!=0)
{

t=(int)pow(double(c),double(s));
for(i=1;i<s;i++)

{
x=gcd(s,i);

t+=(int)pow(double(c),double(x));
}
if(s%2==0)
{
j=s/2;

t+=j*(int)pow(double(c),double(j))*(c+1);
}

else
{
j=s/2;

t+=s*(int)pow(double(c),double(j+1));
}

printf("%d\n",t/(2*s));
}
return 0;
}

追问

怎么感觉你说的题目和我说的不是一个呢, 我说的是浙大acm上面编号2962 StackByStack那道....，在提交程序后，老是出现Float Point Error, 貌似是数据超出表示范围什么的