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

38834 ワード
試合をする まだわからない
タイトル番号
見出し
0
雄鶏が鳴く(rooster)
1
ひよこを救う
2
雌鶏が卵を産む
3
鶏国福祉(kingdom)
T1:
タイトルの説明
               G1   G2，                 。    ，G1        ，     x，G2    G1          ，     y。G1   G2                  。        k    ，                         （           0）。G1   G2     ，          s(s≤k)    ，             。     G1   G2                           （     s）？
  ：   x        y，      。

入力
    k+1  。
  1       x，y   k，     G1、G2             ，     k              。
    k  ，     4     ai，xi，bi，yi，    i     G1   （ai   1）   （ai  -1）      xi，G2   （bi   1）   （bi  -1）     yi。

しゅつりょく
   1      ，             G1   G2           。     k           ，   “-1”（      ）。

サンプル入力
Input1:

2 3 3
1 1 -1 0
-1 1 1 1
1 1 -1 1

Input2:

2 3 4
1 2 -1 2
-1 1 1 1
-1 4 1 1
1 4 1 1

Input3:

2 3 1
1 2 -1 2

サンプル出力
Output1:

1

Output2:

4

Output3:

-1

データ範囲の制限
  
Sample1:
    1  ，G1   G2   1            2   3，   。  1     G1    1，G2    0，       3   3，     1                   。   3     ，           ，      1        。

Sample2:
    2  ，G1   G2   1            2   3，   。  1               4   1，  2               3   2，  3               0（     0）  3，  4               4   4,      4                 。

Sample3:
    3  ，G1   G2   1            2   3，   。  1     G1    2，G2    2，       4   1，     1                     ，   “-1”。

この問題はとても簡単だ.
#include
#include
using namespace std;
long long x,y;
int k;
int ans,f;
int main(){
	freopen("rooster.in","r",stdin);
	freopen("rooster.out","w",stdout);
	cin>>x>>y>>k;
	if(x==y){
		ans=0;
		f=1;
	}
	int i=0;
	while(k--){
		i++;
		int ai,xi,bi,yi;
		scanf("%d%d%d%d",&ai,&xi,&bi,&yi);
		if(ai==1){
			x+=xi;
		}
		else{
			x-=xi;
		}
		if(bi==1){
			y+=yi;
		}
		else{
			y-=yi;
		}
		if(x<0)x=0;
		if(y<0)y=0;
		if(x==y&&f!=1){
			f=1;
			ans=i;
		}
	}
	if(f==0)cout<<-1;else
	cout<<ans;
	return 0;
}

T2:
タイトルの説明
               ，            。        ，           n  ，  i         ti(1≤i≤n)    。
              ，        （         ）   。              t  。              x             。             ：
（1）              。   0       0       （       ）           ，                。
（2）   1        。  i         ，   i+1   i+t          。
         ，                              ？

入力
    2  。
  1        n，t，x，            ，           ，                     。
  2   n             ti(1≤i≤n)，    ti          。

しゅつりょく
   1      ，                       n    ，              ，  “-1”（      ）。

サンプル入力
Input1:

3 3 3
2 3 4

Input2:

1 2 3
3

サンプル出力
Output1:

5

Output2:

-1

データ範囲の制限
ヒント
Sample1:
   1  ，      3  ，     2，3，4    ，           3  ，            3             。      -1，0，1              ，      2       ，      2          ，    0，1           （   -1             ）         3       ，     3          ，    1，2           （    0              ）         4       ，         5    。

Sample2:
   2  ，      1  ，   3    ，           2  ，             3             ，           ，           ，  “-1”。

この問題も簡単ですが、後ろから探すときはdowntoを使うことを覚えています.
var
i,j,k,m,n,ans,sum:longint;
b:array[-20000..20000]of longint;
a:array[1..20000]of longint;
begin
    assign(input,'chicken.in');
    assign(output,'chicken.out');
    reset(input);
    rewrite(output);
    read(n,m,k);
    for i:=1 to n do read(a[i]);
    if(k>m)then
    begin
        write(-1);
        close(input);
        close(output);
        exit;
    end;
    for i:=1 to n do
    begin
        sum:=0;
        for j:=a[i]-m to a[i]-1 do
        if(b[j]=1)then inc(sum);
        if(sum<k)then
        begin
            for j:=a[i]-1 downto a[i]-m do
            if(b[j]=0)then
	    begin
                b[j]:=1;
                inc(ans);
                inc(sum);
                if(sum=k)then break;
            end;
        end;
    end;
    write(ans);
    close(input);
    close(output);
end.

T3:
タイトルの説明
            ，MGMG                      。
        n             “    ”，          1  n。               ，    i             ci。     MGMG                      ，               ，                   ，  MGMG     ，        ，   “    ”     “         ，            ！”。
             ，       MGMG          (     )，         。

入力
    2  。
  1         n   t，  “    ”  n         ，MGMG        t    。
  2   n      ci(1≤i≤n)，      i            ci 。

しゅつりょく
   1           。          MGMG                  。  MGMG                  ，MGMG       ，    “Angry”（      ，     ）。

サンプル入力
Input1:

5 4
1 2 1 2 3

Input2: 
3 9
3 3 3

Input3: 
3 5
1 2 1

サンプル出力
Output1:

2

Outupt2:

3

Output3:

Angry

データ範囲の制限
ヒント
Sample1:
   1  ，  5    ，        1，2，1，2，3。MGMG       1，2，3       4   ，    3    ，     4     5         4   （  1       ），        2  。
  ：    2     4       ，            。 

Sample2:
   2  ，  3    ，        3，3，3，MGMG      3            3   ，        9   。

Sample3:
   3  ，             MGMG     ，     MGMG      ，  “Angry”。

この問題も簡単で,単調な行列の思想で
#include
#include
using namespace std;
int m,n,k,x,y,a[1001000];
int main(){
	freopen("hen.in","r",stdin);
	freopen("hen.out","w",stdout);
	cin>>n>>m;
	k=2147483647;
	int j=1;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		x=x+a[i];
		y++;
		while(x>=m){
			k=min(y,k);
			x-=a[j];
			y--;
			j++;
		}
	}
	if(k==2147483647)cout<<"Angry";
	else cout<<k;
	return 0;
}

T4:
タイトルの説明
                      ，        n              1     2  “  ”（       ）    。              ，           ，          。
                                   （      ），  i          ai 。    i         1   ，     ai  “  ”，     2   ，      2×ai “  ”，        ，  i          。
                  ，   i                 
       ：
（1）                m  。
（2）                        。
                    ，            n                      ?

入力
    2  。
  1         n   m，         （          ）        。
  2   n      ai(1≤i≤n)，      i         “  ”  ai 。

しゅつりょく
   1      ，               。

サンプル入力
Input1:

2 1
2 1

Input2:

3 2
1 2 3

Input3:

6 4
1 2 1 2 1 5

サンプル出力
Output1:

2

Output2:

3

Output3:

3

データ範囲の制限
ヒント
Sample1:
   1  ，     1        1     2  （1  ），  2        2     2  （2  ），      2       。

Sample2:
   2  ，           2  ，    1              。     1        1     2  （2  ），  2        2     2  （1  ），  3        3     3  （1  ），      3       。

Sample3:
   3  ，           4  ，    1  ，  3  ，  5           1   ，    2   ，           。     2        2    4  （2  ），  4        4     4  （2  ），  6        6     5  （1 ），      3       。

この問題は簡単ではありませんが、nlognの最長のサブシーケンスを学んだ人には簡単になります.しかし、なぜi=1のときだけa[i]*2がa[i]変更後に変更できるのか分からないところがあります.よろしくお愿いします
#include
#include
using namespace std;
int m,n,k,x,y,a[1001000],f[1001000];
int rf(int l,int r,int g){
	int ans=0;
	while(l<=r){
		int mid=(l+r)/2;
		if(f[mid]>g)r=mid-1,ans=mid;
		else l=mid+1;
	}
	return ans;
}
int main(){
	freopen("kingdom.in","r",stdin);
	freopen("kingdom.out","w",stdout); 
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++){
		if(a[i]>=m){
			if(a[i]>=f[x]){
			   	x++;
				f[x]=a[i];
	    	}
			else{
				int j=rf(1,x,a[i]);
				f[j]=a[i];
			}
		}
		if(a[i]*2>=m){
			if(a[i]*2>=f[x]&&(a[i]<f[x]||i==1)){
			   	x++;
				f[x]=a[i]*2;
	    	}
			else{
				int j=rf(1,x,a[i]*2);
				f[j]=a[i]*2;
			}
		}
	}
	cout<<x;
	return 0;
}
自己責任でPHP7のcount()関数を改造してエラー抑制する
php接続mssqlのいくつかの関連経験と注意事項