BUPT-2022-summer-4

发表于 | 分类于 |

B(多阶段dp)

大致题意:有若干个任务，有x、t、y、r四个属性(y<=x,r<=t)，有两个阶段，到达第一阶段需要s1经验值，到达第二阶段需要s2经验值，任务属性中，x表示在到达第一阶段前完成该任务所奖励的经验值，y表示在到达第一阶段后完成该任务所奖励的经验值，t表示在在到达第一阶段前完成该任务所花费的时间，r表示在到达第一阶段后完成该任务所花费的时间，先求到达第二阶段需要花费的最少时间

题解:最少时间+二维变量，一看很像背包，但两个阶段所需经验不同、任务数完成情况繁多，明显无法用背包来维护状态

故用dp[i][j]来表示状态，表示第一阶段前所获经验值=i，第一阶段后所获经验值=j时，所花费的最少时间

则dp[i][j]=min{dp[i][j],dp[i-a[k].x][j]+a[k].t,dp[i][j-a[k].y]+a[k].r}(即分别考虑第k个任务是在第一阶段前还是第一阶段后完成还是不完成，取最小值)

细节:任务的处理顺序—若不是从按x的从小到大顺序，会有什么问题?

在同一个阶段内状态转移时，类似于背包，任务的顺序不会产生影响，而overflow时，任务的顺序会产生影响

假设最佳方案时第一阶段的完成任务，按其x值递增排列是(1,2,3,4,5,6)，任务6完成第一阶段并将部分经验值转移到第二阶段，前5个任务随意打乱顺序都不会影响结果(都不会完成第一阶段，相当于一个类似背包的普通dp)，但如果将第6个任务提前，比如(6,5,4,3,2,1)，有可能提前完成第一阶段而导致不是最佳结果。

故将任务按x的顺序从小到大排，确保第一阶段完成前任务的完成顺序按递增顺序排列

下列代码根据j、k的情况分三类讨论:

  1. j<=s1，不会overflow，按正常dp方程处理
  2. j大于s1,此时会发生overflow，k需减去第一阶段转移来的多余值
  3. k不存在跨阶段问题，故按普通dp方程处理
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/
inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const ll maxn = 500 + 5;
ll dp[2*maxn + 5][2*maxn + 5];
struct node
{
    ll x, t, y, r;
    bool operator<(const node &b)
    {
        return x < b.x;
    }
};
node a[maxn];
ll tmp, T, n, m, s1, s2;
int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (T--)
    {
        cin >> n >> s1 >> s2;
        for (ll i = 1; i <= n; i++)
        {
            cin >> a[i].x >> a[i].t >> a[i].y >> a[i].r;
        }
        sort(a + 1, a + 1 + n);
        for (ll i = 2*maxn; i >= 0; i--)
        {
            for (ll j = 2*maxn; j >= 0; j--)
            {
                dp[i][j] = 6e12;
            }
        }
        // memset(dp, 0x3f, sizeof(dp));
        ll noans = dp[1][1];
        // cout << noans << "\n";
        dp[0][0] = 0;
        for (ll i = 1; i <= n; i++)
        {
            for (ll j = 2*maxn; j >= 0; j--)
            {
                for (ll k =2* maxn; k >= 0; k--)
                {
                    if (j <= s1 && j - a[i].x >= 0)
                    {
                        dp[j][k] = min(dp[j - a[i].x][k] + a[i].t, dp[j][k]);
                        // if(dp[j][k]<noans)
                        // {
                        //    cout << j << " " << k << " "<<dp[j][k] << "!!!!\n";
                        //}
                    }
                    if (j >= a[i].x && j - a[i].x < s1 && j > s1 && k - j + s1 >= 0)
                    {
                        dp[j][k] = min(dp[j][k], dp[j - a[i].x][k - (j - s1)] + a[i].t);
                        // if(dp[s1][k]<noans)
                        // cout << j << " " << k << " "<<dp[s1][k] << "!!!!\n";
                    }
                    if (k - a[i].y >= 0)
                    {
                        dp[j][k] = min(dp[j][k - a[i].y] + a[i].r, dp[j][k]);
                        // if(dp[j][k]<noans)
                        // {
                        // cout << j << " " << k <<" "<< dp[j][k] << "!!\n";
                        // }
                    }
                }
            }
        }
        ll ans = noans;
        for (ll i = s1; i <= 2*maxn; i++)
        {
            for (ll j = s2; j <= 2*maxn; j++)
            {
                ans = min(ans, dp[i][j]);
            }
        }
        if (ans != noans)
            cout << ans << "\n";
        else
            cout << "-1\n";
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

《关于我因为数组大小没开对wa了半天这件事》

F(博弈论+图论+树上问题)

大致题意:给定一颗树，在树上进行游戏，游戏规则如下：

  1. A可选定一个节点作为chip出发点，之后由B开始游戏
  2. 当轮到本人操作时，可选择将chip移至当前节点的子节点或父节点处(即与之相邻的节点)，但同一节点不能多次到达，若无法继续移动，则判本人负

题解:

在场上想的是所有的路径只能分为3类，只上、只下和先上后下，如果只下很容易处理，套用博弈论中的必胜点和必输点+树形dp就行，只上的情况根据每个节点的深度也可得出，但先上后下的情况过于复杂

引入图论中完全匹配的概念:

  1. 完全匹配是数量最多的一组边集，满足每条边的左右节点都只出现一次
  2. 若所有节点都在该边集出现过一次，则称该图完美匹配

将树看成图，结论:若图是完美匹配图，则Bob必胜，否则Alice必胜

证明如下：

  1. 若图是完美匹配图，则可将所有点划分成(s1,s2),(s3,s4)…若干个二元组，则当Alice选定任意个节点，Bob都可将其移动到其对应节点上，由于不能多次到达同一节点，Alice只能选择其他二元组的节点，Bob仍可重复上述操作直至所有节点都被遍历完毕，Bob胜利
  2. 若图不是完美匹配，设存在最大匹配(s1,s2),(s3,s4)…若干个二元组，有t个点不在该点集内，则Alice可选择不在该点集内的点开始游戏，Bob只能移动到该点集内的一个点(否则两个不在点集内的点也能匹配，与最大匹配相悖)，此时Alice可重复1中Bob操作，Bob输。若Bob可移动到不在该点集内的点，注意，，一开始时通过一个集外节点进入匹配点集，若再次从匹配点集到达集外节点，可将二元组重新分配且匹配数+1(画个图就很好理解)，与最大匹配定义相悖。

按正常图的方法求最大匹配，时间复杂度过大，而本题是特殊的树形结构，运用树形dp可在O(n)内求出任意子树的最大匹配情况

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
98
99
100
101
102
103
104
105
106
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/
inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const ll maxn = 100005;
vector<ll> g[maxn];
ll dp[maxn];
ll T, n;
void dfs(ll x,ll fa)
{
    ll cnt = 0;
    for (auto&e:g[x])
    {
        if(e==fa)
        {
            continue;
        }
        dfs(e, x);
        cnt += dp[e];
    }
    if(cnt==0)
    {
        dp[x] = 1;
    }else
    {
        dp[x] = cnt - 1;
    }
}
int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (T--)
    {
        cin >> n;
        ll x, y;
        for (ll i = 1; i <= n - 1;i++)
        {
            cin >> x >> y;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        dfs(1, 0);
        if(dp[1]==0)
        {
            cout << "Bob\n";
        }else
        {
            cout << "Alice\n";
        }
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

dp[i]表示以i为根的子树其不匹配的点数量，为0表示该子树完美匹配

今天被博弈论爆打的教训:1.不要纠结于每个人如何作出最佳操作，有时候只看结果思路更简单;2.图和博弈论可以根据完美匹配的定义结合，多留意一下

E

坑位预定