阿里达摩院秋招 2023.08.30 编程题目与题解

发表于 2023-09-02 更新于 2023-09-04 分类于笔试阅读次数：本文字数： 3.6k 阅读时长 ≈ 3 分钟

1、小红的回文博弈

小红和朋友玩游戏，初始有一个字符串\(s\)，两个人轮流操作：

先将字符串重新排列
如果可以通过重新排列得到一个回文串，则游戏结束，当前操作的人获胜
否则，当前操作的人必须删除字符串中的一个字符

小红先手，两人都采用最优策略，问最后谁能获胜。

输入

第一行一个整数\(t\)，表示数据组数。接下来\(t\)行，每行一个字符串\(s\)，仅包含小写学母，长度不超过\(100000\)。

\(1\le t\le 20\)

输出

输出\(t\)行，每行一个字符串，小红获胜输出"red"，朋友获胜输出"friend"。

样例

输入：
3
aab
abc
abcd

输出：
red
red

提示：
第一组，小红可以重新排列得到回文串"aba"，获胜。
第二组，小红删除后，朋友无法获胜，朋友删除后只剩下一个字符，是回文串，小红获胜。

解答

一个字符串可以重新排列成一个回文字符串，当且仅当所有字符的出现频率中，至多只有一个字符的频率值是奇数（这意味着这个字符必须放在中间）。

如果一开始，所有字符的频率都是偶数，那么自然先手必胜。否则，每次删除操作都会改变一个字符频率的奇偶性。这意味着，奇数频率个数的奇偶性也在必定也会发生变化。更具体的，假设有\(k\)个字符的频率是奇数，那么每次操作中，\(k\)要么加\(1\)，要么减\(1\)。只要\(k\)能变成\(1\)，那么当前的玩家就获胜了。最终，只有一开始\(k\)的奇偶性和\(1\)相同（也就是奇数），那么先手才会胜利，否则先手必败。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int T;
    string s;
    cin>>T;
    while(T--){
        cin>>s;
        int bs=0;
        for(char ch:s)
            bs^=1<<(ch-'a');
        int m=__builtin_popcount(bs);
        puts(m==0||(m&1)?"red":"friend");
    }
}

2、小红的二叉树

小红拿到了一个奇怪的二叉树，如下图：

graph TD
  1((1));2((2));3((3));4((4));
  5((5));6((6));7((7));8((8));
  9((9));10((10));11((11));
  1---3;1---2;3---4;3---5;
  2---6;2---7;6---11;6---10;
  7---9;7---8;

输入

第一层从左往右赋值，第二层从右往左赋值，第兰房从左往右赋值……以此类推。这个二叉树有无穷多层。

小红有\(t\)次询问，每次询问输入两个正整数\(x,y\)，她想知道\(x\)和\(y\)在二叉树上的路径长度是多少。你能帮帮她吗？

第一行输入一个正整数\(q\)，代表询问次数。接下来的\(q\)行，每行输入两个正整数\(x,y\)，代表一次询问。

\(1\le q\le 10^5\)
\(1\le x,y\le 10^9\)

输出

输出\(q\)行，每行输出一个整数，代表该次询问的答案。

样例

输入：
3
11 4
2 5
7 7

输出：
5
3
0

解答

这题我们不难想到二叉堆这个数据结构。这棵树和二叉堆的区别在于（假设根处于第\(0\)层）：奇数层的节点是被逆序的。

并且它和二叉堆还有一个共同点：如果结点\(x\)的最高位比特是第\(k\)位，那么它在第\(k\)层。

由于二叉堆求解父亲节点非常方便，因此我们需要将这棵树的节点序号映射回二叉堆的节点序号。具体做法是，如果节点\(x\)在偶数层，那么\(x\)的编号可以直接返回；如果\(x\)在奇数层，那么其在二叉堆的位置可以通过列式计算得出为：\(3\cdot 2^k-1-x\)，其中\(k\)是节点\(x\)所在的层数。

那么，现在假设\(x',y'\)分别是树节点\(x,y\)映射到了二叉堆中所对应的编号。接下来就是模拟求取\(x',y'\)的最小公共祖先(LCA)的搓成，从而求出\(x'\)和\(y'\)之间的距离。不失一般性，假设\(x'<y'\)，那么首先需要将\(y'\)上升到至少和\(x'\)一样的深度，接下来进行多次迭代，每次迭代都让这两个节点走向它们的父亲，直到到达相同的父亲\(z\)，这时\(z\)就是\(x\)和\(y\)的LCA。我们只需要统计整个过程中向父亲总共移动的次数，就能得到\(x'\)和\(y'\)之间的距离。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int bit_count(int x){
    int cnt=0;
    for(;x;x>>=1)
        ++cnt;
    return cnt;
}
int origin_id(int x){
    int k=bit_count(x)-1;
    if(!(k&1)) return x;
    else return (3<<k)-1-x;
}
int solve(int x,int y){
    if(x>y) swap(x,y);
    int bx=bit_count(x),by=bit_count(y),ans=0;
    int d=by-bx;
    ans+=d;
    y>>=d;
    if(x==y) return d;
    for(;(x>>1)!=(y>>1);x>>=1,y>>=1,ans+=2);
    return ans+2;
}
int main(){
    int q,x,y;
    scanf("%d",&q);
    while(q--){
        scanf("%d %d",&x,&y);
        x=origin_id(x);
        y=origin_id(y);
        printf("%d\n",solve(x,y));
    }
}

3、小红的矩形扩散

小红准备用以下方式生成一个无穷大的矩阵：

首先构造一个\(\text{size-}1\)的\(2\ast2\)矩阵：

1
2

1 2
3 4

之后构造一个\(\text{size-}2\)的\(4\ast4\)矩阵：

其中它可以拆分成\(4\)个\(2\ast 2\)的小矩阵，左上j角和右下角即为\(\text{size-}1\)的矩阵，左下角和右上角的\(2\ast2\)矩阵与\(\text{size-}1\)的矩阵中心对称。

然后构造出\(\text{size-}3\)的矩阵:

1 2 4 3 4 3 1 2
3 4 2 1 2 1 3 4
4 3 1 2 1 2 4 3
2 1 3 4 3 4 2 1
4 3 1 2 1 2 4 3
2 1 3 4 3 4 2 1
1 2 4 3 4 3 1 2
3 4 2 1 2 1 3 4

其中它可以拆分成\(4\)个\(4\ast 4\)的小矩阵，左上角和右下角即为\(\text{size-}2\)的矩阵，左下角和右上角的\(2\ast2\)矩阵与\(\text{size-}2\)的矩阵中心对称。

按照这种方式可以无限构造下去，\(\text{size-}n\)的左上角和右下角为\(\text{size-}n-1\)矩阵，左下角和右上角是\(\text{size-}2\)矩阵的中心对称矩阵。

我们定义，矩阵的坐标是从\(1\)开始的（并不是从\(0\)开始）。也就是说，矩阵的左上角的坐标是\((1,1)\)。

小红想知道，对于左上角为\((x_0,y_0)\)，右下角为\((x_1,y_1)\)的子矩阵，该短阵内部的所有数之和是多少？

由于答案过大，请对\(10^9+7\)取模。

输入

一行四个正整数\(x_0,y_0,x_1,y_1\)，用空格隔开。

\(1\le x_0\le x_1\le 10^9\)
\(1\le y_0\le y_1\le 10^9\)

输出

矩阵内部所有数之和对\(10^9+7\)取模的值。

样例

输入：
2 2 3 4

输出：
13

提示：
该子矩阵是：
4 2 1 
3 1 2
所有数之和为13。

解答

本题可以使用二维前缀和的思想进行求解。令\(s(x,y)\)表示前\(x\)行前\(y\)列所围成的子矩阵的整数和，其中\(s(\cdot,0)=s(0,\cdot)=0\)，那么原题目的答案为\(s(x_1,y_1)-s(x_0-1,y_1)-s(x_1,y_0-1)+s(x_0-1,y_0-1)\)。

接下来的问题就转化成了求解\(s(x,y)\)。

令\(f(x,y,k)\)表示，对于一个\(\text{size-}k\)的矩阵，求解其前\(x\)行前\(y\)列的所有数之和。可见，\(s(x,y)=f(x,y,\cdot)\)。

由于一个\(\text{size-}k\)的矩阵可以分成\(4\)块，因此我们可以使用分治法求解\(f(x,y,k)\)。现在考虑如下\(4\)种情况（它们不是互斥的），其中令\(m=2^{k-1}\)（也就是说，\(m\)是这些矩阵的上下或左右半区分界线）：

第一种情况是\(f(x,y,k)\)包含了\(\text{size-}k\)左上角子矩阵。因为这个子矩阵和\(\text{size-}k-1\)是一样的，因此这一部分的值由\(f(\min\{x,m\},\min\{y,m\},k-1)\)给定。
第二种情况是如果\(y>m\)，那么说明\(f(x,y,k)\)包含了右上角子矩阵。包含了右上角子矩阵的前\(\min\{x,m\}\)行，前\(y-m\)列。由于这个矩阵是由\(\text{size-}k-1\)中心对称而来，因此实际上求解的是\(\text{size-}k-1\)中以\((m-\min\{x,m\}+1，m-(y-m)+1)\)为左上角，以\((m,m)\)为右下角的矩阵元素之和。因此这一部分的值由如下式子给定：

\[f(m,m)-f(m-\min\{x,m\},m)-f(m,m-(y-m))+f(m-\min\{x,m\},m-(y-m)).\]

第三种情况和第二种情况类似，如果\(x>m\)，那么说明\(f(x,y,k)\)包含了左下角子矩阵。包含了左下角子矩阵的前\(x-m\)行，前\(\min\{y,m\}\)列。由于这个矩阵是由\(\text{size-}k-1\)中心对称而来，因此实际上求解的是\(\text{size-}k-1\)中以\((m-(x-m)+1，m-\min\{y,m\}+1)\)为左上角，以\((m,m)\)为右下角的矩阵元素之和。因此这一部分的值由如下式子给定：

\[f(m,m)-f(m-(x-m),m)-f(m,m-\min\{y,m\})+f(m-(x-m),m-\min\{y,m\}).\]

第四种情况和第一种情况类似，如果\(x>m\land y>m\)，那么说明\(f(x,y,k)\)包含了右下角子矩阵。包含了右上角子矩阵的前\(x-m\)行，前\(y-m\)列。由于这个矩阵是由\(\text{size-}k-1\)直接得出的，因此实际上这部分的值由\(f(x-m,y-m,k-1)\)给定。

最终将如上\(4\)种情况合并即可。

在实现的过程中，我们还需要记忆化搜索的思想，记录已经求解出的所有\(s(x,y)\)值，避免重复求解。在这时，求解\(s(x,y)\)是非常快的。

代码

mp = {(1, 1): 1, (1, 2): 3, (2, 1): 4, (2, 2): 10}
x0, y0, x1, y1 = map(int, input().split())
mod = 10 ** 9 + 7


def cal(n, m, k):
    if n == 0 or m == 0:
        return 0
    elif (n, m) in mp.keys():
        return mp[(n, m)]
    mid = 1 << (k - 1)
    s = cal(min(mid, n), min(mid, m), k - 1)
    if m > mid:
        n1 = min(mid, n)
        m1 = m - mid
        s += cal(mid, mid, k - 1) - cal(mid - n1, mid, k - 1) - cal(mid, mid - m1, k - 1) + cal(mid - n1, mid - m1, k)
    if n > mid:
        n1 = n - mid
        m1 = min(mid, m)
        s += cal(mid, mid, k - 1) - cal(mid - n1, mid, k - 1) - cal(mid, mid - m1, k - 1) + cal(mid - n1, mid - m1, k)
    if n > mid and m > mid:
        s += cal(n - mid, m - mid, k - 1)
    mp[(n, m)] = s
    return s


k = 32
ans = (cal(x1, y1, k) - cal(x0 - 1, y1, k) - cal(x1, y0 - 1, k) + cal(x0 - 1, y0 - 1, k)) % mod
print(ans)