2022.10.8每日刷题打卡
假期结束开始正常打卡
Find The
题目描述：给一个数，输出这个数的倍数且这个数是一个只有0和1组成的数。
首先想到的就是暴力但是没过qwq，题目时间限制1s暴力绝对会TLE,那么怎么去思考呢，想暴力就得优化，怎么优化呢，我们知道我们遍历的数一定是只有0和1构成的那么我们只遍历0和1就好了，那就是从1开始*10或*10+1就可以做到只遍历01数。传统的for不能很好地调控*10或*10+1，所以选择bfs去通过入队进队来遍历，很nice！
#include
#include
#include
#include
#include
#include
#include
#include
#define int long longint bfs(int x){std::queue q;q.push(1);while(!q.empty()){int t = q.front();q.pop();if(t % x == 0){return t;}q.push(t * 10);q.push(t * 10 + 1);}return -1;
}signed main()
{std::ios_base::sync_with_stdio(false);std::cin.tie(0);int x;while(std::cin >> x, x != 0){std::cout << bfs(x) << "\n";}return 0;
}
更快的做法把打出的表，填到excel表，O(1)就能过。
#include
long long a[300] = {0, 1, 10, 111, 100, 10, 1110, 1001, 1000, 111111111, 10, 11, 11100, 1001, 10010, 1110, 10000, 11101, 1111111110, 11001, 100, 10101, 110, 110101, 111000, 100, 10010, 1101111111, 100100, 1101101, 1110, 111011, 100000, 111111, 111010, 10010, 11111111100, 111, 110010, 10101, 1000, 11111, 101010, 1101101, 1100, 1111111110, 1101010, 10011, 1110000, 1100001, 100, 100011, 100100, 100011, 11011111110, 110, 1001000, 11001, 11011010, 11011111, 11100, 100101, 1110110, 1111011111, 1000000, 10010, 1111110, 1101011, 1110100, 10000101, 10010, 10011, 111111111000, 10001, 1110, 11100, 1100100, 1001, 101010, 10010011, 10000, 1111111101, 111110, 101011, 1010100, 111010, 11011010, 11010111, 11000, 11010101, 1111111110, 1001, 11010100, 10000011, 100110, 110010, 11100000, 11100001, 11000010, 111111111111111111, 100, 101, 1000110, 11100001, 1001000, 101010, 1000110, 100010011, 110111111100, 1001010111, 110, 111, 10010000, 1011011, 110010, 1101010, 110110100, 10101111111, 110111110, 100111011, 111000, 11011, 1001010, 10001100111, 11101100, 1000, 11110111110, 11010011, 10000000, 100100001, 10010, 101001, 11111100, 11101111, 11010110, 11011111110, 11101000, 10001, 100001010, 110110101, 100100, 10011, 100110, 1001, 1111111110000, 11011010, 100010, 1100001, 11100, 110111, 11100, 1110001, 11001000, 10111110111, 10010, 1110110, 1010100, 10101101011, 100100110, 100011, 100000, 11101111, 11111111010, 1010111, 1111100, 1111110, 1010110, 11111011, 10101000, 10111101, 111010, 1111011111, 110110100, 1011001101, 110101110, 100100, 110000, 100101111, 110101010, 11010111, 11111111100, 1001111, 10010, 100101, 110101000, 1110, 100000110, 1001011, 1001100, 1010111010111, 110010, 11101111, 111000000, 11001, 111000010, 101010, 110000100, 1101000101, 1111111111111111110, 111000011, 1000};int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);long long n;while (std::cin >> n && n != 0) {std::cout << a[n] << "\n";}return 0;
}
