米哈游秋招 2023.08.27 编程题目与题解

发表于 2023-08-28 分类于笔试阅读次数：本文字数： 3.3k 阅读时长 ≈ 3 分钟

1、米小游与地城探宝

给定一个$n$行$n$列的地图，米小游初始时在位置$(1,1)$战斗力为$H$。

米小游可以上下左右进行移动，但不可以越过边界，每次移动都视为一次行动，若移动到的格子中有怪物，则可以额外进行一次行动发动战斗（先战斗再结算行动）。

地图上有两个怪物，第$i$个怪物坐标为$(x_i,y_i)$，战斗力为$h_i$，米小游每行动$a_i$次，怪物就会强化一次，战斗力提升$b_i$。

若米小游战斗力严格低于怪物，则她无法击败怪物，否则米小游击败第$i$个怪物后，战斗力会下降，下降大小为战斗前怪物的战斗力。

米小游想知道她击败两个怪物后，最多可以剩余多少战斗力。若米小游无法击败两个怪物，则输出"yingyingying"。

输入

第一行输入两个整数$n(1\le n\le 10^5),H(1\le H\le 10^9)$分别表地图大小、兴小游的战斗力。

接下来两行，每行输入$5$个整教表示第个怪物的属性$x_i,y_i(1\le x_i,y_i \le n),h_i,a_i,b_i(1 \le h_i,a_i,b_i \le 10^5)$

数据保证，米小游和两个怪物一定在$3$个不同的位置。

输出

输出一个整数表示答案。

样例

输入：
3 10
1 3 2 2 1
3 3 1 5 100

输出：
4

提示：
第1次行动，米小游移动到(1,2)
第2次行动，米小游移动到(1,3)，第1个怪物进行了一次强化，战斗力变成3，但米小游不发动战斗
第3次行动，米小游移动到(2,3)
第4次行动，米小游移动到(3.3)，第1个怪物进行了一次强化，战斗力变成4
第5次行动，米小游发动战斗，击败了第2个怪物，米小游战斗力变为9(10-1)
第6次行动，米小游移动到(2.3)，第1个怪物进行了一次强化，战斗力变成5
第7次行动，米小游移动到(1,3)
第8次行动，米小游发动战斗，击败了第1个怪物，米小游战斗力变为4(9-5)
因此答案为4，可以证明，没有更小的答案。

输入：
3 10
1 3 114 5 14
3 3 191 9 810

输出：
yingyingying

提示：
米小游无法击败两个怪物。

解答

为了避免怪物的攻击值添加过大，我们应该尽可能地走近路分别去击败这两只怪物。

路线无非就是决定先击败哪个怪物，这些路线仅有$2$条，直接枚举其中最优的一条即可。

那么，走近路的至少需要的距离为这两点间的曼哈顿距离，即$|x_1-x_2|+|y_1-y_2|$。

不失一般性，假设先击败第$1$只怪物，再击败第$2$只怪物，那么在和第$1$只怪物战斗时，它的攻击力增长到$h_1+\left\lfloor\dfrac{|x_1-1|+|y_1-1|}{a_1}\right\rfloor\cdot b_1$，那么在和第$2$只怪物战斗时，它的攻击力增长到$h_2+\left\lfloor\dfrac{|x_1-1|+|y_1-1|+|x_1-x_2|+|y_1-y_2|}{a_2}\right\rfloor\cdot b_2$。

由此，直接计算出攻击力较大的一条路线即可。

代码

class Monster:
    def __init__(self, x, y, h, a, b):
        self.x, self.y, self.h, self.a, self.b = x, y, h, a, b


n, h = map(int, input().split())
P1 = Monster(*map(int, input().split()))
P2 = Monster(*map(int, input().split()))


def solve(h, P1: Monster, P2: Monster):
    d1 = P1.x - 1 + P1.y - 1
    d2 = d1 + abs(P1.x - P2.x) + abs(P1.y - P2.y) + 1
    P1.h += d1 // P1.a * P1.b
    h -= P1.h
    P2.h += d2 // P2.a * P2.b
    h -= P2.h
    return h


ans = max(solve(h, P2, P1), solve(h, P2, P1))
if ans < 0:
    print("yingyingying")
else:
    print(ans)

2、米小游和派蒙

米小游和派蒙具有相似的属性，所以她们是很好的朋友，她们正在玩一个游戏。

她们拿到了一个数组，然后游戏开始时米小游随机选择个元素作为起点，两人轮流行动，米小游先行动。

每次行动的一方，会选择该元聚左边的比它更小的元素，然后移动到这个元素，接下来交给对方从这个元素开始移动。

如果某个人无法移动了，则输掉这场游戏。米小游想知道，在双方都采取最优策略的情况下，她最终获胜的概率是多少？

输入

第一行输入一个正整数$n$，代表数组的大小。

第二行输入$n$个正整数$a_i$，代表米小游和派蒙拿到的数组。

$1 \le n \le 10^5$
$1 \le a_i\le 10^9$

输出

一个分数，代表米小游获胜的概率。请输出分数的最简形式，即分子和分母互素。如果米小游必胜，则输出$1/1$。如果米小游必败，则输出$0/1$。

样例

输入：
5
3 1 5 4 3

输出：
3/5

提示：
当起点随机在前两个元素时，米小游会失败。当起点随机在后三个元素时，米小游会获胜。

解答

首先进行明确博弈论的必胜态和必败态：

如果当前状态没有后继状态，或者是所有后继状态都是必胜态，那么当前状态是必败态。
如果当前状态存在一个后继状态是必败态，那么当前状态是必胜态。

因此，我们最终统计必胜态的个数$c$即可，答案则为$\dfrac{c}{n}$的最简分数。

按照题意，对于每个状态$i$，它的后继状态$j$满足$1j<ia_j<a_i $。因此对于每个$i$，我们可以统计当前有$c_1$个后继状态是**必胜态**，有$c_2$个后继状态（注意必定有$0\le c_1\le c_2$）。如果$c_2=0$，或者是$c_1=c_2$（其实$c_2=0$意味着$c_1=c_2$），那么说明当前状态是必败态（按照上面的第1条可知，当前所有后继状态是必胜态）；否则，当前状态是必胜态，因为$c_1<c_2$，存在一个后继状态是必败态。

因此，对于每个$i$，如果直接暴力计算出$c_1$和$c_2$的值，那么需要花费的时间为$O(n^2)$。由于它的所有后继状态都是小于当前的数$a_i$，为了节约时间，我们使用树状数组来做到每次$O(\log n)$的修改和查询，从而使这个算法的时间复杂度降到$O(n\log n)$。其次，由于这个树状数组是以每个值作为下标的，因此还需要多一步操作：对数组$a_i$进行离散化，最终使得产生的新数组$a'$的相对大小和$a$相同，但是值域不超过$n$。

最终直接可以计算出先手的胜率。

代码

# include <bits/stdc++.h>
# define lb(x) ((x) & -(x))
# define pi pair<int,int>
using namespace std;
typedef long long ll;

const int N=100004;
int a[N],n,m=0;
map<int,int>mp;

int s1[N],s2[N];
void add(int p,int x){
    for(int i=p;i<=m;i+=lb(i)){
        s1[i]+=x;
        s2[i]++;
    }
}
pi que(int p){
    int c1=0,c2=0;
    for(int i=p;i;i-=lb(i)){
        c1+=s1[i];
        c2+=s2[i];
    }
    return pi(c1,c2);
}

int main(){
    int c=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        mp[a[i]]=0;
    }
    for(auto &[k,v]:mp){
        v=++m;
    }
    for(int i=1;i<=n;i++){
        a[i]=mp[a[i]];
        auto [c1,c2]=que(a[i]-1);
        if(c1==c2){
            add(a[i],0);
        }
        else{
            add(a[i],1);
            ++c;
        }
    }
    int g=__gcd(c,n);
    c/=g;n/=g;
    printf("%d/%d\n",c,n);
}

3、米小游的三元树

米小游拿到了一棵树。所谓树，即$n$个节点，$n-1$条边的无向连通图。

已知每个节点上有'm'、'h'、'y'三个字母中的一个字母。一个路径的权值为：该路径组成的字符串中，包含连续子串"mhy"的数量。例如，若路径为"mhyymmhyh"，则权值为$2$。

显然，这棵树共有$n\ast (n -1)$条路径（请注意，节点$a$到节点$b$和节点$b$到节点$a$视为两条不同路径）。米小游想知道，所有路径的权值之和是多少?

输入

第一行输入一个正整数$n$，代表节点的数量。

第二行输入一个长度为$n$、仅由'm'、'h'、'y'三种字符组成的字符串，第$i$个字符代表$i$号节点上的字母。

接下来的$n-1$行，每行输入两个正整数$u$和$v$，代表节点$u$到节点$u$有一条无向边连接。

$1\le n \le 10^5$

输出

一个整数，代表所有路径的权值之和。

样例

输入：
5
mhyhm
1 2
2 3
3 4
4 5

输出：
6

提示：
共有以下6条路径的权值为1:
1->3、1->4、1->5、5->3、5->2、5->1
其余路径的权值均为0。

解答

由于这里求解的是所有路径的字符串mhy出现次数之和，因此我们可以枚举这棵树$T=(V,E)$中每条带有字符串mhy的路径，再统计有多少条路径完全覆盖这条路径即可。

由于我们仅考虑长度为$3$的路径，因此我们可以考虑枚举每一个节点作为中间节点，再枚举它的每一对邻居，从而不重不漏地枚举出所有长度为$3$的路径。

按照这种思路，我们可以首先枚举出所有标有字符h的节点$u$。然后枚举$u$中所有为m的邻居$x$，以及所有为y的邻居$y$。这时如果将节点$u$删去，那么整棵树就变成了多个连通块。最终，覆盖路径$x\rightarrow u\rightarrow y$的所有路径为$x$所在子树（连通块）的大小的和$y$所在子树（连通块）的大小的乘积，因为这两部分点是可以自由选择的。

假设现在整棵树以$u$节点为根，那么节点$u$对答案的贡献值为：

\[\sum_{(u,x)\in E\land s[x]=m}\sum_{(u,y)\in E\land s[y]=h} z_u[x]\cdot z_u[y]=\left(\sum_{(u,x)\in E\land s[x]=m}z_u[x]\right)\cdot \left(\sum_{(u,y)\in E\land s[y]=h} z_u[y]\right)\]

其中$z_u[x]$表示$x$所在子树的大小（以$u$为根）。因为$x$和$y$也是可以自由选择的，所以需要将它们两两组合在一起。

最终枚举所有为h的节点$u$，并处理出对应的$z$数组，进行计算处理即可。

接下里是描述如何快速处理出任意一个节点$u$的所有子树的大小（即上面的$z$数组）。对$T$指定一个根后，那么以某个节点$u$为根的子树大小$sz[u]$为以$u$的所有子树的大小之和再加上$u$本身。此外，如果$u$不是根节点（那么它就有父节点），那么朝父节点方向也有一棵子树，其大小为$|V|-sz[u]$。最终$|V|-sz[u]$和$u$的所有子树的大小构成了$z$数组。在生成的过程中，直接进行计算最终结果即可。

代码

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

const int N=100004;

char s[N];
vector<int>g[N];
int n;
int sz[N];
ll ans=0;
void dfs(int u,int fa){
    sz[u]=1;
    for(int v:g[u]){
        if(v==fa) continue;
        dfs(v,u);
        sz[u]+=sz[v];
    }
    if(s[u]=='h'){
        int sm=0,sy=0;
        for(int v:g[u]){
            if(v==fa) continue;
            if(s[v]=='m') sm+=sz[v];
            else if(s[v]=='y') sy+=sz[v];
        }
        if(fa!=0){
            if(s[fa]=='m') sm+=n-sz[u];
            else if(s[fa]=='y') sy+=n-sz[u];
        }
        ans+=1ll*sm*sy;
    }
}
int main(){
    scanf("%d %s",&n,s+1);
    int x,y;
    for(int i=1;i<n;i++){
        scanf("%d %d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,0);
    printf("%lld\n",ans);
}