藍雪的Online Judge日誌: 10月 2013

2013年10月31日星期四

STEP5 0031 : 蘿莉切割問題

[霍夫曼HEAP]
兩個兩個一串==>霍夫曼編碼

O(NlgN)

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<cstring>
#define INF 0
#define LL  unsigned long long int
#define N 200000
class minHeap
{
private:
    LL a[N];
    int cnt;
public:
    minHeap()
    {
        memset(a,(LL)INF,sizeof(a));
        cnt=0;
    }
    void add(LL inp)
    {
        a[++cnt]=inp;
        for(int prc=cnt;prc/2;prc/=2)
            if(a[prc]<a[prc/2])
                a[prc]^=a[prc/2]^=a[prc]^=a[prc/2];
            else
                break;
    }
    LL getmin()
    {
        if(cnt==0) return -1;
        return a[1];
    }
    void remove()
    {
        a[1]=a[cnt];
        a[cnt]=INF;
        cnt--;
        int prc=1;
        while(1)
        {
            if(prc*2>cnt) break;
            if(a[prc*2]==INF) break;
            if(a[prc*2+1]==INF)
            {
                if(a[prc]>a[prc*2])
                    a[prc*2]^=a[prc]^=a[prc*2]^=a[prc];
                prc*=2;
                continue;
            }
            if((a[prc]<=a[prc*2])&&(a[prc]<=a[prc*2+1])) break;
            else if(a[prc*2]>=a[prc*2+1])
            {
                a[prc*2+1]^=a[prc]^=a[prc*2+1]^=a[prc];
                prc=prc*2+1;
            }
            else
            {
                a[prc*2]^=a[prc]^=a[prc*2]^=a[prc];
                prc*=2;
            }
        }
    }
};
int main()
{
    minHeap mh;
    int n;      scanf("%d",&n);
    LL cost=0;
    LL inp;
    for(int lx=0;lx<n;lx++)
    {
        scanf("%I64u",&inp);
        mh.add(inp);
    }
    LL a,b;
    for(int lx=1;lx<=n-1;lx++)
    {
        a=mh.getmin();
        mh.remove();
        b=mh.getmin();
        mh.remove();
        cost+=a+b;
        mh.add(a+b);
    }
    printf("%I64u\n",cost);
    return 0;
}

2013年10月30日星期三

[筆記] 關於 A!/B! mod R

前幾天在競賽上碰到了一個問題的子問題：

在多次查尋下使 單次查詢

$\frac{A!}{B!} \ (mod \ R)$

$\forall R>A>B>0$

複雜度達到O(1)

明顯的，是要建表、模逆表。

但模逆運算只在當模為質數時才是可行的(事實上，若模是質數，可以在O(2N)時間建完兩個表)，當模並非質數直接存表時，會發生悲劇。

因此，要設法把 A! 和 B! 提出一部分因數，使其與 R 互值。

藉由Legendre定理：

$\alpha_p(n)=\sum_{i=1}^{\infty}\left \lfloor \frac{n}{p^i} \right \rfloor$

可以找出n!的p的次方數

定理相關細節可參考：Wiki

(1)建表、使用：

舉 R=pq 為例：

要建的表是：

$\beta_R(n)=\frac{n!}{p^{\alpha_p(n)}q^{\alpha_q(n)}}$

Trivial(讀者自己想XD):

$gcd(\beta_R(n),R)=1 \ \forall n<R$

因此，便可以在O(1) 時間內取得

$\beta_R(A)\beta_{R}^{-1}(B)$

進而快速求得：

$\frac{A!}{B!}=p^{\alpha_p(A)-\alpha_p(B)}q^{\alpha_q(A)-\alpha_q(B)} \beta_R(A)\beta_{R}^{-1}(B)$

(2)遞推關係：

$\beta_R(n+1)=(n+1)\beta_R(n)p^{\alpha_p(n)-\alpha_p(n+1)}q^{\alpha_q(n)-\alpha_q(n+1)}$

$\beta_R^{-1}(n)=(n+1)\beta_R^{-1}(n+1)p^{\alpha_p(n)-\alpha_p(n+1)}q^{\alpha_q(n)-\alpha_q(n+1)}$

程式碼：

[待補]

建表時間大致為O(RlogR)

POJ 3468 A Simple Problem with Integers

[線段樹]
開始覺得非遞迴線段樹根本HOLD :3

卡(a^1>>1)卡了頗久 Note: 養成習慣 "(a^1)"

O(NlgN)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define N 100010
#define LL long long
using namespace std;
//BST
LL a[N];
LL NodeCnt[N*4];
LL NodeSum[N*4];
LL NodeImp[N*4];
int n;int base;
void BuildTree()
{
        base=pow(2,ceil(log2(n)))-1;
        if(base>=(n-2))
                base=base*2+1;
        memset(NodeCnt,(LL)0,sizeof(NodeCnt));
        memset(NodeSum,(LL)0,sizeof(NodeSum));
        memset(NodeImp,(LL)0,sizeof(NodeImp));
        for(int lx=0;lx<n;lx++)
                for(int prc=base+lx+1;prc;prc>>=1)
                        NodeSum[prc]+=a[lx],NodeCnt[prc]++;
}
void Edit(int a,int b,LL c)
{
        for(a+=base-1,b+=base+1;a^b^1;a>>=1,b>>=1)
        {
                if(~a&1)
                {
                    NodeImp[a^1]+=c;
                    for(int prc=((a^1)>>1);prc;prc>>=1)
                       NodeSum[prc]+=c*NodeCnt[a^1];
                }
                if(b&1)
                {
                    NodeImp[b^1]+=c;
                    for(int prc=((b^1)>>1);prc;prc>>=1)
                       NodeSum[prc]+=c*NodeCnt[b^1];
                }
        }
}
LL Ask(int a,int b)
{
        LL ret=0;
        for(a+=base-1,b+=base+1;a^b^1;a>>=1,b>>=1)
        {
                if(~a&1)
                {
                    ret+=NodeSum[a^1];
                    for(int prc=a^1;prc;prc>>=1)
                       ret+=NodeImp[prc]*NodeCnt[a^1];
                }
                if(b&1)
                {
                    ret+=NodeSum[b^1];
                    for(int prc=b^1;prc;prc>>=1)
                       ret+=NodeImp[prc]*NodeCnt[b^1];
                }
        }
        return ret;
}

int main()
{
        int Qs;
        while(scanf("%d %d",&n,&Qs)!=EOF)
        {
            memset(a,(LL)0,sizeof(a));
                for(int lx=0;lx<n;lx++)
                        scanf("%I64d",&a[lx]);
                BuildTree();
                int p,q;
                LL r;
                char c[100];
                while(Qs--)
                {
                        scanf("\n%c ",c);
                        if(c[0]=='Q')
                        {
                                scanf("%d %d",&p,&q);
                                printf("%I64d\n",Ask(p,q));
                        }
                        else
                        {
                                scanf("%d %d %I64d",&p,&q,&r);
                                Edit(p,q,r);
                        }
                }
        }
        return 0;
}

2013年10月29日星期二

TIOJ 1272 The Agency

[線段樹+壓樹]
發現vector不能來存子節點QQ
1. 壓扁樹
2. 線段樹

#include<cstdio>
#include<stdlib.h>
#include<cstring>
#include<math.h>
#include<vector>
#define N 200000
using namespace std;
//壓扁樹
int NodeLptr[N];
int NodeRptr[N];
int Lineprc=0;
int n,Q;
struct ND
{
    int a;
    ND *next;
}NDs[N];
void SetTreeLine(int node)
{
    NodeLptr[node]=Lineprc+1;
    Lineprc++;
    for(ND *ptr=&NDs[node];ptr->a>0;ptr=ptr->next)
        SetTreeLine(ptr->a-1);
    NodeRptr[node]=Lineprc+1;
    Lineprc++;
}

//線段樹
int base;
bool BST[N*8];
void BuildTree()
{
    base=(int) pow(2,ceil(log2(2*n)))-1;
    if((base+1)==(2*n))
        base=base*2+1;
    // DELETE ?
    //memset(BST,false,sizeof(BST));
}
void Edit(int inp)
{
    int a=NodeLptr[inp-1];
    int b=NodeRptr[inp-1];
    for(a+=base-1,b+=base+1;a^b^1;a>>=1,b>>=1)
    {
        if(~a&1)BST[a^1]=1-BST[a^1];
        if(b&1)BST[b^1]=1-BST[b^1];
    }
    return;
}
bool Ask(int inp)
{
    int cnt=0;
    for(int prc=NodeRptr[inp-1]+base;prc;prc>>=1)
        cnt+=BST[prc];
    return (cnt%2);
}

int main()
{
    scanf("%d %d",&n,&Q);
    int cnt;
    for(int lx=0;lx<n;lx++)
    {
        scanf("%d",&cnt);
        ND *ptr=&NDs[lx];
        for(int ly=0;ly<cnt;ly++)
        {
            int inp;
            scanf("%d",&inp);
            ptr->a=inp;
            ND *newND=(ND*)malloc(sizeof(ND));
            ptr->next=newND;
            ptr=newND;
            //child[lx].push_back(inp);
        }
        ptr->a=-1;
    }
    SetTreeLine(0);
    BuildTree();
    int a,b;
    while(Q--)
    {
        scanf("%d %d",&a,&b);
        if(a==0)
            Edit(b);
        else
            printf("%d\n",Ask(b));
    }
    return 0;
}

2013年10月26日星期六

TIOJ 1603 胖胖殺蚯事件

[線段樹]
第一次寫TIOJ上的線段樹 :3

#include<stdio.h>

#include<stdlib.h>
#include<math.h>
#include<string.h>
#define N 100000
#define inf 2147483649
#define max(a,b) ((a)>(b)) ? (a):(b)
#define min(a,b) ((a)>(b)) ? (b):(a)
long long int TREE[N*4];
long long int MAXTREE[N*4];
long long int MINTREE[N*4];
int base;
int n;
void BuildTree()
{
    for(int lx=1;lx<=n;lx++)
    {
        for(int prc=(base+lx)>>1;prc;prc>>=1)
        {
            MAXTREE[prc]=max(MAXTREE[prc],TREE[base+lx]);
            MINTREE[prc]=min(MINTREE[prc],TREE[base+lx]);
        }
    }
}
long long int FindSub(int a,int b)
{
    long long int gmin=TREE[b+base];
    long long int gmax=TREE[b+base];
    for(a+=base-1,b+=base+1;(a^b^1);a>>=1,b>>=1)
    {
        if(~a&1)
        {
            gmin=min(gmin,MINTREE[a^1]);
            gmax=max(gmax,MAXTREE[a^1]);
        }
        if(b&1)
        {
            gmin=min(gmin,MINTREE[b^1]);
            gmax=max(gmax,MAXTREE[b^1]);
        }
    }
    return gmax-gmin;
}
int main()
{
    int m;scanf("%d %d",&n,&m);
    memset(MINTREE,inf,sizeof(MINTREE));
    base=pow(2,ceil(log2(n)))-1;
    for(int lx=1;lx<=n;lx++)
    {
        scanf("%I64d",&TREE[lx+base]);
        MINTREE[lx+base]=TREE[lx+base];
        MAXTREE[lx+base]=TREE[lx+base];
    }
    BuildTree();
    for(int lx=0;lx<m;lx++)
    {
        int a,b;scanf("%d %d",&a,&b);
        printf("%d\n",FindSub(a,b));
    }
    return 0;
}

2013年10月24日星期四

HOJ 001 Problem : 1 - Breakfast

[無]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>


int main()
{
    int inp;
    while((scanf("%d",&inp)!=EOF) && inp )
    {
        if((inp==1)||(inp==2)||(inp==4)||(inp==7))
        {
            printf("This is Kongming's Trap!!!\n");
            continue;
        }
        int a,b,k;
        if(inp%3==0){a=inp/3;b=0;}
        if(inp%3==1){a=(inp-10)/3;b=2;}
        if(inp%3==2){a=(inp-5)/3;b=1;}
        k=a/5;
        a-=5*k;
        b+=3*k;
        printf("%d\n",a+b);
    }
    return 0;
}

2013年10月23日星期三

HOJ 002 Problem 2 - 要我寫毛阿

[STACK括弧匹配]
今天拿到HSNU的帳號就先寫吧XDD
O(N)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct point
{
    int pos;
    int index;
};
struct line
{
    int a;int b;
    int index;
};
bool operator<(const line& x,const line& y)
{
    if(x.a<y.a)
        return true;
    if(x.a>y.a)
        return false;
    return (x.b<y.b);
}
bool operator==(const line& x,const line& y)
{
    return ((x.a==y.a)&&(x.b==y.b));
}
bool operator<(const point& x,const point& y)
{
    return (x.pos<y.pos);
}
point ps[200000];
line ls[100000];
line lsp[100000];
int stk[200000];
int main()
{
    int T;scanf("%d",&T);

    for(int lT=1;lT<=T;lT++)
    {
        int n;scanf("%d",&n);
        for(int lx=0;lx<n;lx++)
        {
            scanf("%d %d",&lsp[lx].a,&lsp[lx].b);
            lsp[lx].index=lx;
        }
        sort(lsp,lsp+n);
        //去除重複
        int cnt=1; ls[0]=lsp[0];
        for(int lx=1;lx<n;lx++)
        {
            if(lsp[lx]==lsp[lx-1]) continue;
            ls[cnt]=lsp[lx];cnt++;
        }
        //for(int lx=0;lx<cnt;lx++)
        //  printf("%d %d %d\n",ls[lx].a,ls[lx].b,lx);
        for(int lx=0;lx<cnt;lx++)
        {
            ps[lx*2].pos=ls[lx].a;
            ps[lx*2].index=lx;
            ps[lx*2+1].pos=ls[lx].b;
            ps[lx*2+1].index=lx;
        }
        sort(ps,ps+cnt*2);
        //for(int lx=0;lx<cnt*2;lx++)
        //  printf("%d %d\n",ps[lx].pos,ps[lx].index);

        int stkcnt=0;
        for(int lx=0;lx<cnt*2;lx++)
        {
            if(stkcnt==0)
            {
                stk[0]=ps[lx].index;
                stkcnt++;
            }
            else
            {
                if(stk[stkcnt-1]==ps[lx].index)
                    stkcnt--;
                else
                    stk[stkcnt++]=ps[lx].index;
            }
            //printf("stkcnt=%d\n",stkcnt);
        }
        if(stkcnt==0)
            printf("Y\n");
        else
            printf("N\n");
    }
}

2013年10月22日星期二

TIOJ 1047 C.邏輯計算機

[無]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

int main()
{
    char inp[90];
    while(scanf("%s",inp))
    {
        if((inp[0]=='E')&&(inp[1]=='N')&&(inp[2]=='D'))
            break;
        int now=0;     int inv=0;
        int saved=1; int stack=1;
        int sl=strlen(inp);
        for(int lx=0;lx<sl;lx++)
        {
            //printf("d[%c]\n",inp[lx]);
            if(inp[lx]=='!')
                inv=1-inv;
            else if(inp[lx]=='1')
            {
                stack=stack&&(1-inv);
                inv=0;
            }
            else if(inp[lx]=='0')
            {
                stack=stack&&(inv);
                inv=0;
            }
            else if(inp[lx]=='+')
            {
                now=now+saved*stack;
                stack=1;
                saved=1;
                if(now>=1)
                    break;
            }
            else if(inp[lx]=='*')
            {
                //printf("saved=%d\tstack=%d\n",saved,stack);
                saved=saved&&stack;
                stack=1;
            }
        }
        printf("%d\n",now+saved*stack>=1);
    }
    return 0;
}

2013年10月19日星期六

TIOJ 1098 A.好多油瓶

[數學]
先搜到 ap+bq=n的其中一組解(a0,b0)，再往上或下搜，一轉折就停止。
複雜度O(N)

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<ctype.h>

int gcd(int a,int b)
{
    if(a<b){int tmp=a;a=b;b=tmp;}
    if(a%b==0)
        return b;
    return gcd(b,a%b);
}
bool findlinear(int p,int q,int n,int *a,int *b)
{
    if(n%gcd(p,q)!=0)
        return false;
    //pa+qb=n
    for(int lx=0;lx<p;lx++) //run on b
    {
        if((n-lx*q)%p==0)
        {
            *a=(n-lx*q)/p;
            *b=lx;
            return true;
        }
    }
}
int cost(int a,int b)
{
    if(a*b==0)
    {
        if(a==0)
            return 2*b;
        else
            return 2*a;
    }
    if((a>0)&&(b>0))
        return 2*(a+b);
    return (2*(abs(a)+abs(b))-1);
}
int main()
{
    int p,q,n;
    int a,b;
    while((scanf("%d %d %d",&p,&q,&n)==3))
    {
        if((!p)&&(!q)&&(!n)) break;
        if(findlinear(p,q,n,&a,&b)==false)
        {
            printf("No\n");
            continue;
        }
        int g=gcd(p,q);
        p/=g;q/=g;n/=g;
        findlinear(p,q,n,&a,&b);
        //printf("(%d,%d)\n",a,b);
        int cost0=cost(a,b);
        int costprc1=cost0,costprc2=cost0;
        int pa,pb;
        for(pa=a,pb=b;costprc1>=cost(pa,pb);pa-=q,pb+=p)
        {
            costprc1=cost(pa,pb);
            //printf("[%d,%d]%d\n",pa,pb,cost(pa,pb));
        }

        for(pa=a,pb=b;costprc2>=cost(pa,pb);pa+=q,pb-=p)
        {
            costprc2=cost(pa,pb);
            //printf("{%d,%d}%d\n",pa,pb,cost(pa,pb));
        }

        if(costprc1>costprc2)
            printf("%d\n",costprc2);
        else
            printf("%d\n",costprc1);
    }
    return 0;
}

2013年10月16日星期三

[筆記]關於數論函數在程式碼上的實現

有鑑於在題庫裡出現的各式各樣的數論(不是樹論喔)函數題目，決定整理一下數論函數的算法。

數論函數是指只定義域在整數的函數，對應到的值域並不限於整數(甚至可以是複數)，但常遇的大多只在整數域取值，因此本篇著重在

$f:\mathbb{N} \rightarrow \mathbb{N}$

的數論函數。

關於數論函數還有一個定義：
只要函數符合

$f(mn)=f(n)f(m) \ \ \forall gcd(n,m)=1$
就稱積性函數。

事實上，歐拉函數和*除數函數就是積性函數。(詳細的數論函數介紹待補，這裡大致提他的性質)

對於積性的數論函數，我們可以先進行預處理，把所有的N都進行因數分解。

O(NlglgN)

#include<vector>
#define N 1000000
struct pair
{
    int prime;
    int alpha;
};
std::vector<int>nd[N];
for(int lx=0;lx<prime.size();lx++)
{
    int a=1;
    for(int p=prime[lx];p<=N;p*=prime[lx],a++)
    {
        for(int ly=1;ly*p<=N;ly++)
        {
            if(ly%prime[lx]==0) continue;
            nd[ly*p].push_back(new pair(prime[lx],a));
        }
    }
}

因此在每次詢問，都可以做到O(lgN)的複雜度。

但對於一些比較特別的積性函數，譬如歐拉函數、*Möbius函數：

歐拉函數在p^a的值可以用phi(p^(a-1))和p表示出來，則可以在建質數表時以O(N)的複雜度填好。

以下取Möbius函數做例子：

    vector<int>prime;
    bool seive[1000000];
    int mu[1000000];
    mu[1]=1;
    for(int lx=2;lx<1000000;lx++)
    {
        if(!seive[lx])
        {
            prime.push_back(lx);
            mu[lx]=-1;
        }

        for(int ly=0;lx*prime[ly]<1000000;ly++)
        {
            seive[lx*prime[ly]]=true;
            if(lx%prime[ly]==0)
            {
                mu[lx*prime[ly]]=0;
                break;
            }
            else
                mu[lx*prime[ly]]=-mu[lx];
        }
    }

附上另外一個特別的積性函數：除數和函數，建表O(NlgN)：

1 int d[N];

2 for(int lx=1;lx<N;lx++)

3 for(int ly=1;ly*lx<N;ly++)

4 d[lx*ly]+=lx;

(將會更新)

*除數函數：
$\sigma_0 (n)=\sum_{d | n } 1$
*Möbius函數：
$\mu(p^\alpha )=-\left \lfloor \frac{1}{\alpha} \right \rfloor \forall p \in \mathbb{P}$

訂閱：文章 (Atom)

2013年10月31日 星期四

2013年10月30日 星期三

2013年10月29日 星期二

2013年10月26日 星期六

2013年10月24日 星期四

2013年10月23日 星期三

2013年10月22日 星期二

2013年10月19日 星期六

2013年10月16日 星期三