問題:GoodCompanyDivOne 概要: n ある条件:どの頂点を選んでも、その頂点とその直接の子たち(departmentと呼ぶ)からそれぞれ1つ仕事を選んで、それらが全て異なるようにできる.(頂点を選んだ後に仕事を選んで良いことに注意)解法: departmentの最大の大きさ…

問題:NegativeGraphDiv1 概要: 頂点数n( 解法: chargesがでかいので、上手く割り振ったりするのはむずそう,ダブリング?重みを負に出来る回数k回とj回のデータからk+j回のデータがほしい. a->bに1回以下使って行くときのコスト最小を行列で持つ 合成演算は掛…

Class:getMinimumInversions 問題概要:n( 解答: dfs適当にやって良い,InversionはBITでできる(Vの値の方で持つ)のだが、dfsの引数にvectorint bitとかを持って中でbit2を宣言してコピーして再帰とかするとコピーコストが大量にかかって死にます(死にました) …

SRM[200π] Easy:DivisorsPower 問題概要: 2以上1e18以下の整数xが与えられるので、nの(nの正の約数の個数)乗=xになるnを返せ ない場合は-1解法: i乗根とってやるだけ…と思っていたら落ちた 原因はdoubleがlong long intを表現しきれないことで、doubleは64bi…

問題概要:頂点数N( 解答:にぶたん+01dijkstra "重さwまでの辺を使っていいことにした時、1からNへ残りK本付け加えて辿り着けるなら答えはw以下"なので、wでにぶたん実は01dijkstra書いたことなかった どちらかというとdijkstraというよりかbfsだが、 if(d[e.…

pkuで原因不明のWA,理不尽なTLEが出たら、C++,G++を両方試そう(誤差が変わったり、実行時間が変わったりするようだ)

pku 3259 グラフが疎な時は、ベルマンフォードを使ったほうが良い ベルマンフォードのアルゴリズムでは、始点sが現れるのはd[s]=0の初期化だけなので、全体に負閉路があるかどうかはd[i]=0(0一般に点集合Sからたどり着ける場所に負閉路があるかは普通d[i]=0(…

これで空白系を読み飛ばしてくれるらしい追記 char s[100]; gets(s); で改行かEOF直前まで読み込むらしいまた追記(7/9) scanf("%d") だと改行は読み込まれない scanf("%d\n") だと改行は読み込まれる次の行にspaceを含むstringがあったりした時に、前者の後…