牛客2023寒假集训第一场

A题

  思维题，唯一要注意的就是在奇数场也能获胜（比赛时脑子抽了认定必须要偶数场才能判断是否获胜，也就是必须打完一轮）

#include<bits/stdc++.h>
using namespace std;
int main() {
    int T;
    string s;
    cin >> T;
    while (T--) {
        s.clear();
        cin >> s;
        int a = 0, b = 0, ans;
        bool flag = 1;
        for (int i = 0; i < 10; i++) {
            int w = i + 1;
            if (w % 2) a += s[i] - '0';
            if (!(w % 2)) b += s[i] - '0';

            if (w % 2) {
                if (a > b + 5 - (w + 1) / 2 + 1 || b > a + 5 - (w + 1) / 2) { cout << w << endl; goto ac; }
            }
            else {
                if (abs(a - b) > 5 - w / 2) { cout << w << endl; goto ac; }
            }
        }
        if (a == b) {
            cout << -1 << endl;
            goto ac;
        }
        cout << 10 << endl;
        ac:;
    }
    return 0;
}

C题：

   最大的数据可以弄到1e10，这个数据量就非常蹊跷，最先想到的是一个类单调栈做法，但是是O(T*(n+logn))的，所以被卡掉了

   但是思路其实很简单，会发现所有论文不管如何分组，每篇论文只会做出1的贡献，所以我们干脆不分组，一篇一篇的交上去，会发现只有引用量为0的论文没有贡献，所以排除0的数量便可

D题：

  纯纯计算题，三种情况，P在框内，xp>x0&&yp>y0，xp<x0||yp<y0

  稍加证明第三种情况即可

#include<bits/stdc++.h>
using namespace std;
double a[2], b[2];
int T;
int main() {
    cin >> T;
    while (T--) {
        cin >> a[0] >> a[1] >> b[0] >> b[1];
        if (a[0] >= b[0] && a[1] >= b[1]) {
            double x = max(b[0], a[0] - b[0]);
            double y = max(b[1], a[1] - b[1]);
            printf("%.6lf\n", x * y / (a[0] * a[1]));
            goto ac;
        }

        if (a[0] >= b[0] && b[1] > a[1]) {
            double x = max(b[0], a[0] - b[0]);
            double y = b[1] - a[1];
            printf("%.6lf\n", x * a[1] / (a[0] * a[1] + x * y));
            goto ac;
        }

        if (a[0] < b[0] && a[1] >= b[1]) {
            double x = b[0] - a[0];
            double y = max(b[1], a[1] - b[1]);
            printf("%.6lf\n", y * a[0] / (a[0] * a[1] + x * y));
            goto ac;
        }

        printf("%.6lf\n", a[1] * a[0] / (b[1] * b[0]));
    ac:;
    }
}

F题

  会发现若有炸弹点不在同一个连通块内，那么一定是不可能情况

  然后考虑一个连通块内的情况，假如是SCC，则一定可以，因为对于任意点都有两条不重复路径可到达，我直接走一圈挨着放就行

  假如是一般图呢，考虑一般图的最坏情况——树，会发现树也成立，放炸弹的策略类似dfs回溯

  所以对于一个连通块直接size*size便可，如果没有炸弹则是所有连通块size*size的和

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
vector<int> mp[N];
int n, m, bom[N];
int col[N], cnt, sz[N], siz;
void dfs(int x, int fa) {
    for (auto y : mp[x]) {
        if (y == fa || col[y]) continue;
        col[y] = cnt;
        siz++;
        dfs(y, x);
    }
}
bool vis[N];
signed main() {
    cin >> n >> m;
    int u, v;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        if (u == v) continue;
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) cin >> bom[i];

    for (int i = 1; i <= n; i++)
        if (!col[i]) {
            col[i] = ++cnt;
            siz = 1;
            dfs(i, 0);
            sz[cnt] = siz;
        }

    int sum = 0, flag = 0;
    for (int i = 1; i <= n; i++) {
        if (bom[i] != 0) {
            if (!vis[col[i]]) {
                vis[col[i]] = true;
                sum++;
                if (sum > 1) { cout << 0; goto ac; }
                flag = col[i];
            }
        }
    }

    if (sz[flag] == 1) cout << 1;
    else if (flag == 0) {
        long long ans = 0;
        for (int i = 1; i <= cnt; i++) ans += sz[i] * sz[i];
        cout << ans;
    }
    else {
        cout << sz[flag] * sz[flag];
    }

ac:;
    return 0;
}

G题

  非常妙的一道题，涨经验了（其实是太菜了）

  很明显的线段树维护区间和问题，但是他的操作

  非常的复杂，想要对区间打标记不可能实现。但是我们会发现任何数在进行多次这个操作之后，会变为100，这个次数也不太多

  所以我们直接对每个数进行单点修改，当他们的值不变后我们就打上标记，意思是他们不用再修改了

  从这题上学到的是灵活一点，在碰到一些离谱的东西时，可以打表找下规律

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
struct edge {
    int ct; bool flg;
}tr[4 * N];
int n, m, lis[N], temp;
void update(int id) {
    tr[id].ct = tr[2 * id].ct + tr[2 * id + 1].ct;
    if (tr[2 * id].flg && tr[2 * id + 1].flg) tr[id].flg = true;
    else tr[id].flg = false;
}
void build(int id, int l, int r) {
    if (l == r) {
        tr[id].ct = lis[l]; tr[id].flg = false;
        return;
    }
    int mid = (l + r) >> 1;
    build(2 * id, l, mid); build(2 * id + 1, mid + 1, r);
    update(id);
}
void modify(int id, int l, int r, int ql, int qr, int k) {
    if ((l == ql && r == qr) && (tr[id].flg)) return;
    if (l == r) {
        for (int i = 1; i <= k; i++) {
            temp = round(10 * sqrt(tr[id].ct));
            if (temp == tr[id].ct) { tr[id].flg = true; break; }
            tr[id].ct = temp;
        }
        return;
    }
    int mid = (l + r) >> 1;
    if (qr <= mid) modify(2 * id, l, mid, ql, qr, k);
    else if (ql > mid) modify(2 * id + 1, mid + 1, r, ql, qr, k);
    else {
        modify(2 * id, l, mid, ql, mid, k); modify(2 * id + 1, mid + 1, r, mid + 1, qr, k);
    }
    update(id);
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> lis[i];
    build(1, 1, n);
    int od, a, b, k;
    for (int i = 1; i <= m; i++) {
        cin >> od;
        if (od == 2) cout << tr[1].ct << endl;
        else {
            cin >> a >> b >> k;
            modify(1, 1, n, a, b, k);
        }
    }
    return 0;
}

K题

  贪心思路很容易想到，先100100100······这样放，没有0了就11111这样接着放，这种题注意边界情况，当总球个数小于3和全是黑球的情况

还需补题

M 简单dp
E 计算几何
B 较难dp
I 思维，码力 （可先做）
J 位运算+（思维ordfs）