Codeforces Round #407 (Div. 2)

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

http://codeforces.com/contest/789/problems

A. Anastasia and pebbles

题意：Anastasia有两个口袋，她一次最多可以放k个物品到这两个口袋中，每个口袋只能放同一种类的物品。由于她很忙，所以她一天只能放一次，求她最少需要放多少天。
解法：随意模拟一下就好了。

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 n, k;
    cin >> n >> k;
    int len = 0;
    for(int i = 0; i < n; i++)
    {
        int t; cin >> t;
        int temp = t / k;
        if(t % k) temp++;
        len += temp;
    }
    cout << len / 2 + len % 2 << endl;
    return 0;
}

B. Masha and geometric depression

题意：需要构造出一个类似于等比数列的序列，这个序列的公比和首项都可以为0。有一个商界l，当超过上界时停止。此外，给定一些”bad integers”，当构造出的等比数列出现这些数字时跳过计算下一个。求在这个等比数列中共有多少个数字。
解法：一道需要注意细节的题目。
首先考虑特殊情况，如果首先就超过了上界则一定不存在数字直接输出0
然后考虑公比为0，1，-1的三种情况。
如果公比为0，显然除了第一个数后续所有的数均为0
判断第一个数，如果第一个数为0，判断0是否为”bad integers”进行结论。
如果0不是bad 则输出inf
这里可以发现首项为0的情况也可以归类在这里。
然后判断公比为1的情况，如果首项是bad，则为0 否则inf
最后是如果公比为-1，判断首项和首项的相反数如果有一个不是bad 则inf 否则0
然后就是暴力判断累乘算有几个数即可。因为是等比的所以时间复杂度一定是$log$级别。

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
map<ll, int> g;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll b, q, l, m;
    cin >> b >> q >> l >> m;
    if(abs(b) > l)
    {
        cout << 0 << endl;
        return 0;
    }
    for(int i = 0; i < m; i++)
    {
        int m; cin >> m;
        g[m] = 1;
    }
    if(q == 0 || b == 0)
    {
        if(g[0]){
            if(g[b])
                cout << 0 << endl;
            else
                cout << 1 << endl;
        }
        else
            cout << "inf" << endl;
        return 0;
    }
    if(q == 1)
    {
        if(g[b] == 0)
            cout << "inf" << endl;
        else
            cout << 0 << endl;
        return 0;
    }
    if(q == -1)
    {
        if((g[b] == 0 ||  g[-b] == 0))
            cout << "inf" << endl;
        else
            cout << 0 << endl;
        return 0;
    }
    int size = !g[b];//判断第一位是不是存在于序列中
    while(abs(b * q) <= l)
    {
        b *= q;
        if(g[b] == 0)
            size++;
    }
    cout << size << endl;
    return 0;
}

C. Functions again

题意：
给定一个序列，求最大的$f$值。
解法：dp
这道题在不久的去年曾经做过，所以现在还能很快的想出解法来。
由于每一项都是两个数之间的差，所以我们可以将两个数差计算出来单独成为一个序列。
但是由于l的不同，每一项的正负是不同的。
所以我们需要处理从1开始的每一项的值和从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
#include <bits/stdc++.h>
#define ll long long
const int maxn = 1e5 + 10;
using namespace std;
int n;
ll a[maxn], pl[maxn], mi[maxn];
ll cal(ll *p, int len)
{
    ll res = INT_MIN, temp = 0;
    for(int i = 0; i < len; i++)
    {
        temp += p[i];
        res = max(res, temp);
        if(temp < 0)
            temp = 0;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < n - 1; i++)
    {
        pl[i] = abs(a[i] - a[i + 1]);
        if(i % 2) pl[i] *= -1;
    }
    for(int i = 1; i < n - 1; i++)
    {
        mi[i - 1] = abs(a[i] - a[i + 1]);
        if(i % 2 == 0) mi[i - 1] *= -1;
    }
    ll a = cal(pl, n - 1);
    ll b = cal(mi, n - 2);
    cout << max(a, b) << endl;
    return 0;
}

D. Weird journey

题意：一个图有n个顶点m条边，可能存在自环，问你能够构造出多少条路径使得m-2条路径被经过两次剩下的两条路经过一次。经过一次的两条路不同则视为两个不同的路径。
Announcement: Note that it is not necessary for good path to go through all cities, we care only about roads.
解法：计数+欧拉路
图论还是弱啊。。看到这题可以说是无从下手了。
只能靠看看题解，才能维持得了生活的样子。
首先学习两个姿势：
欧拉路：在一个图中，由$i$点出发，将每个边遍历一次最终到达$j$点的一条路径。
条件：所有点度数为偶数或是有且仅有两个点的度数为奇数。
若有奇数点度，则奇数点度点一定是欧拉路的起点和终点，否则可取任意一点作为起点。
欧拉回路：$i=j$时的欧拉路径。
条件：所有点的度数均为偶数。
这道题我们可以看作是将m-2条经过两次的边拆成两条重边，所以这些边两边的点的度数一定为偶数。
那么剩下的两条边有这么几种情况：

  1. 两条不相交的边，有四个点的度数为奇数，不满足欧拉路
  2. 两条有公共顶点的边，满足有两个点的度数为奇数
  3. 一个环一条边，满足有两个点的度数为奇数
  4. 两个自环，所有点的度数均为偶数，满足欧拉回路

剩下的就是组合数学的东西了，算一算不要算重复了即可。
还有一个问题是判断是否存在路径的问题，只需要判断是不是会有不是孤立的点的块即可。
孤立点是可以的，因为不存在路径。但如果有两个点以上的多个联通块是不合法的。

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
#include <bits/stdc++.h>
#define ll long long
const int maxn = 1e6 + 10;
using namespace std;
ll n, m, self_loop, ans;
vector<int> g[maxn];
bool vis[maxn];
int deg[maxn];
void dfs(int nod)
{
    vis[nod] = 1;
    for(auto idx: g[nod])
    {
        if(!vis[idx])
        dfs(idx);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        deg[u]++;deg[v]++;
        if(u == v) {
            self_loop++;
            continue;
        }
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1; i <= n; i++)
        if(g[i].size())
        {
            dfs(i);
            break;
        }
    for(int i = 1; i <= n; i++)
        if(vis[i] == 0 && deg[i])//如果有边没有被走到
        {
            cout << 0 << endl;
            return 0;
        }
    ans += self_loop * (self_loop - 1) / 2;//两个自环
    ans += self_loop * (m - self_loop);//一个自环一条边
    for(int i = 1; i <= n; i++)//同一个顶点出发的两条边
    {
        ll len = (ll)g[i].size();
        ans += len * (len - 1) / 2;
    }
    cout << ans << endl;
    return 0;
}