题解 P3921 【小学数学题】

解法0： 学习⑨，输出-1 0 期望得分：0分 解法0.5： 输出1 1 期望得分：10分 解法1： 将所有人的位置作为状态，建出图来暴力BFS+DP 加入状态压缩优化常数 条件1等价于状态i中i&((1<<(a-1))|(1<<(b-1)))==0或i&((1<<(a-1))|(1<<(b-1)))==((1<<(a-1))|(1<<(b-1))) 条件2可以进行类似的转化 不要忘记考虑条件2中b==c的情况 时间复杂度O(2^(2\*n)) 期望得分:30~70分（取决于常数） 解法2： 优化建图 新建节点(i,j,k)表示与状态i 后j位完全相同 且 剩余位置上差异恰有k位 从(i,j,k)向(i,j-1,k)和(i^(1<<(j-1)),j-1,k+1)连一条权值为0的边 再从(i,0,k)向(i,n,0)连一条权值为1的边（0<=k<=r） 最后从((1<<n)-1,0,k)向T连一条权值为0的边(0<=k<=r) 再在新图上跑BFS+DP 时间复杂度O((n^2)\*(2^n)) 期望得分90~100分（取决于常数） 有一点细节，DP的时候需要当做所有边权值为1跑，否则答案会出问题（更新顺序不对） 呜呜呜~~~比赛时被解法1水过了（90分），很不开心QAQ 不给标程啦