P10883 [COCI 2017/2018 #2] Doktor题目描述夫人说「我已经骑马十五年了不可能把马倒着钉蹄铁」……「是的那是倒着的。」——多马戈伊低声说道看着马特的手正在玩一个经过大幅修改的纸牌游戏 Hanabi。为了简单起见马特手中有NNN张牌按顺序编号为1,2,…,N1, 2, \dots, N1,2,…,N。每个数字从111到NNN恰好出现一次。就像玩真正的游戏一样他不能主动改变牌的顺序。为了让任务至少与故事有些关联多马戈伊会指向马特手中一段连续的牌子序列。他也可以指向单张牌但至少会指向一张牌。然后马特将「旋转」该连续子数组并放回去。旋转可以被认为是将给定子数组中的所有牌旋转 180 度。这意味着第一张和最后一张牌交换位置第二张和倒数第二张牌交换位置依此类推。和我们所有人一样多马戈伊非常喜欢不动点。换句话说就是牌的数字与它们在手中的位置相匹配的牌从多马戈伊的左侧开始计数。因此他希望在旋转给定子数组后不动点的数量尽可能多。帮助多马戈伊找出他需要指出哪一段连续子数组以便在旋转该子数组后马特手中的不动点数量达到最大。输入格式输入的第一行包含正整数N(1≤N≤500000)N (1 \leq N \leq 500000)N(1≤N≤500000)表示马特手中的牌数。接下来的行包含多马戈伊看到的马特手中牌的顺序。输出格式你必须输出一行包含AAA和BBB即所需连续子数组的起始和结束牌上的数字按此顺序。如果有多个选项输出其中任意一个。输入输出样例 #1输入 #14 3 2 1 4输出 #13 1输入输出样例 #2输入 #22 1 2输出 #21 1输入输出样例 #3输入 #37 3 6 5 7 4 1 2输出 #33 2说明/提示在第一个测试用例中旋转从 3 开始到 1 结束的连续子数组后牌的顺序将变为 1 2 3 4现在所有的牌都是不动点。在这个例子中给定的输出是唯一正确的输出。在第二个测试用例中旋转任何仅包含一张牌的子数组会导致相同的牌顺序这种顺序产生最大数量的不动点。由 ChatGPT 4o 翻译C实现#includebits/stdc.husingnamespacestd;constintmaxn5e5100;intn,a[maxn100],b[maxn100],c[maxn100],ans0,ans11,ans21;vectorintvec[(maxn1)100];boolcmp(inta,intb){returnab;}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;for(inti1;in;i)cina[i];for(inti1;in;i){b[i]b[i-1];if(a[i]i)b[i];vec[a[i]i].push_back(min(a[i],i));}for(inti1;i2*n;i){if(vec[i].size()0)continue;sort(vec[i].begin(),vec[i].end(),cmp);for(intj0;jvec[i].size();j){intlposvec[i][j];if(j1b[lpos-1]-b[i-lpos]ans){ansj1b[lpos-1]-b[i-lpos];ans1a[lpos];ans2a[i-lpos];}}}if(ans0)cout1 1\n;elsecoutans1 ans2\n;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容