首页 > 代码库 > hdu1104Remainder

hdu1104Remainder

2024-07-05 00:50:37   226人阅读

题意：对于n,m,k,定义n的操作，+m,-m,*m,%m,(You should know that if a = b * q + r (q > 0 and 0 <= r < q), then we have a % q = r.),问是否可以经过一系列的操作，使“[(the initial value of N) + 1] % K” is equal to “(the current value of N) % K”。

解题思路：http://acm.hdu.edu.cn/discuss/problem/post/reply.php?action=support&postid=17414&messageid=1&deep=0

              http://www.cnblogs.com/qiufeihai/archive/2012/08/28/2660272.html

bfs。要注意的是：由于操作会让中间的结果很大，所以中间的过程都要取模。但是操作中有个n%m,所以不能一直%k.例如：

 记n = 2, m = 8, k =3.
   则((n * m)%k % m)%k = 1
   而(n * m % m)%k = 0。
n%m%k=n%(mk)%k.所以中间过程我们只要%（mk）就好了。
还一个就是无解情况的判断：我们可以标记每个状态，如果所有状态都搜索过了，还没有得到结果，则无解！

 1 //Accepted 109MS 4208K 
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <string>
 6 #include <queue>
 7 using namespace std;
 8 queue<int >q;
 9 queue<string> sq;
10 int n,k,m;
11 int ans;
12 int vis[1000005];
13 int getpp(int nn)
14 {
15     int visd=nn%(k*m);
16     if (visd<0) visd+=m*k;
17     return visd;
18 }
19 void bfs()
20 {
21     int visd;
22     memset(vis,0,sizeof(vis));
23     while (!q.empty()) q.pop();
24     while (!sq.empty()) sq.pop();
25     visd=getpp(n);
26     q.push(visd);
27     sq.push("");
28     vis[visd]=1;
29     while (!q.empty())
30     {
31         int nn=q.front();
32         q.pop();
33         string ss=sq.front();
34         sq.pop();
35         if ((nn%k+k)%k==ans)
36         {
37             printf("%d\n",ss.length());
38             cout<<ss<<endl;
39             return ;
40         }
41         int nw=(nn+m);
42         nw=getpp(nw);
43         string ns=ss+"+";
44         if (!vis[nw])
45         {
46             q.push(nw);
47             sq.push(ns);
48             vis[nw]=1;
49         }
50         nw=(nn-m);
51         nw=getpp(nw);
52         ns=ss+"-";
53         if (!vis[nw])
54         {
55             q.push(nw);
56             sq.push(ns);
57             vis[nw]=1;
58         }
59         nw=nn*m;
60         nw=getpp(nw);
61         ns=ss+"*";
62         if (!vis[nw])
63         {
64             q.push(nw);
65             sq.push(ns);
66             vis[nw]=1;
67         }
68         nw=nn%m;
69         if (nw<0) nw+=m;
70         nw=getpp(nw);
71         ns=ss+"%";
72         if (!vis[nw])
73         {
74             q.push(nw);
75             sq.push(ns);
76             vis[nw]=1;
77         }
78     }
79     printf("%d\n",0);
80 }
81 int main()
82 {
83     while (scanf("%d%d%d",&n,&k,&m) && !(n==0 && k==0 && m==0))
84     {
85         ans=(n+1)%k;
86         if (ans<0) ans+=k;
87         bfs();
88     }
89     return 0;
90 }
View Code

 

 


联系
我们