2020.02.09【NOIP普及組】アナログC組

45282 ワード
試合をする
0
【普組シミュレーション試合】マノン(farmer.pas/cpp)
1
【普組シミュレーション試合】馬語翻訳(trans.pas/cpp)
2
【一般模擬試合】馬球試合(polo.pas/cpp)
3
【普及シミュレーション】数列(sequence.pas/cpp)
T1
タイトルの説明
                ，               “  ”，      。
             ，        ，   N*N          ，        ，                    。                 。
        ，             。  ，          ，           ，             ，       。  ，                  ，              。
        ，           ，          ，          。

入力
        N，           N*N。
    N  ，   N     A(i,j)，    i    j          。
（  ：       ，        ，              。）

しゅつりょく
                。

サンプル入力
3
1 2 3
4 5 6
7 8 9

サンプル出力
2

【様式解釈】
データ範囲の制限
【    】
40%   ， N<=10。
100%   ， N<=50, -1000

O(N^4) 
#include
#include
#include
using namespace std;
long long f[2001][2001],a[2001][2001],d[5000001],n,ans;
int main(){
	freopen("farmer.in","r",stdin);
	freopen("farmer.out","w",stdout);
	memset(f,0,sizeof(f));
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++){
		scanf("%lld",&a[i][j]);
		f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];	
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++){
		for(int x=1;x<=i;x++)
		for(int y=1;y<=j;y++)
			d[f[i][j]-f[i][y-1]-f[x-1][j]+f[x-1][y-1]]++;
		for(int x=i+1;x<=n;x++)
		for(int y=j+1;y<=n;y++)
			ans+=d[f[x][y]-f[x][j]-f[i][y]+f[i][j]];
		for(int x=1;x<=i;x++)
		for(int y=1;y<=j;y++)
			d[f[i][j]-f[i][y-1]-f[x-1][j]+f[x-1][y-1]]=0;
		
		for(int x=1;x<=i;x++)
		for(int y=j+1;y<=n;y++){
			d[f[i][y]-f[x-1][y]-f[i][j]+f[x-1][j]]++;
		}
		for(int x=i+1;x<=n;x++)
		for(int y=1;y<=j;y++)
			ans+=d[f[x][j]-f[i][j]-f[x][y-1]+f[i][y-1]];
		for(int x=1;x<=i;x++)
		for(int y=j+1;y<=n;y++)
			d[f[i][y]-f[x-1][y]-f[i][j]+f[x-1][j]]=0;
	}
	printf("%lld",ans);
	return 0;
}

T2
タイトルの説明
             ，           。                   。  ，             ，          。
           M  ，         K           。 ，       ，     1     N        。    ，                 。

入力
          N， K   M，       ，             ，       。
      M  ，   K    。                （    1   N）。

しゅつりょく
           。        ，  -1。

サンプル入力
9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9

サンプル出力
4

【様式解釈】
1-3-6-9    1-5-6-9

データ範囲の制限
【    】
40%    N<=100， 1<=K<=20， M<=40。
100%    1<=N<=100000， 1<=K<=1000， 1<=M<=1000。

dijの板題
#include
#include
#include
using namespace std;
long long dis[100100];
int n,m,k,a[2000][2000];
void spfa(){
	long long f=1;
	memset(dis,0x3f,sizeof(dis));
	dis[1]=1;
	while(f!=0){
		f=0;
		for(int i=1;i<=m;i++){
			long long minn=0x3ffffff,bz=0x3fffffff;
			for(int j=1;j<=k;j++)
				if(dis[a[i][j]]<minn)
				   minn=dis[a[i][j]];
			if(minn==bz)continue;
			for(int j=1;j<=k;j++)
			    if(dis[a[i][j]]>minn+1)
				   dis[a[i][j]]=minn+1,f=1; 
		}
	}
}
int main(){
	freopen("trans.in","r",stdin);
	freopen("trans.out","w",stdout);
	cin>>n>>k>>m;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=k;j++)
            cin>>a[i][j];
    spfa();
    if(dis[n]==dis[0])cout<<-1;
	else cout<<dis[n];
}

T3
タイトルの説明
                   ，        ，              ，        。            。
             ，            ，           。  ，       ，             ，      （                   ，     ）。  ，    ，      ，       。
          ，                  ，             ，             ，         。  ，      2      。

入力
        N，           。
    N           a(i)，    i            。

しゅつりょく
             。

サンプル入力
【     1】

3 1 3 6

【入力サンプル2】
5 4 6 3 8 9

サンプル出力
【     1】

6

【様式解釈】
      3   ，   1     。   2   3        ，   2    ，  6  。

【出力サンプル2】
9

【様式解釈】
     3   ，   2,3,5     。   3    ， 9   。

データ範囲の制限
【    】
20%    2<=N<=100， 1<=a(i)<=10000。
50%    2<=N<=20000。
100%    2<=N<=200000， 1<=a(i)<= 2000000。

f[i]iを人数とする行列数を表す我々はまず最大の数を探し出して、1~maxの中で可能な人数を列挙して、それから私達は繰返しで、2からsqrt(i)まで、iの因数を見つけて、この時2つの可能性があります:1.f[j]+=f[i] 2.jの因数k,f[k]+=f[i]となると事は決する
#include
#include
using namespace std;
long long m,n,k,x,y,f[4000000];
int main(){
	freopen("polo.in","r",stdin);
	freopen("polo.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>k;
		f[k]++;
		m=max(k,m);
	}
	for(int i=1;i<=m;i++){
		if(f[i]!=0)
		for(int j=2;j*j<=i;j++){
			if(i%j==0){
				if(i!=j)f[j]+=f[i];
				if(j*j!=i)f[i/j]+=f[i];
			}
		}
	}
	for(int i=1;i<=m;i++){
		if(f[i]>1)//     
		x=max(f[i]*i,x);
	}
	cout<<x;
	return 0;
}

T4
タイトルの説明
       N   ，                          A，         。

入力
        N,A
    N   ，     N   。

しゅつりょく
    ，       。

サンプル入力
5 1
1 2 3 4 5

サンプル出力
14

データ範囲の制限
    
   60%    N <= 1000
  100%    N <= 100000
        longint   。

%60 
#include
#include
using namespace std;
long long m,n,k,a[1000100],b[1000100];
int main(){
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]-=k;
		b[i]=b[i-1]+a[i];
	}
	k=0;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			if(b[j]-b[i-1]>0)k++;
		}
	}
	cout<<k;
	return 0;
}
ms-classの進化
jQuery学習ノートのjQueryの動画