2021 牛客暑期多校训练营8

A

本题是一道模拟题，读懂题意即可

n,m,k,a,l=map(int,input().split())
def getInv(a): return pow(a,4931,4933)
p = 1
for _ in range(k):
    x,y,z=map(int,input().split());
    if x!=0: p = p * (z-y) % 4933 * getInv(z) % 4933
print((a+p)%4933)

D

题意：给定两个长度为n-1的非负整数序列b/c，问有多少个序列a满足 $b_i = a_{i-1} or a_i ,\ c_i=a_{i-1}+a_i$

本题是网上原题。

思路：

$a+b=a|b + a\&b$
第一个数字定了，整个序列就定了
所以答案最高就是 $2^{30}$
逐位考虑，考虑第一个数字这一位可以是几（check）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
int b[N], c[N], n, p2[35];
int check(int k, int x) {
    int _or, _and;
    for (int i = 2; i <= n; ++i) {
        _or = (b[i] & p2[k]) != 0, _and = (c[i] & p2[k]) != 0;
        if (!_or && _and) return 0;
        if (_or && _and && !x) return 0;
        if (!_or && x) return 0;
        if (_or && !_and) x ^= 1;
    }
    return 1;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    p2[0] = 1;
    for (int i = 1; i <= 30; ++i) p2[i] = p2[i - 1] * 2;
    cin >> n;
    for (int i = 2; i <= n; ++i) cin >> b[i];
    for (int i = 2; i <= n; ++i) cin >> c[i];
    for (int i = 2; i <= n; ++i) c[i] -= b[i];
    ll ans = 1;
    for (int i = 30; ~i; --i) {
        ans = ans * (check(i, 0) + check(i, 1));
        if (!ans) break;
    }
    cout << ans << '\n';
    return 0;
}

E

不存在质数闰年

for _ in range(int(input())):print('no')

K

在四个格子中间画一个小小的圈是无损的
所以走直线是一个挺不错的选项：到了合适的地方就画个小圈
但是还有另一种情况，即能走的长度恰好等于 $\sqrt{2}$ ，这种情况走个斜线更优：能占7个格子，所以也需要考虑末端是否改成斜线

from math import pi, sqrt
for _ in range(int(input())):
    w, d = map(float, input().split())
    if w > d: w, d = d, w
    if w > pi: print(4); continue
    cro = sqrt(w * w + d * d)
    ans, xn, crn = 4, w / 2, cro / 3
    if xn < crn: # 直线更优
        xt = int(pi / w)
        ans += xt * 2
        if pi - (xt - 1) * w > cro: ans += 1 # 看最后一个要不要改成斜线
    else: # 斜线更优
        ct = int(pi / cro)
        ans += ct * 3
        if pi - ct * cro > w: ans += 2
        elif pi - (ct - 1) * cro > w * 2: ans += 1
    print(ans)