【2018QBXT刷题游记】
Day1 TEST2
T1 vote
【问题描述】
一场选举有三位选手分别编号为 1,2,3，还有两位评委 4,5。
评委打分时会给出一个{1,2,3}的排列，表示评委对选手的喜爱程度。 例如评
委给出一个排列{2,1,3}，表示最喜欢 2，其次是 1，最后是 3。
两位评委将分别给出排列 x、 y。你需要做的是综合考虑 x、 y，给出一个最
终的排名 z。
由于事先不知道 x、 y，所以你需要对于每一种不同的 x、 y，都提前设计好
相应的 z。（显然 x、 y 有 36 种情况）
正式地，你需要设计一个映射{X,Y}-->{Z}，其中定义域是评委的排列，值
域是你给出的最终排列。（定义域大小是 36，值域大小是 6，所以映射数量是
6^36）。为了方便，用 z=f(x,y)表示评委打分是 x,y 时最终排名是 z。
如果随便给一个映射，可能会被喷，比如两个评委都最喜欢 1，你最后却把
1 排在最后。为了避免这种情况，你的映射可能需要满足几个条件：
一致性：对于选手 a,b，如果两个评委都更喜欢 a，那么最终排名中 a 应当排
在 b 前面。
独立性： 定义函数(I(x,a,b))，如果排列 x 中 a 的位置比 b 靠前，那么 (I(x,a,b)=1). 否则 (I(x,a,b)=0)。 对于选手 a,b，考虑评委打分的两种情况((x1,y1)和(x2,y2))， 如果 (I(x1,a,b)=I(x2,a,b))，并 且 (I(y1,a,b)=I(y2,a,b))，那么 (f(x1,y1)) 和 (f(x2,y2)) 应当满足 (I(f(x1,y1),a,b)=I(f(x2,y2),a,b))。
非独裁： 如果对于任意的排列 x,y， (f(x,y)=x)，那么称评委 4 独裁。如果对于任意的 x,y， (f(x,y)=y)，那么称评委 5 独裁。非独裁就是两个评委都不独裁。
【分析】这……一共就五种可能的m……第一次见到这种题，跪了。
言归正传，这道题归根究底还是搜索，因为对于两个评委和映射值，都分别只有6种可能。我们用二进制数0,1,3,4,6,7表示可能出现的六种情况：
比如：3=011，表示在这种情况下，1在2后面，1在3前面，2在3前面。
于是dfs即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 8
#define ll long long
bool valid[MAXN]={1,1,0,1,1,0,1,1};
int val[MAXN][MAXN];
ll ans=0;int m;
void judge(){
bool flag=1;
for(int i=0;i<MAXN;i++){
for(int j=0;j<MAXN;j++){
if(!valid[i]||!valid[j])continue;
if(val[i][j]!=i){flag=0;break;}
}if(flag==0)break;
}
if(flag)return;
flag=1;
for(int i=0;i<MAXN;i++){
for(int j=0;j<MAXN;j++){
if(!valid[i]||!valid[j])continue;
if(val[i][j]!=j){flag=0;break;}
}if(flag==0)break;
}
if(flag)return;
ans++;return;
}
void dfs(int x,int y){
if(x>=MAXN){
if(m==5){
judge();return;
}
else {ans++;return;}
}
int xx=x,yy=y+1;if(yy>=MAXN){yy=0;xx++;}
if(!valid[x]||!valid[y]){dfs(xx,yy);return;}
for(int i=0;i<MAXN;i++){
if(!valid[i])continue;
val[x][y]=i;
int tmp=(x^y^7);
if(m>3 && (x&tmp)!=(val[x][y]&tmp))//不满足一致性
continue;
bool flag=1;
for(int j=0;j<x;j++){
for(int k=0;k<MAXN;k++){
if(!valid[j]||!valid[k])continue;
if(j==x&&k==y)break;//xy前面的都结束了
int a=(((x^j^7)&(y^k^7)));
int b=(val[j][k]^val[x][y]^7);
if(a!=(a&b)){flag=0;break;
}
}if(flag==0)break;
}
if(flag)dfs(xx,yy);
}
}
void dfs2(int x,int y){
if(x>=MAXN){
ans++;return;
}
int xx=x,yy=y+1;if(yy>=MAXN){yy=0;xx++;}
if(!valid[x]||!valid[y]){dfs2(xx,yy);return;}
int tv=0;
for(int i=0;i<MAXN;i++){
if(!valid[i])continue;
val[x][y]=i;
int tmp=(x^y^7);
if((x&tmp)==(val[x][y]&tmp))tv++;
}
ans*=tv;
dfs2(xx,yy);
}
int main(){
scanf("%d",&m);
if(m==1){
printf("10314424798490535546171949056
");
}
else if(m==2){
ans=1;
dfs2(0,0);
printf("%lld
",ans);
}
else{
dfs(0,0);
printf("%lld
",ans);
}
return 0;
}