Educational Codeforces Round 79(Rated for Div.2)——B.Verse For Santa,C.Stack of Presents概要

タイトル転送ゲート:https://codeforces.com/contest/1279/problem/Bタイトル転送ゲート:https://codeforces.com/contest/1279/problem/C
テーマ:
B.Verse For Santa:サンタクロースにn段の詩を歌うには、各段に時間がかかりますが、サンタクロースはs分を辛抱強く聞くしかありません.そして、詩を歌うには順序があり、その中の1段をスキップするしかありません.サンタクロースに最大何段の詩を歌うことができますか?C.Stack of Presents:スタック内の贈り物を1~n、上部番号a 1、次はa 2、下部はanであり、各番号は一意である.プレゼントを送るリストを提供します.番号はb 1、b 2、...bnです.サンタクロースは番号順にプレゼントを送らなければなりません.毎回プレゼントを送ります.スタックからプレゼントを探します.このプレゼントを持っていくには、まずこのプレゼントの前のプレゼントを持って行かなければなりません.もしこのプレゼントの前にkつのプレゼントがあれば、2 k+1秒かかります.そして、順番を作ってからスタックに戻します.リストのプレゼントを送るのにかかる最短時間を聞いてください.
構想分析及びACコード:
B題:実は貪欲な思想で、スキップした部分は条件を満たす場合に最も長い部分に違いない.だから私たちがしなければならないのは、サンタクロースにずっと歌って、歌った詩の中で一番長い一節を記録することです.歌う詩の段落の全長から最長の段落を引いても規定時間を超えている場合は、停止します.この時はどんなに踊っても問題を満たすことができないからだ.

#include
#include
#include
#include
#include
#define PI 3.1415926
typedef long long ll;
using namespace std;
int main()
{
	int t=0;
	cin>>t;
	while(t--)
	{
		ll n=0,k=-1,ans=0,ansid=0;
		ll s=0,b=0;
		ll a[100010]={0};
		scanf("%lld",&n);
		scanf("%lld",&s);
		ll x=0;
		for(ll i=1;i<=n;i++)
		scanf("%lld",&a[i]);
		for(ll i=1;i<=n;i++)
		{
			b+=a[i];
		}
		if(b<=s)
		{
			cout<<0<<endl;
			continue;
		}
		else
		{
				for(ll i=1;i<=n;i++)
			{
				x+=a[i];
				if(k<a[i])//k         
            {
                ans = i;
                k = a[i];
            }
            if(x - k <= s)//     ，                  
            {
                ansid = ans;
            }
			} 
			cout<<ansid<<endl;
		}
	}
	return 0;
}

C題:まずpos配列でa配列の各数字の位置を記録し、贈り物の最も深い深さを動的に更新すればいい.最大の深さを見つけたら、この深さで送ったプレゼントの個数を減らして2を乗じて、これらのプレゼントを出して、順番に並べて戻した時間に、n個のプレゼントを出す時間を加えると総時間になります.

#include
#include
#include
#include
#include
#define PI 3.1415926
typedef long long ll;
using namespace std;
int main()
{
	ll t=0;
	cin>>t;
	static ll a[100010]={0};
	static ll pos[100010]={0};
	while(t--)
	{
		ll m=0,n=0,b=0,ans=0,bottom=-1;
		scanf("%lld%lld",&m,&n);
		for(ll i=1;i<=m;i++)
		{
			scanf("%lld",&a[i]);
			pos[a[i]]=i;//  a           
		}
		for(ll i=1;i<=n;i++)
		{
			cin>>b;
			if(pos[b]>bottom)//                    
			{
				bottom=pos[b];//       
				ans+=(bottom-i)*2;//     i        ，            i
				//             ，        
			}
		}
		ans+=n;//ans                  ，      n       
		cout<<ans<<endl;
	}
	return 0;
}

注意事項:
B問題は、最大段をスキップしたときに、後でサンタクロースに短い段をたくさん歌うことができる可能性があるので、段落を統計するときはこのような状況を考慮しなければならないという特殊な状況に注意してください.(これもなぜ前の書き方がなかなか通れなかったのかの原因です).C題は題意の理解に注意して、サンタクロースがプレゼントを贈るのは、贈るべきプレゼントを一気に順番に並べてから送るのではなく、一つ一つ贈るものです.題意の理解に注意!!