牛客多校赛题解（八）

1.OR

题目链接：D-OR_2021牛客暑期多校训练营8 (nowcoder.com)

题目大意

有三个数组a, b, c
其中：bi = ai | ai-1，ci = ai + bi
现在给了数组b和c，求a有几种可能

解题思路

做了这么久的题，这题是最坑的！！！

题目没有描述清楚，or 到底是或者还是或运算？
长刀归我，短刀归出题的

好在后来看见出题组又给了补充

言归正传，这题的解题核心思路就是 a+b = a|b + a&b，这是一个数学结论，当然没有这个结论也能做，就是会比较复杂

通过这个结论，我们可以将数组c进行一波变换: ci = ci - bi，然后ci = a&b，我们处理数组c的时候，就无需再考虑进位的问题了，通过观察二进制运算的一些规律，我们发现：

a	b	&	and
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	1

即：当& = 0, | = 1时，有两种可能，a = 0, b = 1 或者a = 1, b = 0，剩下的都是一种可能

我们以题中的样例来说

输入
4
7 5 5
7 9 5
输出
2

c数组变换以后：

b = {7 5 5}
c = {0 4 0}

化为二进制：

b = {111 101 101}
c = {000 100 000}

由上述二进制表可以得出

a1, a2
{111, 000}
{110, 001}
{101, 010}
{011, 100}

剩下的同理，得出这些以后，再对ai所有的可能进行枚举验证，最后就能得出a的可能个数了

ACCode

/*
 * @Author: NorthCityChen
 * @LastEditTime: 2021-08-12 19:44:45
 * @Description: 
 * @Website: https://grimoire.cn
 * Copyright (c) NorthCityChen All rights reserved.
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 + 10;
const ll mod = 4933;

int b[N], c[N];

int main()
{
    int n, flag = 0, pos;
    cin >> n;
    for (int i = 2; i <= n; i++)
        cin >> b[i];
    for (int i = 2; i <= n; i++)
    {
        cin >> c[i];
        c[i] -= b[i];
    }
    int ans = 1;
    for (int i = 0; i < 31; i++)
    {
        int flag = 2, fron = -1;
        for (int j = 2; j <= n; j++)
        {
            int bn = b[j] >> i & 1;
            int cn = c[j] >> i & 1;
            if (bn == cn && flag == 2)
            {
                flag = 1;
                if (bn == 0)
                    fron = 0;
                else
                    fron = 1;
            }
            else if (bn && cn == 0 && flag == 1)
            {
                if (fron == 0)
                    fron = 1;
                else
                    fron = 0;
            }
            else if (bn == cn && flag == 1)
            {
                if ((bn == 0 && fron == 1) || (bn == 1 && fron == 0))
                {
                    cout << "0" << endl;
                    return 0;
                }
                if (bn == 0)
                    fron = 0;
                else
                    fron = 1;
            }
            else if (bn == 0 && cn)
            {
                cout << "0" << endl;
                return 0;
            }
        }
        ans = ans * flag;
    }
    cout << ans << endl;

    return 0;
}

2.Ares, Toilet Ares

题目链接：A-Ares, Toilet Ares_2021牛客暑期多校训练营8 (nowcoder.com)

题目大意

有一个队伍只能做出 a 题的简单题，并拥有 k 次机会获得某一题的部分代码（ 但仍然存在解题失败的概率 ），求过题数的期望

解题思路

就是一个模拟题，直接按照描述的思路把代码实现了就行，注意输入数据里有几个没用的值...

ACCode

/*
 * @Author: NorthCityChen
 * @LastEditTime: 2021-08-12 20:26:21
 * @Description: 
 * @Website: https://grimoire.cn
 * Copyright (c) NorthCityChen All rights reserved.
 */

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

const int N = 1e5 + 10;
const ll mod = 4933;

ll ny(ll a, ll k, ll mod)
{
    ll res = 1;
    while (k)
    {
        if (k & 1)
            res = (ll)res * a % mod;
        a = (ll)a * a % mod;
        k /= 2;
    }
    return res;
}

int main()
{
    int flag = 0;
    ll n, m, k, a, l;
    cin >> n >> m >> k >> a >> l;
    ll ans = 1;
    for (int i = 1; i <= k; i++)
    {
        ll x, y, z;
        cin >> x >> y >> z;
        if (x != 0)
        {
            if (y == 0);
            else
                ans = (ans * ((z - y) * ny(z, mod - 2, mod) % mod)) % mod;
        }
    }
    if (flag)
        cout << a % mod << endl;
    else
        cout << (ans + a) % mod << endl;

    return 0;
}

参考链接：Ares, Toilet Ares（2021牛客多校第八场A）_国家一级划水运动员的博客-CSDN博客

3.Yet Another Problem About Pi

题目链接：K-Yet Another Problem About Pi_2021牛客暑期多校训练营8 (nowcoder.com)

题目大意

有一个网格，横纵间隔为w,d每次只能移动Pi的距离，求最多能经过多少个不同的格子。

解题思路

本题最少的答案是4，因为最优的其实位置为格点处，只需向周围四个格子移动无限趋近于0的距离就可以将四个格子都踩到，因此本题需要考虑的是如何用最省的方式踩到尽可能多的格子

这题我们采用贪心的算法，有两种走法：

1. 走横纵直线，每走一段，可以踩2个格子
2. 走对角线，每段可以走3个格子

ACCode

/*
 * @Author: NorthCityChen
 * @LastEditTime: 2021-08-12 20:26:21
 * @Description: 
 * @Website: https://grimoire.cn
 * Copyright (c) NorthCityChen All rights reserved.
 */

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
typedef long long LL;

int solve(){
    double w, d; cin >> w >> d;
    double y = sqrt(w * w + d * d);
    if (w > d) w = d;
    if (w > pi) return cout << "4" << endl, 0;
    int ans = 4, xt = 0, yt = 0;
    double xn = w / 2, yn = y / 3;
    if (xn < yn){
        xt = int(pi / w);
        ans += xt * 2;
        if (pi - (xt - 1) * w > y) ans++;
    }
    else{
        yt = int(pi / y);
        ans += yt * 3;
        if (pi - yt * y > w) ans += 2;
        else if (pi - (yt - 1) * y > 2 * w) ans++;
    }
    return cout << ans << endl, 0;
}

int main(){
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

参考链接：Yet Another Problem About Pi（2021牛客多校第八场K）_国家一级划水运动员的博客-CSDN博客