[NOI2009] 变换序列

题意

的整数序列中,定义两个数 的距离为 .

现要求构造一个序列 ,使得每一个 的距离都等于给定的 ,且 序列中的元素互不相同。

求出字典序最小的 序列. .

分析

对于每一个 而言有两个数与其对应: .

而要求元素互不相同,就是从序列 做匹配,那就是二分图匹配了

要求字典树最小,我们尝试构造贪心策略

错误的贪心策略

考虑匈牙利算法的执行过程,想到从 依次匹配,优先匹配小的点

但是这个策略是不对的。因为这样的局部贪心不能推导出全局最优解。在匈牙利算法的执行过程中,可能会修改之前的匹配结果,使得字典序变大。

正确的贪心策略

既然匈牙利算法的执行过程会修改之前的匹配结果,那么我们就改变匹配的顺序,使得修改后的结果一定会变得更优。

我们将图的边按结点编号从小到大排序,每次优先访问小的结点,即优先匹配小的结点

然后我们倒着从 枚举到 依次匹配,即可找出最优解。

下面简单感性证明一下:

  • 在匹配结点 的过程中,一定会优先遍历和它连接的字典序最小的点,因此如果成功寻找增广路,那么对结点 部分的点一定是最优解
  • 而正因为 的点采用优先匹配小的结点的策略,使得 匹配到的点是 部分的最优解。也就是说, 的贪心策略能够推导出 的最优解,那么数学归纳一下,倒着贪心就能推导出全局最优解

代码

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=2e4+5;
int n;

struct qxx{int nex,t;};
qxx e[N*2];
int h[N],cnt=1;
void add_path(int f,int t){e[++cnt]=(qxx){h[f],t},h[f]=cnt;}

int match[N],vis[N],cur;
bool dfs(int u){for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t;
        if(vis[v]==cur)continue;
        vis[v]=cur;
        if(match[v]==-1||dfs(match[v]))return match[v]=u,match[u]=v,1;
    }
    return 0;
}
bool hungarian(){
    bool res=1;
    memset(match,-1,sizeof(match));
    for(int i=n-1;i>=0;i--)if(match[i]==-1)++cur,res=res&&dfs(i);
    return res;
}
pair<int,int> tmp_edge[N*2];
int tnt;
int main(){scanf("%d",&n);
    for(int i=0,d;i<n;i++){scanf("%d",&d);
        int x=(i+d)%n+n,y=(i-d+n)%n+n;
        tmp_edge[++tnt]=make_pair(x,i);
        tmp_edge[++tnt]=make_pair(y,i);
        if(x>y)add_path(i,x),add_path(i,y);
        else add_path(i,y),add_path(i,x);
    }
    sort(tmp_edge+1,tmp_edge+tnt+1);
    for(int i=tnt;i>=1;i--)add_path(tmp_edge[i].first,tmp_edge[i].second);
    if(!hungarian())return puts("No Answer"),0;
    for(int i=0;i<n;i++)printf("%d",match[i]-n);
    return 0;
}

  转载请注明: Sshwy's Blog [NOI2009] 变换序列

 上一篇
[USACO12MAR] 花盆 [USACO12MAR] 花盆
题意给定 n 个点 和一个整数 ,求一个最小区间 ,使得点集 中的纵坐标的极差 最大. 输出区间长度 . $n\leq 10^5,x
2019.01.15
下一篇 
[SCOI2010] 连续攻击游戏 [SCOI2010] 连续攻击游戏
题意游戏里有很多的装备,每种装备都有 2 个属性,属性值为 [1,10000] 之间的数。 使用某种装备只能使用该装备的一个属性。每种装备最多只能使用一次。 要求使用的装备的属性值从 1 开始连续递增,想知道他最多能连续攻击多少次? 分析
2019.01.14
  目录