天天看點

【線上筆試題解題報告系列】Google APAC 2017 University Test Round E

最後一輪的 2017 Google APAC Test 了呢。

scoreboard中搜尋hdu.toraoh,可以看我的當時實際送出情況。

照慣例,題意就不翻譯了。(畢竟Google有英文面試的)

本文URLhttp://blog.csdn.net/fcxxzux/article/details/53055195,轉載請留位址(而且現在還沒完工呢)

A. Diwali lightings

顯然要利用這個模式串s很短,查詢區間很長。

我們知道查詢區間裡s完整地出現幾次,再補上最開頭s的末尾一部分,再補上最後s的開頭一部分,這3部分的B的數量之和,完事。

能寫起來更簡單嗎?

對于這種求 [a,b] 之間滿足一定條件的東西的數目的題目,我們可以做以下的轉化:

[a,b]的答案=[1,b]的答案−[1,a]的答案

而[1,a]的答案,在處理的時候,就沒有要補上s尾部一塊的問題了。

(是以我就是這麼寫的)

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;

char s[];
ll a,b;

ll cnt(ll x){
    int len=strlen(s);
    ll d=x/len,mod=x%len;
    ll ans=;
    for(int i=;i<len;i++){
        if(s[i]=='B'){
            ans+=d;
            if(i<mod)ans+=;
        }
    }
    return ans;
}

int main(){
    freopen("A-large.in","r",stdin);
    freopen("A-large.out","w",stdout);
    int T,Case=;
    for(scanf("%d",&T);Case<=T;Case++){
        scanf("%s%I64d%I64d",s,&a,&b);
        printf("Case #%d: %I64d\n",Case,cnt(b)-cnt(a-));
    }
    return ;
}
           

B. Beautiful Numbers

考慮做的方向:

先進制再确定長度?

不行,進制可行解多,範圍極大,還不連續,沒法直接二分進制求得答案。

那先确定長度再考慮幾進制?

因為2^64>10^18,2進制下都不可能長度超過64位,好像可行。

那怎麼确定是幾進制的呢?

A、二分,不是超了就是少了,或者剛好,還是單調變化,非常好

B、為什麼不直接開根号呢?

對輸入的 n ,從最長的長度x枚舉,直接開 (x−1) 次根号并下取整,然後代回檢查。

直接開根号可行的解釋的話。

首先,我們要知道,

對 b 進制的數(12345)b,轉成10進制,要這麼算:

1∗b4+2∗b3+3∗b2+4∗b1+5∗b0

然後反證法:

假設長度x的情況下,開根号,告訴你應該是b進制

先證明不可能是b-1進制

b-1進制的情況下,這個數如果各個位置全1,轉化成10進制,應該是:

1∗(b−1)x−1+⋯+1∗(b−1)3+1∗(b−1)2+1∗(b−1)1+1∗(b−1)0

我們來把 bx−1 變形一下:

bx−1

=((b−1)+1)x−1

=(x−1x−1)(b−1)x−1+(x−1x−2)(b−1)x−2+… (二項式定理)

>(b−1)x−1+(b−1)x−2+…

然而事實上, bx−1≤n

也就是說, b−1 進制再怎麼努力也不行。

b+1 進制也不可能,很直白地能證明:

我們開根号是 n√x−1 ,一個最高位是1,其他位是0的 b+1 進制的數,上來就有 (b+1)x−1>(n√x−1)x−1 ,怎麼想都已經虐過那個n了。

或者直接說,開根号和幂次互為逆操作。你開根号的結果再幂回去,一樣大。你現在開根号的結果+1再幂回去,肯定大于n了。

是以證明了, ⌊n√x−1⌋ 就是我們想要的(進制)。

當然不要忘了,對長度為2的情況,單獨抓出來特判。

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;

ll lpow(ll base,ll time){
    ll ans=;
    for(int i=;i<=time;i++)ans*=base;
    return ans;
}

ll check(ll x,int time){
    ll ans=pow((double)x,/time);
    if(ans<)return -;
    ll t=;
    for(int i=;i<=time;i++){
        t+=lpow(ans,i);
    }
    if(t!=x)return -;
    return ans;
}

int main(){
    freopen("B-large.in","r",stdin);
    freopen("B-large.out","w",stdout);
    int T,Case=;
    for(scanf("%d",&T);Case<=T;Case++){
        ll n;
        scanf("%I64d",&n);
        for(int i=;i>=;i--){
            if(i==){
                printf("Case #%d: %I64d\n",Case,n-);
                break;
            }
            ll res=check(n,i);
            if(res>){
                printf("Case #%d: %I64d\n",Case,res);
                break;
            }
        }
    }
    return ;
}
           

C. Partioning Number

不妨看成3段:

a0,a0+1,a0+2 3種東西

搞 x,y,z 個,使得 x∗a0+y∗(a0+1)+z∗(a0+2)=n ,而且 a0|d

方法1:

枚舉 a0 ,以及到底由幾種不同的數組成

1種:直接來,整除檢查就行

2種:或者沒 y ,得x∗a0+z∗(a0+2)=n,或者沒 z ,得x∗a0+y∗(a0+1)=n

3種:枚舉x,然後剩下的方程是 y∗(a0+1)+z∗(a0+2)=n−x∗a0

3種二進制一次不定方程,求不定方程的整數解的個數的話

掏出擴充歐幾裡得算法來算吧!

具體可參考歐幾裡德與擴充歐幾裡德算法 - jumping_frog - 部落格園 的說明,相關細節摘抄如下:

對于不定整數方程 pa + qb = c,若 c mod gcd(a, b) = 0,則該方程存在整數解,否則不存在整數解。(注:以a b c為已知量)

上面已經列出找p * a + q * b = gcd(a, b)一個整數解的方法(擴充歐幾裡得算法直接求,額外的2個傳回值就是p0和q0,我們要的整數解)

在找到p * a+q * b = gcd(a, b)的一組解p0,q0後,

可以得到p * a+q * b = c的一組解

p1 = p0 * ( c / gcd(a,b) ),

q1 = q0 * ( c / gcd(a,b) ),

p * a+q * b = c的其他整數解滿足:

p = p1 + b / gcd(a, b) * t

q = q1 - a / gcd(a, b) * t(其中t為任意整數)

p 、q就是p * a+q * b = c的所有整數解。

相關證明可參考:

http://www.cnblogs.com/void/archive/2011/04/18/2020357.html

然後,我們要求p>0且q>0,可以得到t的取值範圍,

t>−p1∗gcd(a,b)/b

t<q1∗gcd(a,b)/a

其中為整數的t的數量,就是這個二進制一次不定方程的正整數解的數量了!

時間複雜度?

外層O(n),最内部求解的數量是O(logn)的

中間枚舉 y∗(a0+1)+z∗(a0+2)=n−x∗a0 的時間複雜度呢?

注意到,這裡面每層要枚舉的數量累加起來為:

n/1+n/2+n/3+⋯+n/n

=nlogn (調和級數)

是以,我們的時間複雜度為 O(nlog2n)

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;

void extgcd(ll a,ll b,ll& d,ll& x,ll& y){
    if(!b){
        d=a;x=;y=;
    }else{
        extgcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}

int solve(int a,int b,int n){
    if(n%__gcd(a,b)!=)return ;
    ll g,p0,q0;
    extgcd(a,b,g,p0,q0);
    p0*=n/g;q0*=n/g;
    int less=floor((-p0)*g*/b),great=floor(q0*g*/a);
    if(q0*g%a==)--great;
    return great-less<?:great-less;
}

int main(){
    freopen("C-large.in","r",stdin);
    freopen("C-large3.out","w",stdout);
    int T,Case=;
    for(scanf("%d",&T);Case<=T;Case++){
        int n,d;
        ll ans=;
        scanf("%d%d",&n,&d);
        if(n%d==)ans++;
        for(int i0=d;i0*<=n;i0+=d){
            //1
            if(n%i0==)++ans;
            //2
            ans+=solve(i0,i0+,n);
            ans+=solve(i0,i0+,n);
            //3
            for(int i=;i0*i<n;i++){
                ans+=solve(i0+,i0+,n-i0*i);
            }
        }
        printf("Case #%d: %I64d\n",Case,ans);
    }

    return ;
}
           

跑完大資料,大約5~10秒。

解法2:by [zucc]ChouUn

(我是真沒搞懂,估計是開始的思路就不一樣了……

在這裡貼一下他的說明和代碼)

直接當做3元1次不定方程:

ax+(a+1)y+(a+2)z=n−a…(1)

x+y+z=m−1………………(2)

(其中我們枚舉 a 和m)

(1)−a∗(2) 得

y+2z=(n−a)−a(m−1)

并且補充限制條件 y+z≤m−1

然後畫圖,可以發現: y+2z 跟 y+z 交點是整點,

不用考慮太多,繼續數學一下過了

【線上筆試題解題報告系列】Google APAC 2017 University Test Round E

(這個出解很快,真 · O(nlogn) )

D. Sorting Array

目前并不會做(說實話,題都還沒讀)

有空補上。

繼續閱讀