九月 2008

由 Jianing Yang 于星期六, 2008-09-27 09:33 发表

top=$(dirname -- $(readlink -f -- "$0"))

Tags:

bash

中国余数定理与POJ 1006

由 Jianing Yang 于星期一, 2008-09-22 13:01 发表

“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？” 这道《孙子算经》中的例题是小学或者初中数学竞赛里常见的同余问题。想当年自己解这类问题多是凑数凑出来的，而并不得其法。因此也经常焦头烂额。昨天看到 POJ 1006 ，突然又心血来潮想探寻一下这类问题是否有标准的解法。

浏览于Wikipedia之中，发现了几篇很好的文章：

Modular Arithmetic
Linear Congruence Theorem
Chinese Remainder Theorem

这里以“POJ 1006”:http://acm.pku.edu.cn/JudgeOnline/problem?id=1006 为例演示一下这个计算过程：

“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知”

推导过程见附件

#include <stdio.h>

int main()
{
	int x, p, e, i ,d, k, n = 0, r[1024];

	do {
		scanf("%d%d%d%d", &p, &e, &i, &d);
		if (p == -1 && e == -1 && i == -1 && d == -1) break;
		p = p % 23;
		e = e % 28;
		i = i % 33;
		/* x = 21252 * k - 504504 * p + 503217 * e + 1288 * i; */
		x = (21252  + 5544 * p + 14421 * e + 1288 * i - d) % 21252;
		r[n++] = (x == 0)?21252:x;
	} while (1);

	for (i = 0; i < n; i++) {
		printf("Case %d: the next triple peak occurs in %d days.\n", i + 1, r[i]);
	}
}

附件:

POJ-1006演算过程

Tags:

acm
数学

ACM POJ 1050 To The Max Solution 解题简介

由 Jianing Yang 于星期四, 2008-09-18 22:54 发表

问题原文： http://acm.pku.edu.cn/JudgeOnline/problem?id=1050

自己想了很久没能想出来，主要卡在如何用 DP 求一个二维关系上。后来百度了一下，找到了解法。

首先需要一个三维数组，_score[i][j][k]。意思是，从第i行到第j行所有第k列元素的和保存在_score[i][j][k]里面。这个数组做好以后我们把所有纵向的可能都枚举出来了。之后对于横向部分做一维的 DP .然后找出最大和。这应该就是传说中的最大子段问题吧。

我的解法如下：

#include <stdio.h>
#include <limits.h>

#define SIDE 100

int main()
{
  int i, j, k, s, max, side, _score[SIDE * SIDE * SIDE] = {0};
  int _matrix[SIDE * SIDE];

  scanf("%d", &side);

  for (i = 0; i < side; i++) {
    for (j = 0; j < side; j++) {
      scanf("%d", &s);
      _matrix[i * side + j] = s;
      _score[i * side * side + i * side + j] = _matrix[i * side + j];
    }
  }

  for (i = 0; i < side - 1; i++) {
    for (j = i + 1; j < side; j++) {
      for (k = 0; k < side; k++) {
        _score[i * side * side + j * side + k] =
          _score[i * side * side + (j - 1) * side + k] + _matrix[j * side + k];
      }
    }
  }
  max = INT_MIN;
  for (i = 0; i < side; i++) {
    for (j = i; j < side; j++) {
      s = INT_MIN;
      for (k = 0; k < side - 1; k++) {
        if (_score[i * side * side + j * side + k] > 0) {
          _score[i * side * side + j * side + k + 1] +=
            _score[i * side * side + j * side + k];
        }
        if (s < _score[i * side * side + j * side + k + 1])
          s = _score[i * side * side + j * side + k + 1];
      }
      if (max < s) max = s;
    }
  }

  printf("%d\n", max);
}