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;
}
评论 (0)