2019牛客暑期多校训练营（第六场）

A.Garbage Classification（阅读理解）

•题意

给你一个由小写字母组成的字符串

然后给26个字母所对应的h,d,w，代表垃圾的有害性，干湿性

如果所有有害性的字母的总和>=总字母数的25%则是有害垃圾

如果所有有害性的字母的总和<=总字母数的10%则是可回收垃圾

如果干性字母的总和>=2倍的湿性垃圾字母则是干垃圾

否则是湿垃圾

•思路

吐槽题面，也太难理解了叭...

记录一下每个字母的个数

再根据26个字母的性质判断是h,d还是w

•代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 string s,t;
 4 int num[30];
 5 int main()
 6 {
 7     int tt;
 8     cin>>tt;
 9     for(int k=1;k<=tt;k++)
10     {
11         memset(num,0,sizeof num);
12         int d=0,w=0,h=0;
13         cin>>s>>t;
14         int len=s.length();
15         for(int i=0;i<len;i++)
16             num[s[i]-'a']++;
17         for(int i=0;i<26;i++)
18         {
19             if(t[i]=='h')
20                 h+=num[i];
21             else if(t[i]=='d')
22                 d+=num[i];
23             else if(t[i]=='w')
24                 w+=num[i];
25         }
26 
27         int aa=(len/4+(len%4 == 0 ? 0:1));
28         int bb=len/10;
29         printf("Case #%d: ",k);
30         if(h>=aa)
31             puts("Harmful");
32         else if(h<=bb)
33             puts("Recyclable");
34         else if(d>=2*w)
35             puts("Dry");
36         else
37             puts("Wet");
38     }
39 }

View Code

B.Shorten IPv6 Address（进制转换+模拟）

•题意

给你128位二进制数，为一个IPV6的地址

按照IPV6的规则，化成长度最短的字典序最小的IPV6地址

IPV6规则：

①用十六进制表示地址，并使用冒号':'分隔每四个十六进制数字。每四个数字称为一个字段。

　　例如 0000:0000:0123:4567:89ab: 0000:0000:0000”

②字段中的前导零可以省略

　　上述可化简为0:0:123:4567:89ab:0:0:0:0

③由至少两个字段组成的连续零字段(附近有冒号)可以用双冒号'::'替换。地址中最多只能使用一个双冒号。

　　上述IPv6地址可以缩写为 0:0:123:4567:89ab:: 或 ::123:4567:89ab:0:0:0，但不能 ::123:4567:89ab::

注意！！！

一个0字段不能省略!!!

我在这里卡了好久好久，最后还是鹏哥哥帮我找到的bug

此致，敬礼∠(°ゝ°)

•思路

利用二进制转化为十六进制

二进制数四位一组可以转化成一位十六进制数

转化为十六进制数后处理一下前导0

再找连续0字段的最大长度，然后再选择字典序较小的那个

找最大长度的注意事项：

如果首中尾0字段相同，选择中的0字段，因为会多减少一个冒号“：”

例如 0:0:1:0:0:1:0:0

① : :1:0:0:1:0:0 长度为13

② 0:0:1::1:0:0 长度为12

③ 0:0:1:0:0:1:: 长度为13

其中②的长度最小

找较小字典序的注意事项：

删除比较靠后的那个，但是要同时注意上面的最大长度问题

例如: 1:0:0:1:0:0:1:1

① 1::1:0:0:1:1

② 1:0:0:1::1:1

其中②的字典序比较小

例如： 0:0:0:1:1:0:0:0

①::1:1:0:0:0

②0:0:0:1:1::
②的字典序比较小

总结起来说就是先找0字段长度最大的

当0字段长度相等时

先找中间那个，因为长度最小

没有中间那个就找后边那个，因为字典序较小

•代码

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 char s[200];
  4 char a[40];
  5 int flag=0;
  6 
  7 void trans(char ss[])//二进制转十六进制
  8 {
  9     for(int i=1;i<=8;i++)
 10     {
 11         for(int j=1;j<=4;j++)
 12         {
 13             int num=0;
 14             for(int k=0;k<4;k++)
 15             {
 16                 int cur=(i-1)*16+(j-1)*4+k;
 17                 int x=ss[cur]-'0';
 18                 num=(num<<1)+x;
 19             }
 20             char after='!';
 21             if(num<10)
 22                 after=char('0'+num);
 23             else
 24                 after=char('a'+(num-10));
 25 
 26             flag++;
 27             a[flag]=after;
 28         }
 29     }
 30 }
 31 
 32 
 33 int main()
 34 {
 35 //    freopen("C:/Users/14685/Desktop/stdin&&stdout/contest","r",stdin);
 36     int tt;
 37     cin>>tt;
 38     for(int k=1;k<=tt;k++)
 39     {
 40         flag=0;
 41         scanf("%s",s+1);
 42         trans(s+1);
 43 
 44         for(int i=1;i<=8;i++)//找前导0，并置为 *
 45         {
 46             int one=0;
 47             flag=1;
 48             while(one==0&&flag<=4)
 49             {
 50                 int now=(i-1)*4+flag;
 51                 if(a[now]=='0'&&flag!=4)
 52                 {
 53                     a[now]='*';
 54                     flag++;
 55                     continue;
 56                 }
 57                 one++;
 58                 break;
 59             }
 60         }
 61 
 62         bool vis[10]={0};      //vis[1~8] 代表8个字段,其中0字段为0,非0字段为1
 63         for(int i=1;i<=32;i+=4)
 64         {
 65             if(a[i]=='*'&&a[i+1]=='*'&&a[i+2]=='*'&&a[i+3]=='0')
 66                     vis[(i+3)/4]=true;
 67         }
 68 
 69         int index=1;
 70         int ans=0;
 71         int ansi=0;
 72 
 73         while(index <= 8)//找最大0字段
 74         {
 75             for(;index <= 8 && vis[index] == 0;index++);
 76 
 77             int cnt=0;
 78             int cur=index;
 79             for(;index <= 8 && vis[index];index++,cnt++);
 80 
 81             if(cnt < 2)  //0字段为1个的情况，坑点！
 82                 continue;
 83             if(cnt >= ans) //总结的代码表达
 84             {
 85                 if(cnt==ans&&cur+cnt-1==8&&ansi!=1)//长度相等先找中间
 86                     continue;
 87                 ans=cnt;//最大0字段长度
 88                 ansi=cur;//最大0字段开始位置
 89             }///ansi~ansi+ans-1
 90         }
 91 
 92         printf("Case #%d: ",k);
 93         for(int i=1;i<=32;i++)
 94         {
 95             if(ans >= 2 && i==ansi*4)  //时刻注意0字段长度大于1才能省略
 96                 printf("::");
 97             if(ans >= 2 &&i>=ansi*4&&i<=(ansi+ans-1)*4)
 98                 continue;
 99             if(a[i]!='*')
100                 printf("%c",a[i]);
101             if(i%4==0&&i!=(ansi-1)*4&&i!=32)
102                 printf(":");
103         }
104         printf("
");
105     }
106 }

View Code

D.Move （multiset）

•题意

　　有 n 个物品，第 i 个物品体积为 v_i；

　　有 k 个容积相同箱子装这 n 个物品

　　装箱策略是装尽可能大的

　　即装小于等于剩余体积的最大物品

•思路

我们只能一个一个枚举去试

箱子最小体积是sum/k，也就是不浪费一点空间全部装满

那我们就从这个下界开始，体积逐步增大，

肯定会存在某个体积把物品全都装下

把物体体积放入 multiset中，便于查找小于等于空闲体积的最大物品和删除物品

•代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1005;
 4 int a[maxn];
 5 int n,k;
 6 
 7 bool check(int V)
 8 {
 9     multiset<int> s;
10 
11     for(int i=1;i<=n;i++)
12         s.insert(a[i]);
13 
14     for(int i=1;i<=k;i++)
15     {
16         int cur=V;
17         while(cur&&!s.empty())
18         {
19             auto it=s.upper_bound(cur);
20             if(it==s.begin())
21                 break;
22             it--;
23             cur-= *it;
24             s.erase(it);
25         }
26     }
27     if(s.empty())
28         return true;
29     else
30         return false;
31 }
32 
33 int main()
34 {
35     int t;
36     cin>>t;
37     for(int _t=1;_t<=t;_t++)
38     {
39         cin>>n>>k;
40         int sum=0;
41         for(int i=1;i<=n;i++)
42         {
43             cin>>a[i];
44             sum+=a[i];
45         }
46         for(int i=(sum+k-1)/k;;i++)
47         {
48             if(check(i))
49             {
50                 printf("Case #%d: %d
",_t,i);
51                 break;
52             }
53         }
54     }
55 }

View Code

J.Upgrading Technology（贪心+前缀和）

•题意

　　有 n 种技能，每种技能的最大等级为 m；

　　初始，这 n 种技能的等级全部为 0；

　　定义 C $c_{i, j}$

　　但是，如果 $c_{i, j} < 0$

　　定义 $d_{i}$

　　但是，如果 $d_{i} < 0$

　　每种技能可以升级到 0~m 任意等级，求最终获得的最大能量是多少；

•思路

定义a_i,j为第i种技能前j等级所需要能量的前缀和，

试想如果第j等级需要消耗p能量，而第(j+1)等级会获得q能量

因为我们想尽可能的多获得能量，那我们就把会获得能量的升级和它前面的升级捆绑在一起

即上面从第(j-1)级升到第(j+1)级消耗(q-p)能量，从第(j-1)级升到第j级也是消耗(q-p)能量，因为后面的q能量，不加白不加∠(°ゝ°)

那用代码如何实现呢

可以根据前缀和a_i,j逆序找最大值！Max_i,j代表第i种能量至少到第j等级消耗的能量，实际等级是(j~m)之间，毕竟白送能量，不加血亏

Max_i,j-a_i,j即为白加的能量

白加能量也有一定的限制鸭，每全部到达一个等级j，会得到或消耗一个dj的能量

那我们就从1到m枚举这个等级

在加能量时要注意有白加的能量，也就是实际等级可能比j高

然后每次处理一下，防止等级越过

•代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int maxn=1e3+5;
 5 ll a[maxn][maxn],mx[maxn][maxn];
 6 ll d[maxn];
 7 int main()
 8 {
 9     int t;
10     scanf("%d",&t);
11     for(int Case=1;Case<=t;Case++)
12     {
13         int n,m;
14         scanf("%d%d",&n,&m);
15 
16         ll aij;
17         for(int i=1;i<=n;i++)
18         {
19             for(int j=1;j<=m;j++)
20             {
21                 scanf("%lld",&aij);
22                 a[i][j]=a[i][j-1]-aij;//第i种技能前j等级消耗能量前缀和
23             }
24             mx[i][m]=a[i][m];
25             for(int j=m-1;j>=0;j--)   //逆序找最大的
26                 mx[i][j]=max(mx[i][j+1],a[i][j]);
27         }
28 
29         for(int j=1;j<=m;j++)
30             scanf("%lld",&d[j];)
31 
32         ll dsum=0,ans=0;
33         for(int j=0;j<=m;j++)//枚举每个等级
34         {
35             dsum+=d[j];
36             ll ansj=dsum;
37             for(int i=1;i<=n;i++)//先全部加上能量 注意有白加的能量
38                 ansj+=mx[i][j];
39             for(int i=1;i<=n;i++)//因为有白加的等级，所以要减去白加等级能获得的最小的能量mx[i][j]-a[i][j]
40                 ans=max(ans,ansj-mx[i][j]+a[i][j]);//没有白加的话就是减去0了
41         }
42         printf("Case #%d: %lld
",Case,ans);
43     }
44 }

View Code