nocriz的博客

苔花如米小,也学牡丹开。

CERC 16 D

做了个新的CF头像

唉,累了,题是好题,做出此题感觉还是不错的,只是没时间写题解了。

也没时间打算法竞赛了,周末还要磨锤子。我好难啊。

也没时间写作业了。

也没时间睡觉了。

但是希望周日还是能上分,毕竟人,要有梦想


int dp[10][10];
vector<int> V[6][6];

void msort(int a,int b,int c){
	vector<int> SO,S2;
	//debug(a,b,V[a][b],c);
	for(int i=0;i<c;i++){
		SO.push_back(V[a][b].back());
		V[a][b].pop_back();
	}
	if(a+b == 10){
	//	debug(SO[0]);
		return;
	}
	if(a+b == 9 && c == 2){
		if(SO[0]>SO[1]){
			if(a == 4) cout<<"5 6 D 1\n5 6 D 1\n";
			else cout<<"6 5 R 1\n6 5 R 1\n";
		}else{
			if(a == 4) cout<<"5 6 D 2\n";
			else cout<<"6 5 R 2\n";
		}
		return;
	}
	S2 = SO;
	sort(all(S2));
	int ccnt[6][6] = {0};
	for(auto ct:SO){
		int rk = S2.size()-(lower_bound(all(S2),ct)-S2.begin());
		for(int x=5;x>=a;x-=1){
			for(int y=5;y>=b;y-=1){
				if(x == a && y == b)continue;
				rk-=dp[6-x][6-y];
				if(rk<=0){
					ccnt[x][y]+=1;
					V[x][y].PB(ct);
					for(int i=a;i<x;i++)cout<<i+1<<' '<<b+1<<" D 1\n";
					for(int i=b;i<y;i++)cout<<x+1<<' '<<i+1<<" R 1\n";
					goto nxt;
				}
			}
		}
		nxt:;
	}
	for(int x=5;x>=a;x-=1){
		for(int y=5;y>=b;y-=1){
			if(ccnt[x][y])msort(x,y,ccnt[x][y]);
		}
	}
}

int main() {
    for(int i=1;i<=6;i++){
    	for(int j=1;j<=6;j++){
    		if(i+j == 2){
    			dp[i][j] = 1;
    			continue;
    		}
    		if(i+j == 3){
    			dp[i][j] = 2;
    			continue;
    		}
    		for(int k=1;k<=i;k++){
    			for(int l=1;l<=j;l++){
    				if(!(k == i && l == j))dp[i][j]+=dp[k][l];
    			}
    		}
    	}
    }
    int n,c;
    read(n);
    for(int i=1;i<=n;i++){
    	read(c);
    	V[0][0].PB(c);
    }
    msort(0,0,n);
    return 0;
}


评论

《 “CERC 16 D” 》 有 3 条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注