网站建设类型分类56网站可以做电子相册

网站建设类型分类,56网站可以做电子相册,福建省城乡建设网站,网站建设正版软件题目分析 本题描述了一个古代文明的投票系统#xff0c;我们需要根据每位祭司的偏好顺序#xff0c;推算出最终三个议题的投票结果。这个问题的核心在于每位祭司都会基于后续祭司的最优选择来做出自己的最优决策#xff0c;因此我们需要逆向推理 整个投票过程。 问题重述 …题目分析本题描述了一个古代文明的投票系统我们需要根据每位祭司的偏好顺序推算出最终三个议题的投票结果。这个问题的核心在于每位祭司都会基于后续祭司的最优选择来做出自己的最优决策因此我们需要逆向推理整个投票过程。问题重述有三个议题每个议题用一块双面石头表示黑面N/ 白面Y。初始状态为NNN全否。有m mm位祭司按年龄从小到大依次投票。每位祭司必须翻转恰好一块石头改变一个议题的当前结果。投票结束后石头的最终朝上面决定三个议题的最终结果。每位祭司在投票前会公开自己对8 88种可能结果的偏好顺序1表示最喜欢8表示最不喜欢。每位祭司都是完美理性的会根据已知的其他祭司偏好选择能使最终结果对自己最有利的翻转方式。给定n nn个测试用例每个用例给出m mm和每位祭司的偏好顺序要求输出最终的投票结果。关键点状态表示三个议题共有2 3 8 2^3 8238种状态可以用0 00到7 77的整数表示其中二进制位0 00表示第一个议题最低位对应第一块石头1表示N0表示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 statestate0 − 7 0 - 70−7时最终会达到的结果用0 − 7 0 - 70−7表示对应8 88种结果。边界条件当所有祭司都投票完毕即i m i mim最终状态就是当前状态所以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,2k0,1,2会得到新状态n e x t S t a t e s t a t e ⊕ ( 1 ≪ k ) nextState state \oplus (1 \ll k)nextStatestate⊕(1≪k)异或操作翻转对应位。然后第i 1 i1i1位祭司在该状态下的最终结果是d p [ i 1 ] [ n e x t S t a t e ] dp[i1][nextState]dp[i1][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[i1][\,state \oplus (1 \ll k)\,]\,]dp[i][state]argk∈{0,1,2}min​preferences[i][dp[i1][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-1im−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,m100时完全可行。空间复杂度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//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 8种可能的结果字符串索引0~7对应状态0~7conststring outcomes[]{NNN,NNY,NYN,NYY,YNN,YNY,YYN,YYY};intmain(){intn;cinn;while(n--){intm;cinm;vectorvectorintpreferences(m,vectorint(8));// 读取每位祭司的偏好顺序for(inti0;im;i)for(intj0;j8;j)cinpreferences[i][j];// dp[i][state] 表示从第i位祭司开始当前状态为state时最终结果的编号vectorvectorintdp(m1,vectorint(8,0));// 边界最后一位祭司之后状态即最终结果for(intstate0;state8;state)dp[m][state]state;// 逆序DP从最后一位祭司往前推for(intim-1;i0;i--){for(intstate0;state8;state){intbestPreferenceINT_MAX;// 偏好值越小越好intbestOutcome-1;// 尝试翻转三块石头中的一块for(intflip0;flip3;flip){intnextStatestate^(1flip);// 翻转第flip位intfinalOutcomedp[i1][nextState];// 后续祭司的最终结果// 选择对自己最有利的偏好值最小if(preferences[i][finalOutcome]bestPreference){bestPreferencepreferences[i][finalOutcome];bestOutcomefinalOutcome;}}dp[i][state]bestOutcome;}}// 输出从第一位祭司、初始状态0NNN开始的最终结果coutoutcomes[dp[0][0]]endl;}return0;}总结本题是一个典型的逆向动态规划问题关键在于理解每位祭司的决策依赖于后续祭司的最优选择。通过从最后一位祭司开始向前递推我们可以确定在任意状态下最终会达到的结果。最终答案即为d p [ 0 ] [ 0 ] dp[0][0]dp[0][0]对应的结果字符串。这种“逆推最优决策”的思想在博弈论和动态规划中非常常见本题提供了一个很好的应用实例。