Educational Codeforces Round 93

38482 ワード
codeforces
A、B、C、Dの4つの問題の問題解
一.A題
A題タイトルリンク
(1)題意:
t組のテストデータがあって、各組のテストデータはn個の数があって、しかもこのn個の数は昇順に入力して、この組のデータの中で3個の数を選ぶことができるかどうかを聞いて、彼らが三角形にまとめることができなくて、3個の数の位置を出力することができて、-1を出力することができません.
(2)問題解:
三角形の特性は、両側の和が第3の辺より大きく、両側の差が第3の辺より小さいことです.したがって,最大の差と残りの最小の数の関係,すなわちa[n]−a[1]とa[2]の関係を直接判断し,a[n]−a[1](3)コード:
#include 
#include 
#include 
#include 
#include 
#include  
#include 
#include 
#include 
#include 
#include

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;

int a[maxn],t,n;

bool check()
{
     
	if(a[n] - a[1] < a[2])
		return true;
	return false;
}

int main()
{
     
	scanf("%d",&t);
	while(t--)
	{
     
		scanf("%d",&n);
		for(int i = 1; i <= n; i++)
			scanf("%d",&a[i]);
		//sort(a+1,a+1+n);
		
		if(check())
		{
     
			printf("-1
");
		}
		else{
     
			printf("%d %d %d
",1,2,n);
		}
	}
	return 0;
}

二.B題
B題タイトルリンク
(1)題意:
tグループのデータを与え、各グループのデータには文字列sがあり、文字列は‘0’と‘1’からなる.AliceとBobはゲームをして、Aliceは先に行って、毎回1以上の任意の長さの連続的な等しい文字を選択することができて、それから除去します:例えば110011、[1,2]->0011を選択することができて、[3,4]->1111を選択するたびに1を選択して、1点をプラスして、すべて最適な戦略を選択する場合、Aliceは最大何点を得ることができますか?
(2)問題解:
インタリーブ選択なので連続する「0」を選ぶのは理性的でない行為であり、これによりBobは一度により多くの「1」を選択させられ、同じBobでもこのような行為はしないので、現在の「1」を選択するたびに最も多くの連続する「1」を選択する.すべての連続する“1”を統計して、それから順番を並べて、交差して選択して、Aliceの最も多く得ることができる点数です.
(3)コード:
#include 
#include 
#include 
#include 
#include 
#include  
#include 
#include 
#include 
#include 
#include

using namespace std;

typedef long long ll;
const int maxn = 1e4 + 10;
const int INF = 0x3f3f3f3f;

int t,a[maxn];

bool cmp(int x,int y)
{
     
	return x > y;
}

int main()
{
     
	scanf("%d",&t);
	while(t--)
	{
     
		memset(a,0,sizeof(a));
		int flag = 0,cnt = 0,ans = 0;
		string str;
		cin>>str;
		for(int i = 0; i < str.size(); i++)
		{
     
			if(str[i] == '1' && flag == 0)
			{
     
				cnt++;
				flag++;
			}
			else if(str[i] == '1' && flag != 0)
			{
     
				flag++;
			}
			else if(str[i] == '0' && flag != 0)
			{
     
				a[cnt] += flag;
				flag = 0;
			}
		}
		if(flag != 0)
			a[cnt] = flag;
			
		sort(a+1,a+1+cnt,cmp);
		
		for(int i = 1; i <= cnt; i++)
		{
     
			if(i % 2 == 1)
				ans += a[i];
		}
		
		printf("%d
",ans);
	}
	return 0;
}

三.C題
C題リンク
(1)題意:
t組のテストデータがあり、各組のデータにはn個の数があり、これらの数は連続的に入力され、各数の大きさは「0」~「9」以内であり、a[l]+a[l+1]......+a[r]=r-l+1を満たすサブ列が何個あるかを尋ねる.
(2)問題解:
まず、ansは、条件を満たす値が連続的に遭遇するたびに、1111->ans=1+2+3+4のような現在の数の累積であることを知っておく必要があります.次に、1より大きい数a[i]に出会うたびに、a[i]-1つの0を前または後ろに探してこそ、条件を満たすことができる.同じ理屈で0に出会ったのも同じだ.したがって、すべての値-1を使用すると、1->0はメンテナンスの接頭辞値に影響を与えません.0->1は、前または後ろに1を見つけて埋める必要があることを意味し、この過程で接頭辞値をメンテナンスします.
(3)コード:
#include 
#include 
#include 
#include 
#include 
#include  
#include 
#include 
#include 
#include 
#include

using namespace std;

typedef long long ll;
const int maxn = 1e2 + 10;

int t,n;

int main()
{
     
	scanf("%d",&t);
	while(t--)
	{
     
		scanf("%d",&n);
		ll k = 0, ans = 0;
		
		map<int,int> sum;
		
		sum[0] = 1;
		
		for(int i = 0; i < n; i++)
		{
     
			char ch;
			scanf(" %c",&ch);
			k += ch - '0' - 1;
			
			ans += sum[k];
			sum[k]++;
			//  sum[k]++       500005     ，            
			//  ans       sum = 0   
		}
		
		printf("%lld
",ans);
	}
	return 0;
}

四.D題
D題リンク
(1)題意:
3つの色の木の棒はそれぞれそれぞれR、G、B対があって、毎回2対の異なる色の木の棒を選んで1つの矩形を構成して、すべて構成することができる矩形の面積の和はいくらですかを聞きます
(2)問題解:
R,G,Bはいずれも200を超えないため,すべての三重forサイクルのdpが満たされているが,以下では各変数と状態遷移方程式を決定する:r[i]:第1色の第i対木棒長g[i]:第2色の第i対木棒長b[i]:第3色の第i対木棒長度dp[i][j][k]:前i対r,前j対g,前k対bの最大値は毎回i>=1&&&j>=1でi,jが取ることができ、dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]+r[i]*g[j]);同様にi>=1&&k>=1とj>=1&&k>=1も同様である.
(3)コード:
#include 
#include 
#include 
#include 
#include 
#include  
#include 
#include 
#include 
#include 
#include

using namespace std;

typedef long long ll;
const int maxn = 2e2 + 10;

ll r[maxn], g[maxn], b[maxn];
ll dp[maxn][maxn][maxn];
int R,G,B;

int main()
{
     
    scanf("%d%d%d",&R,&G,&B);
    
    for(int i = 1; i <= R; i++)
    	scanf("%lld",&r[i]);
    for(int i = 1; i <= G; i++)
    	scanf("%lld",&g[i]);
    for(int i = 1; i <= B; i++)
    	scanf("%lld",&b[i]);

    sort(r+1, r+1+R);
    sort(g+1, g+1+G);
    sort(b+1, b+1+B);

    for(int i = 0; i <= R; ++i){
     
        for(int j = 0; j <= G; ++j){
     
            for(int k = 0; k <= B; ++k){
     
                if(i&&j)
					dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k] + r[i]*g[j]);
                if(j&&k)
					dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1] + g[j]*b[k]);
                if(i&&k)
					dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k-1] + r[i]*b[k]);
            }
        }
    }

    printf("%lld
",dp[R][G][B]);

    return 0;
}
【メモ】楽に最新の無料アセットをチェックする魔法の言葉？
【Unity】キャンディー(アイテム)とキャラクター衝突時に発生するOnTriggerEnterイベント