Codeforces ラウンド #283 (ディビジョン 2) D. テニス Game_html/css

Codeforces ラウンド #283 (ディビジョン 2) D. テニス Game_html/css_WEB-ITnose

WBOY

リリース： 2016-06-24 11:52:00

オリジナル

1183 人が閲覧しました

標準的なスケジュールは2点のようでしょうか？

前処理してマークを付け、t を 1 から n まで列挙しました。各 t について、s が存在する場合、s は一意であるため、t を列挙するだけです。

直接的な暴力を使用した場合はタイムアウトになります。

標準プロセスの一般的な考え方が私と同じかどうかはわかりませんが、おそらく標準プロセスはマークされていません。 2 つの部分に分割します

ただし、時間計算量は n*(1+1/2+1/3+......1/n)=n*lnn アプローチ

#include<iostream>#include<map>#include<string>#include<cstring>#include<cstdio>#include<cstdlib>#include<cmath>#include<queue>#include<vector>#include<algorithm>using namespace std;struct Ans{	int s,t;	Ans(){}	Ans(int a,int b){s=a;t=b;}	bool operator <(Ans x)const	{		return s!=x.s?s<x.s:t<x.t;	}};vector<Ans>ans;int in[100010];int as[100010];int ap[200010];int bs[100010];int bp[200010];int n;void maketable(){	int i,x,y;	x=y=0;	memset(ap,-1,sizeof(ap));	memset(bp,-1,sizeof(bp));	for(i=0;i<n;i++)	{		if(in[i]==1)			ap[++x]=i;		else			bp[++y]=i;		as[i]=x;		bs[i]=y;	}}int isok(int s){	int t1,t2,x,y;	t1=t2=s;	x=y=0;	while(1)	{		if(ap[t1]==-1&&bp[t2]==-1)			return 0;		if(ap[t1]==n-1&&bp[t2]==-1)		{			++x;			return x<=y?0:x;		}		if(ap[t1]==-1&&bp[t2]==n-1)		{			++y;			return y<=x?0:y;		}		if(bp[t2]==-1||(ap[t1]!=-1&&ap[t1]<bp[t2]))		{			t2=bs[ap[t1]]+s;			t1+=s;			x++;		}		else if(ap[t1]==-1||(bp[t2]!=-1&&ap[t1]>bp[t2]))		{			t1=as[bp[t2]]+s;			t2+=s;			y++;		}		else			return 0;	}}int main(){	int i,t,m;	scanf("%d",&n);	for(i=0;i<n;i++)		scanf("%d",in+i);	maketable();	for(i=1;i<=n;i++)	{		t=isok(i);		if(t!=0)			ans.push_back(Ans(t,i));	}	sort(ans.begin(),ans.end());	m=ans.size();	printf("%d\n",m);	for(i=0;i<m;i++)		printf("%d %d\n",ans[i].s,ans[i].t);}

ログイン後にコピー

D の方が優れています。テニスゲーム

テストごとの制限時間

2 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

Petya と Gena は卓球が大好きです。シングルマッチは以下のルールに従って行われます。試合は複数のセットで構成され、各セットは複数のサーブで構成され、いずれかのプレーヤーが t ポイントを獲得すると、このプレーヤーは 1 ポイントを獲得します。、彼がセットに勝つと、次のセットが始まり、両方のプレーヤーのスコアが0に設定されます。どちらかのプレーヤーがセットの合計を獲得するとすぐに、彼が試合に勝ち、試合は終了します。さらに、歴史のために、彼らは各試合の記録を残します。つまり、サーブごとに勝者を書き留めます。サーブの勝者は時系列順に記録されます。プレーヤーの 1 人が t ポイントを獲得するとすぐにセットが終了し、プレーヤーの 1 人がセットを獲得するとすぐに試合が終了します。

Petya と Gena が記録を見つけました。残念ながら、記録内のサーブのシーケンスはセットに分割されておらず、特定の試合の数値と t も失われています。すべての値を決定できるかどうか疑問に思っています。可能なオプションは?

入力

最初の行には、一連のゲームの長さである単一の整数 n ? (1?≤?n?≤?105) が含まれます。

2 行目には、スペースで区切られた n 個の整数が含まれます。 . ifai?=?1 の場合、i 番目のサーブは Petya が勝ち、ai?=?2 の場合、i 番目のサーブは Gena が勝ちました。

数値と t のオプションが少なくとも 1 つあることは保証されません。指定されたレコードに対応します。

出力

最初の行では、数値のオプションの数 k ? を出力します。

次の各 k 行では、数値のオプションを 2 つ出力します。

サンプルテスト

入力