[NOI2008]赛程安排(提交答案+模拟退火)

第一道提交答案题

题面

随着奥运的来临，同学们对体育的热情日益高涨。在 ION2008 来临之际，
学校正在策划组织一场乒乓球赛。小 Z 作为一名狂热的乒乓球爱好者，这正是
他大展身手的好机会，于是他摩拳擦掌，积极报名参赛。
本次乒乓球赛采取淘汰赛制，获胜者晋级。恰好有 $n$ ($n$ 是 $2$ 的整数次幂，不
妨设 $n=2^k$)个同学报名参加，因此第一轮后就会有 $2k?1$ 个同学惨遭淘汰，另外 $2k?1$个同学晋级下一轮；第二轮后有 $2k?2$ 名同学晋级下一轮，… 依次类推，直到 $k$
轮后决出冠亚军：具体的，每个人都有一个 $1$~$n$ 的初始编号，其中小 Z 编号为 $1$，
所有同学的编号都不同，他们将被分配到 $n$ 个位置中，然后按照类似下图的赛程
进行比赛：

为了吸引更多的同学参加比赛，本次比赛的奖金非常丰厚。在第 i 轮被淘汰
的选手将得到奖金 $a_i$元，而冠军将获得最高奖金 $a_{k+1}$ 元。显然奖金应满足 $a1<a_2<\dots <a_{k+1}$.
在正式比赛前的热身赛中，小 Z 连连败北。经过认真分析之后，他发现主要的失败原因不是他的球技问题，而是赢他的这几个同学在球风上刚好对他构成相克的关系，所以一经交手，他自然败阵。小 Z 思索：如果在正式比赛中能够避开这几位同学，该有多好啊!
假设已知选手两两之间交手的胜率，即选手 A 战胜选手 B 的概率为 $P_{A,B}$ (保
证 $P_{A,B}+P_{B,A}=1$)。于是小 Z 希望能够通过确定比赛的对阵形势（重新给每个选手安排位置），从而能够使得他获得尽可能多的奖金。你能帮助小 Z 安排一个方案，
使得他这场比赛期望获得的奖金最高么？

评分

每个测试点单独评分。
对于每一个测试点，如果你的输出文件不合法，如文件格式错误、输出解不
符合要求等，该测试点得 $0$ 分。否则如果你的输出的期望奖金为 $you{r}_{ans}$，参考
期望奖金为 $ou{r}_{ans}$，我们还设有一个用于评分的参数 $d$，你在该测试点中的得
分如下：
如果 $you{r}_{ans}>ou{r}_{ans}$，得 $12$ 分。
如果 $you{r}_{ans}<ou{r}_{ans}?d$，得 $1$ 分。
否则得分为：
$$?\frac{you{r}_{ans}?ou{r}_{ans}?d}{ou{r}_{ans}?ou{r}_{ans}?d}?+2$$

题解

下面提供几种做法

乱搞1

我会输入输出！
每个测试点输出$1$~$n$的排列。
期望得分:$1?10=10$

乱搞2

我会$Random$ $shuffle$！
输出$1$~$n$的随机排列。
期望得分:$\ge 10$

乱搞3

我会玩$checker$！
手动调用$checker.exe$计算期望。
期望得分:$???$

checker

显然，在做这道题之前，我们必须先写一个复杂度优秀的$checker$程序。
也就是计算一个排列期望的函数。
考虑借用分治的思想。
设$Pw[p][k]$为第$p$位选手赢得第$k$场比赛的概率。
显然$Pw[p][k]$可以转移为
$$Pw[p][k]=\sum _{j=l}^{r}Pw[p][k?1]?Pw[j][k?1]?P[p][j]$$
$l$,$r$的含义详见checker。
那么期望的计算也十分简单了~
分析一下复杂度
$T(n)=2T(\frac{n}{2})+O(n^2)$
因此复杂度为:$O(n^{2}logn)$

void check(int L,int R,int dep)
{
    if(L==R){
    Pw[sA[L]][dep]=1;return ;}int mid=(L+R)/2;check(L,mid,dep+1);check(mid+1,R,dep+1);for(int i=L;i<=R;i++)Pw[sA[i]][dep]=0;for(int i=L;i<=mid;i++)for(int j=mid+1;j<=R;j++){
    Pw[sA[i]][dep]+=Pw[sA[i]][dep+1]*Pw[sA[j]][dep+1]*P[sA[i]][sA[j]];Pw[sA[j]][dep]+=Pw[sA[i]][dep+1]*Pw[sA[j]][dep+1]*P[sA[j]][sA[i]];}if(L==1)sdist+=(Pw[1][dep+1]-Pw[1][dep])*val[dep];
}

子任务1-2

难度:1
好了，进入正题。

$k=3$,数据随机。
T1 $p=0.1$[明显送分啊qwq] T2 $p=0.95$

此时$n=8$,显然直接枚举排列每次$check$一下，取最优解即可。
复杂度$O(n!n^{2}logn)$

子任务3-5

难度:2

$k=4$,数据随机。
T3 $p=0.1$[送分] T4 $p=0.9$ T5 $p=0.98$

此时$n=16$,考虑使用随机算法。
我们可以用$Random$ $shuffle$来随机生成一个排列再进行$check$。
然而这样并不能找到最优解。
考虑使用模拟退火算法。
初始解为$1$~$n$的排列。
每次交换两个数字并进行计算。
若优于当前解则直接接受这种方案，否则以一定的概率接受这种方案[可以先学一下模拟退火算法]。
然而，即使如此，这个算法也需要$10?500$次模拟退火才能找到最优解。
但已足以解决这5个子任务了。

1-5总结

以上5个子任务属于常规搜索算法技巧。
并没有用到任何优化，只要能够顺利实现便可以轻松拿到$55$分。

子任务6-7

难度:3

T6 $k=6$,T7 $k=8$,数据有明显规律。
T6 $p=0.99$ T7 $p=0.6$

数据规模明显增大，但翻看数据会发现概率只有$0$,$0.5$,$1.0$三种情况。
我们先来研究第六个子任务。

如上图
再仔细观察会发现1的个数较少，我们可以先统计出每个选手对其他选手必胜的个数。
然后是这样的：

0个:16人
1个:8人
2个:4人
3个:2人
4个:1人
5个:1人

规律十分明显，我们可以猜测一下这组数据的意图。
我们或许可以构造出一组排列，使得每次比赛都有一个人必胜?
考虑使用遍历树的方法来遍历它。
将每个人看成一个节点，定义它的$size$为他一定能够打败的总人数。
对于一个人$i$,若他一定能够打败某人，就将他与$i$号节点连边。
我们先从$1$号节点开始遍历，先访问$size$最小的对手，并递归它的儿子。
那么答案就是这颗树的$DFS$序。
解决了子任务6,那么子任务7就简单多了。
按子任务6的方式统计一下:

0个:64人
1个:32人
2个:16人
3个:8人
4个:4人
5个:4人

也同样很有规律，但注意到$size$为5的人有4个，这意味着我们无法保证编号为$1$的人必胜，但是，他能进前4强是必然的。
我们可以找到这4个人的编号，分别为1,65,129,193。
由于我们要保证1的期望最大，所以一定要从1开始遍历。
后面的3个节点任意顺序遍历都可以，我们可以枚举顺序取最优解。
经蒟蒻枚举，这个顺序为1,193,129,65。
以下是参考代码:

//针对测试点#6,7
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstring>
#include<vector>
using namespace std;
#define MAXN 256
#define MAXD 8
#define DB long double
#define INF 10e18
#define SE second
int n,k;
int A[MAXN+5],sA[MAXN+5],val[MAXN+5],best[MAXN+5];
int sx,sy,cnt[MAXN+5],pcnt[MAXN+5],vis[MAXN+5];
DB T,ans,st,sdist,P[MAXN+5][MAXN+5],Pw[MAXN+5][MAXD+1];
vector< pair<int,int> > G[MAXN+5];
int num;
int read()  
{
      int x=0,f=1;char s=getchar();  while(s<'0'||s>'9'){
    if(s=='-')f=-1;s=getchar();}  while(s>='0'&&s<='9'){
    x=x*10+s-'0';s=getchar();}  return x*f;  
}
void check(int L,int R,int dep)
{
    if(L==R){
    Pw[sA[L]][dep]=1;return ;}int mid=(L+R)/2;check(L,mid,dep+1);check(mid+1,R,dep+1);for(int i=L;i<=R;i++)Pw[sA[i]][dep]=0;for(int i=L;i<=mid;i++)for(int j=mid+1;j<=R;j++){
    Pw[sA[i]][dep]+=Pw[sA[i]][dep+1]*Pw[sA[j]][dep+1]*P[sA[i]][sA[j]];Pw[sA[j]][dep]+=Pw[sA[i]][dep+1]*Pw[sA[j]][dep+1]*P[sA[j]][sA[i]];}if(L==1)sdist+=(Pw[1][dep+1]-Pw[1][dep])*val[dep];
}
void slove(int x)
{
    if(vis[x])return ;vis[x]=1;A[++num]=x;for(int i=0;i<G[x].size();i++){
    int xnt=G[x][i].SE;slove(xnt);}
}
int main()
{
    freopen("match6.in","r",stdin);freopen("match6.out","w",stdout);srand(time(NULL));n=read();while(n>(1<<k))k++;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
    cin>>P[i][j];if(P[i][j]==1)cnt[i]++;}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(P[i][j]==1)G[i].push_back(make_pair(cnt[j],j));for(int i=1;i<=n;i++)sort(G[i].begin(),G[i].end());slove(1);/*slove(193);slove(65);//for #7slove(129);*//*for(int i=1;i<=n;i++){printf("%d ",cnt[i]);pcnt[cnt[i]]++;}printf("\n");for(int i=1;i<=k;i++)printf("%d ",pcnt[i]);printf("\n");for(int i=1;i<=n;i++)if(cnt[i]==k-2)printf("%d ",i);printf("\n");//打表专用 */ for(int i=k;i>=0;i--)scanf("%d",&val[i]);for(int i=1;i<=n;i++)sA[i]=A[i];sdist=0;check(1,n,1);sdist+=Pw[1][1]*val[0];ans=sdist;int P=1000;//cout<<ans<<endl;for(int i=1;i<=n;i++)printf("%d\n",A[i]);
}

子任务8-9

难度:2

$k=7$,T8 数据有明显规律,T9 数据有规律。
T8 $p=0.9$ T9 $p=0.9$

其实这两个子任务的规律比两个子任务明显的多。
先来看看子任务8:

极易发现数据每行从上往下单调递减，同时，数据每列从左往右单调递增。
十分容易想出一种贪心的方法，即:一号选手在第一个位置，其余选手按编号从大往小排列。
显然这种方法算出的方案是最优的。
再先来看看子任务9:

感觉很乱?
确实，但这组数据还是有它的规律。
我们单独对行与行，列与列之间两两进行分析，可以发现

若$a_{i,1}>a_{j,1}$则对于 $?p\in [1,n]$有 $a_{i,p}>a_{j,p}$
若$a_{1,i}>a_{1,j}$则对于 $?p\in [1,n]$有 $a_{p,i}>a_{p,j}$
反之亦然

那我们能得到什么呢?
对比子任务8，发现它也满足这样一个条件。
综上，我们可以看出，其实9仅仅只是将8的数据编号打乱了而已。
仅仅需要排序，再重新标号即可。
这里仅提供子任务8的代码

//针对测试点#8
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstring>
#include<vector>
using namespace std;
#define MAXN 256
#define MAXD 8
#define DB long double
#define INF 10e18
#define SE second
int n,k;
int A[MAXN+5],sA[MAXN+5],val[MAXN+5],best[MAXN+5];
int sx,sy,cnt[MAXN+5];
DB T,ans,st,sdist,P[MAXN+5][MAXN+5],Pw[MAXN+5][MAXD+1];
vector< pair<int,int> > G[MAXN+5];
int num;
int read()  
{
      int x=0,f=1;char s=getchar();  while(s<'0'||s>'9'){
    if(s=='-')f=-1;s=getchar();}  while(s>='0'&&s<='9'){
    x=x*10+s-'0';s=getchar();}  return x*f;  
}
void check(int L,int R,int dep)
{
    if(L==R){
    Pw[sA[L]][dep]=1;return ;}int mid=(L+R)/2;check(L,mid,dep+1);check(mid+1,R,dep+1);for(int i=L;i<=R;i++)Pw[sA[i]][dep]=0;for(int i=L;i<=mid;i++)for(int j=mid+1;j<=R;j++){
    Pw[sA[i]][dep]+=Pw[sA[i]][dep+1]*Pw[sA[j]][dep+1]*P[sA[i]][sA[j]];Pw[sA[j]][dep]+=Pw[sA[i]][dep+1]*Pw[sA[j]][dep+1]*P[sA[j]][sA[i]];}if(L==1)sdist+=(Pw[1][dep+1]-Pw[1][dep])*val[dep];
}
int main()
{
    freopen("match8.in","r",stdin);freopen("match8.out","w",stdout);srand(time(NULL));n=read();while(n>(1<<k))k++;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>P[i][j];A[1]=1;for(int i=2;i<=n;i++)A[n-i+2]=i;for(int i=k;i>=0;i--)scanf("%d",&val[i]);for(int i=1;i<=n;i++)sA[i]=A[i];sdist=0;check(1,n,1);sdist+=Pw[1][1]*val[0];ans=sdist;int P=1000;//cout<<ans<<endl;for(int i=1;i<=n;i++)printf("%d\n",A[i]);
}

6-9总结

这类子任务对选手的观察能力要求较高，但对于熟练掌握提答技巧的选手来说较为简单。
其核心在于找到该组数据的特殊性质。

子任务10

难度:3

$k=7$,数据随机。
$p=0.85$

没错，这就是阻止你AK脚步的罪魁祸首。
即使出题人如此毒瘤，但我们仍然能够想办法让自己的答案在这个数据点上得到高分。
怎么做呢?
回顾一下之前我们用于子任务3-5的模拟退火算法。
在之前的算法中，我们的初值设为$1$~$n$的排列，而每次仅交换两个数。
是不是不够“随机”呢?
考虑将初值$Random$ $shuffle$一下，每次随机交换多个数。[当然，也不能交换多了，不然就失掉了原来最优解的性质]
这样的话，找到最优解的概率就大大提升了。
据测试，这样做可以直接通过子任务8-9，子任务10可以获得$7$分及以上的高分，在提答中已经算是很高的分数了。
如果你有时间的话，可以尝试将程序跑上一天，或许就能得到$10$分甚至$12$分的分数了。[ps:这道题仅有最后一个数据点有得到12分的可能]

//针对测试点1-5以及测试点10的部分分 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstring>
using namespace std;
#define MAXN 256
#define MAXD 8
#define DB long double
#define INF 10e18
int n,k;
int A[MAXN+5],sA[MAXN+5],val[MAXN+5],best[MAXN+5];
int sx,sy;
DB T,ans,st,sdist,P[MAXN+5][MAXN+5],Pw[MAXN+5][MAXD+1];
int read()  
{
      int x=0,f=1;char s=getchar();  while(s<'0'||s>'9'){
    if(s=='-')f=-1;s=getchar();}  while(s>='0'&&s<='9'){
    x=x*10+s-'0';s=getchar();}  return x*f;  
}
void check(int L,int R,int dep)
{
    if(L==R){
    Pw[sA[L]][dep]=1;return ;}int mid=(L+R)/2;check(L,mid,dep+1);check(mid+1,R,dep+1);for(int i=L;i<=R;i++)Pw[sA[i]][dep]=0;for(int i=L;i<=mid;i++)for(int j=mid+1;j<=R;j++){
    Pw[sA[i]][dep]+=Pw[sA[i]][dep+1]*Pw[sA[j]][dep+1]*P[sA[i]][sA[j]];Pw[sA[j]][dep]+=Pw[sA[i]][dep+1]*Pw[sA[j]][dep+1]*P[sA[j]][sA[i]];}if(L==1)sdist+=(Pw[1][dep+1]-Pw[1][dep])*val[dep];
}
int main()
{
    freopen("match10.in","r",stdin);//freopen("match10.out","w",stdout);srand(time(NULL));n=read();while(n>(1<<k))k++;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>P[i][j];for(int i=k;i>=0;i--)scanf("%d",&val[i]);ans=0;int P=100;for(int i=1;i<=n;i++)A[i]=i;random_shuffle(A+1,A+n+1);while(P--){
    T=10000000000;while(T>0.01){
    for(int i=1;i<=n;i++)sA[i]=A[i];do{
    do{
    sx=rand()%(n-1)+2,sy=rand()%(n-1)+2;}while(sx==sy||sx==sy+1||sx+1==sy);swap(sA[sx],sA[sy]);}while(rand()%2);sdist=0;check(1,n,1);sdist+=Pw[1][1]*val[0];if(sdist>st){
    st=sdist;for(int i=1;i<=n;i++)A[i]=sA[i];if(sdist>ans){
    ans=sdist;for(int i=1;i<=n;i++)best[i]=sA[i];}}else if(exp((st-sdist)/T)<(rand()%100000)/100000.0){
    st=sdist;for(int i=1;i<=n;i++)A[i]=sA[i];}T*=0.99;}}cout<<ans<<endl;for(int i=1;i<=n;i++)printf("%d\n",best[i]);
}

总结

总的来说，这道题算NOI中提交答案类型题目的简单题。
掌握随机化技巧，寻找数据特殊性质是关键。