2024牛客暑假多校训练营Day10||补题

A-Surrender to My Will

题意

根据上票状态判断是否投降。4票及以上赞同投降则投降成功。

数据范围

• $1\le i\le 5$
• $$\begin{gathered} 1\le j\le i,S[j]\in \\ Y,N \end{gathered}$$

思路

计数模拟即可。

代码

void solve() {
    string s;cin >> s;
    int y = 0, n = 0;
    for (auto c : s) {
        if (c == 'Y')y++;
        else if (c == 'N')n++;
    }
    if (y >= 4)cout << "1\n";
    else if (n >= 2)cout << "-1\n";
    else cout << "0\n";
}

B-std::pair

题意

使用std::pair声明$n$个变量，进行对于这些变量的$q$个询问，回答其数据类型。

数据范围

• $1\le n,q\le 1000$

每行输入不超过5000字符

思路

按.分割询问的变量，逐层确定当前的数据类型。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
const int maxn = 1e6 + 50;
 
map<string, string>mp;
 
void solve() {
    int n, q;cin >> n >> q;
    for (int i = 0;i < n;i++) {
        string s1, s2;
        cin >> s1 >> s2;
        if (s2.back() == ';')s2.pop_back();
        mp[s2] = s1;
    }
 
    while (q--) {
        string s;cin >> s;
        s = s + ".";
        vector<string>stk;
 
        int p = s.find(".");
        int pr = 0;
        while (p != -1) {
            string t = s.substr(pr, p - pr);
            stk.push_back(t);
            s = s.substr(p + 1);
            p = s.find(".");
        }
        string typ = mp[stk.front()];
        for (int i = 1;i < stk.size();i++) {
            string c = stk[i];
            vector<int>v;
            int pp; // 中点的','位置
            int cnt1, cnt2;
            cnt1 = cnt2 = 0;
            for (int j = 0;j < typ.size();j++) {
                if (typ[j] == '<') {
                    cnt1++;
                }
                else if (typ[j] == ',') {
                    cnt2++;
                    v.push_back(j);
                }
                else if (typ[j] == '>') {
                    cnt1--, cnt2--;
                    if (!cnt1 && !cnt2) {
                        pp = v.back();
                        break;
                    }
                    v.pop_back();
                }
            }
            if (c == "first") {
                typ = typ.substr(5, pp - 5);
            }
            else {
                typ = typ.substr(pp + 1, typ.size() - pp - 2);
            }
        }
 
        cout << typ << "\n";
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;cin.get();
    while (t--)
        solve();
 
    return 0;
}

F-Collinear Exception

题意

在$$\begin{gathered} 1,...,n \\ \times \\ 1,...,n \end{gathered}$$的坐标逐渐加入$n\times n$个数，如果即将加入的这个数与已有的形成了三点共线，则该数不能被成功加入，输出一个长度为$n\times n$的01串，表示第$i$个点能否成功加入。

数据结构

• $1\le n\le 1000$
• $1\le x_i,y_i\le n$

思路

每行每列都不能拥有超过$2$个点，若某行或某列已经超过2个点则直接判不能加入，用一个$vis$数组记录某点是否能被成功加入，加入新点时，遍历图中已有的点，枚举与图中已有点形成的直线的斜率$(dx,dy)$，$dx$、$dy$互质，从当前点$(x,y)$向两边转移到$(x\pm dx,y\pm dy)$，并标记该处不能被访问。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1050;
struct point {
    int x, y;
};
int X[maxn], Y[maxn];
bool vis[maxn][maxn];
void solve() {
    int n;cin >> n;
    vector<point>v;
    for (int i = 1;i <= n * n;i++) {
        int x1, y1;cin >> x1 >> y1;
        if (X[x1] + 1 > 2 || Y[y1] + 1 > 2 || vis[x1][y1]) {
            cout << "0";
            continue;
        }
        X[x1]++, Y[y1]++;
        if (i == 1) {
            v.push_back({ x1,y1 });
            vis[x1][y1] = true;
            cout << "1";continue;
        }
        for (auto [x2, y2] : v) {
            if (y2 == y1 || x2 == x1)continue;
            int dx = abs(x2 - x1), dy = abs(y2 - y1), c = (1.0 * (y1 - y2) / (x1 - x2) > 0 ? 1 : -1);
            int g = gcd(dx, dy);
            dx /= g, dy /= g;
            int x = x1, y = y1;
            while (x >= 1 && x <= n && y >= 1 && y <= n) {
                vis[x][y] = true;
                x += dx, y += c * dy;
            }
            x = x1, y = y1;
            while (x >= 1 && x <= n && y >= 1 && y <= n) {
                vis[x][y] = true;
                x -= dx, y -= c * dy;
            }
        }
        v.push_back({ x1,y1 });
        cout << "1";
    }
    cout << "\n";
}
 
int main() {
    int t = 1;
    // cin >> t;cin.get();
    while (t--)
        solve();
 
    return 0;
}

H-All-in at the Pre-flop

题意

两个玩家拥有$a$和$b$的筹码，在一场公平游戏中全押，等概率成为输家或赢家，若赢家的筹码不少于输家，游戏结束，该局赢家为最终胜利者。否则输家向赢家支付等同于赢家筹码的筹码。问游戏结束时两个玩家分别的胜率是多少（模$998244353$）。

数据范围

• $1\le a,b\le 998244353$

思路

游戏结束时要求赢家筹码不少于输家，另$f(x)$为玩家筹码量为$x$时的胜率，$n$为总筹码数，也就是$a+b$，则有：

$$f(0)=0,f(n)=1$$ $$\{\begin{array}{l}f(x)=\frac{1}{2}\times f(0)+\frac{1}{2}\times f(2x)x<n/2\\ f(x)=\frac{1}{2}\times f(n)+\frac{1}{2}\times f(2x-n)x\ge n/2\end{array}$$

玩家押上$x$筹码后，对方押上$n-x$筹码，若$x\ge n-x$则玩家为赢家时直接胜利，为输家时向对方交付$n-x$筹码，自己留下$x-(n-x)=2\times x-n$筹码，这时候的胜率变为$f(2x-n)$，发生这两种情况的概率都是$0.5$。打表后发现$f(x)=\frac{x}{n}$是线性方程的解。

输出$\frac{a}{a+b}$和$\frac{a}{a+b}$。

代码

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1)res = res * a % mo998;
        b >>= 1;
        a = a * a % mo998;
    }
    return res;
}
 
ll inv(ll x) {
    return qpow(x, mo998 - 2);
}
 
void solve() {
    ll a, b;cin >> a >> b;
    ll c = (a + b) % mo998;
    cout << a * inv(c) % mo998 << " " << b * inv(c) % mo998 << "\n";
}