比赛链接：Dashboard - The 2023 ICPC Asia Shenyang Regional Contest (The 2nd Universal Cup. Stage 13: Shenyang) - Codeforces

C

水题

E

题意：有羊 $x$ 只，狼 $y$ 只，有一人用一艘容量为 $p$ 的船要将所有的羊运到对岸，但当人不在的一边中狼严格大于羊的数量加 $q$ ，羊就会被吃掉。在保证羊安全的前提下至少需要运多少次。

考虑设计 $dp$ 状态：$dp[i][j][k]$ ，表示人在 $k $ 岸时，初始岸的羊和狼的数量为 $i,j$ 时的最小次数。

因为求最少次数，用 $bfs$ 更新状态。每次可以转移如下：
$$
dp[i][j][1]\rightarrow dp[i-n][j-m][2],n+m=p,i-n\geq j-m+q
$$

$$
dp[i][j][2]\rightarrow dp[i][j+m][1]
$$

每次运送到对岸时都把容量排满是最优的；

往回运的时候只把多余的狼运回，保证对岸满足条件即可。

最终的答案就是 $dp[0][y’][2]$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
# include <bits/stdc++.h>

using namespace std;
struct state
{
    int x,y,id;
};

const int N = 110;
int n,m,p,q;
int d[N][N][2];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin >> n >> m >> p >> q;
    queue<state>heap;

    heap.push({n, m, 1});
    memset(d, -1, sizeof d);
    d[n][m][1] = 0;
    bool flag = false;

    while(heap.size())
    {
        auto t = heap.front();
        heap.pop();
        int x = t.x, y = t.y, id = t.id;
        int dis = d[x][y][id];
        //cout << x << ' ' << y << ' ' << id << endl;
        if(!x) 
        {
            flag = true;
            cout << dis << '\n';
            break;
        }

        if(id == 1)
        {
            if(x + y <= p) 
            {
                if(d[0][0][2] == -1)
                {

                    d[0][0][2] = dis + 1;
                    heap.push({0, 0, 2});
                }
            }
            else
            {
                for(int i = 0; i <= min(x, p); i ++)
                {
                    if(p - i >= y) 
                    {
                        if(d[x - i][0][2] == -1)
                        {
                            d[x - i][0][2] = dis + 1;
                            heap.push({x - i, 0, 2});
                        }
                    }
                    else
                    {
                        int sheep = x - i;
                        int wolf = y - (p - i);
                        if(!sheep || (sheep + q >= wolf && d[sheep][wolf][2] == -1) )
                        {
                            d[sheep][wolf][2] = dis + 1;
                            heap.push({sheep, wolf, 2});
                        }
                    }
                }
            } 
        }
        else
        {
            int sx = n - x, sy = m - y;
            if(sx && sx + q < sy)
            {
                int cnt = sy - sx - q;
                if(d[x][y + cnt][1] == -1)
                {
                    d[x][y + cnt][1] = dis + 1;
                    heap.push({x, y + cnt, 1});
                }
            }
            else if(d[x][y][1] == -1)
            {
                d[x][y][1] = dis + 1;
                heap.push({x, y, 1});
            }
        }
    }
    if(!flag) cout << -1 << '\n';
    return 0;
}

dp，bfs/dfs

J

题意：给出一颗树，两人轮流执行，每次选择相连的一对顶点 $u,v$ ，然后将所有与 $u$ 相连的顶点全部连向 $v$ ，保证每次操作之后的新树与操作之前的原树不是同构树，当某人无法操作时则输掉比赛。求谁会赢。

找规律题。

最后的终止状态是一棵只有两层的树，所有的儿子都连向一个根节点。

因此，每次最优解是选择某一父节点与一个子节点，将所有与子节点相连的点连向父节点，相当于每次将深度减少一层，故只需统计每个点的度来判断满足条件的操作对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int d[100];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        d[x]++;
        d[y]++;
    }

    int cnt=0;
    for(int i=1;i<=n;i++)if(d[i]>=2)cnt++;
    if(cnt==0)cout<<"Bob";
    else if(cnt%2==0)cout<<"Alice";
    else if(cnt%2==1)cout<<"Bob";
    return 0;
}

K

题意：给出 $n$ 场比赛每场比赛后rating的升降，初始rating是0，可以随便安排比赛的顺序，问rating最大值的更新次数有多少种不同的取值。

前置知识：http://aaaarnoldddd.github.io/2024/03/19/ACM/模板/权值线段树/

想出思路但是不会数据结构

将所有的rating分为正负两类，将正rating降序排列，将负rating求和看做一个整体，考虑负rating能产生多大的影响：

若将负rating放在最后，那么rating更新次数就是正rating的个数；

若将负rating放在最后一个正rating之前且大于最后一个正rating，那么rating更新次数就是正rating的个数-1；

若将负rating放在最后两个正rating之前且大于最后两个正rating和，那么rating更新次数就是正rating的个数-2；

……

假设前 $k$ 次更新可行，那么前 $k$ 个数的和一定大于所有rating的和，因此使用权值线段树，其中包括单点更新和查询操作，每次查询最少的最大的 $k$ 个数的和大于等于 $sum$ ，答案就是 $cnt(+)-k+1$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
# include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010, M = 2 * N;
const int inf=1e9+1;

int n,m;
int a[N];

struct Node
{
	int l,r,num;
	LL sum;
}tr[4 * M + M * 19];
int tot;

void update(int &id,int l,int r,int pos,int val)
{
    if(id==0)id=++tot;
    tr[id].num+=val;
    tr[id].sum+=pos*val;

    if(l==r)return ;

    int mid=(l+r)>>1;
    if(pos<=mid)update(tr[id].l,l,mid,pos,val);
    else update(tr[id].r,mid+1,r,pos,val);
}

int query(int id,int l,int r,LL sum)
{
    if(l==r)
    {
        if(sum<=0)return 0;
        return (sum+l-1)/l;//一个节点可能有重复的多个数
    }

    int mid=(l+r)>>1;
    if(tr[tr[id].r].sum>sum)return query(tr[id].r,mid+1,r,sum);
    return query(tr[id].l,l,mid,sum-tr[tr[id].r].sum)+tr[tr[id].r].num;
}

int main()
{
    LL sum=0;
    int cnt=0;
    int rt=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]>0)
        {
            update(rt,1,inf,a[i],1);
            cnt++;
        }
        sum+=a[i];
    }

    for(int i=1;i<=m;i++)
    {
        int pos,t;
        cin>>pos>>t;
        if(a[pos]>0)update(rt,1,inf,a[pos],-1),cnt--;
        if(t>0)update(rt,1,inf,t,1),cnt++;
        sum=sum-a[pos]+t;
        a[pos]=t;
        
        // cout<<sum<<" "<<cnt<<" "<<query(rt,1,inf,sum)<<" ";
        cout<<cnt-query(rt,1,inf,sum)+1<<endl;
    }
    return 0;
}

权值线段树