AtCoder Beginner Contest 160 题解（F待填坑）

A Coffee

题意：给你一个字符串，判断第3、4个字符是否相同，第5、6个字符是否相同。
模拟水题。直接判断就好。

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;
signed main()
{
    string a;
    cin>>a;
    if(a[2]==a[3]&&a[4]==a[5])cout<<"Yes";
    else cout<<"No";
    return 0;
}

B Golden Coins

题意：有数目X的money，500日元是1000快乐值，5日元是5快乐值，5日元可以通过和其他纸币组合达到500从而增加快乐值。问最大能获得多少快乐值。
显然500比5要优，贪心一下能取500就取500，否则就取5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 110
signed main()
{
    ll x;
    cin>>x;
    ll ans=0;
    ans+=(x/500)*1000;
    x%=500;
    ans+=(x/5)*5;
    cout<<ans;
    return 0;
}

C Traveling Salesman around Lake

题意：一个周长为k的圆，上面有n座房子，输出从一座房子出发走遍所有房子的最短路程。
直接找相邻的两个房子中距离最大的一对就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 200005
int a[maxn];
signed main()
{
    int k,n;
    cin>>k>>n;
    for (int i = 1; i <=n ; ++i) {
        cin>>a[i];
    }
    int tmp=k-a[n]+a[1];
    for (int j = 2; j <=n ; ++j) {
        tmp=max(tmp,a[j]-a[j-1]);
    }
    cout<<k-tmp;
    return 0;
}

D Line++

题意：每个点都和编号比他大一的点连边，同时给定一对不相邻的点连边，问距离为1~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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 2005
int d[maxn][maxn],ans[maxn],a[maxn][maxn];
signed main()
{
    int n,x,y;
    cin>>n>>x>>y;
    for (int i = 1; i <n ; ++i) {
        for (int j = i+1; j <=n ; ++j) {
            d[j][i]=d[i][j]=j-i;
        }
    }
    for (int k = 1; k <=n ; ++k) {
        for (int i = 1; i <=n ; ++i) {
            d[k][i]=min(d[k][x]+d[y][i]+1,d[k][i]);
        }
    }
    for (int i = 1; i <n ; ++i) {
        for (int j = i+1; j <=n ; ++j) {
            ans[d[i][j]]++;
        }
    }
    for (int l = 1; l <n ; ++l) {
        cout<<ans[l]<<endl;
    }
    return 0;
}

E Red and Green Apples

题意：有a个红苹果，b个绿苹果，c个无色苹果，每个无色苹果可以被涂成绿色或者红色，问在合理涂色的情况下取x个红苹果和y个绿苹果的最大权值。
先把三种苹果权值排个序，取红苹果权值前x个，绿苹果权值前y个，然后先取权值最大的无色苹果，整个双指针分别指向红苹果第x个，绿苹果第y个，如果当前无色苹果比指向的两个苹果中权值最小的一个要大，那就换成无色苹果，相应的移动有色苹果和无色苹果的指针即可。
（一开始没初始化极大值乱waQAQ

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100005
#define int long long
ll p[maxn],q[maxn],r[maxn];
int x,y,c,a,b;
#pragma GCC optimize(2)
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>x>>y>>a>>b>>c;
    for (int k = 1; k <maxn ; ++k) {
        p[k]=q[k]=r[k]=20000000000;
    }
    for (int i = 1; i <=a ; ++i) {
        cin>>p[i];
    }
    for (int i = 1; i <=b ; ++i) {
        cin>>q[i];
    }
    for (int i = 1; i <=c ; ++i) {
        cin>>r[i];
    }
    sort(p+1,p+1+a);
    sort(q+1,q+1+b);
    sort(r+1,r+1+c);
    ll ans=0;
    int cnt=0;
    for (int j = a; j >=1 ; --j) {
        ans+=p[j];
        cnt++;
        if(cnt==x)break;
    }
    cnt=0;
    for (int j = b; j >=1 ; --j) {
        ans+=q[j];
        cnt++;
        if(cnt==y)break;
    }
    int l=a-x+1,rs=b-y+1;
    int pos=c;
    while(pos>=1){
        if(l>a&&rs>b)break;
        if(r[pos]<=q[rs]&&r[pos]<=p[l])break;
        if(q[rs]<=p[l]&&r[pos]>q[rs]){
            ans-=q[rs];
            rs++;
            ans+=r[pos];
            pos--;
        }else{
            if(r[pos]>p[l]){
                ans-=p[l];
                l++;
                ans+=r[pos];
                pos--;}
        }
    }
    cout<<ans;
    return 0;
}

F Distributing Integers

换根dp，先溜先溜，数分写不完了QAQ