首页
关于
Search
1
Codeforces Round 930 (Div. 2)
14 阅读
2
Codeforces Round 931 (Div. 2)
9 阅读
3
测试页面
6 阅读
4
Codeforces Round 922 (Div. 2)
6 阅读
5
Codeforces Round 926 (Div. 2)
6 阅读
默认分类
codeforces
登录
Search
算法小何
累计撰写
87
篇文章
累计收到
1
条评论
首页
栏目
默认分类
codeforces
页面
关于
搜索到
86
篇与
的结果
2024-08-26
Codeforces Round #812 (Div. 2)
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; }
2024年08月26日
4 阅读
0 评论
0 点赞
1
...
17
18