第一场

https://ac.nowcoder.com/acm/contest/46800#question

A：

题目：

按照 ABABABABAB， 来点球，问你在第几球结束比赛，或者没有分出胜负。

思路：

如果胜场少的一方后面都赢了，还是无法胜场大于另一方，那么已经结束比赛。

否则到最后都没分出胜负

代码

void solved()
{
    cin >> s + 1;

    int A, B;
    A = B = 0;

    bool flag = false;

    for(int i = 1; i <= 10; i++)
    {
        if(i % 2 != 0 && s[i] == '1')
            A++;

        if(i % 2 == 0 && s[i] == '1')
            B++;

        if(A > B)
        {
            if(A > B + (10 - i) / 2 + (i % 2))
            {
                flag = true;
                cout << i << endl;
                return;
            }
        }

        if(B > A)
        {
            if(B > A + (10 - i) / 2)
            {
                flag = true;
                cout << i << endl;
                return;
            }
        }
    }

    if(!flag)
    {
        cout << -1 <<endl;
    }
}

C：

题目：

略

思路：

不难发现，对于所有引用量 > 0, 的文章，都各自找一人发表，这样是最多的情况。

代码

void solved()
{
    int n;
    cin >> n;
    int ans = 0;

    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        if(a[i]) ans++;
    }

    cout <<ans <<  endl;
}

F：

题目：

现在存在一些树，存在一些点上有炸弹，我们找到一组方案 S T， S 为终点 T 为七点，使得我们必须经过有炸弹的点。

思路：

题目只要求方案数，所以只需要判断是否炸弹都在一个连通块内，或者不存在炸弹。

因为炸弹可以随便放，所以个数不影响答案。

对于炸弹所在连通块的数量 > 1, 那么无论如何也不能找到一个路径使得都经过。

如果数量 == 1， 那么连通块内任意两个点都可以，为连通块内点的数量 ^ 2

如果数量 == 0， 那么任意连通块都可，任意连通块参考上面

代码

void solved()
{
    cin >> n >> m;

    for(int i = 1; i <= n; i++) p[i] = i, cnt[i] = 1;


    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        int pa = find(a), pb = find(b);
        if(pa != pb)
        {
            p[pa] = pb;
            cnt[pb] += cnt[pa];
        }
    }

    int p = 0;
    int ans = 0;
    int ans2 = 0;

    for(int i = 1; i <= n; i++)
    {
        int x, px;
        cin >> x;

        if(x)
        {
            px = find(i);
            if(!bom[px])
            {
                p++;
                ans += cnt[px] * cnt[px];
                bom[px] = true;
            }
        }
        if(i == find(i)) ans2 += cnt[i] * cnt[i];
    }


    if(!p)
    {
        cout << ans2 << endl;
    }else if(p == 1) cout << ans <<endl;
    else cout << 0 << endl;

}

G：

题目：

略

思路：

不难发现是区间操作，由此想到线段树，但是因为根号操作不满足线段树内合并，所以只能单点操作。

但是单点操作时间复杂度是不够的。

对于根号操作，我们打表发现，所有的数字都会归于一个数字，所以有很多操作是多余的，如果说当前操作的

数字已经归于终点，那么没必要操作了。

代码

int f(int x)
{
    return round(10 * sqrt(x));
}

void push_up(int u)
{
    tr[u].sum = tr[u << 1]. sum + tr[u << 1 | 1].sum;
    tr[u].flag = tr[u << 1].flag & tr[u << 1 | 1].flag;
}


void build(int u, int l, int r)
{
    if(l == r)
    {
        tr[u] = {l, r, a[l], 0, 0};
        return;
    }

    tr[u] = {l, r};
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);

    push_up(u);
}

void modify(int u, int l, int r, int k)
{
    int lr = (tr[u].r - tr[u].l + 1);
    if(tr[u].flag) return;

    if(tr[u].l == tr[u].r)
    {

        for(int i = 0; i < k; i++)
        {
            int last = tr[u].sum;
            tr[u].sum = f(tr[u].sum);
            if(last == tr[u].sum)
            {
                tr[u].flag = true;
                break;
            }
        }
    }else
    {
        int mid = tr[u].r + tr[u].l >> 1;

        if(mid >= l) modify(u << 1, l, r, k);
        if(r > mid) modify(u << 1 | 1, l, r, k);
        push_up(u);
    }
}




void solved()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];

    build(1, 1, n);


    for(int i = 0; i < m; i++)
    {
        int op, l, r, k;
        cin >> op;

        if(op == 1)
        {
            cin >> l >> r >> k;
            modify(1, l, r, k);
        }else
        {
            cout << tr[1].sum << endl;
        }
    }
}

H:

题目：

略

思路：

因为题目保证了拼图是完好的，所以最终都会一个凸出对于一个凹下去。

所以我们统计目前给出的拼图的 凸凹个数，然后差来找到对应成本

代码

void solved()
{
    cin >> n;

    int p1 = 0, p2 = 0;

    for(int i = 0; i < n * n - 1; i++)
    {
        cin >> ss[i];

        int np1 = 0, np2 = 0;

        for(int j = 0; j < 4; j++)
        {
            if(ss[i][j] == '1') p1++;
            else if(ss[i][j] == '2')p2++;
        }
    }

    cout <<  p1 - p2 + 10<< endl;

}

K：

题目：

略

思路：

首先我们优先考虑最多放置1的，满足 0 个坏区间。

发现 1 0 0 1 0 0 1，这样放置是边界 0 个坏区间，然后接下来放一定会出现坏区间。

那么我们贪心的来说接下来肯定是连续放置1，尽可能在一个区间内。

因为后面可能出现 1 00 1 0，而前面的 1 0 0，已经固定，所以我们从后面开始放。

然后统计坏区间即可

代码

void solved()
{
    int n, m;
    cin >> n >> m;

    string s = "";

    if((n - 1) / 3 + 1 >= m)
    {
        cout << 0 << endl;
        return;
    }

    for(int i = 0; i < n; i++)
        s += '0';

    int sum = 2;
    int pos = 0 ;

    for(int i = 0; i < n; i++)
    {
        sum++;
        if(sum == 3) s[i] = '1', sum = 0, pos++;
        if(pos == m) 
            break;
    }


    sum = 0;

    for(int i = n  - 1; i >= 0; i--)
    {
        if(sum + pos == m) break;

        if(s[i] == '0') 
        {
            s[i] = '1';
            sum++;
        }
    }


    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(i + 2 == n) break;

        int sum = 0;
        for(int j = i; j < i + 3; j++)
        {
            if(s[j] == '1') sum++;
        }

        if(sum >= 2)
        {
            ans++;
        }
    }

    cout << ans << endl;
}

代码

void solved()
{
    int n, m;
    cin >> n >> m;

    string s = "";

    for(int i = 0; i < n; i++)
        s += '0';

    int sum = 2;
    int pos = 0 ;

    for(int i = 0; i < n; i++)
    {
        sum++;
        if(sum == 3) s[i] = '1', sum = 0, pos++;
        if(pos == m) 
            break;
    }


    sum = 0;

    for(int i = n  - 1; i >= 0; i--)
    {
        if(sum + pos == m) break;

        if(s[i] == '0') 
        {
            s[i] = '1';
            sum++;
        }
    }


    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(i + 2 == n) break;

        int sum = 0;
        for(int j = i; j < i + 3; j++)
        {
            if(s[j] == '1') sum++;
        }

        if(sum >= 2)
        {
            ans++;
        }
    }

    cout << ans << endl;
}

M：

题目：

略

思路：

不难发现，每一个前面的送出多少仙贝都影响后面，所以思考 dp。

状态表示：f[i][j] 表示已经给了 i个人，还剩下 j 个仙贝。

状态转移

首先枚举 i j，其次要枚举当前第 i 个人要给多少仙贝。

所以 f[i][j] = max(f[i][j], f[i - 1][j + k] + (k) / (j + k));

最后统计答案，看看给了 n 个人，剩下多少个仙贝的好感度最多。。

代码

void solved()
{
    cin >> n >> m;

    for(int i = 1; i <= n; i++)
    {
        for(int j = m; j >= 0; j--)
        {            
            for(int k = 0; k <= m; k++)
            {
                if(j + k <= m)
                f[i][j] = max(f[i][j], f[i - 1][j + k] + (k * 1.0 /(j + k)));
            }
        }
    }

    long double ans = 0;

    for(int i = 0; i <= m; i++) ans = max(ans, f[n][i]);

    printf("%.8llf",ans);
}