首页 > USACO题解 > USACO Your Ride Is Here

USACO Your Ride Is Here

Your Ride Is Here是USACO第一题,很简单,没有trick,没有算法。但是题目给的分析将功能部分写入了一个Hash函数之中。由于本人数学基础太差,刚开始没有太明白,后来简单推理了一下,发现了其中的小技巧。

对于求多个数的乘积然后对某一个数取余,分析中的方法显得更为安全一点(如果先算出所有乘积,有可能会溢出。当然,本题条件下不会溢出,所以说没有trick)。下面是一个简单的分析过程:

①(a + b) % c = (a % c + b % c) % c

②a = a%c + a/c*c

③n * c % c = 0

可知a * b % c = (a%c + a/c*c) * b % c = (a%c * b + a/c*c * b)  % c

①可知 (a%c * b + a/c*c * b)  % c = (a%c * b %c + a/c*c * b % c)  % c

③可知(a%c * b %c + a/c*c * b % c)  % c = ((a % c) * b) % c

USACO提供的分析代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <ctype.h>
 
int hash(char *s)
{
	int i, h;
 
	h = 1;
	for(i=0; s[i] && isalpha(s[i]); i++)
		h = ((s[i]-'A'+1)*h) % 47;
	return h;
}
 
void main(void)
{
	FILE *in, *out;
	char comet[100], group[100];
 
	in = fopen("input.txt", "r");
	out = fopen("output.txt", "w");
 
	fgets(comet, sizeof comet, in);
	fgets(group, sizeof group, in);
 
	if(hash(comet) == hash(group))
		fprintf(out, "GO\n");
	else
		fprintf(out, "STAY\n");
	exit (0);
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> USACO Your Ride Is Here
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



分类: USACO题解 标签: , , ,
  1. endless
    2012年4月14日15:12 | #1

    最后一个步骤没看懂。。。(a%c * b %c + a/c*c * b % c) % c = (a%c * b%c) % c ?= ((a % c) * b) % c

    [回复]

    代码疯子 回复:

    @endless,

    (a%c * b%c) % c

    equals to

    a%c * b%c

    , then add some parenthese to this expression, that’s just

    ((a % c) * b) % c

    [回复]

  2. endless
    2012年5月4日16:43 | #2

    我一开始以为%的优先级会大于*来着-_-

    还有一种证明也可以参考下(数学不好,轻拍。。。 [em002] )

    求证:(a*b*c*d*…) % n = ((a%n)*b*c*d*…) % n

    证明:设a = k*n + x,则x = a%n。(a*b*c*d*…) % n = ((k*n + x)*b*c*d*…) % n = ((k*n*b*c*d*…) + (x*b*c*d*…)) % n

    根据:(a + b) % n = (a%n + b%n) % n,上式变为:

    ((k*n*b*c*d*…)%n + (x*b*c*d*…)%n) % n = (x*b*c*d*…) % n = ((a%n)*b*c*d*…) % n

    [回复]

  3. keon
    2012年9月5日01:06 | #3

    不知道hash這東西, 簡單不是很好嗎?

    #include
    #include
    using namespace std;

    int main()
    {
    string a, b;
    cin >> a;
    cin >> b;
    int a_sum = 0;
    int b_sum = 0;

    for (int i = 0; i < a.length(); i++)
    a_sum += a[i] – 64;

    for (int i = 0; i < b.length(); i++)
    b_sum += b[i] – 64;

    if (a_sum % 47 == b_sum % 47)
    cout << "GO" << endl;
    else
    cout << "STAY" << endl;

    return 0;
    }

    [回复]

    ace 回复:

    @keon, 要求的sum是乘法,作者说的很清楚了,int型变量可能导致溢出

    [回复]

  1. 本文目前尚无任何 trackbacks 和 pingbacks.