2021牛客暑期多校训练营1

Alice and Bob

SG暴力转移即可

#include <stdio.h>
const int N = 5e3;
bool f[N + 5][N + 5];
int main() {
    for (int i = 0; i <= N; i++)
        for (int j = 0; j <= N; j++) 
            if (f[i][j] == 0) {
                for (int k = 1; k + i <= N; k++)
                    for (int s = 0; s * k + j <= N; s++)
                        f[i + k][j + s * k] = 1;
                for (int k = 1; k + j <= N; k++)
                    for (int s = 0; s * k + i <= N; s++)
                        f[i + s * k][j + k] = 1;
            }
    int t, n, m;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        puts(f[n][m] ? "Alice" : "Bob");
    }
    return 0;
}

可以找规律优化(打表)

Ball Dropping

如图，由于圆心在等腰梯形的中垂线上，且切圆于，所以均为直角三角形，设所求长为，可得，，可得，进而可得

同理，，可得，进而可得

又有，可得

故可根据联立方程：

解得

这些三角形均为直角三角形，三边的比分别为：

r, a, b, h = map(int, input().split())
from math import sqrt
GJ = r / h * sqrt((a - b)**2 / 4 + h**2)
GK = GJ / ((a - b) / 2) * h
FK = (b / 2) / ((a - b) / 2) * h
GF = GK - FK
print('Stuck\n%.10f' % GF if GF > 0 else 'Drop')

Determine the Photo Position

由于2是连续的，对于每一行，考虑连续的有多少个即可

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 2e3 + 7;
const int mod = 1e9 + 7;
char a[N][N], b[N];
int n, m;
int main() {
    cin >> n >> m;
    rep(i, 1, n) cin >> a[i] + 1;
    cin >> b + 1;
    if (n < m) return puts("0"), 0;
    ll res = 0;
    rep(j, 1, n) {
        int cnt = 0;
        rep(i, 1, n) {
            if (a[j][i] == '0')
                ++cnt;
            else {
                if (cnt >= m) res += cnt - m + 1;
                cnt = 0;
            }
        }
        if (cnt >= m) res += cnt - m + 1;
    }
    cout << res;
    return 0;
}

Find 3-friendly Integers

规律题，打表可知三位及以上的数字全部满足，所以更高位也就全部满足（因为多位数字是包含三位数的）。
所以只需要手动处理一下两位数即可。

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
int g[121];
bool chk(int n) {
    int digit[15], p = 0;
    while (n) {
        digit[++p] = n % 10;
        n /= 10;
    }
    rep(i, 1, p) if (digit[i] % 3 == 0) return 1;
    rep(i, 2, p) {
        if ((digit[i] + digit[i - 1]) % 3 == 0) return 1;
    }
    int sum = 0;
    rep(i, 1, p) sum += digit[i];
    return sum % 3 == 0;
}
int main() {
    rep(i, 1, 120) g[i] = chk(i);
    ll T, L, R;
     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--) {
        cin >> L >> R;
        ll ans = 0;
        ll tot = min(R, 90LL);
        if (L <= 90) {
            rep(i, L, tot) if (g[i])++ ans;
            if (R > 90) ans += R - 90;
        } else
            ans += R - L + 1;
        cout << ans << '\n';
    }
    return 0;
}

Hash Function

1. hash seed不能是任意两数之差的倍数。
2. hash seed必然在和之间
3. 求解任意两数之差，想要降复杂度，考虑FFT，采用类似桶的处理，将的幂次标记为1
4. 两数之差的本质是取负数做和，负数采用一个偏移量做标记即可。

#include <bits/stdc++.h>

typedef unsigned long long ull;

const int P = 998244353;

inline int norm(int x) { return x >= P ? x - P : x; }
inline int reduce(int x) { return x < 0 ? x + P : x; }
inline int neg(int x) { return x ? P - x : 0; }
inline void add(int& x, int y) {
    if ((x += y - P) < 0) x += P;
}
inline void sub(int& x, int y) {
    if ((x -= y) < 0) x += P;
}
inline void fam(int& x, int y, int z) { x = (x + y * (ull)z) % P; }
inline int mpow(int x, unsigned k) {
    if (k == 0) return 1;
    int ret = mpow(x * (ull)x % P, k >> 1);
    if (k & 1) ret = ret * (ull)x % P;
    return ret;
}

const int L = 20;

namespace NTT {

const int OMEGA_2_21 = 31;

int l, n;
int w2[(1 << L) + 1];

void init() {
    n = 1 << l;
    *w2 = 1;
    w2[1 << l] = mpow(OMEGA_2_21, 1 << (21 - l));
    for (int i = l; i; --i) w2[1 << (i - 1)] = w2[1 << i] * (ull)w2[1 << i] % P;
    for (int i = 1; i < n; ++i) w2[i] = w2[i & (i - 1)] * (ull)w2[i & -i] % P;
}

void DIF(int* a) {
    int i, *j, *k, len = n >> 1, r, *o;
    for (i = 0; i < l; ++i, len >>= 1)
        for (j = a, o = w2; j != a + n; j += len << 1, ++o)
            for (k = j; k != j + len; ++k)
                r = *o * (ull)k[len] % P, k[len] = reduce(*k - r), add(*k, r);
}

void DIT(int* a) {
    int i, *j, *k, len = 1, r, *o;
    for (i = 0; i < l; ++i, len <<= 1)
        for (j = a, o = w2; j != a + n; j += len << 1, ++o)
            for (k = j; k != j + len; ++k)
                r = reduce(*k + k[len] - P),
                k[len] = ull(*k - k[len] + P) * *o % P, *k = r;
}

void FFT(int* a, int d = 1) {
    if (d == 1)
        DIF(a);
    else {
        DIT(a);
        std::reverse(a + 1, a + n);
        ull nv = P - (P - 1) / n;
        for (int i = 0; i < n; ++i) a[i] = a[i] * n***amespace NTT

using NTT::l;// 偏移量

int n, m;
int a[1 << L], b[1 << L];
#define rep(i, l, r) for (int i = l; i <= r; ++i)
inline bool chk(int x) {
    for (int i = x; i <= m; i += x)
        if (a[i]) return 0;
    return 1;
}
int main() {
    scanf("%d", &n);
    for (int i = 0, x; i < n; ++i) {
        scanf("%d", &x);
        if (x > m) m = x;
        a[x] = 1;
    }++m;
    while ((1 << l) <= m * 2) ++l;
    NTT::init();
    memcpy(b, a, sizeof(a));
    std::reverse(b + 1, b + (1 << l));
    NTT::FFT(a);
    NTT::FFT(b);
    for (int i = 0; i != 1 << l; ++i) a[i] = a[i] * (ull)b[i] % P;
    NTT::FFT(a, -1);
    rep(i, n, m) {
        if (chk(i)) {
            printf("%d\n", i);
            return 0;
        }
    }
}