【線上筆試題解題報告系列】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 交點是整點，

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

（這個出解很快，真 · O(nlogn) ）

D. Sorting Array

目前并不會做（說實話，題都還沒讀）

有空補上。