专栏文章

题解：P12782 [ICPC 2024 Yokohama R] E-Circuit Is Now on Sale!

rregular_heptagon
P12782题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minus4in
此快照首次捕获于
2025/12/02 08:41
3 个月前
此快照最后确认于
2025/12/02 08:41
3 个月前
查看原文
根据题意可知最多会进行 n2n^2 次计算也就是最多 25002500 次。
由于 n≤50n \leq 50，直接考虑暴力。
循环 n2n^2 次，每次循环枚举每个位置可否完成计算将结果传到下一个位置，每次循环枚举 n2n^2 次。合起来时间复杂度就是 O(n4)O(n^4)。
6.25×1066.25\times 10^6 的数量级，并不会超时。
此外，需要注意运算过程中，数字的值在 101810^{18} 以内，不能用 char 来存，需要开一个布尔数组判断是否是数字，在输入过程中和枚举过程中都应注意哪些数据是数字。
遇到符号就判断旁边是否有符合其运算需求数字数量的数字，满足就运算，并把旁边删掉。
CPP
#include<bits/stdc++.h>
using namespace std;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
char a[55][55];
long long b[55][55];
bool digit[55][55];
int n,m;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if('0'<=a[i][j]&&a[i][j]<='9'){
				digit[i][j]=true;
				b[i][j]=a[i][j]-'0';
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int r=1;r<=n;r++){
				for(int c=1;c<=m;c++){
					if(a[r][c]=='#'){
						vector<int> dire;
						int num=0;
						for(int k=0;k<4;k++){
							int x=r+dx[k],y=c+dy[k];
							if(x>=1&&x<=n&&y>=1&&y<=m&&digit[x][y]){
								num++;
								dire.push_back(k);
							}
						}
						if(num==1){
							int x=r+dx[dire[0]],y=c+dy[dire[0]];
							b[r][c]=b[x][y];
							digit[x][y]=false;
							digit[r][c]=true;
							a[r][c]='.';
						}
					}else if(a[r][c]=='+'){
						vector<int> dire;
						int num=0;
						for(int k=0;k<4;k++){
							int x=r+dx[k],y=c+dy[k];
							if(x>=1&&x<=n&&y>=1&&y<=m&&digit[x][y]){
								num++;
								dire.push_back(k);
							}
						}
						if(num==2){
							int x1=r+dx[dire[0]],y1=c+dy[dire[0]];
							int x2=r+dx[dire[1]],y2=c+dy[dire[1]];
							b[r][c]=b[x1][y1]+b[x2][y2];
							digit[x1][y1]=digit[x2][y2]=false;
							digit[r][c]=true;
							a[r][c]='.';
						}
					}else if(a[r][c]=='-'){
						vector<int> dire;
						int num=0;
						for(int k=0;k<4;k++){
							int x=r+dx[k],y=c+dy[k];
							if(x>=1&&x<=n&&y>=1&&y<=m&&digit[x][y]){
								num++;
								dire.push_back(k);
							}
						}
						if(num==2){
							int x1=r+dx[dire[0]],y1=c+dy[dire[0]];
							int x2=r+dx[dire[1]],y2=c+dy[dire[1]];
							b[r][c]=max(b[x1][y1],b[x2][y2])-min(b[x1][y1],b[x2][y2]);
							digit[x1][y1]=digit[x2][y2]=false;
							digit[r][c]=true;
							a[r][c]='.';
						}
					}else if(a[r][c]=='*'){
						vector<int> dire;
						int num=0;
						for(int k=0;k<4;k++){
							int x=r+dx[k],y=c+dy[k];
							if(x>=1&&x<=n&&y>=1&&y<=m&&digit[x][y]){
								num++;
								dire.push_back(k);
							}
						}
						if(num==2){
							int x1=r+dx[dire[0]],y1=c+dy[dire[0]];
							int x2=r+dx[dire[1]],y2=c+dy[dire[1]];
							b[r][c]=b[x1][y1]*b[x2][y2];
							digit[x1][y1]=digit[x2][y2]=false;
							digit[r][c]=true;
							a[r][c]='.';
						}
					}else if(a[r][c]=='/'){
						vector<int> dire;
						int num=0;
						for(int k=0;k<4;k++){
							int x=r+dx[k],y=c+dy[k];
							if(x>=1&&x<=n&&y>=1&&y<=m&&digit[x][y]){
								num++;
								dire.push_back(k);
							}
						}
						if(num==2){
							int x1=r+dx[dire[0]],y1=c+dy[dire[0]];
							int x2=r+dx[dire[1]],y2=c+dy[dire[1]];
							b[r][c]=max(b[x1][y1],b[x2][y2])/min(b[x1][y1],b[x2][y2]);
							digit[x1][y1]=digit[x2][y2]=false;
							digit[r][c]=true;
							a[r][c]='.';
						}
					}else if(a[r][c]=='P'){
						vector<int> dire;
						int num=0;
						for(int k=0;k<4;k++){
							int x=r+dx[k],y=c+dy[k];
							if(x>=1&&x<=n&&y>=1&&y<=m&&digit[x][y]){
								num++;
								dire.push_back(k);
							}
						}
						if(num==1){
							int x1=r+dx[dire[0]],y1=c+dy[dire[0]];
							cout<<b[x1][y1];
							return 0;
						}
					}
				}
			}
		}
	}
}
码风不好，并且用了 vector ，而且好像很多地方是屎山，喷轻点。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...