Solutions to some problems of scuacm22 retreat competition before summer training

Portal

author ：hans774882968 as well as hans774882968

this paper juejin Portal

A

Simple geometry problems , It is easy to deduce with trigonometric function knowledge （ For passing the exam SCU Classmate ）.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 1e6 + 5;

int r, a, b, h;

void dbg() {
    
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {
    }
template<typename T, typename ...R>void read (T &x, R &...r) {
    
    read (x);
    read (r...);
}

int main() {
    
    read (r, a, b, h);
    if (2 * r <= b) {
    
        puts ("Drop");
        return 0;
    }
    double H = 1.0 * h * a / (a - b);
    double theta = atan (1.0 * a / 2 / H);
    printf ("Stuck\n%.10lf\n", r / sin (theta) - b / (2 * tan (theta) ) );
    return 0;
}

B

At first glance, it is a game dp. Type a watch first

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 5e3 + 5;

int dp[N][N], a[N];
int n, m;

void dbg() {
    
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {
    }
template<typename T, typename ...R>void read (T &x, R &...r) {
    
    read (x);
    read (r...);
}

bool dfs (int x, int y) {
    
    if (~dp[x][y]) return dp[x][y];
    dp[x][y] = false;
    if (! (x + y) ) return dp[x][y] = false;
    if (!x || !y) return dp[x][y] = true;
    if (x == y) return dp[x][y] = true;
    if (x < y) return dp[x][y] = dfs (y, x);
    rep (k1, 1, x) {
    
        for (int k2 = 0; k2 <= y; k2 += k1) {
    
            dp[x][y] |= !dfs (x - k1, y - k2);
            if (dp[x][y]) break;
        }
    }
    rep (k1, 1, y) {
    
        for (int k2 = 0; k2 <= x; k2 += k1) {
    
            dp[x][y] |= !dfs (x - k2, y - k1);
            if (dp[x][y]) break;
        }
    }
    return dp[x][y];
}

void bf (int n) {
    
    memset (dp, -1, sizeof dp);
    rep (i, 0, n) rep (j, 0, n) dfs (i, j);
    // rep (i, 0, n) rep (j, 0, n) cout << dp[i][j] << " \n"[j == n];
    rep (i, 0, n) rep (j, 0, n) if (!dp[i][j]) dbg (i, j);
    puts ("");
    rep (i, 0, n) rep (j, 0, n) if (!dp[i][j] && i < j) dbg (i, j);
}

int main() {
    
    bf (300);
    // memset (dp, -1, sizeof dp);
    // int lim = 500;
    // rep (i, 1, lim) {
    
        // if (a[i]) continue;
        // rep (j, i + 1, lim) {
    
            // if (!dfs (i, j) ) {
    
                // a[i] = j;
                // break;
            // }
        // }
        // if (a[i]) a[a[i]] = i;
        // if (i % 100 == 0) cout << "i=" << i << endl; //dbg
    // }
    // rep (i, 1, lim) cout << a[i] << " \n"[i == lim];
    return 0;
}

Find at most one... Per line false, But no other laws have been found . So one way is to run the annotated code above , Put each line of false The point of （ May not exist ） Find it out . But it will take a long time , Forget it .

The exact solution is ： Since false No more than 5000, Then use the brush table method directly . According to the game dp common sense , The value is true Can't push out any points , The value is false The point of can be derived from a series of values true The point of . According to the harmonic series , Complexity O(n^2*logn). To tell you the truth, this is the first time I have seen such a routine .

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 5e3 + 5;

bool dp[N][N];
int n, m;

void dbg() {
    
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {
    }
template<typename T, typename ...R>void read (T &x, R &...r) {
    
    read (x);
    read (r...);
}

void init (int n) {
    
    rep (i, 0, n) rep (j, 0, n) {
    
        if (dp[i][j]) continue;
        rep (k1, 1, n - i) {
    
            for (int k2 = 0; j + k2 <= n; k2 += k1) {
    
                dp[i + k1][j + k2] = true;
            }
        }
        rep (k1, 1, n - j) {
    
            for (int k2 = 0; i + k2 <= n; k2 += k1) {
    
                dp[i + k2][j + k1] = true;
            }
        }
    }
}

int main() {
    
    init (5000);
    int T;
    read (T);
    while (T--) {
    
        read (n, m);
        puts (dp[n][m] ? "Alice" : "Bob");
    }
    return 0;
}

E

set up dp[i] The maximum value of the currently obtained data set is i, The number of steps you can take . Set up again ans[i] Indicates that the maximum value of the currently obtained data set is i, The expectation of getting a score . Because in the title , Score only 1 Time , So we assume that there is currently a maximum value of a set of numbers , But I didn't get a score . Obviously, this constructive assumption is legitimate .

There are no numbers , Just use “ There is one 0” To express , therefore ans[0] That is, what you want .

It is worth noting that , We can also use mathematical form E(x[i]) and E(x[i] ^ 2) To express dp[i] and ans[i].

PUSH dp

Full expectation formula ：E(X) = sum(E(X|Y = y[i]) * P(Y = y[i]))

Let the next number be j. The next number is less than i, The number of steps you can take is 1; Greater than or equal to i, The number of steps you can take is E(1 + x[j]) = 1 + dp[j]. Therefore, from the full expectation formula ：

dp[i] = sum(p[j])(j < i) + sum(p[j] * (1 + dp[j]))(j >= i)

Transposition to ：

dp[i] = (1 + sum(p[j] * dp[j])) / (1 - p[i]) (j > i)

PUSH ans

The next number is less than i, The score you can get is 1. Greater than or equal to i, From the above mathematical form E((1 + x[j]) ^ 2) = E(x[j] ^ 2) + 2 * E(x[j]) + 1 = ans[j] + 2 * dp[j] + 1. Therefore, from the full expectation formula ：

ans[i] = sum(p[j])(j < i) + sum(p[j] * (ans[j] + 2 * dp[j] + 1))(j >= i)

Transposition to ：

ans[i] = (1 + 2 * dp[i] * p[i] + sum(p[j] * (ans[j] + 2 * dp[j]))) / (1 - p[i]) (j > i)

summary ： Focus on expectations dp Mathematical notation for ！

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 5e3 + 5;
const int mod = 998244353;

LL dp[N], ans[N], p[N];
int a[N];
int n;

void dbg() {
    
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {
    }
template<typename T, typename ...R>void read (T &x, R &...r) {
    
    read (x);
    read (r...);
}

LL q_pow (LL a, LL b) {
    
    LL r = 1;
    for (; b; b >>= 1) {
    
        if (b & 1) r = r * a % mod;
        a = a * a % mod;
    }
    return r;
}

int main() {
    
    read (n);
    rep (i, 1, n) read (a[i]);
    LL isuma = q_pow (accumulate (a + 1, a + n + 1, 0LL), mod - 2);
    rep (i, 1, n) p[i] = a[i] * isuma % mod;
    dwn (i, n, 0) {
    
        LL s1 = 1, inv1_p = q_pow ( (1 - p[i] + mod) % mod, mod - 2);
        rep (j, i + 1, n)
            s1 = (s1 + p[j] * dp[j] % mod) % mod;
        dp[i] = s1 * inv1_p % mod;
        LL s2 = (1 + 2 * p[i] * dp[i] % mod) % mod;
        rep (j, i + 1, n)
            s2 = (s2 + p[j] * (ans[j] + 2 * dp[j] % mod) % mod) % mod;
        ans[i] = s2 * inv1_p % mod;
    }
    printf ("%lld\n", ans[0]);
    return 0;
}

H

a[i]*a[j] = a[k], And data range 1e6 All remind us that we need Enumerating multiples . Open a bucket to count , Then enumerate the values i and i Multiple j, The contribution is c[i] * c[j] * c[j/i].

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 1e6 + 5;

int n, c[N];

void dbg() {
    
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {
    }
template<typename T, typename ...R>void read (T &x, R &...r) {
    
    read (x);
    read (r...);
}

int main() {
    
    read (n);
    int mx = 0;
    rep (_, 1, n) {
    
        int x;
        read (x);
        c[x]++;
        mx = max (mx, x);
    }
    LL ans = 0;
    rep (i, 1, mx) {
    
        if (!c[i]) continue;
        for (int j = i; j <= mx; j += i) {
    
            ans += 1LL * c[i] * c[j] * c[j / i];
        }
    }
    printf ("%lld\n", ans);
    return 0;
}

I

Sign in .

• x yes s Subset ,x by 1 Take whatever part you like ,x by 0 but s by 1 The part of is fixed as 1.
• x No s Subset , The number is obviously 0.

It's easy to get wrong ：x == s when 0 It's also the answer , But the question is a positive integer , Want to lose .

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 2e5 + 5;

int x, s;

void dbg() {
    
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {
    }
template<typename T, typename ...R>void read (T &x, R &...r) {
    
    read (x);
    read (r...);
}

int main() {
    
    read (x, s);
    if (! ( (x & s) == x && (x | s) == s) ) {
    
        puts ("0");
        return 0;
    }
    printf ("%lld\n", (1LL << __builtin_popcount (x) ) - (x == s) );
    return 0;
}