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

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

1、相加异或

对于一个数组\(c\)，定义\(f(c)\)为\(c\)数组所有元素的总和。

现在给定两个长度为\(n\)的数组\(a,b\)，请你恰好删除一个数组\(a\)的元素或者一个数组\(b\)的元素，使得\(f(a)\)异或\(f(b)\)最大。

输入

第一行输入一个整数\(n\)。

第二行输入\(n\)个整数\(a_i\)。

第三行输入\(n\)个整数\(b_i\)。

\(1\le n,a_i,b_i \le 10^5\)

输出

输出最大的异或和。

样例

输入：
3
1 2 3
3 2 1

输出：
5

提示：
删除a数组的3。

解答

令\(s_a\)表示原来的数组\(a\)中的元素和，\(s_b\)表示原来的\(b\)数组的元素和。那么对于删除\(a\)中的某个元素\(a_i\)后，最终\(f(a)\oplus f(b)=(s_a-a_i)\oplus s_b\)。对于\(b\)数组也同理。因此最终答案为

\[\max_{i=1}^n\{\max\{(s_a-a_i)\oplus s_b,(s_b-b_i)\oplus s_a\}\}\]

代码

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

const int N=100004;
int a[N],b[N],n;
int main(){
    scanf("%d",&n);
    int sa=0,sb=0,ans=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sa+=a[i];
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
        sb+=b[i];
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,(sa-a[i])^sb);
        ans=max(ans,(sb-b[i])^sa);
    }
    printf("%d\n",ans);
}

2、米小游与魔法少女-奇运

米小游都快保底了还没抽到希儿，好生气哦！只能打会活动再拿点水晶。

米小游和世界第一可爱的魔法少女TeRiRi正在打BOSS，BOSS的血量为\(h\)，当BOSS血量小于等于\(0\)时，BOSS死亡。TeRiRi有一套牌，在一轮中，她会按顺序一张一张的将卡牌打出，套牌中有两种卡牌：

时来运转：获得\(x\)个幸运币。
幸运一掷：造成\(x\)点伤害，并投掷所有幸运币，造成等于所有幸运币掷出的点数之和的伤害。

幸运币可以等概率的投掷出\(1\sim 6\)之间的点数。（所以为什么不叫骰子呢？）

米小游想知道，TeRiRi的套牌在一轮内击杀BOSS的概率。

输入

第一行输入两个整数\(n(1\le n\le 100),h(1\le h\le 10^9)\)，分别表示卡牌张数和BOSS血量。

接下来\(n\)行，每行首先输入两个整数\(t(1\le t\le2),x(1\le x\le 10)\)，\(t\)为\(1\)表示卡牌为时来运转，\(t\)为\(2\)表示卡牌为幸运一掷。

输出

输出一个实数表示答案，你的答案与标准答案的误差不超过\(10^{-4}\)都被认为是正确答案。

样例

输入：
2 5
1 1
2 1

输出：
0.5

提示：
幸运币掷出4及以上的概率为0.5，再加上1点固定伤害，即可击杀BOSS。

输入：
3 1145
1 4
1 9
1 9

输出：
0

提示：
无论如何都无法击杀BOSS。

解答

需要注意的是，只有幸运一掷被使用出时，前面获得的幸运币才会有用处。如果到最后都没有使出过幸运一掷，那么最后得到的幸运币也是没有用处的。通过统计，我们最终可以知道有效被投掷的幸运币有\(a\)个，并且幸运一掷造成的固定伤害总共为\(b\)。

由于每个幸运币之间都是独立的，因此我们可以考虑将它们合并进行处理。我们将使用动态规划来解决本问题。令\(f(i,j)(0\le i\le a,0\le j\le 6i)\)表示\(i\)枚幸运币投掷出总点数\(j\)的概率值，那么我们可以写出它的状态转移方程：

\(f(i,j)= \left \{\begin{aligned} &1 & & \text{if}\quad i=0\land j=0 \\ &0 & & \text{if}\quad i=0\land j>0 \\ &\dfrac{1}{6}\cdot\sum_{k=1}^{\min\{j,6\}} f(i-1,j-k) & & \text{if}\quad i>0 \\ \end{aligned}\right.\)

由于每个骰子都能均等地以\(\dfrac{1}{6}\)的概率投掷出从\(1\sim 6\)中的一个值，因此从状态\(f(i,j)\)能够以均等地概率转移到\(f(i+1,j+1),f(i+1,j+2),\dots,f(i+1,j+6)\)。

由于还收到了\(b\)点固定伤害，因此只需要造成至少\(h'=\max\{0,h-b\}\)点伤害，就能够击败BOSS，因此最终答案为\(\displaystyle{\sum_{j=h'}^{6a} f(a,j)}\)。

代码

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

const int N=1002;
double f[N][N*6];
int main(){
    int n,h,t,x;
    int a=0,b=0,tmp=0;
    scanf("%d %d",&n,&h);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&t,&x);
        if(t==1){
            tmp+=x;
        }
        else{
            b+=x;a+=tmp;tmp=0;
        }
    }
    f[0][0]=1;
    for(int i=1;i<=a;i++){
        for(int j=i;j<=6*a;j++){
            for(int k=1;k<=6&&k<=j;k++){
                f[i][j]+=f[i-1][j-k]/6;
            }
        }
    }
    h=max(0,h-b);
    double ans=0;
    for(int j=h;j<=a*6;j++)
        ans+=f[a][j];
    printf("%.10f\n",ans);
}

3、米小游的极差之和

米小游拿到了一个数组\(a\)，她用这个数组构造一个新数组\(b\)，其中\(a_i\)代表\(b\)数组中有\(a_i\)个\(i\)。

例如，若\(a=[2,3,1]\)，那么\(b=[1,1,2,2,2,3]\)，因为\(a_1 = 2\)，代表\(b\)数组中有\(2\)个\(1\)；\(a_2=3\)，代表\(b\)数组中有\(3\)个\(2\)；\(a_3=1\)，代表\(b\)数组中有\(1\)个\(3\)。

现在给定\(a\)数组，你需要帮米小游求出\(b\)数组中所有连续子数组的极差之和。由于答案可能过大，请对\(10^9+7\)取模。

数组的极差指最大值减去最小值。

输入

第一行输入一个正整数\(n\)，代表\(a\)数组的元素数量。

第二行输入\(n\)个正整数\(a_i\)，代表\(a\)数组的元素。

\(1\le n\le 10^5\)
\(1 \le a_i \le 10^9\)

输出

一个整数，代表数组中所有区间的极差之和，对\(10^9+7\)取模的值。

样例

输入：
2
2 1

输出：
2

提示：
a=[2,1]时，b数组为[1,1,2]。
此时b数组共有6个连续子数组：
[1]的极差为0。
[1]的极差为0。
[2]的极差为0。
[1,1]的极差为0。
[1,2]的极差为1。
[1,1,2]的极差为1。
因此答案是0+0+0+0+1+1=2。

解答

由于\(b\)是一个单调非递减数组，因此它的任意子数组极差就相当于是最后一个元素减去第一个元素的值。因此，只有最后一个元素的值和第一个不同时，才会对极差做出贡献。

可以知道，对于任意一对\(i,j(1\le i<j\le n)\)，\(b\)中都有\(a_i\cdot a_j\)个子数组以\(i\)开头，以\(j\)结尾，它们都做出了\(j-i\)的贡献。因此，这道题的答案为\(\displaystyle{\sum_{i=1}^n\sum_{j=i+1}^n (j-i)\cdot a_i\cdot a_j}\)，令\(\displaystyle{s_i=\sum_{i=1}^n a_i,s_0=0,t_i=\sum_{i=1}^n i\cdot a_i,t_0=0}\)。那么我们可以将这个结果进一步化简一下，有：

\(\begin{aligned} &\sum_{i=1}^n\sum_{j=i+1}^n (j-i)\cdot a_i\cdot a_j\\ =&\sum_{i=1}^n a_i\cdot\left(\sum_{j=i+1}^n (j-i)\cdot a_j\right)\\ =&\sum_{i=1}^n a_i\cdot\left(\sum_{j=i+1}^n j\cdot a_j-i\cdot\sum_{j=i+1}^n a_j\right)\\ =&\sum_{i=1}^n a_i\cdot((t_n-t_i)-i\cdot(s_n-s_i))\\ \end{aligned}\)

由此，我们可以在\(O(n)\)的时间内，通过计算\(s,t\)，从而计算出最终结果。

代码

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

const int N=100004;
ll a[N],s1[N],s2[N];
ll mod=1e9+7;
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        s1[i]=(s1[i-1]+a[i])%mod;
        s2[i]=(s2[i-1]+a[i]*i)%mod;
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans+=((s2[n]-s2[i])-(s1[n]-s1[i])*i%mod)*a[i]%mod;
        ans=(ans%mod+mod)%mod;
    }
    printf("%lld\n",ans);
}