SGU 491

全世界第46个A掉这道题的唉。。激动死了。。
激动完了。。讲讲算法吧。
题目是说给一个N。让你求有多少对A和B,让方程Ax+By=N有自然数解。。
N<=100000。。
这个N卡的太紧了。。我花了3个小时加速程序。。
一开始我的想法是首先算出所有小于N的数的因子,一个数的因子个数是logn级别的。
总共就是NlogN这不是问题。。
关键是后面的,时限卡得太紧了,4s,我一开始暴力枚举Ax的值,然后By=N-Ax。
那么Ax的任何因子配上By的任何因子都是解。。然后去重就可以了。。
看一下我的优化之路吧。。下面的时间表示最大数据。。
使用set加上pair<int,int>来去重。。23s
讲pair<int,int>压缩成一个long long。。21s
先讲这些long long存下来。再排序之后去重。。8s
一些细节上的小优化,比如vector使用由索引改成iterator之类的。。7s
大叫了一声TMD,人品爆发     6.2s
晕了。。写了个hash。。    MLE
使劲改Hash。。。    还是MLE
总算改好了Hash    23.3s
震精了。用了Hash+set 15s
撞死。。吃饭去了。。
吃饭好了继续想。。我把最快的那个算法的用时分析了一下。。
发现读入0s输出0s预处理1.6s,枚举0.7s,排序+去重5s。。
于是我发现预处理可以该进。。一开始我是暴力枚举平方根以下的因子并用set去重的,发现更本没必要。只要用vector就可以了。。于是预处理变成0.8s。。
还是超时。。
最后我快绝望了。。于是我想可能是因为排序的东西太多了。。一股脑排序可能慢了点。。
于是我先枚举a再枚举x。。然后算出所有可能的b。。然后对于每个a去一次重。。
实际上这两个算法是一摸一样的。。但是这个就AC了。。
累啊。。。。。
Code:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<ctime>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=100000+1;int n;
vector<int> A[maxn];
typedef vector<int>::iterator it;
typedef vector<int>::reverse_iterator rit;
typedef long long ll;
void Cal(int x)
{
static int tmp[10000];
int cnt=0;
for(int i=1;i*i<=x;i++)if(x%i==0)
tmp[cnt++]=i,tmp[cnt++]=x/i;
sort(tmp,tmp+cnt);A[x].push_back(tmp[0]);
for(int j=1;j<cnt;j++)
if(tmp[j]!=tmp[j-1])
A[x].push_back(tmp[j]);
}
int Ans[maxn*50];
int main()
{
//freopen("in","r",stdin);
int o=clock();
cin>>n;
for(int i=1;i<n;i++) Cal(i);
int ans=0;
for(int a=1;a<n;a++)
{
int*end=Ans;
for(int l=a;l<n;l+=a)
{
int r=n-l;
for(rit i=A[r].rbegin();i!=A[r].rend();i++)
if(*i>a) *(end++)=*i;
else break;
}
if(Ans==end) continue;
sort(Ans,end);
ans++;
for(int*i=Ans+1;i!=end;i++)
if(*i!=*(i-1)) ans++;
}
cout<<ans<<endl;
}
本高亮代码使用codeHl生成,
loading… loading…

One thought on “SGU 491

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>