Panasonic Programming Contest 2022(AtCoder Beginner Contest 251)

75 阅读 0 评论 50 点赞

我是靠谱客的博主开心玉米，这篇文章主要介绍Panasonic Programming Contest 2022(AtCoder Beginner Contest 251)，现在分享给大家，希望可以做个参考。

D - At Most 3 (Contestant ver.)

题意：给定 $W < = 1 e 6$ 构造一个长度不超过300的数组使得数组中任意一个数字，任意两个数字相加，任意三个数字相加组成的数能得到 $1 - W$ 间的所有数字。

贪心构造：参照了tourist佬的代码构造的合理性证明放在代码后的注释中

复制代码

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<iostream>
#include<algorithm>
using namespace std;
#define ll long long
int main()
{
    printf("300n");
    for(int i=1;i<=100;i++)
    {
        printf("%d %d %d ",i,i*100,i*10000);
    }

    return 0;
}
/*
按数位来划分
1.1~100 
2.100 ~ 10000 中 相隔100的数都存在
3.10000 ~ 1000000 中 相隔10000的数都存在
所有的一位数都存在1中
所有的两位数都存在1中
所有的三位数 百位都在2中存在 十位个位在1中存在 例如 983 900在2中存在 83在1中存在 
所有的四位数 千位和百位数都在2中存在 十位数个位数在1中存在 例如：1234 1200在2中存在 34在1中存在 最多需要两个数字来构成
所有的五位数 万位数都在3中存在 剩下的数字可以参照四位数的构造情况 例如81234 80000 1200 34
所有的六位数 十万位和万位数都在3中 剩下的数参照四位数的构造
所有的七位数 因为W <= 1000000 所以七位数只有一个 在3中存在 
*/

E Tahakashi and Animals

题意： $n$ 条狗，喂每个狗的花费为 $a i$ 喂第 $i$ 条狗的同时也会喂将 $i + 1$ 号狗喂一遍例如喂1号狗花费2 喂2号狗花费10 那么我可以花费2将1,2号狗都喂到。特别的喂 $n$ 号狗的时候也会喂到 $1$ 号狗

状态机：队内大佬教我的，解析在代码注释中

复制代码

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
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
int n,a[N];
ll f[N][2];
/*
状态机模型
f[i][0] 1,0代表喂或不喂i狗
对于i号狗来说 一定要喂i-1狗或者喂自己

f[i][0] 既然自己不喂，说明一定喂了i-1号狗 f[i][0] = f[i-1][1]
f[i][1] 喂自己，不管之前的狗喂或不喂都可以喂自己 取最小值+喂自己的费用  = min(f[i-1][0],f[i-1][1]) + a[i]

特别的因为存在特殊的环 即喂n号狗也会喂到1号狗
那么要对初始分两种情况讨论 
1.一定喂1号狗 n号狗随状态机转移得到 for(2~n)
2.一定喂n号狗 1号狗加入状态机模型 for(1~n-1)
*/
int main()
{
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    
    //因为一定喂1号狗，那么就不存在不喂的情况 f[1][0] = f[1][1]
    f[1][1] = a[1];
    f[1][1] = a[1];
    for(int i=2;i<=n;i++)
    {
        f[i][0] = f[i-1][1];
        f[i][1] = min(f[i-1][0],f[i-1][1]) + a[i];
    }
    ll res1 = min(f[n][0],f[n][1]);

    //将0号视为n号狗 与一定喂1号狗的情况同理
    f[0][1] = a[n];
    f[0][1] = a[n];
    for(int i=1;i<n;i++)
    {
        f[i][0] = f[i-1][1];
        f[i][1] = min(f[i-1][0],f[i-1][1]) + a[i];
    }
    ll res2 = min(f[n-1][0],f[n-1][1]);
    cout << min(res1,res2);
    return 0;
}