E. Cross Swapping
算法本质
思维
思路推演
先说点废话。
做题无非就是题目给你要求，你使用给的条件完成目的。
所以最简单的题都是一眼看出来的，所以要想题目难度增加，得学会伪装。
比如上一题：D.Tournament Countdown
你就会发现一个点，如果要用平时的眼观去看，你需要2^n^次询问才能搞定，但是实际题目只给你2/3*2^n^的询问次数，这个少出来的地方，明确是缺信息熵的，题目肯定会补给你，但是会换一种方式。后面仔细一看题，哦参赛选手是按照编号站位置的，细细一琢磨，就把这个信息熵补上了。
E题也是一样的，但是既然作为E题，难度增加了，题目又会给一点伪装。
- 搞明白规则，发现图分为左下、右上2个部分
- 从最重要的位置开始模拟一下会发现，整个图只用右上部分（右上的优先级更高，而左下被右上确定了）
这上面这2点基础的伪装看破了，剩下的其实就和D题难度差不多了。
这个时候已经没可以一眼看破的伪装了，就观看这个题整体，发现我们最担心的是，当我用操作k改变高优先级的格子时，可能会导致一些低优先级格子出现变化。这就导致没有一个特定的解去搞定。
但是我们也知道，说是没有解，肯定是信息用的不够全。
有一个暴力做法的想法是，优先级依次降低的格子进行操作，如果操作能不改变更高优先级格子状态，就允许。
我当时是这个做法，但实际上后来发现，如何判断能否改变更高优先级格子状态这个点没考虑全面，最后出现了一个可做的复杂度算法，wa了。
实际这个没有被抓住的信息在这：每个格子改变自身状态的方式只有2种。
如果以操作k为思考单位的话，就会发现，实际上这是一个关系问题。
比如对于格子x，若其想改变状态，其对应的2种操作必须相异。
我们依照优先级访问格子，每个格子会告诉其对应2种操作的关系，我们尽量一一满足直到无法满足。
至于如何满足这种类似朋友、敌人、路人的关系，则需要涉及一点点数据结构知识：改版并查集
只要是有关系，都用并查集圈起来，如果是朋友，则正常处理，如果是敌人，则需要一些标记。
代码思路
见代码注释。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int mp[maxn][maxn];
//先使用init_set()初始化
int fu[maxn];
void init_set()
{
for (int i=0; i<=n; i++) fu[i] = i; // i 就在它本身的集合里
return;
}
int find_set(int x)
{
if (fu[x]==x) return fu[x]; //查询到根节点
if (x < 0) //有关系，但是是敌对状态
return -find_set(-x); //转化为正常的x
else //有关系，但是是友好状态
return fu[x] = find_set(fu[x]);
}
void union_set(int x, int y) // x 与 y 所在家族合并, 如果是敌对关系，让x y其中一个为负数
{
x = find_set(x);
y = find_set(y);
if (abs(x) == abs(y)) //已经存在关系了，无论后面的关系与前面一致与否，都可以直接忽略
return;
if (x < 0)
fu[-x] = -y;
else
fu[x] = y;
}
void huan(int k) //操作k反应到mp[][]中的函数
{
//具体替换
for (int x=1; x<k; x++)
swap(mp[x][k], mp[k][x]);
for (int y=k+1; y<=n; y++)
swap(mp[k][y], mp[y][k]);
}
inline void solve()
{
//init
cin>>n;
rep(i,1,n) rep(j,1,n)
cin>>mp[i][j];
//cal
init_set();
for (int x=1; x<=n; x++)
{
for (int y=x+1; y<=n; y++)
{
if (mp[x][y] > mp[y][x]) //需要改变，2个操作是敌人
union_set(x, -y);
else if (mp[x][y] < mp[y][x]) //不改变，2个操作是朋友
union_set(x, y);
// debug2(x, y)
}
}
//cal 2
for (int i=1; i<=n; i++)
{
fu[i] = find_set(i); //规定一个关系集里面，为负号的操作需要进行
if (fu[i] < 0)
huan(i);
}
//out
for (int x=1; x<=n; x++)
{
for (int y=1; y<=n; y++)
cout<<mp[x][y]<<" ";
cout<<endl;
}
return;
}
评论 (0)