bzoj1562:[noi2009]变换序列

关键词：

Description

Input

Output

Sample Input

Sample Output

HINT

30%的数据中N≤50；
60%的数据中N≤500；
100%的数据中N≤10000。

思路{

　　容易想到,问题的答案就是i和d(i,T)所限制的点连边做最大匹配,

　　问题是怎么保证字典序呢?

　　然后发现如果从后开始做匈牙利的话根据匈牙利的思想(

　　能上就上,否则创造机会上.若能匹配表示匹配当前字典序最大,

　　否则为了满足当前字典序更改后面的节点的匹配状况)是能够满足的.

　　直接上匈牙利就可以了.

}

#include<bits/stdc++.h>
#define LL long long
#define RG register
#define il inline
#define N 100010
using namespace std;
int n,d[N],BL[N],Ans[N];bool used[N];
int dd(int x,int y){return min(n-abs(x-y),abs(x-y));}
struct ed{int nxt,to;}e[N*2];
int head[N],tot;
void link(int u,int v){e[tot].nxt=head[u];e[tot].to=v;head[u]=tot++;}
bool find(int u){
  for(int i=head[u];i!=-1;i=e[i].nxt)
  if(!used[e[i].to]){
    int v=e[i].to;
    used[v]=true;
    if((!BL[v])||find(BL[v])){
      BL[v]=u;
      return true;
    }
  }return false;
}
int main(){
  memset(head,-1,sizeof(head));
  scanf("%d",&n);
  for(int i=0;i<n;++i){
    scanf("%d",&d[i]);
    int x=i+d[i],y=i-d[i];
    x%=n,y=(y+n)%n;
    if(dd(x,i)!=d[i])x=-1;
    if(dd(y,i)!=d[i])y=-1;
    if(x>y)swap(x,y);
    if(y!=-1)link(i,y);
    if(x!=-1)link(i,x);
  }
  for(int i=n-1;i!=-1;i--){
    memset(used,0,sizeof(used));
    if(find(i)!=1)cout<<"No Answer
",exit(0);
  }for(int i=0;i<n;++i)Ans[BL[i]]=i;
  for(int i=0;i<n-1;++i)cout<<Ans[i]<<" ";
  cout<<Ans[n-1];
  return 0;
}

bzoj1562:[noi2009]变换序列

二分图匹配求最小字典序。从后面往前搞就可以了。然后因为我邻接表的写法不能add(i,v)再add(i,d)！！！注意邻接表的顺序#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>#include<bitset>usingnamespacestd;#def 查看详情

bzoj1562[noi2009]变换序列：二分图匹配

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1562题意：　　给定n，定义D(x,y)= min(|x-y|,n-|x-y|)，然后给定数组d[i]=D(i,T[i])。　　让你求一个0到n-1的排列T，下标i∈[0,n-1]，满足给定的D(i,T[i])，且字典序最小。　　若没有答案... 查看详情

bzoj1562[noi2009]变换序列km算法(代码片段)

题目输入格式输出格式输入样例511221输出样例12403提示30%的数据中N≤50；60%的数据中N≤500；100%的数据中N≤10000。题解每个位置可以和两种数匹配，显然是一个二分图匹配问题但要求字典序最小，我们就按字典序存边由于在KM算法... 查看详情

bzoj1562jzyzoj1730cogs409noi2009变换序列二分图匹配

...     对于N个整数0,1,……, N-1，一个变换序列T可以将i变成Ti，其中定义x和y之间的距离。给定每个i和Ti之间的距离D(i,Ti)，你需要求出一个满足要求的变换序列T。如果有多个满足条件的序列，输出其中字典序... 查看详情

noi2009变换序列

noi2009变换序列一、题目1843变换序列 2009年NOI全国竞赛 时间限制:1s 空间限制:128000KB 题目等级:大师Master题解   题目描述 Description对于N个整数0，1，&hellip;，N-1，一个变换序列T可以将i变成Ti，其中... 查看详情

p1963[noi2009]变换序列(代码片段)

https://www.luogu.org/problemnew/show/P1963 题目描述对于 NN 个整数 0,1,\cdots,N-10,1,?,N?1 ，一个变换序列 TT 可以将 ii 变成 T_iTi? ，其中 T_i\in\0,1,\cdots,N-1\Ti 查看详情

[noi2009]变换序列(代码片段)

DescriptionInputOutputSampleInput511221SampleOutput12403HINT 30%的数据中N≤50；60%的数据中N≤500；100%的数据中N≤10000。二分图匹配匈牙利算法的原理是冲突时替换不过要求字典序最小，一个点会连出2条边，加边先加入大的，这样在匹配时... 查看详情

p1963[noi2009]变换序列(匈牙利)(代码片段)

P1963[NOI2009]变换序列(匈牙利)构造一个字典序最小的全排ppp(0开始)满足min(∣i−pi∣,n−∣i−pi∣)=aimin(|i-p_i|,n-|i-p_i|)=a_imin(∣i−pi​∣,n−∣i−pi​∣)=ai​可以转化为二分图匹配问题。关键如何求字典序最求，我们知... 查看详情

[luogup1963][noi2009]变换序列（二分图最大匹配）

传送门 根据公式xjb推一下，然后就可以连边。考虑到字典序最小，和匈牙利算法的实现过程，要倒序匹配。 #include<cmath>#include<cstdio>#include<vector>#include<cstring>#include<iostream>#include<algorithm>#d 查看详情

题解[noi2009]变换序列（二分图匹配）

懒得复制，戳我戳我Solution:这个题面出的很毒瘤，读懂了其实是个板子题qwq题面意思：有个\(0\)至\(N-1\)的数列是由另一个数列通过加减得到的，相当于将\(A_i\)变成\(i\)，每一步的代价计算就是\(min(A_i-i,N-(A_i-i))\)，并且\(A_i\left(0<... 查看详情

bzoj1566noi2009管道取珠

...66　　　两个栈不断pop，共C（n+m，n）种，ai表示每个相同序列的方案数，求∑(ai^2)sol ：首先，将相同的序列看做两个人选取后相同的方案数　　　考虑Dp，dp[i][j][k][l]表示第一个人从上面选i个，下面选j个，第二个人上k个下l... 查看详情

bzoj1566noi2009管道取珠

...也没有想明白……首先，这道题要我们求所有（不同输出序列的方案数）的平方和，于是我们当然就想到求所有不同输出序列的方案数……（大雾） 。这道题一个巧妙的地方就在于对问题的转化。（以下摘自BYVoid大神的题解... 查看详情

bzoj1565:[noi2009]植物大战僵尸

1565:[NOI2009]植物大战僵尸TimeLimit: 10Sec  MemoryLimit: 64MBSubmit: 2317  Solved: 1071[Submit][Status][Discuss]DescriptionInputOutput仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不 查看详情

bzoj1565:[noi2009]植物大战僵尸

1565:[NOI2009]植物大战僵尸TimeLimit: 10Sec  MemoryLimit: 64MBSubmit: 2318  Solved: 1072[Submit][Status][Discuss]DescriptionInputOutput仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不 查看详情

bzoj1565noi2009植物大战僵尸

1565:[NOI2009]植物大战僵尸TimeLimit: 10Sec  MemoryLimit: 64MBSubmit: 2034  Solved: 944[Submit][Status][Discuss]DescriptionInputOutput仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进 查看详情

[bzoj1564][noi2009]二叉查找树

[BZOJ1564][NOI2009]二叉查找树试题描述输入输出只有一个数字，即你所能得到的整棵树的访问代价与额外修改代价之和的最小值。输入示例410123412341234输出示例29数据规模及约定(n)开成(110)足够了。题解先将节点按照中序遍历（即数... 查看详情

bzoj1565[noi2009]植物大战僵尸

TimeLimit: 10Sec  MemoryLimit: 64MBSubmit: 2363  Solved: 1092DescriptionInputOutput仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。SampleInput32100200-100-51001 查看详情

bzoj1566[noi2009]管道取珠

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1566【题解】考虑表示的实际意义，相当于我取两次球，得到方案完全相同的个数。设$f_{i,j,k}$表示取了$i$个，第一种上面取$j$个，第二种上面取$k$个，随便转移。复杂度$O(n^3)$。#includ... 查看详情