Codeforces Round #816 (Div. 2) C. Min-Max Array Transformation算法本质思维思路推演a[] + d[] = b[]，独立的求d[i]的最值。可以看作对某个a[i]找出可以选择的b[j]。因为一定有解，所以至少会有一个解是，每个a[i]对应的就是b[i]，这种对应解先称之为标准解。既然让我们求最值，说明一定是存在一些情况，对b[]的选择起到限制作用。先看最小值，明面上的限制：b[j]>=a[i]，思考，如果采用简单的贪心去做，是否可能导致最后无解。经过简单的推算可知，方法：先对特定的a[i]对应尽量小的b[i]，对于有解一定是正面作用。所以最小值就搞定了。再看最大值，如果考虑贪心，明面上甚至没有限制条件了。当然题目不可能这么简单，所以自己造样例来找到暗地里的限制。自造样例1： a[]：2 5 6 b[]：4 8 9这里可以看出，a[1]只能对应b[1]的，完全不符合我们说的贪心，究其原因是因为b[1]太小，只有标准解的对应。这样的逻辑关系该如何表示呢？自造样例2： a[]：2 5 9 b[]：4 8 9在自造样例2中，就只有标准解这唯一方法了。通过这2个样例，敏锐地可以察觉到，a[1]之所以不能选择b[2]、b[3]，是因为a[2]、a[3]的最低对应已经把b[2]、b[3]给用完了。可以看到，当我们思考a[1]能对应的最大b[j]时，需要考虑a[2]、a[3]，这明显是需要从后往前遍历来获取信息。逻辑方面，我们把a[i]的最低对应的b[j]的j记录出现次数，用cnt[]来存放。以自造样例1为例，cnt[]的情况如下：cnt[]：1 2 0 cnt[i]=x表示：b[i]被对应了x次。最开始设mm=b[n]，mm表示当前a[i]能取到对应的最大b[i]的值。然后我们从右往左遍历，当下标为i时，取cnt[i+1 ~ n]的和，如果和等于n-i，说明a[i+1 ~ n]通过最低对应，已经用完了b[i+1 ~ n]，当前的a[i]的最大对应为b[i]，更新mm=b[i]，更新cnt[]。同时也可以结合题目性质做出一些改进，比如会发现，要想满足cnt[i+1 ~ n]的和==n-i，其实等同于当前的a[i]最低对应值为b[i]。代码思路因为求最小值（最低对应值）是不需要额外信息的，所以整体从右往左遍历，最小、大值一起求解。设mm=b[n]，从右往左遍历，用二分求得a[i]最低对应值b[j]，b[j]-a[i]记录到答案最小值。mm-a[i]记录到答案最大值，若j等于i，更新mm=b[i-1]，ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], b[maxn]; int da[maxn][2]; //da[][0、1]分别记录最小、大值 inline void solve() { // init cin>>n; rep(i,1,n) cin>>a[i]; rep(i,1,n) cin>>b[i]; //cal int mm=b[n]; for (int i=n; i>=1; i--) { int pos = lower_bound(b+1, b+1+n, a[i])-b; //找到a[i]的最低对应b[pos] da[i][0] = b[pos]-a[i]; da[i][1] = mm-a[i]; if (pos==i) mm=b[i-1]; } //out rep(i,1,n) cout<<da[i][0]<<" "; cout<<endl; rep(i,1,n) cout<<da[i][1]<<" "; cout<<endl; return; }D. Maximum AND算法本质思维（贪心）思路推演最开始可能会误以为是数学题，整个题的运算就是异或、和，通过改变部分数字的位置，寻求最大值。但是朝这个方向思考了一会，没有找到规律和式子。所以转向了另一个比较明显的方向，求多个数字位运算和的最大值。很明显，把数字以二进制展开，肯定优先保证最高位为1。至于优先保证的方法，可以通过调整b[]中元素位置来实现。这个思路其实相对简单，甚至担心有假，用数据推算了一下复杂度，发现是有可能的，于是继续思考。若要使得答案二进制x位为1，则c[]所有元素二进制x位都得为1，则需要所有的相对应的a[i]、b[i]二进制x位必须一个为0、一个为1。这个实现挺简单的，我们只需要统计他们的二进制x位出现的次数就好了。形象的，我们调整a[] b[]中元素位置：把a[]中二进制x位为1的统统放到左边，二进制x位为0的放到右边。b[]则为0的放到左边，为1的放到右边。若能对齐（a[]中元素二进制x位为1的数目 == b[]中元素二进制x位为0的数目），则说明二进制x位可以对齐。但是发现一个问题，我们可能在对齐x位时，打乱了x+?位的布置。于是为了贯彻贪心思想，从高位开始遍历，一旦对齐了x位，就需要对原数组采取分块的思想，分成2组。之后要想答案y位为1，就需要所有组都能对齐。可以看到，代码将会由2部分组成：分块思想+对齐思想。对齐思想十分简单，只需要历遍一次元素即可。那么分块思想该如何实现：朴素的想法当然是用分块实现。参考分块那章的思想。把是一组的元素放在一起，为一个分块，同时记录每个分块的左右边界。运算时，如果所有分块都能对齐。则对每个分块进行再分块——使用deque先记录元素，然后重新赋值元素，更改原分块的信息、创建一个新的块。整体过程虽然有些繁琐，但是思路十分清晰，复杂度也是可行的。另外一个想法则更为巧妙，分到一组的元素有什么特点：他们在ans（答案值）为1的二进制位上，一定是一致的。表现为ans&a[i] == ans&a[j]，则a[i]与a[j]一定是一组的。（b[]同理）所以我们可以建立2个map<int, int> mapa, mapb，分别记录ans&a[i]的个数——即mapa[ ans&a[i] ]++，mapb同理。这个操作实质上是记录每个组的，面对当前x位的0、1数目。a[]中ans&a[i]一组所对应的是b[]中的ans&a[i]^ans。这也就意味，如果：mpa[ a[i]&ans ] == mpb[ a[i]&ans^ans ]就说明这个组是可对齐的。第二个想法整体更巧妙，代码采用第二个想法。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], b[maxn]; inline void solve() { // init cin>>n; rep(i,1,n) cin>>a[i]; rep(i,1,n) cin>>b[i]; //cal ans=0; int shu=qpow(2, 30); //小优化，虽然实际没有用 for (int j=30; j>=0; j--) { ans += shu; unordered_map <int, int> mpa, mpb; //记录不同组的0、1个数 rep(i,1,n) mpa[ a[i]&ans ]++; rep(i,1,n) mpb[ b[i]&ans ]++; flag=1; for (int i=1; i<=n; i++) { if (mpa[ a[i]&ans ] != mpb[ a[i]&ans^ans ]) //^ans是全部对应，^shu是当前位对应 { flag=0; break; } } if (!flag) ans-=shu; shu /= 2; } //out cout<<ans<<endl; return; }可以注意到的是，每个组的对齐检测可能存在多次检测（位运算），这也是为什么第二个想法用时相对较长的原因。不过实际上2个方法的最坏复杂度是一致的。E. Prefix Function Queries算法本质dp（字符串kmp）考察对kmp算法里的nxt[]理解是否深刻。思路推演首先看到这个题会觉得很奇怪，kmp算法的复杂度是O(n)，题面上只是简单的更换了最后部分的数据。但马上就会联想到，虽然kmp算法复杂度为O(n)，但是那种平摊复杂度。以aaaab举例，在计算nxt[]数组时，很明显为0 1 2 3 0，但是在计算字母b也就是nxt[4]时，其用时显著高于其他元素，单次计算达到了O(n)，但是平摊综合来看（数学推导），整体复杂度任然为O(n)。所以题目中，如果我们采取正常的kmp算法，其最坏复杂度约为O(n*q)，肯定无法通过。这里面，最重要的是降低查询的复杂度，必须做到O(1)或者O(log~2~n)查询。到这里也就明白了，题目要求我们根据条件对kmp求nxt[]进行优化。至于如何优化，就从复杂度过高的情况说起。复杂度最高的情况就是类似aaa...aaab，求nxt[n]时，需要一点一点向前动。最好能整个一步到位或者倍增实现，两个想法的复杂度分别对应O(1)和O(log~2~n)。至于倍增，没有什么说法，此题中没有单调性，字符串里的字母没有特殊意义（比如大小）、单纯表示两者不同或相同。再看一步到位，相对可行，于是朝这个方向继续思考。为了适应不同的字符串t，所以肯定是需要对26个字母的情况都作出维护。维护数组qf[][]，qf[x][y]=z表示当nxt[]回溯下标为x且当前字符为y时，直接回溯到正确下标z——这样就可以省去中间的许多步骤，降低复杂度。通过仔细思考、研究，发现维护qf[][]可行。（具体实现看代码思路、代码）思路回顾想到基础的做法——发现难点（基础做法复杂度过大）——找到导致复杂度过大的情况，根据题目优化。这道题整体简单，是因为题目的意义会引导向kmp算法方向去想，最后去针对性优化kmp。代码思路核心就是如何维护qf[][]，这个维护的过程就是dp（其实kmp也可以看作dp）。维护的核心就在于找到状态转移方程。转移方程：nxt[i] = qf[ nxt[i-1] ][ ch[i] ] //使用qf[][]一步到位 qf[i-1][ ch[i] ] = i //显而易见，回溯到上一个点，且当下字符为ch[i]时，最终回溯下标一定为i qf[i-1][ 其他字母 ] = qf[ nxt[i-1] ][ ch[i] ] //若当前的还没更新，直接找到上一个点ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int last[maxn], qf[maxn][30], q; //qf[x][y]=z：回找下标为x，字符为y的情况，可以直接查找到下标z去 char ch2[100]; inline void solve() { //init scanf("%s", ch+1); n = strlen(ch+1); cin>>q; //构造时间回溯功能——last[]和它的升级版：qf[][] last[1]=0; qf[0][ ch[1]-'a' ] = 1; //qf[x][y]=z：回找下标为x，字符为y的情况，可以直接查找到下标z去，不用依次查找浪费时间 for (int i=2; i<=n; i++) { last[i] = qf[ last[i-1] ][ ch[i]-'a' ]; //使用qf[][]一步到位 for (int j='a'; j<='z'; j++) //状态转移方程 { if (ch[i] == j) qf[i-1][j-'a'] = i; //回溯到上一个点，且当下字符为ch[i]时，最终回溯下标一定为i else qf[i-1][j-'a'] = qf[ last[i-1] ][j-'a']; //若当前的还没更新，直接找到上一个点 } } //cal while (q--) { // init scanf("%s", ch2+1); m = strlen(ch2+1); for (int i=1; i<=m; i++) //衔接到ch上 ch[n+i] = ch2[i]; //cal for (int i=n+1; i<=n+m; i++) { last[i] = qf[ last[i-1] ][ ch[i]-'a' ]; //同上 for (int j='a'; j<='z'; j++) { if (ch[i] == j) qf[i-1][j-'a'] = i; //同上 else qf[i-1][j-'a'] = qf[ last[i-1] ][j-'a']; //同上 } } //out rep(i, n+1, n+m) cout<<last[i]<<" "; cout<<endl; } return; }

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; }

测试页面 Hello World!