首页 > 代码库 > hdu--1216--暴力过了<链表没想到>
hdu--1216--暴力过了<链表没想到>
这题 题意别搞错就是了 它给你的数据 很容易让你种错觉 是求第N位素数 但其实不是这样的
而是第一个数如果给了你一个2 那么后面的4 6 8 10 ......都应该被pass 然后接下去就是3了 再后面的 9 15 21..同样被pass就是说在一个 2~inf的数字串中距离选出的那个数字是 K*I 倍的都应该被pass<这个数首先未被pass>
然后 我采取的做法是 暴力 因为 数据不大的 就问你到3000为止 而且只需要一次预处理过后 就是直接O（1）的查询了 肯定不会TLE的
看到别人是用了 结构体 模拟链表写的 太cool了 完全没想到 写的狠飘逸
我直接把他的 核心代码 放上来
touch me
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 const int size = 38000; 6 bool vis[size]; 7 int ans[3500]; 8 9 void init( )10 {11 int cnt = 1 , temp , times;12 memset( vis , true , sizeof(vis) );13 for( int i = 2 ; i<size ; i++ )14 {15 if( cnt>=3001 )16 break;17 if( vis[i] )18 {19 ans[cnt++] = i;20 temp = i+1;21 times = 0;22 while( temp<size )23 {24 if( vis[temp] )25 {26 times++;27 }28 if( times % i == 0 )29 {30 vis[temp] = false;31 }32 temp ++;33 } 34 }35 }36 }37 38 int main()39 {40 cin.sync_with_stdio(false);41 int n;42 init( );43 while( cin >> n && n )44 {45 cout << ans[n] << endl;46 }47 return 0;48 }
struct Node{ int v; int next;};Node L[35001]; for(i=2;i<=37999;i++) { L[i].v=i; L[i].next = i+1; } L[38000].v=38000; L[38000].next=-1; top=1; for( i=2 ; L[i].next!=-1 ; i=L[i].next ) { res[top++] = L[i].v; if( top>=3001 ) break; j=i; while( L[j].next!=-1 ) { k=0; while( L[j].next!=-1 && k<L[i].v ) { k++; p = j; j = L[j].next; } if( L[j].next!=-1 ) { L[p].next=L[j].next; } } }
好代码 就不 折叠了 =-=
有点迷惘啊 ....
突然想起买个梦幻号玩了 2 3年了 哎..........
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。