Codeforces Round #408 (Div. 2)

发表于 | 分类于 |
字数统计: 2.4k | 阅读时长 ≈ 11

题面：http://codeforces.com/contest/796/problems

A. Buying A House

题意：要求离某个房子距离最近且没有被占用且费用小于预算的房子。
解法：按题意模拟。

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[200];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    int loc = m, mmin = 0xffff;
    while(loc++ <= n)
    {
        if(a[loc] && a[loc] <= k)
        {
            mmin = loc - m;
            break;
        }
    }
    loc = m;
    while(loc-- > 0)
    {
        if(a[loc] && a[loc] <= k)
        {
            mmin = min(mmin, m - loc);
            break;
        }
    }
    cout << mmin * 10 << endl;
    return 0;
}

B. Find The Bone

题意：有n个杯子和m个洞，在1号杯子下有一根骨头，现在交换一系列的杯子，如果杯子下方是一个洞则骨头掉入，问最后骨头在几号位置。
解法：按题意模拟，每次只需要记录骨头在几号位置。注意一开始的位置也可能有洞，这里是一个wa点。

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
#include <bits/stdc++.h>
#define ll long long
const int maxn = 1e6 + 10;
using namespace std;
bool hole[maxn];
int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 0; i < m; i++)
    {
        int t; scanf("%d", &t);
        hole[t] = 1;
    }
    int loc = 1;
    while(k--)
    {
        if(hole[loc]){
            printf("%d\n", loc);
            return 0;
        }
        int u, v;
        scanf("%d%d", &u, &v);
        if(u == loc)
        {
            loc = v;
            continue;
        }
        if(v == loc)
        {
            loc = u;
            continue;
        }
    }
    printf("%d\n", loc);
    return 0;
}

C. Bank Hacking

题意：有n个银行，每个银行有自己的防御能力$a_i$ ，这n个银行间有n-1个相连关系。现 Inzane 想要hack这n个银行，一开始可以选择任意一个hack，接下来每个要hack的银行必须满足。每次一个银行被hack了以后，所有与之直接连接和间接相连的银行的防御能力都会加1。所谓间接相连是指两个银行与同一个还没被hack的银行直接相连。

  1. 它还没有被hack过
  2. 必须要有一个被hack的银行和它直接相连
  3. 它的防御能力必须要小于等于 Inzane 的攻击能力

问 Inzane 所需要最小的攻击能力是多少。
解法：思维 贪心
这题还是参考了题解，自己想还是没能够想到。
由于边的条数为n-1，所以这显然是一棵树。第一次hack的银行防御能力为本身的防御能力，与之相连的所有银行的防御能力为原先能力+1，其它银行为原先能力+2。设所有银行中最大的防御力为$maxv$，答案显然就在$maxv$, $maxv+1$, $maxv + 2$中。
首先考虑答案maxv的情况，如果仅有一个最大值且所有能力值为maxv-1的银行都与之直接相连（没有maxv-1的银行也可以），则答案为maxv-1。
答案为maxv+1的情况就比较难想到了，考虑2-2-2，2-1-2，这类情况可以发现
如果选择中间的结点，则可以使得答案为maxv+1，所以就是看是否存在一点使得包括它自身在内加上所有与之直接相连的点是否包括了所有值为maxv的结点，此时答案为maxv+1
剩下的所有情况答案为maxv+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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 3e5 + 10;
struct e
{
    int to, nxt;
} g[2 * maxn];
int head[maxn];
int a[maxn];
int n, maxi, maxv = INT_MIN, edge = 1;
map<int, int> q;
bool judge()
{
    for(int i = 1; i <= n; i++)
    {
        int cnt = 0;
        if(a[i] == maxv)
            cnt++;
        for(int j = head[i]; j; j = g[j].nxt)
        {
            if(a[g[j].to] == maxv)
                cnt++;
        }
        if(cnt == q[maxv])
            return true;
    }
    return false;
}
void add_edge(int u, int v)
{
    g[edge] = e{v, head[u]};
    head[u] = edge++;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        q[a[i]]++;
        if(a[i] > maxv)
        {
            maxv = a[i];
            maxi = i;
        }
    }
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }
    int exto = 0;
    for(int i = head[maxi]; i; i = g[i].nxt)
        if(a[g[i].to] == maxv - 1) exto++;
    if(exto == q[maxv - 1] && q[maxv] == 1)
        cout << maxv << endl;
    else if(judge())
        cout << maxv + 1 << endl;
    else
        cout << maxv + 2 << endl;
    return 0;
}

D. Police Stations

题意：在一个国家里有n个城镇，k个有警察局的城镇。要求所有的城镇离警察局的距离不能大于d，现有n-1条边，问能删除几条边并给出删除边的序号。
解法：BFS
将k个警察局加入队列，然后搜索的深度限制最深为d，标记所有走过的边，遍历一遍看有多少条边没被走过并输出即可。
标记边的话一开始用了一个map<pair<int, int>, int>, 后来觉得有点慢。跑出来要1200+ms，改成读入时直接存储每条边的序号优化到了327ms。

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
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int maxn = 3e5 + 10;
vector<pii> g[maxn];
bool vis[maxn], vis_edge[maxn];
vector<int> ans;
queue<pii> T;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k, d, i;
    cin >> n >> k >> d;
    for(int j = 0; j < k; j++)
    {
        cin >> i;
        T.push(pii(i, 0));
        vis[i] = 1;
    }
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(make_pair(v, i));
        g[v].push_back(make_pair(u, i));
    }
    while(T.size())
    {
        pii now = T.front();
        T.pop();
        if(now.second == d)
            continue;
        for(auto id: g[now.first])
            if(!vis[id.first])
            {
                vis[id.first] = 1;
                T.push(pii(id.first, now.second + 1));
                vis_edge[id.second] = 1;
            }
    }
    for(int i = 1; i <= n - 1; i++)
        if(!vis_edge[i])
            ans.push_back(i);
    cout << ans.size() << endl;
    for(auto idx: ans)
        cout << idx << ' ';
    cout << endl;
    return 0;
}

E. Exam Cheating

题意：在一场考试中共有n道题目，有一个人想要作弊，他可以选择偷看左边或是右边的人。他一次最多可以看连续的k道题目，一共可以偷看p次。左边的人和右边的人做出了某几道题（可以是不相邻的若干道题）。问此人最多可以通过作弊做对几道题。
解法：将题目抽象出来以后就是一道区间覆盖问题。可以通过dp求解。
有两个区间长度为n，用长度为k的区间去覆盖它们，最多可以覆盖p次，问最多能覆盖多少个数。我们可以单独考虑每个位子，并做出决策，对于当前的位置我可以选择偷看甲，也可以偷看乙，也可以不偷看。如果我前一次选择了偷看某个人，也许我还剩余一些位子可以不进行一次新的偷看也可以看到。用题解的话来说就是：
It is optimal to look as many consecutive questions as possible, so when we decide to look, we share this benefit (of looking) to the next questions too, and it are stored in a and b, which denote how many of the next consecutive questions can be looked without paying one more glance.
考虑dp，$dp[i][j][x][y]$表示前i道题用了j次偷看的机会，并且甲还剩连续的x道题可以看，乙还剩连续的y道题可以看。然后dp就可以了。
$dp[i][j][x][y]$分别可以转移到:

  1. $dp[i+1][j][x-1][y-1] + i$能否看到
  2. $dp[i+1][j+1][x - 1][k - 1]+i$能否看到
  3. $dp[i +1][j +1][k - 1][y-1]+i$能否看到

这样子的时间复杂度显然是不够的，达到了$O(n\cdot k^2\cdot p)$考虑到数据范围会超时。
所以我们可以进行优化，发现p的次数可能不需要这么多，最多是只需要把整个区间覆盖到即可。优化至$O(n^2\cdot k)$
显然$1e3 \cdot 1e3 \cdot 50 \cdot 50$这么大的数组也是开不下的所以要用滚动数组。
每次使用完要把原来的置为-inf。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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e3 + 10;
int a[maxn], b[maxn];
int dp[2][maxn][55][55];
inline int ip(int k)
{
    return k > 0 ? k : 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //  cout << sizeof(dp) << endl;
    int n, p, k;
    cin >> n >> p >> k;
    int r, s;
    cin >> r;
    for(int i = 0; i < r; i++)
    {
        int t; cin >> t;
        a[t] = 1;
    }
    cin >> s;
    for(int i = 0; i < s;i ++)
    {
        int t; cin >> t;
        b[t] = 1;
    }
    p = min(p, (2 * n) / k + 2 * (2 * n % k != 0));//decrease时间复杂度
    int f = 0;
    memset(dp, -0x3f, sizeof(dp));
    dp[0][0][0][0] = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= p; j++)
        {
            for(int x = 0; x < k; x++)
            {
                for(int y = 0; y < k; y++)
                {
                    //不进行新的一轮偷看
                    dp[!f][j][ip(x - 1)][ip(y - 1)] = max(dp[!f][j][ip(x - 1)][ip(y - 1)], dp[f][j][x][y] + ((x && a[i]) || (y && b[i])));
                    //偷看甲
                    dp[!f][j + 1][k - 1][ip(y - 1)] = max(dp[!f][j + 1][k - 1][ip(y - 1)], dp[f][j][x][y] + (a[i] || (y && b[i])));
                    //偷看乙
                    dp[!f][j + 1][ip(x - 1)][k - 1] = max(dp[!f][j + 1][ip(x - 1)][k - 1], dp[f][j][x][y] + (b[i] || (x && a[i])));
                }
            }
        }
        memset(dp[f], -0x3f, sizeof(dp[f]));
        f = !f;
    }
    int ans = 0;
    for(int i = 0; i < k; i++)
        for(int j = 0; j < k; j++)
            ans = max(ans, dp[f][p][i][j]);
    cout << ans << endl;
    return 0;
}