2020.04.11【NOIP普及組】シミュレーションC組25まとめ
14915 ワード
2020.04.11 2020.04.11 2020.04.11【N O I P NOIP NOIP普及グループ】模擬試合C C Cグループ25 25まとめ
今度の試合は180,180点を取ったが、250,250点を取ることができたのに、ソートが間違って70,70点を失った.
第一題:B e r y Berry Berry P i c k i n g Picking Picking
タイトル
問題を解く構想.
この問題の解き方は欲張りだ.各バスケットのベリー数を直接列挙して並べ替えを判断すればいい.時間的複雑度はO(maxi=1 nb i⋅n logn 2)O(max_{i=1}^{n}{b_i}cdot nlog_n^2)O(maxi=1 nbi⋅nlogn 2)である.
得点状況
試合は60,60点で、変更後は満点です.
第二題:L o a n Loan Loan R e p a y m e n t Repayment Repayment
タイトル
解題方法
この問題の方法は二分答え+数学です.
30～30%のデータの場合:
私たちは答えを二分して、k k k日を直接シミュレートすればいいです.時間的複雑度はO(k logn 2)O(klog_n^2)O(klogn 2)である.
100,100%のデータの場合:
私たちは2点の答えx x xを求めて、上の方法を最適化します.その日に与える牛乳の数をy y yと仮定すると、合計a a日連続で同じ数を与えるが、g g個の牛乳がまだ与えられておらず、t t t t日残って牛乳を与える.では,a番目のa a a日にy y個の⌊g−(a−1)y x⌋=y
簡略化1 1 1式
下取整を外してg−(a−1)y x≧yfrac{ g−(a−1)y}{x}{x}geq y xg−(a−1)y≧y両側にx x xを同時に乗じてg−(a−1)y≧xy{g−(a−1)y}geq xy g−(a−1)y}geq xy g−(a−1)y≧xy両側をy y yで同時に除算し、g y−(a−1)≧xfrac{ g}−(a−1)geq x yg−(a−1)≧x≧xx x x x yg−(a−1)≧x≧xx x x x yg−(a−1)≧x(a−1)≧x x x x x xかっこを外し、得られたg y−a+1≧xfrac{g}{y}−a+1geq x yg−a+1≧xはa a aに関する式を整理し,得られたg y−x+1≧afrac{g}{y}−x+1geq a yg−x+1≧a
簡略化2 2 2式
下取りを行い、g−a y xyg−x<aを得る
整理1 1 1と2 2式
2つの式を組み合わせて、g y−xyg−x<a≤yg−x+1を得る.a a aは整数であるため、a=⌊gy−x+1⌋a=lfloorfrac{g}{y}−x+1rfloor a=⌊yg−x+1⌋
したがって,ブロック計算,すなわちa a a aを1回計算するだけで効率が向上する.しかし、a a aは残りの日数t t t tよりも大きく、境界を越える場合があるので、a=min(⌊g y−x+1⌋,t)a=min(lfloorfrac{g}{y}−x+1rfloor,t)a=min(⌊yg−x+1⌋,t)
g g gからa a a a aにy yを乗じて残りの牛乳数を得、t t tからa a a a aを減算して残りの日数を得るだけです.注意:上記の演算はy>my>my>mに限られます.y<=my<=my<=mであれば、残りのすべてを直接持ち去るべきである.すなわち、g gからy y y yを差し引いてt t tを乗じ、t=0 t=0 t=0とする.この問題はこのように解決され,時間的複雑度はO(n logn 2)O(sqrt{n}log_{n}^{2})O(n logn 2)程度であり,n≦1 0 12 nleq 10^{12}n≦1012のデータを通過できる.
得点状況
試合で満点をとる.
第三題:W o r m h o l e Wormhole Wormhole S o r t Sort Sort
タイトル
解題方法
この問題は私たちが直接使ってセットを調べればいいです.地図を作成し、連通を判断するために、集計を使用することができます.時間的複雑度はO(n logn 2)O(nlog_n^2)O(nlogn 2)であり、この複雑度はソートの複雑さであることに注意する.
得点状況
試合は50分50分で、問題を変えて満点です.
今度の試合は180,180点を取ったが、250,250点を取ることができたのに、ソートが間違って70,70点を失った.
第一題:B e r y Berry Berry P i c k i n g Picking Picking
タイトル
Bessie Elsie Farmer John 。Farmer John N （1≤N≤1000）； i Bi （1≤Bi≤1000）。Bessie K （1≤K≤1000，K ）。 ， ， 。 。
Bessie 。 ，Farmer John Bessie ， Bessie K/2 Elsie。 Elsie Bessie ， ， 。
Bessie 。
N K。
N B1,B2,…,BN。
， 。
5 4
3 6 8 4 2
8
1-3 K≤10。
4-10 。
Bessie 2 6
3 4
4 4
4 ， 8 。
問題を解く構想.
この問題の解き方は欲張りだ.各バスケットのベリー数を直接列挙して並べ替えを判断すればいい.時間的複雑度はO(maxi=1 nb i⋅n logn 2)O(max_{i=1}^{n}{b_i}cdot nlog_n^2)O(maxi=1 nbi⋅nlogn 2)である.
得点状況
試合は60,60点で、変更後は満点です.
第二題:L o a n Loan Loan R e p a y m e n t Repayment Repayment
タイトル
Farmer John Bessie N （1≤N≤10^12）。 K Bessie。 ， 。 ， ， Bessie M （1≤M≤10^12）。
Farmer John Bessie 。 X。 ：
（1） Farmer John Bessie G ， (N−G）/X 。 Y。
（2） Y M， Y M。
（3） Bessie Y 。
X ， Farmer John K Bessie N （1≤K≤10^12）。
， N、K M， K⋅M<N。
64 （ ，C/C++ “long long”）。
X， Farmer John Bessie N 。
10 3 3
2
1-3 K≤10^5。
4-10 。
， X=2 Farmer John Bessie 5 ， Bessie M=3 。
解題方法
この問題の方法は二分答え+数学です.
30～30%のデータの場合:
私たちは答えを二分して、k k k日を直接シミュレートすればいいです.時間的複雑度はO(k logn 2)O(klog_n^2)O(klogn 2)である.
100,100%のデータの場合:
私たちは2点の答えx x xを求めて、上の方法を最適化します.その日に与える牛乳の数をy y yと仮定すると、合計a a日連続で同じ数を与えるが、g g個の牛乳がまだ与えられておらず、t t t t日残って牛乳を与える.では,a番目のa a a日にy y個の⌊g−(a−1)y x⌋=y
簡略化1 1 1式
下取整を外してg−(a−1)y x≧yfrac{ g−(a−1)y}{x}{x}geq y xg−(a−1)y≧y両側にx x xを同時に乗じてg−(a−1)y≧xy{g−(a−1)y}geq xy g−(a−1)y}geq xy g−(a−1)y≧xy両側をy y yで同時に除算し、g y−(a−1)≧xfrac{ g}−(a−1)geq x yg−(a−1)≧x≧xx x x x yg−(a−1)≧x≧xx x x x yg−(a−1)≧x(a−1)≧x x x x x xかっこを外し、得られたg y−a+1≧xfrac{g}{y}−a+1geq x yg−a+1≧xはa a aに関する式を整理し,得られたg y−x+1≧afrac{g}{y}−x+1geq a yg−x+1≧a
簡略化2 2 2式
下取りを行い、g−a y x
整理1 1 1と2 2式
2つの式を組み合わせて、g y−x
したがって,ブロック計算,すなわちa a a aを1回計算するだけで効率が向上する.しかし、a a aは残りの日数t t t tよりも大きく、境界を越える場合があるので、a=min(⌊g y−x+1⌋,t)a=min(lfloorfrac{g}{y}−x+1rfloor,t)a=min(⌊yg−x+1⌋,t)
g g gからa a a a aにy yを乗じて残りの牛乳数を得、t t tからa a a a aを減算して残りの日数を得るだけです.注意:上記の演算はy>my>my>mに限られます.y<=my<=my<=mであれば、残りのすべてを直接持ち去るべきである.すなわち、g gからy y y yを差し引いてt t tを乗じ、t=0 t=0 t=0とする.この問題はこのように解決され,時間的複雑度はO(n logn 2)O(sqrt{n}log_{n}^{2})O(n logn 2)程度であり,n≦1 0 12 nleq 10^{12}n≦1012のデータを通過できる.
得点状況
試合で満点をとる.
第三題:W o r m h o l e Wormhole Wormhole S o r t Sort Sort
タイトル
Farmer John 。 ， 。
， ，Farmer John N 1…N （1≤N≤10^5）， N 1…N ， i pi。 M 1…M （1≤M≤10^5）， i ai bi， wi（1≤ai,bi≤N,ai≠bi,1≤wi≤10^9）。
， 。 ， 1≤i≤N， i i。
。 。 。
N M。
N p1,p2,…,pN。 p 1…N 。
1 M i， i+2 ai、bi wi。
， 。 ， −1。
4 4
3 2 1 4
1 2 9
1 3 7
2 3 10
2 4 3
9
1-5 N,M≤1000。
6-10 。
9 ：
1 2 。
1 3 。
2 3 。
解題方法
この問題は私たちが直接使ってセットを調べればいいです.地図を作成し、連通を判断するために、集計を使用することができます.時間的複雑度はO(n logn 2)O(nlog_n^2)O(nlogn 2)であり、この複雑度はソートの複雑さであることに注意する.
得点状況
試合は50分50分で、問題を変えて満点です.