1 条题解

  • 0
    @ 2025-5-4 16:21:50

    分析:

    此代码运用的是模拟算法,通过模拟棋盘上棋子的移动规则来计算最终结果。主要是根据给定的棋子位置关系和初始状态,按照特定顺序检查可移动的情况,进行棋子的移动并计算移动带来的数值变化,直到无法再进行移动为止。

    解题思路

    给定一个类似棋盘的场景,棋盘上有一些初始放置的棋子,每个棋子有对应的编号。目标是通过特定的移动规则,将棋子进行移动,计算每次移动后数值的变化,最终得到一个总和。算法思想是从编号较大的位置开始,按照下、右、左、上的顺序检查每个位置是否可以根据规则进行棋子移动,若可以则进行移动并计算数值变化,不断重复此过程,直到没有位置可以进行移动为止。

    解题原理

    1.初始化棋盘状态:使用一个布尔数组 board 来表示棋盘上每个位置是否有棋子,初始时将所有位置设为没有棋子,然后根据输入将有棋子的位置标记为 1,并计算初始棋子编号的总和 sum。

    2.定义移动规则数组:分别定义了 shang(上)、xia(下)、zuo(左)、you(右)四个数组,用于表示每个位置的棋子按照相应方向移动时,所涉及的其他位置的编号。

    3.移动判断与执行:在 solve 函数中,从编号为 33 的位置开始向前遍历。对于每个位置,如果该位置已经有棋子则跳过。然后按照下、右、左、上的顺序检查该位置是否满足移动条件(即相应方向上的两个位置都有棋子)。如果满足条件,则将当前位置标记为有棋子,将相应方向上的两个位置标记为没有棋子,并计算这次移动所带来的数值变化(即相应方向上两个棋子编号之和减去当前位置的编号)。

    4.循环计算:在 main 函数中,不断调用 solve 函数进行移动计算,每次将计算得到的数值变化从 sum 中减去,直到 solve 函数返回特定值(表示无法再进行移动)为止,最终输出 sum 的值。

    实现步骤

    1.输入处理:读取测试用例的数量 n。

    2.初始化与输出标题:输出结果的标题 HI Q OUTPUT,对于每个测试用例,调用 init 函数进行棋盘状态的初始化,包括读取棋子的初始位置并标记,计算初始总和。

    3.移动计算:通过循环不断调用 solve 函数进行棋子的移动计算,每次根据 solve 函数的返回值更新 sum。

    4.输出结果:当无法再进行移动时,输出最终的 sum 值。

    5.结束输出:输出结束标记 END OF OUTPUT

    c++代码:

    #include <stdio.h>
    #include <string.h>
    #include <iostream>
    #include <cstdlib>
    #include <string>
    #include <vector>
    #include <map>
    
    using namespace std;
    
    bool board[34];
    int sum;
    int FLAG = -233;
    void init(){
    	for(int i = 0; i < 34; i++) board[i] = 0;
    	sum = 0;
    	int tmp;
    	while(1){
    		cin >> tmp;
    		if(!tmp) break;
    		board[tmp] = 1;
    		sum += tmp;
    	}
    }
    
    int shang[34] = {0,0,0,0,1,2,3,0,0,4,5,6,0,0,7,8,9,10,11,12,13,14,15,16,17,18,19,20,23,24,25,28,29,30};
    int xia[34] = {0,4,5,6,9,10,11,14,15,16,17,18,19,20,21,22,23,24,25,26,27,0,0,28,29,30,0,0,31,32,33,0,0,0};
    int zuo[34] = {0,0,1,2,0,4,5,0,7,8,9,10,11,12,0,14,15,16,17,18,19,0,21,22,23,24,25,26,0,28,29,0,31,32};
    int you[34] = {0,2,3,0,5,6,0,8,9,10,11,12,13,0,15,16,17,18,19,20,0,22,23,24,25,26,27,0,29,30,0,32,33,0};
    
    int solve(){
    	for(int i = 33; i > 0; i--){
    		//顺序:下,右,左,上
    		if(board[i]) continue;
    		if(board[xia[xia[i]]] && board[xia[i]]){
    			board[i] = 1; board[xia[xia[i]]] = 0; board[xia[i]] = 0;
    			return xia[i]+xia[xia[i]]-i;
    		}
    		if(board[you[you[i]]] && board[you[i]]){
    			board[i] = 1; board[you[you[i]]] = 0; board[you[i]] = 0;
    			return you[i]+you[you[i]]-i;
    		}
    		if(board[zuo[zuo[i]]] && board[zuo[i]]){
    			board[i] = 1; board[zuo[zuo[i]]] = 0; board[zuo[i]] = 0;
    			return zuo[i]+zuo[zuo[i]]-i;
    		}
    		if(board[shang[shang[i]]] && board[shang[i]]){
    			board[i] = 1; board[shang[shang[i]]] = 0; board[shang[i]] = 0;
    			return shang[i]+shang[shang[i]]-i;
    		}
    	}
    	return FLAG;
    }
    
    int main(int argc, char **argv){
    	int n;
    	cin >> n;
    	cout << "HI Q OUTPUT" << endl;
    	while(n--){
    		init();
    		int sub;
    		while((sub = solve()) != FLAG){
    			sum -= sub;
    		}
    		cout << sum << endl;
    	}
    	cout << "END OF OUTPUT" << endl;
    	return 0;
    }
    • 1

    信息

    ID
    526
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    4
    已通过
    1
    上传者