CodeForce CF菗517 Div.2

A.ゴールデンプランの水問題、公式は全部押さなくてもいいです.循環すればいいです.http://codeforces.com/contest/1072/problem/A

int n,m,k;
	cin>>n>>m>>k;
	int ans=0;
	while(k--){
		ans+=2*n+2*m-4;
		n-=4;
		m-=4;
	}
	cout<

B.Curriosity Has No Limitsは、生成関数を二つと生成した数列をあげて、元の数列を探してもらうという意味です.私のやり方は、任意のiに対して、aiとbiは全部で16種類しかありません.彼らを挙げて、tiとti＋1の可能な存在形式を探します.一つのセットのaiとbiを除いて、二つのセットのtiとti＋1が得られることがわかった.他のものはせいぜい一つしか発売できない.では、私たちはt 1とt 2を挙げることができます.O(n)時間内に上式によって後ろの要素を出すことができます.どれも押し出せないなら、説明は解りません.http://codeforces.com/contest/1072/problem/B

const int maxn=2e5+7;
struct node{
	int x,y;
}c[maxn];
int a[maxn],b[maxn]; 
int n;
int err=0;
int ans[maxn];

void check(){
	if(err==-1)return;
	for(int i=2;i

PS:でも、この問題は私が書いたのが面倒です.明らかにai(またはbi)ごとに二人に分解できます.一人はtの中間の相対的な位置に対応しています.このように席を外したら、もっと簡単に処理できます.変数が少ないからです.もちろん複雑さはあまりないです.しかし、これはもっと大規模な問題を解決することができます.aiの範囲は0-255です.したがって、ビットを解体することは、ビット演算を処理する際に非常に重要な思想である.
C.Cram Time欲張り問題.明らかに私達は発見しにくくなくて、解答のansの上界は以下の性質を満たします:①(ans+1)*ans/2<=(a+b)で、その後私達はこの上界が私達の必要な解答なことを証明することを望みます.最初はdpと思っていましたが、考えてみると、この上界は必ず取ることができます.以下の証明を示します.1.MIN(a,b)<=ansなら、MIN(a,b)の日をaとbの中で小さい日にします.2.MIN(a,b)＞ansの場合は、ansの日をより小さい日に配置し、ans-1のサブ問題を構成して、このステップを繰り返すだけでいいです.最後に必ずステップ1で解決されます.

LL n,m,sum,maxn;
LL ans1[100005],ans2[100005],cnt1=0,cnt2=0,sum1=0,sum2=0;

int main()
{
	cin>>n>>m;
	sum=m+n;
	LL l=0,r=n+m+1;
	while(l>1;
		if((mid+1)*mid<=(n+m)*2)l=mid;
		else r=mid;
	}
	maxn=l;
	for(int i=maxn;i;--i){
		if(sum1+i<=n){
			sum1+=i;
			ans1[++cnt1]=i;
		}
		else{
			sum2+=i;
			ans2[++cnt2]=i;
		}
	}
	cout<

D.Minimum pathはわかりやすく、これは裸のdp問題です.そう言えば、少なくとも最初のコードセグメントはdpです.問題の第一部分はやはり簡単です.dpで保存すれば、あとどれぐらいの非aをaに変えられますか?そして、現在の格子がaかどうかを考えて、変わった文字をaに変えてもいいです.次に辞書の序文の一番小さい串を探します.私たちがよく知っているdpを思い出しやすいです.
dp[i][j]=min(dp[i-1][j],dp[i]、[j-1]+c[i]、[j]のうち、dpはi行目のj列の辞書順の最小文字列に格納され、cは図中のi行目のj列の文字を保存する.
このように粗暴な保存ならば、O(N^3)の空間の複雑さであり、与えられたn=2000の確率は空間が爆発するので、1次元のdpに圧縮しました.
dp[j]=max(dp[j-1]、dp[j]+c[i]、[j]はi行目のj列の状態を考慮すると、彼は左から来たり、上から来たりする.本格にアクセスしたことがない場合、dp[j]には前の列の状態が存在しますが、dp[j-1]はすでに更新されているので、本行j-1列の状態が格納されています.
そして計算時間の複雑度O(N^3)は、私の定数が非常に小さいことを考慮して、通過できると思います.
そして、もっと巧みなdp方法を学びました.dp自体はOですが(N^2)、比較的stringの時間消費を免れました.私たちは一つのUSBを使って、ある点が一番いい解の中の点かもしれないかどうかを表します.明らかに出発点はその中にあります.続いて、私達の第一重循環はk=i+j(0が上の階の中でusedの中の点の中で最小の点を接続してusedと表記して、明らかに少なくとも一つを探し当てることができます.循環不変式によって証明することができます.現在の層の中で、usedの中で選んだ点から遡るのは一番良い解です.
初期化:k==0の場合、1つの要素だけが明らかに保持されます.k-1の層でこの性質を満たすと、選択された数字の各々には、2つのケースが含まれます.一つは上部usedで接続されていないものです.辞書の順序の性質のために、彼が選ばれたら、前の階は絶対最適ではないので、切り捨てます.もう一つは前の階に接続されていますが、最小ではないです.もちろん、最適ではないので、切り捨てます.残りの条件は満たされています.上の階に少なくとも1つは米国の中にあるので、この層も少なくとも1つは米国の中に入れることができます.最後のレイヤーに達したら停止します.
明らかにレイヤーごとにusedの文字を入れるのは唯一の値です.私たちは彼らがusedに加入する順番を保存しておけば、辞書の順序が一番小さい答えが得られます.

char c[2005][2005];
int lt[2005][2005];
bool used[2005][2005];
int n;
int now=1;
int maxx=0;

int getlastlt(int i,int j){
	if(!i)return lt[i][j-1];
	if(!j)return lt[i-1][j];
	return MAX(lt[i][j-1],lt[i-1][j]);
}

string MINn(string x,string y){
	int la=x.size(),lb=y.size();
	int p=0;
	while(py[p])return y;
		p++;
	}
	return x;
}

int main()
{
	INI(lt);
	INI(used);
	cin>>n>>lt[0][0];
	for(int i=0;i=0){
				if((rr&&used[rr-1][cc])||(cc&&used[rr][cc-1]))minn=MIN(minn,c[rr][cc]),used[rr][cc]=1;	
				++cc;
				--rr;
			}
			rr=i;
			cc=0;
			while(rr>=0){
				if(c[rr][cc]!=minn)used[rr][cc]=0;
				++cc;
				--rr;
			}
		}
		else{
			rr=n-1;
			cc=i-rr;
			while(cc=0){
				if(c[rr][cc]!=minn)used[rr][cc]=0;
				++cc;
				--rr;
			}
		}
		ans.push_back(minn);
	}
	cout<