poj1426--Find The Multiple(广搜,智商题)
-- The Find multiple 智商
2023-09-11 14:20:43 时间
Find The Multiple
Time Limit: 1000MS | Memory Limit: 10000K | |||
Total Submissions: 18527 | Accepted: 7490 | Special Judge |
Description
Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding
m containing no more than 100 decimal digits.
Input
The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.
Output
For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any
one of them is acceptable.
Sample Input
2 6 19 0
Sample Output
10 100100100100100100 111111111111111111
在广搜的题中看到这一个,表示根本想不到广搜,,,,,
每一位仅仅能是0或1,那么求n的倍数。从第一位開始搜。一直找到为止。
第一位一定是1,然后存余数temp,假设下一位是1。那么(temp*10+1)%n得到新的余数。假设是0,那么(temp*10)%n得到余数。这样进行广搜。大小是2^100
剪枝的方法:对于每个求的余数,最多有200个,每个仅仅要出现过一次就好了,出现多的减掉
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; struct node{ int k , temp ; int last ; }p[1000000] , q ; int flag[210] , a[120] , n ; int bfs() { int low = 0 , high = 0 ; p[high].k = 1 ; p[high].temp = p[high].k % n ; flag[p[high].temp] = 1 ; p[high++].last = -1 ; while( low < high ) { q = p[low++] ; if( q.temp == 0 ) return low-1 ; if( !flag[ (q.temp*10+1)%n ] ) { p[high].k = 1 ; p[high].temp = (q.temp*10+1)%n; flag[ p[high].temp ] = 1 ; p[high++].last = low-1 ; } if( !flag[ (q.temp*10)%n ] ) { p[high].k = 0 ; p[high].temp = (q.temp*10)%n ; flag[ p[high].temp ] = 1 ; p[high++].last = low-1 ; } } return -1 ; } int main() { int i , j ; while(scanf("%d", &n) && n) { memset(flag,0,sizeof(flag)); i = 0 ; j = bfs(); while( j != -1 ) { a[i++] = p[j].k ; j = p[j].last ; } for(j = i-1 ; j >= 0 ; j--) printf("%d", a[j]); printf("\n"); } return 0; }
相关文章
- 第一百三十节,JavaScript,封装库--连缀
- android--listview设置高度
- python后端面试第四部分:django框架--长期维护
- 第1章 1.8计算机网络概述--OSI参考模型和网络排错
- [Express] Level 5: Route Instance -- refactor the code
- The total number of locks exceeds the lock table size错误(已纠正)
- The nodes should be added to the underlying vendor clusterware before adding them to the CRS cluster
- C++设计模式7--外观模式--The Client don't want to know
- Error: Connection lost: The server closed the connection
- 编写高质量代码:改善Java程序的151个建议 --[0~25]
- 第1章 1.2计算机网络概述--Intenet和广域网
- [Angular HTML] Implementing The Input Mask Cursor Navigation Functionality -- setSelectionRange
- [AngularJS] Transclude -- using what existing in DOM to replace the template elements in directive
- Unexpected XML declaration. The XML declaration must be the first node in the document and no white
- 解决The type or namespace name 'XXXX' does not exist in the namespace 'XXXXXXXXX' 的错误
- Atitit 数据库的事件机制--触发器与定时任务attilax总结
- Atitit.软件开发概念(11)--网络子系统--url编码 空格问题URLEncoder java js php
- 判断滚动条距离顶部为0执行事件jq--滚动到顶部的距离
- The difference between the request time and the current time is too large.阿里云oss上传图片报错
- The Light --CHPTRS
- chroumium electron apply_all_patches.py patch git error WindowsError: [Error 2] The system cannot find the file specified
- 【问题解决】The connection to the server localhost:8080 was refused
- Ignatius and the Princess III --undo
- DB2 “The transaction log for the database is full” 存在的问题及解决方案
- 服务发现--初识Consul
- The Django Book 2.0--中文版
- MySQL----JDBC无法连接数据库,报The driver has not received any packets from the server的解决办法
- ERROR 1290 (HY000): The MySQL server is running with the --secure-file-priv option so it cannot ···
- 存在隐患 : 3 racks are required for the erasure coding policies: RS-6-3-1024k. The number of racks is on
- (六)Jenkins部署项目报错The username you provided is not allowed to use the text-based Tomcat Manager (error
- RHCE之路--04使用 RHEL 系统角色-02