2019牛客暑期多校训练营第六场
2019-08-04 / Luo Jinrong   

进度

A B C D E F G H I J
√ √ √

A. Garbage Classification

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;
const int N = 2e3 + 10;
char s[N];
char p[30];
int h, d, w;
char output[4][20] = { "Harmful","Recyclable","Dry","Wet" };
int main() {
    int t;
    scanf("%d", &t);
    int ex = 0;
    while (t--) {
        h = d = w = 0;
        scanf("%s%s", s, p);
        for (int i = 0; s[i]; i++) {
            int le = s[i] - 'a';
            if (p[le] == 'h')h++;
            else if (p[le] == 'd')d++;
            else if (p[le] == 'w')w++;
        }
        int ans = 0;
        int len = strlen(s);
        if (4 * h >= len)ans = 0;
        else if (10 * h <= len)ans = 1;
        else if (d >= 2 * w)ans = 2;
        else ans = 3;
        printf("Case #%d: %s\n", ++ex, output[ans]);
    }
    return 0;
}

B. Shorten IPv6 Address

题意

给一个128位的2进制串，每16位为一块转换为IPV6地址。对于每一块可以去掉前导零，有两块及以上连续的零区域可以省略为::，但只能省略一处，求最短长度的地址串中字典序最小的。

做法

暴力模拟。每16位作为一个串转换为16进制变成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
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
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
#define FIN freopen("./B.in","r",stdin)
using namespace std;
typedef long long ll;
const ll maxn(1e5+5);
ll T,n,a[maxn],flag[10],len,l,r;
char s[130],c[10][5];
int main(){
#ifndef ONLINE_JUDGE
    FIN;
#endif
    cin>>T;
    for(int t=1;t<=T;t++){
        memset(flag,0,sizeof(flag));
        len=l=r=0;
        cin>>s;
        for(int i=0;i<128;i+=4){
            int tmp=(s[i]-'0')*8+(s[i+1]-'0')*4+(s[i+2]-'0')*2+(s[i+3]-'0')*1;
            char t_c;
            if(tmp<10){
                t_c=tmp+'0';
            }else{
                switch(tmp){
                    case 10:
                        t_c='a';
                        break;
                    case 11:
                        t_c='b';
                        break;
                    case 12:
                        t_c='c';
                        break;
                    case 13:
                        t_c='d';
                        break;
                    case 14:
                        t_c='e';
                        break;
                    case 15:
                        t_c='f';
                        break;
                }
            }
            c[i/16][(i%16)/4]=t_c;
        }
        for(int i=0;i<8;i++){
            if(c[i][0]=='0'&&c[i][1]=='0'&&c[i][2]=='0'&&c[i][3]=='0'){
                flag[i]=1;
            }
        }
        int ff=0,nlen=0,nl=0,nr=0;
        for(int i=0;i<=8;i++){
            if(ff&&flag[i]){
                nlen++;
                nr=i;
            }else if(ff&&flag[i]==0){
                ff=0;
                if(nlen>len){
                    len=nlen;
                    l=nl;
                    r=nr;
                }else if(nlen==len){
                    if((nr!=7)||(nr==7&&l==0)){
                        l=nl;
                        r=nr;
                    }
                }
            }else if(ff==0&&flag[i]){
                ff=1;
                nl=i;
                nr=i;
                nlen=1;
            }
        }
        //cout<<len<<" "<<l<<" "<<r<<"\n";
        cout<<"Case #"<<t<<": ";
        for(int i=0;i<8;i++){
            if(len>1&&i==l){
                if(l==0){
                    cout<<"::";
                }else{
                    cout<<":";
                }
                i=r;
                if(i==7){
                    cout<<"\n";
                }
                continue;
            }else{
                if(flag[i]){
                    cout<<"0";
                }else{
                    int f=0;
                    for(int j=0;j<4;j++){
                        if((!f)&&c[i][j]!='0'){
                            f=1;
                            cout<<c[i][j];
                        }else if(f){
                            cout<<c[i][j];
                        }
                    }
                }
            }
            cout<<":\n"[i==7];
        }
//      for(int i=0;i<8;i++){
//          for(int j=0;j<4;j++){
//              cout<<c[i][j];
//          }
//          cout<<":";
//      }
//      cout<<"\n";
    }
}

J. Upgrading Technology

题意

有一个科技树，共$n$种科技，每种科技有$m$个等级，对于第$i$个科技从$j-1$级升到j级需要花费$c_{ij}$，当所有科技都达到j级可获得$d_j$的奖励，问最大收益。

做法

假设所有科技的最低级为k级，即可以领取d_1-d_k所有的奖励。然后遍历所有科技，升到收益最大的那一级，如果所有科技都有一个大于k的正收益的等级，那么选择一个收益最小的让他保留在k级，k从0遍历到m，然后取这里面的最大值。

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
#include<bits/stdc++.h>
#define FIN freopen("./J.in","r",stdin)
using namespace std;
typedef long long ll;
const ll maxn(1e3+5);
ll T,ans,n,m,c[maxn][maxn],d[maxn],pre_c[maxn][maxn],pre_d[maxn],dp[maxn][maxn][12],flag,maxc,now;
void makermq(ll jn,ll n,ll b[])
{
    ll i,j;
    for(i=1;i<=n;i++)
        dp[jn][i][0]=b[i];
    for(j=1;(1<<j)<=n;j++)
        for(i=1;i+(1<<j)-1<=n;i++)
            dp[jn][i][j]=min(dp[jn][i][j-1],dp[jn][i+(1<<(j-1))][j-1]);
}
ll rmq(ll jn,ll s,ll v)
{
    ll k=(ll)(log((v-s+1)*1.0)/log(2.0));
    return min(dp[jn][s][k],dp[jn][v-(1<<k)+1][k]);
}
int main(){
#ifndef ONLINE_JUDGE
    FIN;
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    for(ll t=1;t<=T;t++){
        ans=0;
        cin>>n>>m;
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=m;j++){
                cin>>c[i][j];
                pre_c[i][j]=pre_c[i][j-1]+c[i][j];
            }
            makermq(i,m,pre_c[i]);
        }
        for(ll i=1;i<=m;i++){
            cin>>d[i];
            pre_d[i]=pre_d[i-1]+d[i];
        }//输入
        for(ll i=0;i<m;i++){//枚举最低等级为0-m
            flag=1,maxc=-1e17-5,now=pre_d[i];
            for(ll j=1;j<=n;j++){
                now-=pre_c[j][i];
            }
            for(ll j=1;j<=n;j++){//每个技能遍历
                ll tmp=rmq(j,i+1,m);
                if(tmp-pre_c[j][i]>0&&flag){
                    flag=0;
                }else if(tmp-pre_c[j][i]<0){
                    now-=tmp-pre_c[j][i];
                    maxc=max(maxc,tmp-pre_c[j][i]);
                }
            }
            if(flag){
                now+=maxc;
            }
            ans=max(ans,now);
        }
        now=pre_d[m];
        for(ll i=1;i<=n;i++){
            now-=pre_c[i][m];
        }
        ans=max(ans,now);
        cout<<"Case #"<<t<<": "<<ans<<"\n";
    }
}

return 0;

本文链接：
https://luojinrong.github.io/2019/08/04/2019牛客暑期多校训练营第六场/