[HDU][ACM]1104 Remainder
海胖子 - 2014/08/04题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1104
题解:
又是一道数论宽搜题,因为栽到BFS的一个逻辑坑里,所以发一篇加深印象。
注意题目中的%是指mod,开始给了你n, k, m。每次由+m, -m, *m, mod m得到新的N,继续对N这样的操作,直到(n+1) mod k== N mod k时结束,并且打印路径。
%与mod的区别:
%出来的数有正有负,符号取决于左操作数。
mod只能是正(a = b*q + r (q > 0 and 0 <= r < q), then we have a mod q = r 中r要大于等于0小于q)。
所以要用%来计算mod的话就要用这样的公式:a mod b = (a % b + b) % b括号里的目的是把左操作数转成正数由于新的N可以很大,所以我们每一步都要取%,而且最后要mod k,正常来说每步都%k就行了,但是由于其中的一个操作是N%m,所以我们每一步就不能%k了(%k%m混用会导致%出来的答案错误),而要%(k *m)(其实%(k,m的公倍数都行))。
然后,vis[这里放的要是遍历的点mod k (想清楚标记的目的是避免结果重复)]而那四个操作避免过大则取余就可以了,而不需要取mod记录路径。
因为题目没有一开始就等于结果的数据,所以我的程序中不是直接Q.push(s)开始,而是PUSH所有s的下一个节点,避免PRINT输出的时候陷入死循环。
/* * Author: Haipz * School: HDU * File Name: 1104.cpp */ #include <cstdio> #include <cmath> #include <ctime> #include <cctype> #include <cfloat> #include <cstdlib> #include <cstring> #include <climits> #include <iostream> #include <vector> #include <string> #include <stack> #include <queue> #include <set> #include <map> #include <algorithm> using namespace std; queue<int> Q; int pre[1000000], cur[1000000], cnt[1000000]; void PRINT(int x) { if (pre[x] != -1) PRINT(pre[x]); switch (cur[x]) { case 1: printf("+"); break; case 2: printf("-"); break; case 3: printf("*"); break; case 4: printf("%%"); break; } return; } int mode(int t, int i, int m, int MOD) { switch (i) { case 1: return ((t + m) % MOD + MOD) % MOD; case 2: return ((t - m) % MOD + MOD) % MOD; case 3: return ((t * m) % MOD + MOD) % MOD; case 4: return (t % m + m) % m % MOD; } return 0; } void bfs(int s, int k, int m, int MOD) { int goal = ((s + 1) % k + k) % k; s = (s % MOD + MOD) % MOD; while (!Q.empty()) Q.pop(); memset(pre, -1, sizeof(pre)); memset(cur, 0, sizeof(cur)); memset(cnt, 0, sizeof(cnt)); for (int i = 1; i <= 4; ++i) { int v = mode(s, i, m, MOD); if (cur[v] == 0) { Q.push(v); pre[v] = -1, cnt[v] = 1, cur[v] = i; } } while (!Q.empty()) { int u = Q.front(); Q.pop(); if ((u % k + k) % k == goal) { printf("%d\n", cnt[u]); if (cnt[u]) { PRINT(u); printf("\n"); return; } } for (int i = 1; i <= 4; ++i) { int v = mode(u, i, m, MOD); if (cur[v] == 0) { Q.push(v); pre[v] = u, cnt[v] = cnt[u] + 1, cur[v] = i; } } } printf("0\n"); return; } int main() { int n, k, m; while (scanf("%d%d%d", &n, &k, &m), n || k || m) { bfs(n, k, m, k*m); } return 0; }
转载保留版权:http://haipz.com/blog/i/5557 - 海胖博客