MENU

牛客多校赛题解(八)

August 12, 2021 • 题解

1.OR

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

题目大意

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

解题思路

做了这么久的题,这题是最坑的!!!

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

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

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

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

ab&and
0000
0101
1001
1111

即:当& = 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博客

作者:NorthCity1984
出处:https://grimoire.cn/acm/nk8.html
版权:本文《牛客多校赛题解(八)》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任