题目名称 | 1303. [HAOI 2012初中]01数字 |
---|---|
输入输出 | torch.in/out |
难度等级 | ★★ |
时间限制 | 1000 ms (1 s) |
内存限制 | 128 MiB |
测试数据 | 10 |
题目来源 | sywgz 于2013-03-08加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:132, 提交:160, 通过率:82.5% | ||||
合金装备布狼牙 | 100 | 0.000 s | 0.00 MiB | C++ |
乐未殇 | 100 | 0.000 s | 0.00 MiB | C++ |
Apocana-Wisbtsml | 100 | 0.000 s | 0.00 MiB | C++ |
1020 | 100 | 0.000 s | 0.00 MiB | C++ |
sudv | 100 | 0.000 s | 0.00 MiB | C++ |
yrtiop | 100 | 0.000 s | 0.00 MiB | C++ |
䱖虁職 | 100 | 0.000 s | 0.00 MiB | C++ |
lihaoze | 100 | 0.000 s | 0.00 MiB | C++ |
op_组撒头屯 | 100 | 0.000 s | 0.00 MiB | C++ |
HeSn | 100 | 0.000 s | 0.00 MiB | C++ |
本题关联比赛 | |||
20130802初中 | |||
2009noip模拟试卷 |
关于 01数字 的近10条评论(全部评论) | ||||
---|---|---|---|---|
好吧,一开始的做法不太对,不过关于这一题,有一个非常巧妙的方法证明答案 $m$ 一定存在。
设一个序列 $f(n) = 1, 11, 111, 1111, 11111 ...$,易知序列中任意两个数做差的结果只由 $1, 0$构成,又因为任意一个正整数 $mod n $ 的值一定不会超过 $n$ ,因此,根据鸽笼原理,一定存在两个数 $x, y \in f(n)$,使得这两个数对 $n$ 取模的值相等,对这两个数做差,得到的数就是 $n$ 的倍数,除以 $n$ 之后,就得到一个数 $m$ 满足条件,不过这个方法求出来的不一定是最小值,实测只能过 $4$ 个点。不过由于这一题的数据规模不大,所以暴力也能很好的求解。这一巧妙的证明方法我是在 matrix67 大佬的 Blog 中了解到的,其中有很多巧妙的证明,推荐去看看 | ||||
#include <iostream>
#include<cstdio> using namespace std; int main() { freopen("torch.in","r",stdin); freopen("torch.out","w",stdout); int n,t=1,tt,a; cin>>n; for(;;) {tt=t*n; for(;;) {a=tt%10; if(a>1) {tt=t*n;break;} tt=tt/10; if(tt==0) break;} if(tt==0) {cout<<t;break;} t++;} return 0; } 渣程序仅供参考。。。。。。 tmd读错题了,以为m也必须是由0,1组成的,调试了20+min。。。。。。
ShallowDream雨梨
2017-11-13 21:18
9楼
| ||||
我能怎么办。。。枚举256比枚举30000还慢
| ||||
水
| ||||
嗯,这题真的可以说难度不大,怪不得是“初一必过”。
| ||||
水题水题水题水题
这都一颗星???不应该空心吗? | ||||
| ||||
这题·················不能懒省事啊!!!!
此题有Bug,@ Letter zZZz 你代码中的Bug已纠正 | ||||
这速度有点快的说(我的代码有漏洞的说)
| ||||
喵喵……
|