Noip 2011問題解レポート
NOIP 2011解題レポート
ラベル(スペース区切り):試験問題まとめ:Day 1-T 1アナログDay 1-T 2記録前駆+観察性質Day 1-T 3探索+剪定Day 2-T 1組合せ数学+高速べき乗Day 2-T 2二分+接頭辞と最適化Day 2-T 3貪欲
備考:性質を観察するのは1種の思考方式で、問題の方法と技巧ではありません!態度です!
Day-1
T 1:カーペットを敷く
データ範囲:30%のデータに対して、n≦2がある.50%のデータに対して、0≦a、b、g、k≦100;100%のデータに対して,0≦n≦10000,0≦a,b,g,k≦100000であった.
ぶぶんぶん
O(n)のアルゴリズム以外に何の方法も思いつかないので、昔からT 1シミュレーション問題(Noip 2017が顔を殴られた)
注意すべき最適化
上のカーペットから下のカーペット(つまり後ろから前へ)を掃き、掃いた最初のカーペットは条件を満たす一番上のカーペット、breakでいいです
コード#コード#
T 2:宿屋の選択
データ範囲:30%のデータに対して、n≦100がある.50%のデータに対して、n≦1000がある.100%のデータに対して,2≦n≦200000,0ぶぶんぶん
30%:O(n^3)は左端点、右端点、さらにO(n)のcheck 50%:O(n^2*logn)またはO(n^2)を列挙し、O(n)のcheckを最適化し、区間最大最小値(線分ツリー、stテーブルともに可能)100%:O(n*k)を事前に処理し、2つの同じ色の宿屋の間に問題を満たすカフェが存在する場合、その後、この宿屋と同じ色のものはすべて答えに計上できることに気づいた.1つのバケツで色ごとの回数と色ごとの合法数を統計すればいいと思います
注目すべきは
合法的なバケツを更新してから色バケツを更新するのは実はこのテーマのデータが強くなくて、O(n^2)は过ごすことができて、ただ1つの优良な性质に気づくだけです"もし2つの同じ色の宿屋の间に1つの题意を満たす吃茶店が存在するならば、后でこの宿屋の色と同じものはすべて解答に计算することができます"すべての色が同じ位置と次の同じ色が現れる位置を記録し、問題を満たす喫茶店を見つけたら、後ろの宿屋の数を直接加えてbreakします.
コード#コード#
ある大物からの問題解報告
同じ色だけが貢献して前の同じ色の位置を記録し、現在条件を満たしている喫茶店が接頭辞と処理すればいいからです.
O(n 2∗k)O(n 2∗k)もAC A C
T 3:Mayanゲーム
データ範囲は30%のデータに対して、初期の碁盤の上のブロックはすべて碁盤の一番下の行にあります.100%のデータに対して、0ぶぶんぶん
30%:せいぜい5つの駒しかないのに、暴力シミュレーションでいいのに、私には100%:まず枝を切ることを話しましょう.要するに、4つの枝を切る原則:(1)2つの色の同じブロックを交換するのは意味がありません(2)1つのブロックの左が非空のブロックである場合、左を考慮する必要はありません.前のブロックと右を繰り返すからです.すなわち左ブロックが空である場合のみ左シフト(3)タイトル優先度のソートにより右シフトが左シフトよりも優先されることが分かるので、dfsにおいて右シフト(4)ある色の現在のブロック数xが1<=x<=2を満たす場合には、この場合が合法的に消滅しない場合には、別の碁盤としてマークすることができ、一旦消滅しない(少なくなった場合を防ぐため)消去できるすべての駒をマークしてから一緒に消去します.
お知らせ
この問題は細部が多くて、掛けやすいので、辛抱強くデバッグしてください.
Day-2
T 1:計算係数
データ範囲は30%のデータに対して、0≦k≦10である.50%のデータに対して、a=1、b=1がある.100%のデータに対して,0≦k≦1000,0≦n,m≦k,n＋m＝k,0≦a,b≦1000000であった.
ぶぶんぶん
50%:いいえ、実はa=1、b=1は裸の楊輝三角です100%:
注目すべきは
コンビネーション数は逆元を要求します!!!コンビネーション数は逆元を要求します!!!コンビネーション数は逆元を要求します!!!(重要なことは3回言う)逆元を求めないと30点に爆発する!
T 2:賢い質監員
データ範囲は10%のデータに対して、1≦n、m≦10である.30%のデータに対して、1≦n、m≦500がある.50%のデータに対して、1≦n、m≦5000がある.70%のデータに対して、1≦n、m≦10000がある.100%のデータに対して,1≦n,m≦200000,0ぶぶんぶん
50%:接頭辞と最適化を使わないでいくつかのカードをプラスしていつも60分ぐらいあるようにしましょう残りの部分は私は100%辛くありません:2分+接頭辞と最適化、毎回2分出た標準値Wに対して1回の接頭辞和を計算して、もし現在のY>Sならば、W分が小さくなったことを説明して、r=mid-1、Y=Sならば、ちょうど
注目すべきは
long longを開いて、それから更に穴があいたのは入力値Sがlong longで、読み込みは最適化してintに打たないでください!
T 3:観光バス
データ範囲は10%のデータに対して、k=0である.20%のデータに対して、k=1;40%のデータに対して,2≦n≦50,1≦m≦1000,0≦k≦20,0≦Di≦10,0≦Ti≦500であった.60%のデータに対して、1≦n≦100、1≦m≦1000、0≦k≦100、0≦Di≦100、0≦T i≦10000;100%のデータに対して,1≦n≦1000,1≦m≦10000,0≦k≦100000,0≦Di≦100,0≦Ti≦100000であった.
ぶぶんぶん
部分的には分けられないので、直接正解(部分的には細部や欲張りな人の分でしょう)正解:加速しながら答えを計算するのは面倒なので、アクセルを使わない答えを算出して加速の時間を減らします.肝心なのはどこで加速器を使うかです...私たちは1つの加速器にできるだけ多くの価値を貢献させ、彼にもっと多くの人に幸福をもたらしなければなりません.この辺を通る人が多いと加速器を使う方がお得です.最も多くの人に影響を与える経路を探すたびに.各ポイントの出発時間は必ず最後の人が到着した時間の後になるので、毎回探すときは、各エッジがどれだけ後ろに影響できるかを計算し、最大値を取って、O(nk)の複雑さを繰り返し計算するのが受け入れられます.
コード#コード#
Thanks for your attention.
ラベル(スペース区切り):試験問題まとめ:Day 1-T 1アナログDay 1-T 2記録前駆+観察性質Day 1-T 3探索+剪定Day 2-T 1組合せ数学+高速べき乗Day 2-T 2二分+接頭辞と最適化Day 2-T 3貪欲
備考:性質を観察するのは1種の思考方式で、問題の方法と技巧ではありません!態度です!
Day-1
T 1:カーペットを敷く
データ範囲:30%のデータに対して、n≦2がある.50%のデータに対して、0≦a、b、g、k≦100;100%のデータに対して,0≦n≦10000,0≦a,b,g,k≦100000であった.
ぶぶんぶん
O(n)のアルゴリズム以外に何の方法も思いつかないので、昔からT 1シミュレーション問題(Noip 2017が顔を殴られた)
注意すべき最適化
上のカーペットから下のカーペット(つまり後ろから前へ)を掃き、掃いた最初のカーペットは条件を満たす一番上のカーペット、breakでいいです
コード#コード#
for(int i=n;i>=1;i--)
{
if(pd(i)) {printf("%d
",i);return 0;}
}T 2:宿屋の選択
データ範囲:30%のデータに対して、n≦100がある.50%のデータに対して、n≦1000がある.100%のデータに対して,2≦n≦200000,0
30%:O(n^3)は左端点、右端点、さらにO(n)のcheck 50%:O(n^2*logn)またはO(n^2)を列挙し、O(n)のcheckを最適化し、区間最大最小値(線分ツリー、stテーブルともに可能)100%:O(n*k)を事前に処理し、2つの同じ色の宿屋の間に問題を満たすカフェが存在する場合、その後、この宿屋と同じ色のものはすべて答えに計上できることに気づいた.1つのバケツで色ごとの回数と色ごとの合法数を統計すればいいと思います
注目すべきは
合法的なバケツを更新してから色バケツを更新するのは実はこのテーマのデータが強くなくて、O(n^2)は过ごすことができて、ただ1つの优良な性质に気づくだけです"もし2つの同じ色の宿屋の间に1つの题意を満たす吃茶店が存在するならば、后でこの宿屋の色と同じものはすべて解答に计算することができます"すべての色が同じ位置と次の同じ色が現れる位置を記録し、問題を満たす喫茶店を見つけたら、後ろの宿屋の数を直接加えてbreakします.
コード#コード#
for(int i=1;i<=n;i++)
{
scanf("%d%d",&se,&mon);
for(int j=0;jif(mon<=p&&color[j])
{
tongji[j]=color[j];
}
}
ans+=tongji[se];
color[se]++;
if(mon<=p)tongji[se]++;
} ある大物からの問題解報告
同じ色だけが貢献して前の同じ色の位置を記録し、現在条件を満たしている喫茶店が接頭辞と処理すればいいからです.
for(int i=1;i<=N;++i)
{
int c=read(),v=read();
if(v<=P)lt=i;
if(pos[c]<=lt)last[c]=sum[c];
ans+=last[c];sum[c]++;pos[c]=i;
}O(n 2∗k)O(n 2∗k)もAC A C
for(rg int i=1;i<=K;i++)
{
b[0]=0;
for(rg int j=head[i];j;j=a[j].next)
{
rg int v=a[j].to;
b[++b[0]]=v;
}
for(rg int j=1;j<=b[0];j++)
{
for(rg int z=j+1;z<=b[0];z++)
{
rg int u=b[z],v=b[j],k=log[v-u+1];
if(min(f[k][u],f[k][v-(1<1])<=P)
{ans+=b[0]-z+1;break;}
}
}
} T 3:Mayanゲーム
データ範囲は30%のデータに対して、初期の碁盤の上のブロックはすべて碁盤の一番下の行にあります.100%のデータに対して、0
30%:せいぜい5つの駒しかないのに、暴力シミュレーションでいいのに、私には100%:まず枝を切ることを話しましょう.要するに、4つの枝を切る原則:(1)2つの色の同じブロックを交換するのは意味がありません(2)1つのブロックの左が非空のブロックである場合、左を考慮する必要はありません.前のブロックと右を繰り返すからです.すなわち左ブロックが空である場合のみ左シフト(3)タイトル優先度のソートにより右シフトが左シフトよりも優先されることが分かるので、dfsにおいて右シフト(4)ある色の現在のブロック数xが1<=x<=2を満たす場合には、この場合が合法的に消滅しない場合には、別の碁盤としてマークすることができ、一旦消滅しない(少なくなった場合を防ぐため)消去できるすべての駒をマークしてから一緒に消去します.
お知らせ
この問題は細部が多くて、掛けやすいので、辛抱強くデバッグしてください.
Day-2
T 1:計算係数
データ範囲は30%のデータに対して、0≦k≦10である.50%のデータに対して、a=1、b=1がある.100%のデータに対して,0≦k≦1000,0≦n,m≦k,n＋m＝k,0≦a,b≦1000000であった.
ぶぶんぶん
50%:いいえ、実はa=1、b=1は裸の楊輝三角です100%:
a=1,b=1から発見することができて、唯一の違いは再楊輝三角の係数の上で更にa^n*b^mを乗じます注目すべきは
コンビネーション数は逆元を要求します!!!コンビネーション数は逆元を要求します!!!コンビネーション数は逆元を要求します!!!(重要なことは3回言う)逆元を求めないと30点に爆発する!
T 2:賢い質監員
データ範囲は10%のデータに対して、1≦n、m≦10である.30%のデータに対して、1≦n、m≦500がある.50%のデータに対して、1≦n、m≦5000がある.70%のデータに対して、1≦n、m≦10000がある.100%のデータに対して,1≦n,m≦200000,0
50%:接頭辞と最適化を使わないでいくつかのカードをプラスしていつも60分ぐらいあるようにしましょう残りの部分は私は100%辛くありません:2分+接頭辞と最適化、毎回2分出た標準値Wに対して1回の接頭辞和を計算して、もし現在のY>Sならば、W分が小さくなったことを説明して、
l=mid+1、Y注目すべきは
long longを開いて、それから更に穴があいたのは入力値Sがlong longで、読み込みは最適化してintに打たないでください!
T 3:観光バス
データ範囲は10%のデータに対して、k=0である.20%のデータに対して、k=1;40%のデータに対して,2≦n≦50,1≦m≦1000,0≦k≦20,0≦Di≦10,0≦Ti≦500であった.60%のデータに対して、1≦n≦100、1≦m≦1000、0≦k≦100、0≦Di≦100、0≦T i≦10000;100%のデータに対して,1≦n≦1000,1≦m≦10000,0≦k≦100000,0≦Di≦100,0≦Ti≦100000であった.
ぶぶんぶん
部分的には分けられないので、直接正解(部分的には細部や欲張りな人の分でしょう)正解:加速しながら答えを計算するのは面倒なので、アクセルを使わない答えを算出して加速の時間を減らします.肝心なのはどこで加速器を使うかです...私たちは1つの加速器にできるだけ多くの価値を貢献させ、彼にもっと多くの人に幸福をもたらしなければなりません.この辺を通る人が多いと加速器を使う方がお得です.最も多くの人に影響を与える経路を探すたびに.各ポイントの出発時間は必ず最後の人が到着した時間の後になるので、毎回探すときは、各エッジがどれだけ後ろに影響できるかを計算し、最大値を取って、O(nk)の複雑さを繰り返し計算するのが受け入れられます.
コード#コード#
for(int i=1;ifor(int i=1;i<=m;++i)
{
T[i]=read();fr[i]=read();to[i]=read();
lst[fr[i]]=max(lst[fr[i]],T[i]);//
down[to[i]]++;//
}
for(int i=2;i<=n;++i)tt[i]=max(tt[i-1],lst[i-1])+d[i-1];
for(int i=1;i<=n;++i)ss[i]=ss[i-1]+down[i];
for(int i=1;i<=m;++i)ans+=tt[to[i]]-T[i];
us[n]=us[n-1]=n;//
tt[1]=lst[1];
while(k--)
{
for(int i=2;i<=n;++i)
tt[i]=max(tt[i-1],lst[i-1])+d[i-1];//
for(int i=n-2;i;--i)
us[i]=tt[i+1]<=lst[i+1]?i+1:us[i+1];
nn=mm=0;
for(int i=1;iif(ss[us[i]]-ss[i]>nn&&d[i])
{
nn=ss[us[i]]-ss[i];
mm=i;
}
}
ans-=nn;d[mm]--;
} Thanks for your attention.