NOIP 2016シミュレーション試合[南開題]問題解&まとめ
5656 ワード
今回の試合はよくできたのに、第二題は少なくとも60点に加えて220点だったのに、残念ながらlonglongの2000000配列を運転していたので、結局空間が超えてしまった......腹が立った.
次回はぜひ空を観察してみましょう!間!制限!作る!勝手に運転しないで!
1.ハノータ+
(han.pas/c/cpp)
【問題の説明】
易さんは最近ハノタに興味を持っています.ハンロタゲームには柱が3本あり、n個の皿があり、皿は柱に串刺しできるが、大皿は小皿の上に置くことができない.各ステップは、1本の柱の上部の皿を別の柱の上部に移動することができます.
易さんは、i番目の小さな円盤がa[i]番目の柱にある場合、少なくともどのくらいのステップで3番目の柱にすべて移動する必要があるかを知りたいと思っています.
【入力】
1行目の整数nは、円盤の個数を表す.
2行目のn個の整数a[i],i番目の小さな円盤はa[i]番目の柱(a[i]=1または2または3)にある.
【出力】
最小ステップ数を表す整数は1行1個のみです.(解答型100000007)
【入出力サンプル】
han1.in
han1.out
3 1 1 1
7
han2.in
han2.out
5 3 1 2 2 1
18
【データ範囲】
30%データの場合、1<=n<=10
100%データの場合、1<=n<=1000000
最も簡単なハンノッタ問題(すべての皿が1番柱にある)を考えると、私たちは再帰的に作ったので、この問題は再帰的に作ることもできます.
最大の皿について、3番目の柱にあれば、私たちは彼を動かさず、他のN-1の皿について議論を続けます.
もし彼が2番目の柱にいたら、私たちはそれを3番目の柱に移動する必要があります(1歩)、この時他の彼より小さいものを2番の柱に移動する必要があります(2^(n-1)-1歩)、そのため総歩数は2^(n-1)歩です
他の柱に対してこのように押して、最後に境界を判断すればいいのです
2.逆順序ペア+
(ni.pas/c/cpp)
n個の数のシーケンスA 1,A 2,…,Anについて.
定義数対(Ai,Aj)は、逆シーケンス対+当であり、i 2*Ajのみである.
逆順序ペア+の個数を計算します.
【入力】
1行目、1つの数nは、シーケンスの長さを表す.
2行目、n個目A 1,A 2,...,An.
【出力】
逆順対+の個数を表す1行1個の数のみ
【出力サンプル】
ni1.in
ni1.out
5 9 3 5 3 1
6
ni2.in
ni2.out
14 7 19 11 10 2 18 14 5 8 17 9 3 19 16
20
【データ範囲】30%のデータに対して、1<=n<=100
100%のデータに対して、1<=n<=200000、Aiはintの範囲内である.
明らかに普通の木状の配列は逆の順序を求めてすべてのデータに対してきっとよくありません(親測60分)
しかし、私たちは離散化すれば済む......まるで
3.食いしん坊の悩み
(chi.pas/c/cpp)
【問題の説明】
ある食べ物はnバレルのカップラーメンがあって、カップラーメンは異なる味があって、異なる小文字で異なる味を表します.
彼は一度にその中の連続したいくつかのバケツしか食べられず、kバケツを食べたとした.このkカップラーメンの味の中で最も多く出た味の数から、最も出た味の数を減算する値を定義します(味の出た回数に応じて>=1).
一度食べる最大の美味しさはいくらなのか知りたいです.
【入力】
1行目、整数nで、nバケツラーメンがあることを示します.
2行目、n個の小文字で、カップラーメンの味を表します.
【出力】
1行1個の整数しかなく、1回食べる最大の美味しさを表します.
【出力サンプル】
chi1.in
chi1.out
9 abbaaabab
3
chi2.in
chi2.out
13 cccaaccbcbbbc
5
【サンプル説明】
赤色は、食べられたサンプル1:abbaaababサンプル2:cccaaccbcbbbc【データ範囲】30%のデータに対して、1<=n<=100が60%のデータに対して、1<=n<=10000が100%のデータに対して、1<=n<=1000000
それぞれの味に接頭辞和を求めると、sum[i][j]はi位までにj番目の味が何回現れたかを示す.
1、O(26*n*n)
食べる区間の左端点lと右端点rを列挙し,それぞれの味kを列挙し,出現する味の中で最も出現回数の多い味の数max{sum[r][k]−sum[l−1][k]}と出現回数の最も少ない味の数min{sum[r][k]−sum[l−1][k],ans=max{sum[r][j]−sum[l−1][j]−min{sum[r][k]−sum[l−1][k]}を得た.
2、O(26*26*n)
ある2つの味がそれぞれ出現回数が最も多い味jと出現回数が最も少ない味kであると仮定し、それらを列挙し、それから食べる区間の右端点rを列挙し、minで表す!!この2つの味のカップラーメンが出てきたとき!!sum[i][j]-sum[i][k](1<=i<=r)の最小値、ans=max{ans、sum[r][j]-sum[r][k]-min}です.
3、O(26*n)
食べる区間の右端点rを列挙し、sum[i][j]-sum[i][k]の最小値をmin[j][k]で表し(1<=i<=r、0<=j、k<26)、Min[j][k]はsum[i][j]-sum[i][k]の最小値を表す(1<=i<=kが最後に現れる位置、0<=j、k<26).
jをr位の味とし,kを他の25種類の味とし,r−1位からr位まで出現回数が最も多い味がjの場合にのみ答えを大きくするのでans=max{ans,sum[r][j]−sum[r][k]−min[j][k]}である.
最後にもう一言言います.
問題を作る時は必ず大体消費するメモリを計算して、メモリを超えないでください、むやみにLLを開けないでください!
次回はぜひ空を観察してみましょう!間!制限!作る!勝手に運転しないで!
1.ハノータ+
(han.pas/c/cpp)
【問題の説明】
易さんは最近ハノタに興味を持っています.ハンロタゲームには柱が3本あり、n個の皿があり、皿は柱に串刺しできるが、大皿は小皿の上に置くことができない.各ステップは、1本の柱の上部の皿を別の柱の上部に移動することができます.
易さんは、i番目の小さな円盤がa[i]番目の柱にある場合、少なくともどのくらいのステップで3番目の柱にすべて移動する必要があるかを知りたいと思っています.
【入力】
1行目の整数nは、円盤の個数を表す.
2行目のn個の整数a[i],i番目の小さな円盤はa[i]番目の柱(a[i]=1または2または3)にある.
【出力】
最小ステップ数を表す整数は1行1個のみです.(解答型100000007)
【入出力サンプル】
han1.in
han1.out
3 1 1 1
7
han2.in
han2.out
5 3 1 2 2 1
18
【データ範囲】
30%データの場合、1<=n<=10
100%データの場合、1<=n<=1000000
最も簡単なハンノッタ問題(すべての皿が1番柱にある)を考えると、私たちは再帰的に作ったので、この問題は再帰的に作ることもできます.
最大の皿について、3番目の柱にあれば、私たちは彼を動かさず、他のN-1の皿について議論を続けます.
もし彼が2番目の柱にいたら、私たちはそれを3番目の柱に移動する必要があります(1歩)、この時他の彼より小さいものを2番の柱に移動する必要があります(2^(n-1)-1歩)、そのため総歩数は2^(n-1)歩です
他の柱に対してこのように押して、最後に境界を判断すればいいのです
#include
#include
#define LL long long
using namespace std;
const LL maxn=1e6+5,inf=0x3f3f3f3f,mod=1000000007;
inline void _read(LL &x){
char t=getchar();bool sign=true;
while(t'9')
{if(t=='-')sign=false;t=getchar();}
for(x=0;t>='0'&&t<='9';t=getchar())x=x*10+t-'0';
if(!sign)x=-x;
}
LL n,s[maxn];
LL MG(LL a,LL b){
LL ans=1;
a%=mod;
while(b){
if(b&1)ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
LL Solve(LL a,LL b,LL c,LL N,LL p[]){
if(N==1)return p[N]!=c;
if(p[N]==c)return (Solve(a,b,c,N-1,p))%mod;
if(p[N]==a)return (Solve(a,c,b,N-1,p)+MG(2,N-1))%mod;
if(p[N]==b)return (Solve(b,c,a,N-1,p)+MG(2,N-1))%mod;
}
int main(){
_read(n);
LL i,j;
for(i=1;i<=n;i++)_read(s[i]);
cout< 2.逆順序ペア+
(ni.pas/c/cpp)
n個の数のシーケンスA 1,A 2,…,Anについて.
定義数対(Ai,Aj)は、逆シーケンス対+当であり、i 2*Ajのみである.
逆順序ペア+の個数を計算します.
【入力】
1行目、1つの数nは、シーケンスの長さを表す.
2行目、n個目A 1,A 2,...,An.
【出力】
逆順対+の個数を表す1行1個の数のみ
【出力サンプル】
ni1.in
ni1.out
5 9 3 5 3 1
6
ni2.in
ni2.out
14 7 19 11 10 2 18 14 5 8 17 9 3 19 16
20
【データ範囲】30%のデータに対して、1<=n<=100
100%のデータに対して、1<=n<=200000、Aiはintの範囲内である.
明らかに普通の木状の配列は逆の順序を求めてすべてのデータに対してきっとよくありません(親測60分)
しかし、私たちは離散化すれば済む......まるで
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define lowbit(xx) (xx&-xx)
using namespace std;
const int maxn=4e5+5,inf=0x3f3f3f3f;
inline void _read(int &x){
char t=getchar();bool sign=true;
while(t'9')
{if(t=='-')sign=false;t=getchar();}
for(x=0;t>='0'&&t<='9';t=getchar())x=x*10+t-'0';
if(!sign)x=-x;
}
int s[maxn],p[maxn],c[maxn],n,N,ans;
void insert(int x,int d){for(int i=x;i<=N;i+=lowbit(i))c[i]+=d;}
int getsum(int x){
int sum=0,i;
for(i=x;i;i-=lowbit(i))sum+=c[i];
return sum;
}
int main(){
_read(n);
int i,j,k;
for(i=1;i<=n;i++){
_read(s[i]);
p[i]=s[i]-1;
p[i+n]=s[i]<<1;
}
N=n<<1;
sort(p+1,p+1+N);
N=unique(p+1,p+1+N)-p;
for(i=n;i;i--){
int a=lower_bound(p+1,p+1+N,s[i]-1)-p;
int b=lower_bound(p+1,p+1+N,s[i]<<1)-p;
ans+=getsum(a);
insert(b,1);
}
cout< 3.食いしん坊の悩み
(chi.pas/c/cpp)
【問題の説明】
ある食べ物はnバレルのカップラーメンがあって、カップラーメンは異なる味があって、異なる小文字で異なる味を表します.
彼は一度にその中の連続したいくつかのバケツしか食べられず、kバケツを食べたとした.このkカップラーメンの味の中で最も多く出た味の数から、最も出た味の数を減算する値を定義します(味の出た回数に応じて>=1).
一度食べる最大の美味しさはいくらなのか知りたいです.
【入力】
1行目、整数nで、nバケツラーメンがあることを示します.
2行目、n個の小文字で、カップラーメンの味を表します.
【出力】
1行1個の整数しかなく、1回食べる最大の美味しさを表します.
【出力サンプル】
chi1.in
chi1.out
9 abbaaabab
3
chi2.in
chi2.out
13 cccaaccbcbbbc
5
【サンプル説明】
赤色は、食べられたサンプル1:abbaaababサンプル2:cccaaccbcbbbc【データ範囲】30%のデータに対して、1<=n<=100が60%のデータに対して、1<=n<=10000が100%のデータに対して、1<=n<=1000000
それぞれの味に接頭辞和を求めると、sum[i][j]はi位までにj番目の味が何回現れたかを示す.
1、O(26*n*n)
食べる区間の左端点lと右端点rを列挙し,それぞれの味kを列挙し,出現する味の中で最も出現回数の多い味の数max{sum[r][k]−sum[l−1][k]}と出現回数の最も少ない味の数min{sum[r][k]−sum[l−1][k],ans=max{sum[r][j]−sum[l−1][j]−min{sum[r][k]−sum[l−1][k]}を得た.
2、O(26*26*n)
ある2つの味がそれぞれ出現回数が最も多い味jと出現回数が最も少ない味kであると仮定し、それらを列挙し、それから食べる区間の右端点rを列挙し、minで表す!!この2つの味のカップラーメンが出てきたとき!!sum[i][j]-sum[i][k](1<=i<=r)の最小値、ans=max{ans、sum[r][j]-sum[r][k]-min}です.
3、O(26*n)
食べる区間の右端点rを列挙し、sum[i][j]-sum[i][k]の最小値をmin[j][k]で表し(1<=i<=r、0<=j、k<26)、Min[j][k]はsum[i][j]-sum[i][k]の最小値を表す(1<=i<=kが最後に現れる位置、0<=j、k<26).
jをr位の味とし,kを他の25種類の味とし,r−1位からr位まで出現回数が最も多い味がjの場合にのみ答えを大きくするのでans=max{ans,sum[r][j]−sum[r][k]−min[j][k]}である.
#include
#include
#include
using namespace std;
const int maxn=1e6+5;
int n,ans;
char s[maxn];
int sum[maxn][26],tempmin[26][26],curmin[26][26];
int main(){
int i,j,k;
scanf("%d%s",&n,s+1);
for(i=1;i<=n;i++)
for (j=0;j<26;j++)
sum[i][j]=sum[i-1][j]+(j==s[i]-'a');
for(i=1;i<=n;i++){
j=s[i]-'a';
for(k=0;k<26;k++){
int t=sum[i][j]-sum[i][k];
if(sum[i][k])ans=max(ans,t-curmin[j][k]);
curmin[k][j]=tempmin[k][j];
tempmin[k][j]=min(tempmin[k][j],-t);
}
}
printf("%d",ans);
} 最後にもう一言言います.
問題を作る時は必ず大体消費するメモリを計算して、メモリを超えないでください、むやみにLLを開けないでください!