好似係final round, 正式比賽既A,B,C = d2 既C,D,E
剩係做到4題, 但後來對照番正式比賽, 其實200名內(有T-shirt)既好多都剩係做到題A(即d2 C)..
嗚呀
http://codeforces.com/contest/299 <--題目
A:
題意係N個數, 想知有無一個數係大家既common factor
B:
題意係比N個char你, 每個可以係行得/唔行得(石頭)
你可以由原地跳前 1<=i<=k 格, given N,k 同N個char, 問可唔可以由最左去到最右
永遠都可以最近石頭既空格跳, 即detect有無連續k個石頭
C:
就係正式比賽既A, 如果可以15分鐘內1棍過就有200名內 = 有T-shirt =[
係一題所謂既game, 但其實簡單greedy就ok
基本就係定好每個人最好既pick次序:
1. 兩個都係1一定最大價值, 自己多1對面少1
2. 自己係1 對面係0
3. 自己係0 對面係1
4. 兩個都係0
2同3 唔可以掉轉, 利己 > 損人, 因為自己pick 1 對面下一步只可以pick 番1 (打和) 或者ban 你1 (少你1) 黎對抗, 貪心地諗一定係最好, 反之如果ban 人行先, 去到極端可以出現你咩都無(因為你全部都ban人), 對面有少數1
另外注意下行先個個可以pick先...不過數據好細, 其實照simulate就ok
E:
其實過左都唔覺得特別難..係我數學特別差(所以從來都好憎見到咩number theory個d)
題意大約就係given n (<= 10^14),
solve ordered tuple(a,b,c) for
(a+b)^3 - (a^3 + b^3 + c^3) = n
a,b,c are positive integers
是咁的, 由於數據太大, 基本一定係sqrt(N) / lg(N) 甚至更少去做..當然先試下factorize條式等佢靚仔
呢度就係我覺得自己廢既原因, 我fac極都係出左d 極樣衰既form
結果問左偉大既chin爺, 之後再親身fac多次 無錯
LHS 係 3(a+b)(a+c)(b+c) 黎
其實呢度已經end of story...因為我覺得最難個part都比佢一下講完, adore
之後就係coding 上既問題..
首先 if(n%3)就無解, 跟住先了解一件事...我數底再差都知每一個component都係 <= cubicroot(N)
所以, 就先用O(cubicroot(N)) 黎搵哂合格既factors先
(小插曲, 其實我印象中唔知邊個講過total # of factors of integer N 係O(lg N), 但點諗都唔似係,結果問chin爺, 好似未有確定既Order?)
anyway, fac[] <-- 所有 <= cubicroot(N) 既factors, ~O(10^3)
咁就可以let (a+b) = fac[i] , (a+c)(b+c) = N/fac[i]
咁樣set係好合理, 因為fac[i] <= N/fac[i] && (a+b) <= (a+c)(b+c)
由, 我唔想數到重複count左一樣既組合, 所以我希望先搵哂所有(a',b',c') where a<=b<=c
用多一個loop j , fix死 a = j, b = fac[i] - j, 跟住計c出黎 (solve quadratic equation)
最後睇情況,
如果 a,b,c 一樣既就 +1, 如果是旦2個1樣既就+3, 3個都唔同既就+6
處理好唔同order既數目
LL fac[1000005];
LL solve(LL a, LL b,LL t){
LL c = 0;
LL delta = (a+b)*(a+b) - 4*(a*b-t);
LL sq = (LL)sqrt(delta)*(LL)sqrt(delta);
//血的教訓, 想test delta是否perfect square, 一定要parse做LL type先..
if(delta < 0 || sq != delta) return 0;
LL up = -(a+b)+sqrt(delta);
if(up > 0 && up%2 == 0) c = up/2;
//只拎 -b + sq(delta) 就得, 因為另一個一定係負數(如果有)
//c 已計, 下面處理重點問題
if(!c) return 0;
if(a == b && b==c)return 1;
if(a==b || b==c || a==c) return 3;
//如果c係正數, 先check下有無3個一樣或2個一樣既情況
//注意呢2個情況一定唔會repeat counting, 唔識用字面解釋, 總之唔會
if(c <= b) return 0;
//呢句一定要加, 就係減走d 當3個數唔同時repeat count既tuple
//當c <= b, 咁c 曾經係之前某次數既a或者b黎, 所以唔使再計
return 6;
}
int main(){
LL n,p=0,a,b,c,ans = 0;
scanf("%I64d", &n);
if(n%3){printf("0\n"); return 0;}
n/=3;
for(LL i=1; i*i*i<=n;i++) if(n%i == 0)fac[p++] = i;
for(int i=0; i<p;i++){
for(int j=1; j+j <= fac[i]; j++){
a = j; b = fac[i]-j;
ans+=solve(a,b,n/fac[i]);
}
}
printf("%I64d\n", ans);
return 0;
}
D: (唔識做)
終極變態題..話說開頭睇錯題目..以為係半頹半唔頹既COMBINATORICS..
後尾發現係要<紅色超大>所有</紅色超大>path都唔撞色...
如果問題係成個grid都係吉既任我填, 而且d 色係唔會多過你需要既(即n+m-1種)咁好易數
因為非正式prove左咁既情況所有path既排列一定要一樣, 唔係會影響到某d其它path令佢地撞色
答案係 kP(n+m-1), 由於k == n+m-1, 所以答案即係k!, 例子係example 3,答案係10!
好啦,問題是咁的,
1. 顏色係可以多過你需要既
2. 某d格係已填色, fix死左, 唔可以轉
嗚..
暫時諗到既只有
1. 真正既grid好細 (n+m 大約10之內) 所以做法可以暴力d
2. 似dp + combinatoric
3. 由最左邊"L"型條PATH開始填, 跟住一個個"L"型既path咁填落去
4. 每一個"L"型既某一格, 可以用番上一個"L"型相對應個格既色, 或者一d so far未用過既色
....
唉頭都爆, 放棄鳥 /.\
