AtCoder Beginner Contest 274 D E F

发表于 更新于 分类于

AtCoder Beginner Contest 274 D E F

D. DP
E. 状压DP
F. 思维/分类讨论

D - Robot Arms 2 【dp】

img
img
img
题意：
  先输入，n,x,y，表示可以走n次，终点是(x,y),起点是(0,0)，之后输出n个数字，第i个数字$a_i$表示第i次可以走多远，每次只能横着走或者竖着走，如果上一次是横着走，这一次必须竖着走，上一次是竖着，这一次必须横着，第一次必须由点(0,0)走到(ai,0)，问你是否存在一种符合要求的走法能走到终点。
分析：
  做dp，dp数组定义为bool，表示能否走到当前位置 dp[2][10005]
  或者整两个STL容器转移也可以。
  整体做法比较暴力。
AC代码：

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
#include <bits/stdc++.h>

using namespace std;

int n, x, y;
int ar[1050];
vector<int> vt;
set<int> st;
set<int>::iterator it;

bool judge()
{
    st.insert(ar[1]);
    for(int i = 3; i <= n; i += 2)
    {
        vt.clear();
        for(it = st.begin(); it != st.end(); ++it)
        {
            vt.push_back((*it) + ar[i]);
            vt.push_back((*it) - ar[i]);
        }
        st.clear();
        for(int j = 0; j < vt.size(); ++j) st.insert(vt[j]);
    }
    bool flag = false;
    for(int i = 0; i < vt.size(); ++i)
    {
        if(vt[i] == x)
        {
            flag = true;
            break;
        }
    }
    if(!flag) return false;

    vt.clear();
    st.clear();

    st.insert(ar[2]);
    st.insert(-ar[2]);
    for(int i = 4; i <= n; i += 2)
    {
        vt.clear();
        for(it = st.begin(); it != st.end(); ++it)
        {
            vt.push_back(*it + ar[i]);
            vt.push_back(*it - ar[i]);
        }
        st.clear();
        for(int j = 0; j < vt.size(); ++j) st.insert(vt[j]);
    }
    bool boo = false;
    for(int i = 0; i < vt.size(); ++i)
    {
        if(vt[i] == y) return true;
    }
    return false;
}

int main()
{
    scanf("%d%d%d", &n, &x, &y);
    for(int i = 1; i <= n; ++i) scanf("%d", &ar[i]);

    n += 5;

    if(judge()) printf("Yes\n");
    else printf("No\n");

    return 0;
}

E - Booster 【状压dp】

img
img
img
题意：
  输入n,m代表有n的城市和m个宝箱，n+m行给出城市和宝箱的坐标，一开始在(0,0)，你需要经过n个城市并且回到起点，起始时你的速度是1。宝箱不是必须的，但是每获取一个宝箱，你的斯必得就会翻倍。同一个地点的宝箱不可多次获取，问你最少需要多少时间回到起点。
分析：
  状压dp
  max(n)+max(m) = 17,$O(2^{n+m}\times(n+m)^2)$可以接受。
  对于状态，需要用一个二进制下长度为n+m的数组表示，前m位表示走过的宝箱，后n位表示经过的城市，状态的转移的时候先计算一下速度，之后跟普通的状压一样，统计答案的时候，一方面，只需要统计后n位全是1的状态，另一方面，计算回到起点的时间，也是先计算速度。
AC代码

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n, m, r;
pair<double, double> pi[20];
double dp[1<<17][20];
ll x, y, z;

int sped(int st)
{
    st >>= n;
    int res = 0, v = 1;
    while(st)
    {
        if(st&1) ++res;
        st /= 2;
    }
    for(int i = 1; i <= res; ++i) v *= 2;
    return v;
}

double calc_dis(int x, int y)
{
    return sqrt((pi[x].first - pi[y].first) * (pi[x].first - pi[y].first)+ (pi[x].second - pi[y].second) * (pi[x].second - pi[y].second));
}

bool judge(int x)
{
    if((x & ((1<<n)-1)) != ((1<<n) - 1)) return true;
    return false;
}

int main()
{
    scanf("%d%d", &n, &m);
    r = n + m;

    pi[0] = make_pair(0, 0);

    for(int i = 1; i <= n; ++i)
    {
        scanf("%lld%lld", &x, &y);
        pi[i] = make_pair(x, y);
    }

    for(int i = n + 1; i <= n + m; ++i)
    {
        scanf("%lld%lld", &x, &y);
        pi[i] = make_pair(x, y);
    }

    int mx_st = (1 << r) - 1;
    double dis;
    double vv, tt;

    for(int i = 0; i <= mx_st; ++i)
    {
        for(int j = 1; j <= r; ++j)
        {
            dp[i][j] = 999999999999.9;
        }
    }

    for(int i = 1; i <= r; ++i){
        dp[1<<(i-1)][i] = calc_dis(i, 0);
    }

    for(int s = 0; s < mx_st; ++s)
    {
        vv = sped(s);
        for(int i = 1; i <= r; ++i)
        {
            if(!(s >> (i - 1) & 1)) continue;
            for(int j = 1; j <= r; ++j)
            {
                if(s >> (j - 1) & 1) continue;
                dis = calc_dis(i, j);
                tt = (double)dis / vv;
                dp[s|(1<<(j-1))][j] = min(dp[s][i] + tt, dp[s|(1<<(j-1))][j]);
            }
        }
    }

    double ans = 999999999999.9;
    for(int i = 0; i <= mx_st; ++i)
    {
        if(judge(i)) continue;
        vv = sped(i);
        for(int j = 1; j <= r; ++j)
        {
            if(!(i >> (j - 1) & 1)) continue;
            dis = calc_dis(j, 0);
            tt = (double)dis / vv;
            ans = min(ans, dp[i][j] + tt);
        }
    }
    printf("%.6lf", ans);
    return 0;
}

F - Fishing

img
img
img
题意：
  输入n和a，表示有n条鱼和一张长度为a的渔网。
  之后n行每行三个数字，分别表示每条鱼的权值，起始坐标，速度，鱼会随着时间移动，问你这张长度为a的渔网最多能获得权值为多少的鱼。
分析：
  枚举每一条鱼作为渔网左界的情况，可获取的权值最大值（像坐标x，时间t等变量都是double，理应排除，想到枚举n，即每一条鱼）。作为渔网的左界是为了处分利用取最大值。
  之后对于剩下的n-1条鱼，随着时间流动都有三种情况，1是永远不会进入渔网中，2是进入一次渔网，出去一次渔网，之后永远不会进入（可能0时刻就进入了），3是一直在渔网内。把可能的鱼进出网时间求出，放入一个数组中（进网权值算w，出网算-w），按照时间排序，遍历一遍求前缀和即可（任何一个位置的前缀和都是合理的，因为同时处理了进网时间和出网时间，权值也做了正负区分）。
  做个简单的分类讨论。（简单的高一物理追只因与相遇问题）
img
AC代码：

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
#include <bits/stdc++.h>

using namespace std;

int n, a;
struct node
{
    int w, x, v;
} ar[4050], tmp[4050];
int ans, cnt, sum;

bool cmp(node a, node b)
{
    if(a.x * b.v != b.x * a.v) return a.x * b.v < b.x * a.v;
    return a.w > b.w;
}

int calc(int id)
{
    cnt = 0;
    sum = ar[id].w;
    int res = 0;
    int x1 = ar[id].x, v1 = ar[id].v;
    int x2, v2, w;

    for(int i = 1; i <= n; ++i)
    {
        if(i == id) continue;

        x2 = ar[i].x;
        v2 = ar[i].v;
        w = ar[i].w;

        if(x2 < x1 && v2 > v1)
        {
            tmp[++cnt] = {w, x1 - x2, v2 - v1};
            tmp[++cnt] = {-w, x1 + a - x2, v2 - v1};
        }
        else if(x2 >= x1 && x2 <= x1 + a)
        {
            sum += w;
            if(v2 < v1) tmp[++cnt] = {-w, x2 - x1, v1 - v2};
            else if(v2 > v1) tmp[++cnt] = {-w, x1 + a - x2, v2 - v1};
        }
        else if(x2 > x1 + a && v2 < v1)
        {
            tmp[++cnt] = {w, x2 - x1 - a, v1 - v2};
            tmp[++cnt] = {-w, x2 - x1, v1 - v2};
        }
    }

    sort(tmp + 1, tmp + cnt + 1, cmp);

    res = max(res, sum);

    for(int i = 1; i <= cnt; ++i)
    {
        sum += tmp[i].w;
        res = max(res, sum);
    }

    return res;
}

int main()
{
    scanf("%d%d", &n, &a);

    for(int i = 1; i <= n; ++i) scanf("%d%d%d", &ar[i].w, &ar[i].x, &ar[i].v);

    for(int i = 1; i <= n; ++i) ans = max(ans, calc(i));

    printf("%d\n", ans);

    return 0;
}