注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

Codeforces 176 Div1 B(纯坑爹向)  

2013-03-28 21:37:15|  分类: CodeForces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
为什么我会把一道B等级的题目拿出来呢???
只是因为我的算法被卡了。。。很恶心地被卡常数了。。。而且卡了我好久好久结果最后放弃只得使用标准做法
很郁闷很郁闷。都没有心思了
是这样的:
f(n,k)表示将数列(0,1,2,3,4,,,,,n-1),按a/k的值划成很多块,然后进行一次shift操作,也就是1,2,3变成了2,3,1这样的。
对于k=2,,,,,n都进行一次,求问最后的序列。

标准算法是极其简单粗暴的。。不过我讲讲我的做法:
对于初始的每个值,我们要求出其最后的位置。
由于大部分情况,一个数的位置都是减1,而其余情况则是将这个数加上当前的k值-1。我们知道后面的操作的次数是nlogn的。那么只要模拟出这个就行了吧。
问题是我们不知道什么时候加k什么时候-1
实际就是对于当前的k,和位置p,要求最小的正整数x,使得(p-x+1)%(k+x)==0。如果可以O(1)解这个方程就可以解决问题了吧。
我们观察这个方程(我一直觉得我好蛋疼,与其观察这个还不如观察样例!!!)发现p-x+1+k+x==p+k+1是个与x无关的常数。
那么方法就有了,事先预处理,枚举出所有的(a,b)对,使得a|b。那么求解p,k,x的方程时,只需要在a,b和为p+k+1的对数中找到a>k的最小的一个对就行了。我们将这些东西排序就可以二分了对吧。。。但是这是O(nlognlogn)的。不过如果我们按照k值递增的顺序同时处理所有的位置,那么就具有单调性了吧。。于是发现这个问题可以就在O(nlogn)的时间内解决了。
写完程序后发现这个问题可以在3s内解决了。紧接着意识到时限是2s。。。
于是滚回去写正解了。

后来发现rng_58也是写的类似算法。。。好开心啊,因为他也TLE了。。。。
TLE代码:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;

const int MAX=15000000+10;
const int NUM=1000000+10;

int n;

int head[NUM*2],t[MAX],next[MAX],tot;
int head2[NUM],next2[NUM],tot2,ans[NUM];
int place[NUM];

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
scanf("%d",&n);
int i,j;
for(i=n;i>=2;--i)
for(j=i;j<=n+i;j+=i)
{
t[++tot]=i;
next[tot]=head[j];
head[j]=tot;
}
REP2(i,0,n)
{
place[i]=i;
next2[i]=head2[1];
head2[1]=i;
}
int h,c,d,nt;
t[0]=n+1;
REP(i,1,n)
{
h=head2[i];
for(;h;)
{
c=h,d=place[h]+i;
h=next2[c];
int *h2=head+d+1;
while(t[*h2]<=i)
*h2=next[*h2];
if(!(*h2))
ans[d-n]=c;
else
{
nt=t[*h2];
if(d>=n)
d=n-1;

place[c]=d;
next2[c]=head2[nt];
head2[nt]=c;
}
}
}
REP2(i,0,n)
printf("%d ",ans[i]+1);
printf("\n");
return 0;
}



  评论这张
 
阅读(230)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017