Codeforces Round钻313(Div.1)

公式英語の解説:http://codeforces.com/blog/entry/19237
Problem A:
タイトルの大意:
内角とともに120°の六辺形の六辺長(いずれも正の整数)を与え、最大でいくつの辺長が1の正三角形に分割できるかを求めます.
 
クイズ:
六角形を補完して正三角形にして、三角形を減らせばいいです.
 
Problem B:
 
タイトルの大意:
長さが等しい二つの列ABを与え,二つの列が等しいと定義した. 当たる者は当  A=B  または  長さが偶数の場合、A[1...n/2]=B[1...n/2]  && A[n/2＋1…n]=B[n/2＋1…n]  または
長さが偶数の場合、A［1…n／2］＝B［n／2＋1…n］  && A[n/2＋1…n]=B[1...n/2] 
 
クイズ:
1.試合の時は、直接定義に基づいて判断するつもりはないと思います. 複雑さは私の感じと速さは同じです. 結局ショックを受けました.  試合後に考えたら複雑度が高いです.F(n)=4*F(n/2)+O(n).F(n)=O(n 2)
後の2つの条件は、長さが偶数である必要があるので、ランダムデータは簡単に過ぎる.次のデータは暴力をカードから落とすことができます.カードを使いたいですが、他の人は本当に大変です.
バ*32768
ab*32768 
2.正解:タイトルの中で「等しい」という定義は伝達性があります.だから、ABと同じ」という字典の順序が一番小さい文字列をそれぞれ求めて、等しいかどうかを判断することができます.

String smallest(String s) { if (s.length() % 2 == 1) return s; String s1 = smallest(s.substring(0, s.length()/2)); String s2 = smallest(s.substring(s.length()/2), s.length()); if (s1 < s2) return s1 + s2; else return s2 + s1; }

 
 
  
Problem C:
タイトルの大意:
N*Mの碁盤とK個の黒い格子の座標を与えて、左上から右下まで黒い格子を経ない方案数を求めます. 毎回右か下の1つしかできません. K<=3000 N,M<=100000.
 
クイズ:
1.この問題は以前にやったことがあります.だから、すぐに思い出しました.全体案から非合法な案を差し引くことができます.F[i]は左の上から黒い格子を経ないからi番目の黒い格子の方案数を表します.黒い格子を並べて、その後
F[i]=左上からiまでのスキーム数-F[j]*(jからiまでのスキーム数)   j番目の格子はi番目の格子の左上にある.  そしてAns=全体案-F[i]*(iから右下までのスキーム数).
2.(x 1、y 1)から(x 2、y 2)までの方案数はC(x 2-x 1+y 2-y 1、x 2-x 1)である. 逆元をあらかじめ処理してやればいいです.
 
Problem D:
N点の凸包を与え、サブ多角形内の整数点の数を求める.  N<=100000. 1 e-9まで正確です
 
クイズ:
1.ピケの定理は必ず使うべきですが、このテーマが一番巧妙だと思います.それとも多角形を線分に変換します.ピケの定理の内部の整数点=面積-境界の整数点+1です.だから期待面積と期待境界の整数点を処理すればいいです.
2.期待面積:フォーク積と多角形面積を求める方法を利用して、一つの多角形面積を複数の線分に変換する貢献. 境界全体の点数を期待するのも同じです. だから,各線分の面積と境界の整数点に対する寄与を考慮するだけである. この線分をPiPiPi+kとすると、i+kがi反時計方向の最初の点の多角形を考えます.多角形の面積を計算する時は順番に計算します.このような多角形は2 n-k-1-1個あります.
全部で2 n-1-n*(n-1)の多角形があります.この線分を選ぶ確率は除かれます.