题目描述题目要求计算每个沼泽投票者的Banzhaf\texttt{Banzhaf}Banzhaf权力指数。给定通过一项法令所需的最低票数majority\textit{majority}majority以及每个沼泽持有的票数Banzhaf\texttt{Banzhaf}Banzhaf权力指数定义为该沼泽能够改变投票结果即从失败变为通过的次数。具体来说对于每个沼泽iii考虑所有不包括iii的投票子集若这些子集的票数和SSS满足SmajorityS \textit{majority}Smajority但Svotes[i]≥majorityS \textit{votes}[i] \ge \textit{majority}Svotes[i]≥majority则该子集计为一次关键投票。权力指数即为这样的关键投票子集的数量。输入格式输入包含多行每行最多808080个字符。每行第一个整数为majority\textit{majority}majority通过所需的最低票数后续若干个整数为每个沼泽持有的票数。沼泽数量不超过272727。输出格式对于每个测试用例每行输入输出一行包含每个沼泽的Banzhaf\texttt{Banzhaf}Banzhaf权力指数按输入顺序排列之间用单个空格分隔。样例输入17 1 7 3 12 9 1 2000 214 306 298 274 270 261 246 404 241 240 240 238 224 333 210 12 1 7 3 12 9 1 2200 214 306 298 274 270 261 246 404 241 240 240 238 224 333 210输出2 14 2 18 14 2 2666 3934 3806 3474 3418 3218 3094 4734 3022 3006 3006 2978 2798 4402 2622 1 5 5 19 11 1 2453 3593 3493 3183 3137 3051 2841 4817 2777 2763 2763 2741 2527 4035 2395题目分析本题的核心是计算每个投票者的Banzhaf\texttt{Banzhaf}Banzhaf权力指数即统计所有不含该投票者的子集中票数和小于majoritymajoritymajority但加上该投票者后大于等于majoritymajoritymajority的子集个数。问题转化设总共有nnn个投票者票数数组为v[0..n−1]v[0..n-1]v[0..n−1]通过所需票数为MMM。对于投票者kkk定义power(k)∣{S⊆{0,…,n−1}∖{k} | ∑i∈Sv[i]M≤∑i∈Sv[i]v[k]}∣ power(k) \left| \left\{ S \subseteq \{0,\ldots,n-1\} \setminus \{k\} \;\middle|\; \sum_{i \in S} v[i] M \le \sum_{i \in S} v[i] v[k] \right\} \right|power(k){S⊆{0,…,n−1}∖{k}i∈S∑v[i]M≤i∈S∑v[i]v[k]}即所有不含kkk的子集中满足上述条件的个数。动态规划方法对于每个kkk我们需要统计所有不含kkk的子集的票数和分布。这可以通过0/1\texttt{0/1}0/1背包问题实现定义dp[s]dp[s]dp[s]表示不考虑kkk时子集和为sss的方案数。初始化dp[0]1dp[0] 1dp[0]1。遍历所有i≠ki \ne kik对于每个iii从大到小更新dpdpdpdp[j]dp[j−v[i]]dp[j] dp[j - v[i]]dp[j]dp[j−v[i]]。计算完成后power(k)∑jmax(0,M−v[k])M−1dp[j]power(k) \sum_{j \max(0, M - v[k])}^{M-1} dp[j]power(k)∑jmax(0,M−v[k])M−1dp[j]。复杂度分析对于每个kkk需要运行一次0/1\texttt{0/1}0/1背包时间复杂度O(n×sum)O(n \times sum)O(n×sum)其中sumsumsum为总票数和。由于n≤27n \le 27n≤27票数可能较大但总和有限直接使用大小为sum1sum1sum1的数组即可。若总和过大可优化只计算到MMM附近但题目数据范围下直接运行可接受。实现细节使用memset或fill初始化dpdpdp数组。注意dp[0]1dp[0] 1dp[0]1表示空子集。在累加power(k)power(k)power(k)时注意下界max(0,M−v[k])\max(0, M - v[k])max(0,M−v[k])和上界M−1M-1M−1。输出时按输入顺序输出每个power(k)power(k)power(k)。代码实现// Swamp County Supervisors// UVa ID: 430// Verdict: Accepted// Submission Date: 2018-03-19// UVa Run Time: 0.000s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN10010;intdp[MAXN];intvotes[30],majority0,members0,cnt0;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;while(getline(cin,line)){// Read input.istringstreamiss(line);issmajority;cnt0;while(issmembers)votes[cnt]members;// DP, knapsack, count of different subset sum.for(intk0;kcnt;k){memset(dp,0,sizeof(dp));dp[0]1;for(inti0;icnt;i){if(ik)continue;for(intjmajority;jvotes[i];j--)if(dp[j-votes[i]])dp[j]dp[j-votes[i]];}// Print.intpowerIndex0;for(intimax(0,majority-votes[k]);imajority;i)powerIndexdp[i];if(k)cout ;coutpowerIndex;}cout\n;}return0;}
UVa 430 Swamp County Supervisors
题目描述题目要求计算每个沼泽投票者的Banzhaf\texttt{Banzhaf}Banzhaf权力指数。给定通过一项法令所需的最低票数majority\textit{majority}majority以及每个沼泽持有的票数Banzhaf\texttt{Banzhaf}Banzhaf权力指数定义为该沼泽能够改变投票结果即从失败变为通过的次数。具体来说对于每个沼泽iii考虑所有不包括iii的投票子集若这些子集的票数和SSS满足SmajorityS \textit{majority}Smajority但Svotes[i]≥majorityS \textit{votes}[i] \ge \textit{majority}Svotes[i]≥majority则该子集计为一次关键投票。权力指数即为这样的关键投票子集的数量。输入格式输入包含多行每行最多808080个字符。每行第一个整数为majority\textit{majority}majority通过所需的最低票数后续若干个整数为每个沼泽持有的票数。沼泽数量不超过272727。输出格式对于每个测试用例每行输入输出一行包含每个沼泽的Banzhaf\texttt{Banzhaf}Banzhaf权力指数按输入顺序排列之间用单个空格分隔。样例输入17 1 7 3 12 9 1 2000 214 306 298 274 270 261 246 404 241 240 240 238 224 333 210 12 1 7 3 12 9 1 2200 214 306 298 274 270 261 246 404 241 240 240 238 224 333 210输出2 14 2 18 14 2 2666 3934 3806 3474 3418 3218 3094 4734 3022 3006 3006 2978 2798 4402 2622 1 5 5 19 11 1 2453 3593 3493 3183 3137 3051 2841 4817 2777 2763 2763 2741 2527 4035 2395题目分析本题的核心是计算每个投票者的Banzhaf\texttt{Banzhaf}Banzhaf权力指数即统计所有不含该投票者的子集中票数和小于majoritymajoritymajority但加上该投票者后大于等于majoritymajoritymajority的子集个数。问题转化设总共有nnn个投票者票数数组为v[0..n−1]v[0..n-1]v[0..n−1]通过所需票数为MMM。对于投票者kkk定义power(k)∣{S⊆{0,…,n−1}∖{k} | ∑i∈Sv[i]M≤∑i∈Sv[i]v[k]}∣ power(k) \left| \left\{ S \subseteq \{0,\ldots,n-1\} \setminus \{k\} \;\middle|\; \sum_{i \in S} v[i] M \le \sum_{i \in S} v[i] v[k] \right\} \right|power(k){S⊆{0,…,n−1}∖{k}i∈S∑v[i]M≤i∈S∑v[i]v[k]}即所有不含kkk的子集中满足上述条件的个数。动态规划方法对于每个kkk我们需要统计所有不含kkk的子集的票数和分布。这可以通过0/1\texttt{0/1}0/1背包问题实现定义dp[s]dp[s]dp[s]表示不考虑kkk时子集和为sss的方案数。初始化dp[0]1dp[0] 1dp[0]1。遍历所有i≠ki \ne kik对于每个iii从大到小更新dpdpdpdp[j]dp[j−v[i]]dp[j] dp[j - v[i]]dp[j]dp[j−v[i]]。计算完成后power(k)∑jmax(0,M−v[k])M−1dp[j]power(k) \sum_{j \max(0, M - v[k])}^{M-1} dp[j]power(k)∑jmax(0,M−v[k])M−1dp[j]。复杂度分析对于每个kkk需要运行一次0/1\texttt{0/1}0/1背包时间复杂度O(n×sum)O(n \times sum)O(n×sum)其中sumsumsum为总票数和。由于n≤27n \le 27n≤27票数可能较大但总和有限直接使用大小为sum1sum1sum1的数组即可。若总和过大可优化只计算到MMM附近但题目数据范围下直接运行可接受。实现细节使用memset或fill初始化dpdpdp数组。注意dp[0]1dp[0] 1dp[0]1表示空子集。在累加power(k)power(k)power(k)时注意下界max(0,M−v[k])\max(0, M - v[k])max(0,M−v[k])和上界M−1M-1M−1。输出时按输入顺序输出每个power(k)power(k)power(k)。代码实现// Swamp County Supervisors// UVa ID: 430// Verdict: Accepted// Submission Date: 2018-03-19// UVa Run Time: 0.000s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN10010;intdp[MAXN];intvotes[30],majority0,members0,cnt0;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;while(getline(cin,line)){// Read input.istringstreamiss(line);issmajority;cnt0;while(issmembers)votes[cnt]members;// DP, knapsack, count of different subset sum.for(intk0;kcnt;k){memset(dp,0,sizeof(dp));dp[0]1;for(inti0;icnt;i){if(ik)continue;for(intjmajority;jvotes[i];j--)if(dp[j-votes[i]])dp[j]dp[j-votes[i]];}// Print.intpowerIndex0;for(intimax(0,majority-votes[k]);imajority;i)powerIndexdp[i];if(k)cout ;coutpowerIndex;}cout\n;}return0;}
