Codeforces Round #521 (Div. 3)

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

题面：http://codeforces.com/contest/1077/problems
赛中：a了5题真开心，200名诶第一次这么靠前应该能涨好多好多分
赛后：b题fst了555，600名 不过涨了89分美滋滋。
https://wx1.sinaimg.cn/mw690/006tWL1Bgy1fyed42imm2j31cs0ecgob.jpg

A. Frog Jumping

题意：青蛙会先向右跳距离$a$，再向左跳距离$b$，问n次后跳到哪个位置
解法：按题意模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define ll long long
const int maxn = 1e2 + 10;
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        ll a, b, k;
        cin >> a >> b >> k;
        ll ans = (a - b) * (k / 2);
        if(k % 2)
            ans += a;
        cout << ans << endl;
    }
    return 0;
}

B. Disturbed People

题意：有一排房子处于亮灯或是灭灯状态，对于一个灭灯状态的房子，如果两边房子都亮着则这个房子处于被打扰状态，问最少关几个房子的灯可以使得没有房子被打扰。
解法：考虑1010101发现存在贪心策略，对于被打扰的房子尽可能地让右边的灯关掉就可以使得关灯的数量最少而满足要求。

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 = 1e2 + 10;
using namespace std;
int a[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(a[i] && !a[i + 1] && a[i + 2])
        {
            ans++;
            a[i + 2] = 0;
        }
    }
    cout << ans << endl;
    return 0;
}

C. Good Array

题意：我们定义一个array是good的如果在这个array中存在一个元素是剩下的元素之和。 现在你可以任意删除其中的一个元素，要使得它成为一个good的array，求可以删除哪个元素。输出所有的可能。
解法：要使array满足good的条件，必然是最大的元素等于剩下的元素之和。所以只需要跑一遍看删除当前元素后的最大的元素（即第二大的元素）满不满足条件即可。所以只需要排序，记录一下先前的索引即可。

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
#include <bits/stdc++.h>
#define ll long long
const int maxn = 2e5 + 10;
using namespace std;
struct node{
    ll v, idx;
}a[maxn];
bool cmp(const node& a, const node& b)
{
    return a.v < b.v;
}
ll sum;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i].v;
        sum += a[i].v;
        a[i].idx = i;
    }
    sort(a + 1, a + n + 1, cmp);
    set<ll> q;
    for(int i = 1; i <= n - 1; i++)
    {
        if(sum - a[i].v - a[n].v == a[n].v)
            q.insert(a[i].idx);
    }
    if(sum - a[n].v - a[n - 1].v == a[n - 1].v)
        q.insert(a[n].idx);
    cout << q.size() << endl;
    for(auto idx: q)
        cout << idx << ' ';
    cout << endl;
    return 0;
}

D. Cutting Out

题意：给定一个数组a。要从之中删除给定长度k的子数组，（不考虑顺序问题）。要求找出能够删除最多次数的子数组。
解法：二分删除次数，找到最多的删除次数且满足题目要求长度的数组。如果最后找出的数组长度大于所需长度k，输出前k个即可。

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
#include <bits/stdc++.h>
#define ll long long
const int maxn = 2e5 + 10;
using namespace std;
int a[maxn];
map<int, int> q;
vector<int> ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        q[a[i]]++;
    }
    int l = 1, r = n;
    for(int i = 0; i < 100; i++)
    {
        vector<int> temp;
        int mid = (l + r) >> 1;
        for(auto idx: q)
        {
            if(idx.second >= mid)
            {
                for(int j = 0; j < idx.second / mid; j++)
                    temp.push_back(idx.first);
                if(temp.size() >= k)
                    break;
            }
        }
        if(temp.size() >= k)
        {
            ans = temp;
            l = mid;
        }
        else
            r = mid;
    }
    for(int i = 0; i < k; i++)
        cout << ans[i] << ' ';
    cout << endl;
    return 0;
}

E. Thematic Contests

题意：有一堆不同的问题，各自有各自的难度系数。每次选取难度系数的题，后一次选择的题的数量必须是前一次的两倍。且每次选取难度必须递增。例如第1个难度取2题，后面必须取的题目数量必须是4.8.16….第1难度取3次，后面取的题目数量是6.12.24…要求出最多能选择几道题。
解法：直接暴力就行。暴力取每种难度取j道。由于是指数变化的，所以复杂度可以接受，为$O(nlognlogn)$

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
#include <bits/stdc++.h>
#define ll long long
const int maxn = 2e5 + 10;
int a[maxn];
using namespace std;
map<int, int> q;
int ans;
vector<int> p;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        q[a[i]]++;
    }
    for(auto idx: q)
        p.push_back(idx.second);//存入次数
    sort(p.begin(), p.end());
    int len = (int)p.size();
    for(int i = 0; i < len; i++)
    {
        int temp = 0;
        for(int j = 1; j <= p[i]; j++)
        {
            int k = i + 1, power = j;
            temp = j;
            while(k < len && p[k] >= 2 * power)
            {
                temp += 2 * power;
                power *= 2;
                k++;
            }
            ans = max(ans, temp);
        }
    }
    cout << ans << endl;
    return 0;
}

F. Pictures with Kittens

题意：一个长度为$n$的数组，要求连续的$k$个中必须取一个，总共取$x$个。求能取得的最大的和为多少。
解法：考虑dp。
$dp[i][j]$表示最后一个取了第$i$个位置且共取了$j$个的最大和。
每次$dp[i][j]$可以从$dp[y][j - 1]$转移而来，其中$ i - k < y < i$
每次转移方程为$dp[i][j] = max(dp[y][j - 1] + a[i], dp[i][j]])$
一开始所有的dp值初始化为-inf，$dp[0][0]$初始化为0
这样的话$O(n^3)$easy version可以做。
但是如果hard version $n$范围达到$5e3$，需要用单调队列优化dp
需要优化的是$dp[i][j]$从$dp[y][j - 1]$转移，其中$ i - k < y < i$
有一个经典的滑动窗口优化，在一个队列中从头部向尾部dp值单调递减(存的是下标)每次将那些不在范围里的下标出队
并将当前下标$i$入队列，小于其dp值的直接舍弃。因为不可能会用到那些值。给出的代码是单调队列优化后的。
easy version

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
#include <bits/stdc++.h>
#define ll long long
const int maxn = 1e3 + 10;
using namespace std;
int a[maxn];
ll dp[maxn][maxn];//dp[i][j]表示在最后一个选中的是i且取了j个的最大beauty值
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k, x;
    cin >> n >> k >> x;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= x; j++)
            dp[i][j] = -1e18;
    dp[0][0] = 0;
    for(int i = 1; i <= x; i++)
        for(int j = 1; j <= n; j++)
            for(int t = 1; t <= min(k, j); t++)
                    dp[j][i] = max(dp[j][i], dp[j - t][i - 1] + a[j]);
    ll ans = -1;
    for(int i = n - k + 1; i <= n; i++)
        ans = max(ans, dp[i][x]);
    cout << ans << endl;
    return 0;
}

hard version:

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 5e3 + 10;
ll a[maxn], que[maxn];
ll dp[maxn][maxn];
int head, tail;
int main()
{
    int n, k, x;
    cin >> n >> k >> x;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= x; j++)
            dp[i][j] = -1e18;
    dp[0][0] = 0;
    for(int i = 1; i <= x; i++)
    {
        que[++tail] = 0;
        for(int j = 1; j <= n; j++)
        {
            while(head <= tail && que[head] < j - k)
                head++;
            dp[j][i] = dp[que[head]][i - 1] + a[j];
            while(head <= tail && dp[que[tail]][i - 1] <= dp[j][i - 1])
                tail--;
            que[++tail] = j;
        }
        head = 1;
        tail = 0;
    }
    ll ans = -1;
    for(int i = n - k + 1; i <= n; i++)
        ans = max(ans, dp[i][x]);
    cout << ans << endl;
    return 0;
}