50 条题解
-
3
Fop_zz LV 10 @ 2017-06-06 08:10:50
这不是个BFS嘛。。一脸懵逼
先对输入的数字排序,就可以保证先生成出0的那个数字一定最小
最多5000种状态。。BFS秒过#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <queue> #include <string> #include <map> #include <cstring> #include <ctime> #include <vector> #define inf 1e9 #define ll long long #define For(i,j,k) for(int i=j;i<=k;i++) #define Dow(i,j,k) for(int i=k;i>=j;i--) using namespace std; int n,m,a[101],q[10001],num[10001],nxt[10001],vis[10001],l=1,r,ans,tot,ANS[10001]; int main() { scanf("%d%d",&n,&m); For(i,1,m) scanf("%d",&a[i]); sort(a+1,a+m+1); For(i,1,m) if(a[i]&&!vis[a[i]%n]) q[++r]=a[i]%n,vis[a[i]%n]=1,num[r]=a[i],nxt[r]=-1; while(l<=r) { int t=q[l]; if(t==0){ans=l;break;} For(i,1,m) { int tmp=(t*10+a[i])%n; if(!vis[tmp]) q[++r]=tmp,num[r]=a[i],nxt[r]=l,vis[tmp]=1; } l++; } while(ans!=-1) { ANS[++tot]=num[ans]; ans=nxt[ans]; } Dow(i,1,tot) printf("%d",ANS[i]); }
-
12008-11-01 16:59:17@
(a*b) mod c=(a mod c*b mod c) mod c
(a+b) mod c=(a mod c+b mod c) mod c因此构图,一个余数对应一个点,对于每一个余数k,若(j*10+a[i]) mod n=l,则k与l连边,权为a[i]
求最短路即可
-
12008-11-01 16:29:18@
感谢吴豪..
令我恍然大虎..
``原来余数可以这样转换的..
好弱的数据..
我自己写了一组.
44440
10
44
88242
52
24
346
241
254
123褂掉..抱着试试的心态交上去..竟然..A了..
-
12006-05-24 20:42:04@
不用记录前面所有除过的数,只需要记录前面的余数。建一个图,图中的节点表示任意数除以n的余数,利用广搜,假设前一步的节点是x,那么下一步的节点就是(x*10+a[i]) mod n,两点间的权值是a[i],那么从0出发,当走回0的时候,一路上的权值全部连起来,就是所求的数字。其核心思想就是利用余数代表前面的运算结果,避免记录和处理太大的数。注意针对余数进行判重。
-
02018-07-28 13:34:28@
=<
题目没说答案范围,我一开始估计是100位数字以内,结果总是WA第一个点,我以为第一个点是小数字的边界问题,结果开成500位就AC了。。DP+按模分类
#include <bits/stdc++.h> using namespace std; #define FOR(i,n) for (int i=1;i<=n;i++) #define REP(i,a,b) for (int i=a;i<=b;i++) #define pb push_back #define mp make_pair #define ll long long #define pos(x,y) (x+(y)*n) const int N=100000+10; const int inf=0x3f3f3f3f; const ll mod=1000000007; const double eps=1e-8; int n,m; int a[20]; int f[510][10][5010]; int ten[510]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); cin>>n>>m; FOR(i,m) { int t;cin>>t; a[t]=1; } if (n<10) { FOR(i,9) { if (n*i<10&&a[n*i]) { cout<<n*i<<endl; return 0; } } } REP(i,0,9) if (a[i]) f[1][i][i%n]=1; ten[0]=1; FOR(i,500) ten[i]=ten[i-1]*10%n; FOR(i,500) { REP(j,0,9) if (a[j]) REP(j2,0,9) if (a[j2]) { REP(k,0,n-1) { f[i+1][j2][(j2*ten[i]+k)%n]|=f[i][j][k]; } } } REP(i,2,500) FOR(j,9) if (a[j]) { if (f[i][j][0]) { int s=j; cout<<s; int t=(n-(j*ten[i-1])%n)%n; int now=i-1; while (now) { REP(k,0,9) if (a[k]) { if (f[now][k][t]) { cout<<k; t=(n+t-(k*ten[now-1])%n)%n; break; } } now--; } return 0; } } return 0; }
-
02012-08-03 23:43:31@
#01: Accepted (364ms, 644KB)
#02: Accepted (367ms, 644KB)
#03: Accepted (102ms, 644KB)
#04: Accepted (106ms, 644KB)
#05: Accepted (94ms, 644KB)
#06: Accepted (110ms, 644KB)
#07: Accepted (121ms, 644KB)
#08: Accepted (129ms, 644KB)
#09: Accepted (129ms, 644KB)
#10: Accepted (145ms, 644KB)
Accepted / 100 / 1671ms / 644KB
o(n)的没秒杀?真心自卑了 -
02010-07-14 15:34:51@
Accepted 有效得分:100 有效耗时:9ms
这题用DP好啊~只是被那ansistring恶心到了,速度降了不少……
-
02009-11-07 14:13:59@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms1次秒杀 呵呵
-
02009-11-02 19:42:59@
核心代码
for j:=0 to n-1 do
if v then
for k:=1 to m do
begin
e:=(a[k]*x+j)mod n;
if not v then
begin
v:=true;
f:=a[k];
g:=j;
end else
if (a[k]0) then
if (a[k] -
02009-10-30 16:02:25@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms
不幸 第299个通过 …………………………………… -
02009-10-29 21:20:29@
太囧了,第一次竟然内存溢出...
我只能说,评测机太萎了,还好最后秒掉了... -
02009-10-27 08:41:06@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0msorz花了我二十分钟...
BFS解决~
不过DP确实没想出来,膜拜想出DP并写出来秒杀的牛们...
OTL... -
02009-09-12 15:27:00@
楼下神牛:
BFS可以拿余数判重……所以也可以AC
不过我为啥202了?
-
02009-10-15 09:27:28@
我第一个点TLE/格式错误
其他90分……
真是无语……我回楼下的。。。确实这样。。。
囧了。。。
谢谢。 -
02009-08-04 20:43:15@
要用高精吗
-
02009-07-26 14:58:42@
比较大小要从头比哦.不要像我一样犯低级错误..
-
02009-07-19 20:25:14@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 9ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:9ms呼呼,滚动数组太牛B了!
-
02009-07-12 23:07:15@
这10个十进制数字,有多少位啊?????????????????????????????????????????????????????????????????
也就是说,是用以个数字(0,1,2....9)还是任意自然数啊????????????????????????????????????? -
02009-05-28 09:58:04@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0msBFS万岁!
AC第一百题! -
02009-03-28 09:36:57@
FT。BFS水题一次AC
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms