Codeforces Round #515 (Div. 3)

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

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

A. Vova and Train

题意：需要回答一系列的query。给定L, v, l, r, 已知每隔距离v会有一盏灯。上限为L。且l和r之间没有灯。问你总共有多少盏灯。
解法：由于L的范围到达$1e9$，query个数也到达$1e4$, 暴力肯定不可行。
所以只需要计算1-L间的灯的个数减去[l, r]区间内的灯的个数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int cnt = 0;
        int L, v, l, r;
        cin >> L >> v >> l >> r;
        cnt += L / v;
        cnt -= (r / v - (l - 1) / v);
        cout << cnt << endl;
    }
    return 0;
}

B. Heaters

题意：在一排元素组成的序列中存在一些取暖器，每个取暖器能温暖到所有坐标为$[pos - r + 1, pos + r -1]$的点，pos为取暖器的位置。现给定这么一个序列，其中有一些位置是取暖器。现问你最少需要多少个取暖器就可以温暖所有的点。
解法：贪心。
事实上这一题做的时候思路并不是很清晰，很混乱。
最后想到的做法：每次判断当前取暖器是不是可以不放。所有我们可以用一个数组记录每个位置的“热度”，从左向右扫描，如果遇到取暖器就把所有覆盖的点热度加1。
然后每次判断当前取暖器不放是不是存在有点的热度减为0的情况，如果没有则说明可以不放
否则就说明这个取暖器可以不放。

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, r, t;
const int maxn = 2e3 + 10;
int a[maxn], b[maxn], dp[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> r;
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        if(a[i])cnt++;
    }
    for(int i = 0; i < n; i++)
    {
        if(a[i])
            for(int j = max(0, i - r + 1); j < min(n, i + r); j++)
                dp[j]++;
    }
    for(int i = 0; i < n; i++)
        if(dp[i] == 0)//如果所有的取暖器都不能满足取暖需求
        {
            cout << -1;
            return 0;
        }
    for(int i = 0; i < n; i++)
    {
        int f = 1;
        for(int j = max(0, i - r + 1); j < min(n, i + r); j++)
        {
            dp[j]--;
            if(dp[j] == 0) f = 0;
        }
        if(f) cnt--;
        else
        {
            for(int j = max(0, i - r + 1); j < min(n, i + r); j++)
                dp[j]++;
        }
    }
    cout << cnt << endl;
    return 0;
}

C. Books Queries

题意：有三种类型的query：

  1. L id — put a book having index id on the shelf to the left from the leftmost existing book;
  2. R id — put a book having index id on the shelf to the right from the rightmost existing book;
  3. ? id — calculate the minimum number of books you need to pop from the left or from the right in such a way that the book with index id will be leftmost or rightmost.

给定一系列query，当为第三种类型的query时输出结果。
解法：我可太垃圾了。。。这题都不能很快的秒了。。
还在想用双端队列或者用数组存位置啥的。。
事实上，只需要，定义一个左边界和右边界，如果放在左边，则当前ID的位置左边界，同时左边界减减，否则位置为右边界，右边界加加。然后query位置时直接输出离左边界和右边界近的距离即可。一定要记住了！

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
#include <bits/stdc++.h>
#define ll long long
const int maxn = 2e5 + 10;
using namespace std;
int s[maxn];
int main()
{
    int q;
    scanf("%d", &q);
    getchar();
    int l = 0, r = 1;
    for(int i = 0; i < q; i++)
    {
        char c; int v;
        scanf("%c %d", &c, &v);
        getchar();
        if(c == 'L')
            s[v] = l--;
        else if(c == 'R')
            s[v] = r++;
        else
            cout << min(s[v] - l - 1, r - s[v] - 1) << endl;
    }
    return 0;
}

D. Boxes Packing

题意：有n个物品，m个盒子，每个盒子的大小为k，现在要把物品放进盒子中，只能从前向后放，所有物品的放入顺序不能变化。且每次从一个位置开始，必须要把其后所有的物品都放入。求最多能放多少个物品。
解法：这题好像比前三题都要简单的样子。一开始二分位置做，后来发现由于一定要放到最后一个物品，只要从后向前放，放到不能放为止即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define ll long long
const int maxn = 2e5 + 10;
using namespace std;
int a[maxn];
int n, m, k;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    int loc = n - 1;
    for(int i = 0; i < m; i++)
    {
        int siz = k;
        while(siz - a[loc] >= 0 && loc >= 0)
            siz -= a[loc--];
    }
    cout << n - 1 - loc << endl;
    return 0;
}

E. Binary Numbers AND Sum

题意：有两个二进制串a和b，每次计算$a \& b$的值并将b右移一位，直至b等于0，计算累加和模$998244353$的结果。
解法：前缀和思路
我们可以举个例子来观察，比如a=0111，b=1011
每次计算的是：
0111 & 1011
0111 & 101
0111 & 10
0111& 1
对于a的最高位而言，它仅被计算了1次。观察次高位，它被计算了2次，第一次是与b的次高位与运算，第二次是与b的最高位进行计算。
首先处理两个数的位数，使得它们的位数相等。
显然如果a的位数较多，多出来的高位是用不上的。如果位数较少，则需要前面补零。
所以我们只需要算一算b的前缀和，如果a的对应位是1则说明被加了这么多次，否则为0。
进制转换转10进制算一算就好了。

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
#include <bits/stdc++.h>
#define ll long long
const int maxn = 2e5 + 10;
using namespace std;
int bit[maxn];
const int MOD = 998244353;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    string a, b;
    cin >> a >> b;
    if(n > m)
    {
        a = a.substr(n - m);
        n = m;
    }
    if(m > n)
    {
        string t = "";
        for(int i = 0; i < m - n; i++)
            t += '0';
        a = t + a;
        n = m;
    }
    for(int i = 0; i < n; i++)
        bit[i] = b[i] -'0';
    for(int i = 1; i < n; i++)
        bit[i] += bit[i - 1];
    ll ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(a[i] == '1')
            ans = ans * 2 + bit[i];
        else
            ans *= 2;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}

F. Yet another 2D Walking

题意：在一个坐标系中，一个点可以向上下左右四个方向进行移动。在这个坐标系中有一些点需要经过，且每次只有当level内所有的点都被经过时才能走level+1的点。每个点$(x, y)$的level定义为$max(x, y)$。求经过所有点的最短路径。
解法：dp
首先我们发现由于level的存在，我们必须是先走完level小的所有点才能走大的。
一开始将$(0, 0)$塞入序列。
对于同一个level的点，其实就是一个正方行边上的所有点，我们必然是从左向右从上向下走或者是从下向上从右向左走且这个的距离是确定的。所以我们只需要每次判断是从左上开始走还是从右下开始走比较近即可。
考虑dp，令dp[i][0]为level为i的那一层在左上点结束的距离，dp[i][1]为level为i的那一层在右下点结束的距离。每次计算下一level的点，计算当前level的左上到下一level的左上和右下到xiayilevel的左上加上到达这一层左上或右下的dp值。最后答案就是最后一个level的两个点结束的最小值。
由于x, y的范围到达$1e9$，所以不能直接dp，还需要进行连续化，用map存储映射索引。
现行用map存储连续化后再用vector存储。
此外每个level内的一圈的长度也可以先行处理完成，同时排序等等工作也都需要预处理。

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>
#define fi first
#define se second
#define ll long long
#define pii pair<int, int>
const int maxn = 2e5 + 10;
using namespace std;
//每个边缘的最后一个点要不在左上要不在右下
ll dp[maxn][2];
//dp[i][0]表示第i个等级左上方结束
//dp[i][1]表示第i个等级右下方结束
map<int, vector<pii> > t;
map<int, int> ind;
int lev[maxn];//记录每一level的一圈的长度
vector<vector<pii> > T;
bool cmp(const pii& a, const pii& b)
{
    if(a.fi == b.fi)
        return a.se < b.se;
    return a.fi > b.fi;
}
int dis(pii a, pii b)
{
    return abs(a.fi - b.fi) + abs(a.se - b.se);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int x, y; cin >> x >> y;
        t[max(x, y)].push_back(make_pair(x, y));
    }
    t[0].push_back(make_pair(0, 0));
    int s = 0;
    for(auto& idx: t)
    {
        sort(idx.se.begin(), idx.se.end(), cmp);
        ind[idx.fi] = s++;
    }
    for(auto idx: t)
    {
        if(idx.se.size() == 1)
            continue;
        if(idx.se[0].se == idx.fi)
            lev[ind[idx.fi]] = idx.se[0].fi - idx.se.back().fi;
        else if(idx.se.back().fi == idx.fi)
            lev[ind[idx.fi]] = idx.se.back().se - idx.se[0].se;
        else
            lev[ind[idx.fi]] = 2 * idx.fi - idx.se.back().fi - idx.se[0].se;
    }
    for(auto idx: t)
        T.push_back(idx.se);
    int len = (int)T.size();
    for(int i = 0; i < len - 1; i++)
    {
        vector<pii> idx = T[i];
        pii a = idx.back(), b = idx[0];
        dp[i + 1][0] = min(dis(a, T[i + 1][0]) + dp[i][0], dis(b, T[i + 1][0]) + dp[i][1]) + lev[i + 1];
        dp[i + 1][1] = min(dis(a, T[i + 1].back()) + dp[i][0], dis(b, T[i + 1].back()) + dp[i][1]) + lev[i + 1];
    }
    cout << min(dp[len - 1][0], dp[len - 1][1]) << endl;
    return 0;
}