CSP 最简单的一道T1了,简单到我都不信需要算法
查看原帖
CSP 最简单的一道T1了,简单到我都不信需要算法
525297
yaoyao1910楼主2023/11/8 14:21

1组数据有81种情况,特判1种,剩下的把每组数据的81种情况都算出来,转化成5位数,放到大根堆里比大小,如果堆顶都一样,答案数++,堆顶都踢掉。如果堆顶有不一样的,踢掉数大的,重新比较。代码很暴力,时间复杂度O(1e5),不优化了,我要去清理门户了,那几个逆徒都说这个题难,没一个拿满分的。

#include<bits/stdc++.h>
using namespace std;

int n,tem,res;
priority_queue<int> q[10];

void kick(int n){
	int x=0,pos=0;
	for(int i=1;i<=n;i++){
		if(q[i].top()>x){
			x=q[i].top();
			pos=i;
		}
	}
	q[pos].pop();
}

void kickall(int n){
	for(int i=1;i<=n;i++){
		q[i].pop();
	}
}

int main(){
	cin>>n;
	if(n==1){
		cout<<81;
		return 0;
	}
	for(int i=1;i<=n;i++){
		int a,b,c,d,e;
		cin>>a>>b>>c>>d>>e;
		for(int j=1;j<=9;j++){
			tem=(a+j)%10*10000+b*1000+c*100+d*10+e;
			q[i].push(tem);
			tem = a*10000+(b+j)%10*1000+c*100+d*10+e;
			q[i].push(tem);
			tem = a*10000+b*1000+(c+j)%10*100+d*10+e;
			q[i].push(tem);
			tem = a*10000+b*1000+c*100+(d+j)%10*10+e;
			q[i].push(tem);
			tem = a*10000+b*1000+c*100+d*10+(e+j)%10;
			q[i].push(tem);
			if(1){
				tem = (a+j)%10*10000+(b+j)%10*1000+c*100+d*10+e;
				q[i].push(tem);
				tem = a*10000+(b+j)%10*1000+(c+j)%10*100+d*10+e;
				q[i].push(tem);
				tem = a*10000+b*1000+(c+j)%10*100+(d+j)%10*10+e;
				q[i].push(tem);
				tem = a*10000+b*1000+c*100+(d+j)%10*10+(e+j)%10;
				q[i].push(tem);
			}
		}
	}
	bool flag=true;
	while(flag){
		for(int i=1;i<=n;i++){
			if(q[i].empty()){
				flag=false;
				break;
			}
		}
		if(!flag){
			break;
		}
		bool st=true;
		for(int i=1;i<n;i++){
			if(q[i].top()!=q[i+1].top()){
				kick(n);
				st=false;
				break;
			}
		}
		if(st){
			res++;
			kickall(n);
		}
	}
	cout<<res;
	return 0;
} 
2023/11/8 14:21
加载中...