最後一輪的 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
目前并不會做(說實話,題都還沒讀)
有空補上。