2020.02.03【NOIP普及組】シミュレーションC組

44702 ワード
試合をする
0【10.5 NOIP普及シミュレーション】sort(sort.pas/cpp)1【10.5 NOIP普及シミュレーション】sum(sum.pas/cpp)2【10.5 NOIP普及シミュレーション】count(count.cpp/pas)3【10.5 NOIP普及シミュレーション】ranking(ranking.pas/cpp)
T1
タイトルの説明
   x  y    。 y     ，    GPA（    ）     。      N    ，         GPA，       ，   GPT = GPA ×     。 x     y    ，  y      ：     GPA          K     。       ，      ：

               GPT（      ），         。      y      K       GPA    。

入力
  1  2     N, K。

  2- (N + 1)  ，   1        1    ，     GPT        。

  ：          [1, 250]    。

しゅつりょく
  1  1    ，      K     GPA，   2      。

サンプル入力
5 3

73 20

79.8 21

72.6 22

85.1 23

65.7 18

サンプル出力
3.65

データ範囲の制限
   50%    ：1 ≤ N ≤ 100。

   100%    ：1 ≤ K ≤ N ≤ 100000，GPT        1  ，GPA    4.0。

データが少し水なのか、速い列が通るのか分からないが、配列が大きくなっていないので...
#include
#include
using namespace std;
int m,n,k,num;
int y[1000000];
double x[1000001],z[1000100],f[10000100];
void up(int x){
	int x1=x/2;
	while(f[x1]<f[x]&&x1>=1){
		double t=f[x1];
		f[x1]=f[x];
		f[x]=t;
		x=x1;
		x1=x/2;
	}
}
void down(int x){
	int x1=x*2,y1=x*2+1;
	while((f[x]<f[x1]&&x1<=num)||(f[x]<f[y1]&&y1<=num)){
		double t=f[x1];
		int q=x1;
		if(f[y1]>f[x1]&&y1<=num){
			t=f[y1];
			q=y1;
		}
		f[q]=f[x];
		f[x]=t;
		x=q;
		x1=x*2;y1=x*2+1;
	}
}
int main(){
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
		z[i]=x[i]*1.0/y[i];
	}
	for(int i=1;i<=n;i++){
		num++;
		f[num]=z[i];
		up(num);
	}
	for(int i=1;i<=n;i++){
		z[i]=f[1];
		f[1]=f[num];
		f[num]=0;
		down(1);
	}
	printf("%.2lf",z[m]);
	return 0;
}

T2
テーマ説明小xはキャンディがたくさんあって、Nの山に分かれて、一列に並んでいます.xさんは、yさんがL番目の山からR番目の山まで全部でどれだけのキャンディがあるかを迅速に求めることができれば、これらのキャンディを彼にあげます.
           ，        L   R，      y，           。   ，          y     。

入力
  1  2     N, M,            。

  2  N     Ai，    i        。

  3- (M + 2)  ，   2     Li, Ri，    i      [Li， Ri]。

しゅつりょく
M  ，      ，      。

サンプル入力
5 5

1 2 3 4 5

1 5

2 4

3 3

1 3

3 5

サンプル出力
15

9

3

6

12

データ範囲の制限
   50%    ：1 ≤ N， M ≤ 100。

   100%    ：1 ≤ N，M ≤ 100000，0 ≤ Ai ≤ 10000，1 ≤ Li ≤ Ri ≤ N。

この問題は水接頭辞とACと言わざるを得ない.
#include
#include
using namespace std;
long long m,n,k,a[1000010];
int main(){
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]=a[i]+a[i-1];
	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		cout<<a[y]-a[x-1]<<endl;
	}
	return 0;
}

はい、次は難点に入ります
T3
タイトルの説明
  x          ，         ：     ，    N   M     ，  i    j        (i， j)，   ，        (1， 1)，        (N， M)。     ， y  (1， 1)，      (N， M)。   ， y                 。    ，  y    (x， y)，        (x， y + 1)   (x + 1， y)。  ， y           。

        ，    1~10      。      ，           （            ）。      ：   (N， M)    ，      P 。

                 ，      y，         ，    P        。

入力
  1  3     N, M, P 。

    N  ，   M     Aij ，     (i， j)    。

しゅつりょく
1  1    ，      P      。

      ，           (10^9 + 7)     。

サンプル入力
3 3 9

2 2 1

2 2 2

1 2 2

サンプル出力
2

データ範囲の制限
   50%    ：1 ≤ N， M ≤ 10。

   100%    ：1 ≤ N， M ≤ 100，0 ≤ Aij ≤ 10。

この問題はDPで解決できるi行目j列まで歩いたときのk積分のシナリオ数をf[i][j][k]種とする
#include
#include
using namespace std;
int m,n,k,x,y,p;
long long f[101][101][2001],a[101][101];
int main(){
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
	cin>>n>>m>>p;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	f[1][1][a[1][1]]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=a[i][j];k<=p;k++){
				f[i][j][k]=(f[i][j][k]+f[i-1][j][k-a[i][j]]+f[i][j-1][k-a[i][j]])%1000000007;
			}
		}
	}
	cout<<f[n][m][p];
	return 0;
}

T4
タイトルの説明
 x n    (    ，    n≤3000)。                 (da) (fen)。  ，                。                    ，                       。

     ，                 。

   ， x       ：

                   ，                。

   ， MARTHA MARY     ，    MAR  ，   MARCO MARVIN                ，  MAY      。

   ，                ，         。                 。         ，     mod 1 000 000 007。

入力
       n， x      。

 2~n+1 ，       ，          。

しゅつりょく
      ，      。

サンプル入力
3

IVO

JASNA

JOSIPA

サンプル出力
4

データ範囲の制限
  60%   ：3 ≤ n ≤ 10。

  100%   ：

3 ≤ n ≤ 3000

1 ≤       ≤ 3000，         。

本題:
ツリーDPと乗算(?)でこの問題を解決することができます(私がDFSを打ったのかどうか分かりません)コードで説明します.
#include
#include
#include
using namespace std;
long long m,n,k,x,y,f[100010];
string s[100000];
long long dp(int x,int y,int z){
	if(z>m)return f[y-x+1];//  ，      
	char c=s[x][z];//       
	int j=x,t=1;
	long long ans=1;
	for(int i=x+1;i<=y;i++){
		if(c!=s[i][z]){//       
			t++;//       
			ans=(ans*dp(j,i-1,z+1))%1000000007;//  ，               ，     
			j=i;//    
			c=s[i][z];//    
		}
	}
	if(j!=y)ans=(ans*dp(j,y,z+1))%1000000007;//  ，          
	ans=(ans*f[t])%1000000007;//    
	return ans;
}
void sort1(int l,int r){
	if(l>r)return;
	int i=l,j=r;
	string m=s[r];
	string sw;
	while(i<=j){
		while(s[i]>m)i++;
		while(s[j]<m)j--;
		if(i<=j){
			sw=s[i];
			s[i]=s[j];
			s[j]=sw;
			i++;j--;
		}
	}
	sort1(l,j);
	sort1(i,r);
}
int main(){
	freopen("ranking.in","r",stdin);
	freopen("ranking.out","w",stdout);
	f[0]=1;
	for(int i=1;i<=3000;i++){
		f[i]=(f[i-1]*i)%1000000007;
	}
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		long long df=s[i].size();
		m=max(m,df);
	}//  ，         
	for(int i=1;i<=n;i++){
		for(int j=s[i].size()+1;j<=m;j++)
		s[i]=s[i]+' ';
	}//    （      ）
	sort1(1,n);//     STL
	cout<<dp(1,n,0);//??
	return 0;
}
書かれたnode RSS爬虫類を共有し、主な実装プロセスを共有します.