BC42 ProB thinking

5月 24 2015

13*6=80, 在多少进制下成立。

十进制=78，进制数应该小于10，再试9就出来了。

不能只看80然后就确定78在8进制下是80，这是错误的，为什么呢？

因为不同进制下的乘法表都是不同的！

昨晚CF的D题有点意思，当我学了筛法，遇到Facebook Hackercup R1 Homework时其实我是拒绝的，因为我回了艾式筛法，却不会利用筛法算素数的种类数，看了王超晖代码后才知道可以把01变成整数存储。但是2*i的内循环
is needed.

当我看到昨晚CF D题时，其实我是拒绝的，因为我知道怎么算素因子的种类数，却不会再利用dp来算素因子的个数。对于合数，只要存一个素因子，就可以利用整除以一个素因子之后的数的素因子个数来算这个数的素因子个数, 分治思想真是帅啊。

艾式筛法比较多，其实本题还可以用欧拉筛法，虽然还不太会写code。

看了屌夫同学大背头的代码之后顿悟
PS:

栈的数组申请比较有限，可以用全局的申请更大的数组，比如此处LL的5e6级别的大小
B题居然写错了前后减的关系，应该是a[i-1]+1是目标，a[i]是原始，同样的错误在GCJ的一道题目也犯过，尤其是这种存储在一起，特别当心计算顺序的时候，看来还是练习不够，或者就用一个变量存储。

LL dp[maxn+10], n, t, m;
LL P[maxn+10];
void Prime()
{
    memset(P, 0, sizeof P);
    P[1]=1;
    for(LL i=2;i*i<=maxn;i++)
    {
        if(!P[i])
        {
            for(LL j=i*i;j<=maxn;j+=i) P[j]=i;
        }
    }
    //cout<<"zhang";
    dp[1]=dp[2]=dp[3]=1;
    for(LL i=4;i<=maxn;i++)
    {
        if(P[i]) dp[i]=dp[i/P[i]]+1;
        else dp[i]=1;
    }
    for(LL i=2;i<=maxn;i++) dp[i]+=dp[i-1];
    //for(LL i=1;i<=100;i++ ) cout<<dp[i]<<" ";
}

PS:
代码卡着时间过的2.9s, 时限3s，我都不知道开了输入挂是加速呢，还是加速呢，还是加速呢。。。。。

insane 可怕的

story after ID
http://codeforces.com/blog/entry/18021

my id is normal, just richard+zrc(zhang ruichang), richard
sounds similar to my Chinese name, and add suffix just for distinct from others.

How about the story after turmoil, fawkes, ahdoc, shawn. z?

in a row表示连续的

He has been to many countries to participate in IOI (7 years in a row) and also other competitions.

http://acm.hdu.edu.cn/showproblem.php?pid=5233

昨晚BC B题，就是查询。

一开始想着怎么维护代价最小，居然用优先队列，其实id的顺序是递增的，直接顺序存储的数据结构就好了，用队列。但是MLE了，这里多组数据的题目会说一定要用
while(cin), queue可能STL里面的空间开销较大，但是换vector还是T，最后还是拿了学弟的代码A的。

int x,q;
while(n=getint())
{
    m=getint();
myset.clear();
for(int i=0;i<n;i++)
{
    x=getint();
    //Node nd(i+1);
    myset[x].push(i+1);
}
for(int i=0;i<m;i++)
{
    q=getint();
    map<int, queue<int> >:: iterator it=myset.find(q);
    if(it==myset.end()) puts("-1");
    else if(it->second.empty()) puts("-1");
    else
    {
        printf("%d\n", it->second.front());
        it->second.pop();
    }
}
}

另外附上一种编程非常简答的方法，例如，直接把所有query一起处理，最后也就是分别sort两个数组，然后归并，最后再sort按照query顺序打印，这样也TLE，
卡常数，nlgn+mlgm+m+n, 但是常数项大导致TLE了。

对于离线算法往往一起处理可以提高效率。

int x;
while(n=getint())
{
    m=getint();
    for(int i=0;i<n;i++) x=getint(), h[i]=(Node1){x, i+1};
    sort(h, h+n, comp0);
    for(int i=0;i<m;i++) x=getint(), q[i]=(Node2){x, i+1, 0};
    sort(q, q+m, comp1);
    for(int i=0, j=0; i<m && j<n; )
    {
        if(h[i].x<q[j].x) i++;
        else if(h[i].x>q[j].x) q[j++].z=-1;
        else q[j++].z=h[i].y, i++;
    }
    sort(q, q+m, comp2);
    for(int i=0;i<m;i++) printf("%d\n", q[i].z);
}

Posted by richard爱闹 - 5月 24 2015
如需转载，请注明：本文来自 Richard

留言