UVa 10654 The Uxuhul Voting System-平芜编程栈

题目分析

本题描述了一个古代文明的投票系统，我们需要根据每位祭司的偏好顺序，推算出最终三个议题的投票结果。这个问题的核心在于每位祭司都会基于后续祭司的最优选择来做出自己的最优决策，因此我们需要逆向推理整个投票过程。

问题重述

有三个议题，每个议题用一块双面石头表示（黑面N/ 白面Y）。
初始状态为NNN（全否）。
有m mm位祭司按年龄从小到大依次投票。
每位祭司必须翻转恰好一块石头，改变一个议题的当前结果。
投票结束后，石头的最终朝上面决定三个议题的最终结果。
每位祭司在投票前会公开自己对8 88种可能结果的偏好顺序（1表示最喜欢，8表示最不喜欢）。
每位祭司都是完美理性的，会根据已知的其他祭司偏好，选择能使最终结果对自己最有利的翻转方式。
给定n nn个测试用例，每个用例给出m mm和每位祭司的偏好顺序，要求输出最终的投票结果。

关键点

状态表示：三个议题共有2 3 = 8 2^3 = 823=8种状态，可以用0 00到7 77的整数表示，其中二进制位0 00表示第一个议题（最低位对应第一块石头），1表示N，0表示Y（或者反过来，只要一致即可）。在代码中我们使用outcomes数组进行映射。
决策顺序：祭司按年龄从小到大投票，但决策逻辑是逆向的。因为最后一位祭司投票后状态即为最终结果，而前面的祭司会预判后续祭司的选择。
最优子结构：对于当前祭司，他可以根据下一个祭司在不同状态下的最终结果，选择对自己最有利的翻转方式。这符合动态规划的特性。

解题思路

逆向动态规划

设d p [ i ] [ s t a t e ] dp[i][state]dp[i][state]表示从第i ii位祭司（0-based）开始投票，当前状态为s t a t e statestate（0 − 7 0 - 70−7）时，最终会达到的结果（用0 − 7 0 - 70−7表示，对应8 88种结果）。

边界条件：当所有祭司都投票完毕（即i = m i = mi=m），最终状态就是当前状态，所以d p [ m ] [ s t a t e ] = s t a t e dp[m][state] = statedp[m][state]=state。
状态转移：对于第i ii位祭司，当前状态为s t a t e statestate，他可以翻转三块石头中的任意一块。翻转第k kk块石头（k = 0 , 1 , 2 k = 0,1,2k=0,1,2）会得到新状态n e x t S t a t e = s t a t e ⊕ ( 1 ≪ k ) nextState = state \oplus (1 \ll k)nextState=state⊕(1≪k)（异或操作翻转对应位）。然后，第i + 1 i+1i+1位祭司在该状态下的最终结果是d p [ i + 1 ] [ n e x t S t a t e ] dp[i+1][nextState]dp[i+1][nextState]。第i ii位祭司会从这三种可能的n e x t S t a t e nextStatenextState中，选择使自己的偏好值最小（即最喜欢）的那个最终结果作为自己的选择，并将该结果记录在d p [ i ] [ s t a t e ] dp[i][state]dp[i][state]中。

转移方程：

d p [ i ] [ s t a t e ] = arg ⁡ min ⁡ k ∈ { 0 , 1 , 2 } p r e f e r e n c e s [ i ] [ d p [ i + 1 ] [ s t a t e ⊕ ( 1 ≪ k ) ] ] dp[i][state] = \arg\min_{k \in \{0,1,2\}} preferences[i][\,dp[i+1][\,state \oplus (1 \ll k)\,]\,]dp[i][state]=argk∈{0,1,2}minpreferences[i][dp[i+1][state⊕(1≪k)]]

其中arg ⁡ min ⁡ \arg\minargmin返回的是对应偏好值最小的那个最终结果编号。

计算步骤

读取测试用例数n nn。
对每个用例：
- 读取祭司人数m mm。
- 读取m mm行偏好顺序，每行 8 个整数。
- 初始化d p [ m ] [ 0..7 ] dp[m][0..7]dp[m][0..7]为对应状态值。
- 从i = m − 1 i = m-1i=m−1到0 00逆序计算d p [ i ] [ s t a t e ] dp[i][state]dp[i][state]。
- 最终d p [ 0 ] [ 0 ] dp[0][0]dp[0][0]就是从第一位祭司、初始状态NNN（即0 00）开始最终会达到的结果编号。
- 通过outcomes数组转换为字符串输出。

复杂度分析

状态数：m × 8 m \times 8m×8。
每个状态需要尝试3 33种翻转。
总时间复杂度：O ( n × m × 8 × 3 ) = O ( 24 n m ) O(n \times m \times 8 \times 3) = O(24nm)O(n×m×8×3)=O(24nm)，在n , m < 100 n, m < 100n,m<100时完全可行。
空间复杂度：O ( m × 8 ) O(m \times 8)O(m×8)。

代码实现

// The Uxuhul Voting System// UVa ID: 10654// Verdict: Accepted// Submission Date: 2025-12-14// UVa Run Time: 0.000s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 8种可能的结果字符串，索引0~7对应状态0~7conststring outcomes[]={"NNN","NNY","NYN","NYY","YNN","YNY","YYN","YYY"};intmain(){intn;cin>>n;while(n--){intm;cin>>m;vector<vector<int>>preferences(m,vector<int>(8));// 读取每位祭司的偏好顺序for(inti=0;i<m;i++)for(intj=0;j<8;j++)cin>>preferences[i][j];// dp[i][state] 表示从第i位祭司开始，当前状态为state时，最终结果的编号vector<vector<int>>dp(m+1,vector<int>(8,0));// 边界：最后一位祭司之后，状态即最终结果for(intstate=0;state<8;state++)dp[m][state]=state;// 逆序DP，从最后一位祭司往前推for(inti=m-1;i>=0;i--){for(intstate=0;state<8;state++){intbestPreference=INT_MAX;// 偏好值越小越好intbestOutcome=-1;// 尝试翻转三块石头中的一块for(intflip=0;flip<3;flip++){intnextState=state^(1<<flip);// 翻转第flip位intfinalOutcome=dp[i+1][nextState];// 后续祭司的最终结果// 选择对自己最有利的（偏好值最小）if(preferences[i][finalOutcome]<bestPreference){bestPreference=preferences[i][finalOutcome];bestOutcome=finalOutcome;}}dp[i][state]=bestOutcome;}}// 输出从第一位祭司、初始状态0（NNN）开始的最终结果cout<<outcomes[dp[0][0]]<<endl;}return0;}