CodeForces Round #586(Div1+Div2)
28585 ワード
A. Cards
テストアドレスの問題は簡単に説明します:長さnの文字列を与えて、この文字列はいくつかのoneといくつかのzeroを組み合わせることができて、各文字は一回しか使えません.
コードの例:
#includeB. Multiplication Table
テストアドレスの問題は簡単に説明します:1つのn*n表を与えて、ここでM i,j=a i∗a j M_{i,j} = a_i * a_j Mi,j=ai∗aj,今悪党が序列aを投げて、同時にM_{i,i}が引かれてしまいましたので、残りの情報を利用してaシーケンスを求めてください.
解題の構想:ガウス消元問題ではなく、実は法則を探す問題だ.もし私たちがa 1 aを求めることができたら1 a 1では、最初の列に基づいてすべての答えを求めることができます.a 1 a 2=x a_に基づいて1a_2 = x a1a2=x , a 1 a 3 = y a_1a_3 = y a1a3=y , a 2 a 3 = z a_2a_3=z a 2 a 3=zでa 1 a_を求める1 a 1で、他のすべての結果を求めることができます.コードの例:
#includeC. Substring Game in the Lesson
AnnとMikeはゲームをしています.文字列sがあります.最初はl=r=kで、一人一人が交代で操作します.
Ann先手は,位置kごとに,誰が勝つかを出力する.
簡単なゲーム理論では、まず必敗状態は「lの前にl'
#include
");
else puts("Mike");
}
int main(){
scanf("%s",str);
solve();
return 0;
}
D. Alex and Julian
テストアドレスの題意は簡単に述べる:1つの正の整数の集合Bを与えて、全集Z(すべての整数)内の要素を無方向図の頂点として、図の中の任意の2点iとjに対して、abs(i-j)が集合Bに属するならば、iとjの間に1本の無方向の辺がある.今、Bのいくつかの頂点を少なくとも削除して、残りの図を二分図にすることができます.
解題構想:二分図の問題ではなく、「一枚の図は二分図であり、図中に奇環が存在しない場合のみ」という二分図判定定理を用いた.なぜ二分図アルゴリズムで解決できないのかというと,問題規模から推測できるが,図を構築するにはO((1 e 18)2)O((1 e 18)^2)O((1 e 18)2)が必要であり,nの規模では許されないことは明らかである.
では、数学的に考えて(法則を探す)、ノード0とノードaがあれば、0からaまで辺があり、ノード2*aがまだ存在すれば、aと2*aにも辺があり、2*aと0にも辺があり、これが奇環である(3*aがあっても、奇環+偶環である)ため、2*aは存在せず、同じ理屈でも4*aは存在しないので、aを残すには、2*a、4*a、8*a、...は削除しなければならない.しかし,頂点集合は[1,1 e 18]であり,個々の計算は明らかに現実的ではないため,集合B中の各要素b,B中のどの要素がbとともに保持できるかについては複雑度が高すぎる.
aにx個の因数2があり、bにy個の因数2(x!=y)があると、aとbは同時に存在しないに違いない.c=lcm(a,b)と仮定すると、0->a->2*a->c->2*b->b->0は必ず奇環を構成することができるので、aとbは同時に存在しない.だからx!=yは、aとbが同時に存在しない(aとbは共に集合B内の要素である).
x=yであれば、aとbは同時に存在してもよい.aがbの倍数である場合、またはbがaの倍数である場合、0を削除することはできないので、リングがあれば必ず双環である.
以上のように,B集合中の各要素にどれだけの因子2があるかを統計することで,最大で同時にどれだけの要素が存在するか,すなわち少なくともどれだけの要素が削除されるかを判断できる.コードの例:
#include
",n-num[p]);
for(int i = 1;i <= n;i++)
if(tc[i] != p) printf("%I64d ",a[i]);
}
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i++) scanf("%I64d",a+i);
solve();
return 0;
}