NOIP 2003年普及グループ問題解
これは最初の問題です.https://www.luogu.org/problemnew/show/P1042まず、問題を解く前に二つの点に注意しなければならない.「E」はテキストの末尾に現れるとは限らないし、ある行の末尾に現れるとは限らない.試合は2つのボールをリードしなければならない.11:10のスコアは存在しないほうがいい.くだらないことは言わないで、直接コードをつけなければならない.
ここでは2番目の問題です.https://www.luogu.org/problemnew/show/P1043定義f[0/1][i][j][k]は左端点がiで、右端点がjで、k個の部分に分かれた最大/最小積が最初にこの問題を5層ループし、内層がブレークポイントとブレークポイントの両側をそれぞれ何個の部分に分けたかを列挙したことを示す...その後(抄題解)は、実は列挙両側で何個の部分に分けられていないことを発見し、これは、前または後のループによって列挙されるので、例えば、左端点がiであれば、右端点がjであり、ブレークポイントがkであり、左がp個の部分に分かれ、右がq個の部分に分かれている.もちろん、ここで必要なのは五重サイクルで、タイムアウトのリスクがあります.だから、最後のグループ数がどこから始まったのかを考えるだけでいい.理屈を言い終わったら、直接暴力的にコードをつけて~~~
P.Sという問題は少し気まずいですが、私は模擬試合をしている間に元のプログラムを盗んで、先生に見られました.これが初めてで、最後であることを願っています.△学生たちは決して私のように、試験の時に物をめくってはいけない.逆に、試験が終わったら、自分が理解していない問題をあらゆる方法で理解し、本末転倒してはいけない...
さて、本題に戻り、3題目に入ります.https://www.luogu.org/problemnew/show/P1044
正直に言うと、この問題は2番目の問題よりずっと簡単で、普通のカトランの数で、カトランの数に対して、みんなはきっとすべて熟知しているのは更に熟知することができなくて、直接暴力の上でコード~~~
#include
#include
#include
#include
#include
using namespace std;
const int maxN=100100;
string s[maxN];
int a[maxN],b[maxN],a2[maxN],b2[maxN];
int n=1,t=1,t2=1;
bool check(int x)
{
int t=s[x].size();
for(int i=0;iif(s[x][i]=='E')return 0;
return 1;
}
int main()
{
freopen("table.in","r",stdin);
freopen("yable.out","w",stdout);
cin>>s[n];
while(check(n)){
n++;
cin>>s[n];
}
for(int i=1;i<=n;i++){
int lenth=s[i].size();
for(int j=0;jif(s[i][j]=='E'){
for(int i=1;i<=t;i++)
cout<":"<cout<for(int i=1;i<=t2;i++)
cout<":"<return 0;
}
if(s[i][j]=='W')
a[t]++,a2[t2]++;
else if(s[i][j]=='L')
b[t]++,b2[t2]++;
if((a[t]>=11||b[t]>=11)&&abs(a[t]-b[t])>=2)
t++;
if((a2[t2]>=21||b2[t2]>=21)&&abs(a2[t2]-b2[t2])>=2)
t2++;
//ここは2 リードしてこそ つことに
}
}
return 0;
}
ここでは2番目の問題です.https://www.luogu.org/problemnew/show/P1043定義f[0/1][i][j][k]は左端点がiで、右端点がjで、k個の部分に分かれた最大/最小積が最初にこの問題を5層ループし、内層がブレークポイントとブレークポイントの両側をそれぞれ何個の部分に分けたかを列挙したことを示す...その後(抄題解)は、実は列挙両側で何個の部分に分けられていないことを発見し、これは、前または後のループによって列挙されるので、例えば、左端点がiであれば、右端点がjであり、ブレークポイントがkであり、左がp個の部分に分かれ、右がq個の部分に分かれている.もちろん、ここで必要なのは五重サイクルで、タイムアウトのリスクがあります.だから、最後のグループ数がどこから始まったのかを考えるだけでいい.理屈を言い終わったら、直接暴力的にコードをつけて~~~
#include
#include
using namespace std;
const int maxN=0x7fffffff;
int n,m,maxn,minn=maxN;
int qzh[105];
int val[105];
int f[2][105][105][15];
int mod(int x){
return (x%10+10)%10;
}
void prepare()
{
for(int i=1;i<=(n<<1);i++)
qzh[i]=qzh[i-1]+val[i];
for(int i=1;i<=(n<<1);i++)
for(int j=i;j<=(n<<1);j++)
f[0][i][j][1]=f[1][i][j][1]=mod(qzh[j]-qzh[i-1]);
for(int i=2;i<=m;i++){
for(int l=1;l<=(n<<1);l++){
for(int r=l+i-1;r<=l+n-1;r++){
f[1][l][r][i]=maxN;
for(int k=l+i-2;k0][l][r][i]=max(f[0][l][r][i],f[0][l][k][i-1]*mod(qzh[r]-qzh[k]));
f[1][l][r][i]=min(f[1][l][r][i],f[1][l][k][i-1]*mod(qzh[r]-qzh[k]));
}
}
}
}
for(int i=1;i<=n;i++){
maxn=max(maxn,f[0][i][i+n-1][m]);
minn=min(minn,f[1][i][i+n-1][m]);
}
}
int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w"mstdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>val[i];
val[i+n]=val[i];
}
prepare();
cout<return 0;
}
P.Sという問題は少し気まずいですが、私は模擬試合をしている間に元のプログラムを盗んで、先生に見られました.これが初めてで、最後であることを願っています.△学生たちは決して私のように、試験の時に物をめくってはいけない.逆に、試験が終わったら、自分が理解していない問題をあらゆる方法で理解し、本末転倒してはいけない...
さて、本題に戻り、3題目に入ります.https://www.luogu.org/problemnew/show/P1044
正直に言うと、この問題は2番目の問題よりずっと簡単で、普通のカトランの数で、カトランの数に対して、みんなはきっとすべて熟知しているのは更に熟知することができなくて、直接暴力の上でコード~~~
#include
#include
using namespace std;
int n,f[20][20];
void prepare()
{
for(int i=1;i<=n;++i){
f[i][0]=1;
for(int j=1;j<=i;++j){
f[i][j]=f[i-1][j]+f[i][j-1];
}
}
}
int main()
{
freopen("stack.in","r",stdin);
freopen("stack.out","w",stdout);
cin>>n;
prepare();
cout<