夜深人静写题解--牛客第六场

A  Garbage Classification

  模拟题

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

View Code

B Shorten IPv6 Address

  大模拟题

  1 #include <iostream>
  2 #include <string.h>
  3 #include <stdio.h>
  4 #include <string>
  5 #include <stack>
  6 #include <queue>
  7 #include <algorithm>
  8 #include <math.h>
  9 #include <vector>
 10 #include <set>
 11 #define ll long long
 12 using namespace std;
 13 const int maxn = 1e6+7;
 14 ll mod   = 1e9+7;
 15 char a[130];
 16 int num[40];
 17 char b[17][10]={"0000","0001","0010","0011","0100","0101","0110","0111","1000","1001","1010","1011","1100","1101","1110","1111"};
 18 int judge(int local){
 19     int flag=1;
 20     for(int j=0;j<16;j++){
 21         flag=1;
 22         for(int i=local,k=0;k<4;k++,i++){
 23             if(b[j][k]!=a[i]){
 24                 flag=0;
 25                 break;
 26             }
 27         }
 28         if(flag) return j;
 29     }
 30     return 0;
 31 }
 32
 33 int judgez(int local){
 34     for(int i=local;i<local+4;i++){
 35         if(num[i]!=0)
 36             return 0;
 37     }
 38     return 1;
 39 }
 40
 41 int main()
 42 {
 43     int t;
 44     cin>>t;
 45     for(int cas=1;cas<=t;cas++){
 46         scanf("%s",a);
 47         int cnt=0;
 48         for(int i=0;i<128;i+=4){
 49             num[cnt++]=judge(i);
 50         }
 51         int maxx=2,tmp=0;
 52         int x=-1,y=-1;
 53         for(int i=0;i<32;i+=4){
 54             if(judgez(i)==1){
 55                 tmp++;
 56             }
 57             if(judgez(i)==0){
 58                 //printf("%d %d %d\n",i,tmp,maxx);
 59                 if(tmp>=maxx){
 60                     maxx=tmp;
 61                     y=i;
 62                     x=y-tmp*4;
 63                     y--;
 64                 }
 65                 tmp=0;
 66             }
 67             if(i==28&&tmp>=maxx){
 68                 maxx=tmp;
 69                 y=i+4;
 70                 x=y-tmp*4;
 71                 y--;
 72                 tmp=0;
 73             }
 74         }
 75         vector<pair<int,int> >front;
 76         vector<pair<int,int> >zhong;
 77         vector<pair<int,int> >back;
 78         tmp=0;
 79         for(int i=0;i<32;i+=4){
 80             if(judgez(i)==1){
 81                 tmp++;
 82             }
 83             if(judgez(i)==0){
 84                 //printf("%d %d %d\n",i,tmp,maxx);
 85                 if(tmp>=maxx){
 86                     y=i;
 87                     x=y-tmp*4;
 88                     y--;
 89                     //printf("maxx=%d\n",maxx);
 90                     if(x!=0&&y!=31)
 91                         zhong.push_back(make_pair(x,y));
 92                     if(x==0)
 93                         front.push_back(make_pair(x,y));
 94                     if(y==31)
 95                         back.push_back(make_pair(x,y));
 96                 }
 97                 tmp=0;
 98             }
 99             if(i==28&&tmp>=maxx){
100                 y=i+4;
101                 x=y-tmp*4;
102                 y--;
103                 //printf("maxx=%d\n",maxx);
104                 if(x==0)
105                     front.push_back(make_pair(x,y));
106                 if(x!=0&&y!=31)
107                     zhong.push_back(make_pair(x,y));
108                 if(y==31)
109                     back.push_back(make_pair(x,y));
110                 tmp=0;
111             }
112         }
113 //        printf("%d %d\n",x,y);
114         x=-1,y=-1;
115 //        /printf("%d %d %d\n",front.size(),zhong.size(),back.size());
116         if(zhong.size()!=0){
117             for(int i=0;i<zhong.size();i++){
118                 x=zhong[i].first;
119                 y=zhong[i].second;
120             }
121         }
122         else if(back.size()!=0){
123             x=back[0].first;
124             y=back[0].second;
125         }
126         else if(front.size()!=0){
127             x=front[0].first;
128             y=front[0].second;
129         }
130 //        printf("%d %d\n",x,y);
131         printf("Case #%d: ",cas);
132         cnt=0;
133 //        for(int i=0;i<32;i++) {
134 //            printf("%d",num[i]);
135 //            if(i%4==3)
136 //                printf(":");
137 //        }
138 //        printf("\n");
139         for(int i=0;i<32;i+=4){
140             if(i==x){
141                 printf("::");
142                 i=y-3;
143                 continue;
144             }
145             if(judgez(i)){
146                 printf("0");
147             }
148             else{
149                 int flag=0;
150                 for(int j=i;j<i+4;j++){
151                     if(num[j]) flag=1;
152                     if(flag==1) {
153                         if(num[j]>=10) printf("%c",'a'+num[j]-10);
154                         else printf("%d",num[j]);
155                     }
156                 }
157             }
158             //printf("   %d  &&\n",i);
159             if(i!=28&&i+4!=x)
160                 printf(":");
161         }
162         printf("\n");
163     }
164 }

View Code

D Move

  假二分题qaq

  题意：总共有n个物品需要装进k个箱子里，放箱子的策略为放尽可能能放进去的，也就是每次取最合适的放进去，直至放不了，问箱子的最少容量是多少

  思路：由于不满足单调性，所以无法直接对箱子容积进行二分答案check，那么就对于上下界进行讨论，对于每个箱子最小容量至少为sum/k，最大体积为sum/k+max(v) ，暴力check，总复杂度为O(maxv*n*log(n));

  思路正确性：最小容量显然满足，最大容量，考虑到当前如果每个箱子都无法装入某个物品，那么对于对于每个箱子实际最大使用空间即为v-v1+1,v1为物品体积，v为箱子体积，则可以建立不等式

k*(v-v1+1)<sum,即v<sum/k+v1-1，限制该不等式主要为v1，将其设为最大值，则一定可以求得答案。

  代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+7;
 4 int a[maxn];
 5 multiset<int >mm;
 6 int main()
 7 {
 8     int t;
 9     scanf("%d",&t);
10     int temp=0;
11     while(t--)
12     {
13         int n,m;
14         temp++;
15         scanf("%d%d",&n,&m);
16         int sum=0;
17         int mxx=0;
18         for(int i=1; i<=n; i++)
19         {
20             scanf("%d",&a[i]);
21             mxx=max(a[i],mxx);
22             sum+=a[i];
23         }
24         int l,r;
25         r=0;
26         mm.clear();
27         for(int i=0;i<=mxx;i++){
28             mm.clear();
29             int mid=i+sum/m;
30             //printf("%d %d %d\n ",l,r,mid);
31             for(int i=1; i<=n; i++)
32             {
33                 mm.insert(a[i]);
34             }
35             int s=mid;
36             int jishu=0;
37             while(mm.size()>0)
38             {
39                // printf("%d\n",mm.size());
40                 auto ss=mm.upper_bound(s);
41                 if(ss==mm.begin())
42                 {
43                     s=mid;
44                     jishu++;
45                     continue;
46                 }
47                 ss--;
48                     s-=(*ss);
49                     mm.erase(ss);
50             }
51             if(s!=mid)
52             {
53                 jishu++;
54             }
55             //printf("%d\n",jishu);
56             if(jishu<=m)
57             {
58                 l=mid;
59                 break;
60             }
61         }
62         printf("Case #%d: %d\n",temp,l);
63     }
64 }

View Code 

J Upgrading Technology

  属实自闭，赛后发现有个地方值初始化没写好qaq，交了25发。。

  题意：有n个人，可以升到m级，升级花费不同的价值，当所有人达到某一级时会获得该等级的收入，花费有可能为负

  思路：对于每个等级进行暴力枚举，预处理1-m区间的前缀花费，对预处理结果建立线段树，保存最小值，log（m）查询区间最小值，当前等级一定会取到，主要是枚举后面是否能够使当前花费最小，每个每个人花费最小得到的值，假如当前枚举到i等级，则求处i+1-m的最小值，与当前的值比较，若比当前值小则加入选择的集合，注意的点是如果当前所有人的最小值都在后面，这样就会直接导致等级被迫提升，所以我们要去掉一个值，以保证可以不得到后面的奖励，去掉对当前答案影响最小的值，也就是min(sum)-sum[i]的最大值

  代码：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int inf=1e17+7;
  4 long long int  a[1500][1500];
  5 long long int sum[1500][1500];
  6 long long int d[1500];
  7
  8 typedef struct node
  9 {
 10     int l,r;
 11     long long int minn;
 12 } Node;
 13 const int maxn = 1e3+7;
 14 Node tree[maxn][maxn<<2];
 15 void push_up(int i,int rt)
 16 {
 17     tree[i][rt].minn=min(tree[i][rt<<1].minn,tree[i][rt<<1|1].minn);
 18 }
 19 void build(int i,int rt,int l,int r)
 20 {
 21     tree[i][rt].l=l,tree[i][rt].r=r;
 22     if(l==r)
 23     {
 24         tree[i][rt].minn=sum[i][l];
 25         return ;
 26     }
 27     int mid = (l+r)/2;
 28     build(i,rt<<1,l,mid);
 29     build(i,rt<<1|1,mid+1,r);
 30     push_up(i,rt);
 31 }
 32 long long int query(int i,int rt,int l,int r)
 33 {
 34     if(r<l)return 1e15+7;
 35     //printf("%d %d\n",l,r);
 36     if(tree[i][rt].l>r||tree[i][rt].r<l)
 37     {
 38         return inf;
 39     }
 40     if(tree[i][rt].l>=l&&tree[i][rt].r<=r)
 41     {
 42         return tree[i][rt].minn;
 43     }
 44     int mid = (tree[i][rt].l+tree[i][rt].r)/2;
 45     long long int ans =1e17+7;;
 46     if(mid>=r)
 47     {
 48         ans=query(i,rt<<1,l,r);
 49     }
 50     else if(mid<l)
 51     {
 52         ans=query(i,rt<<1|1,l,r);
 53     }
 54     else
 55     {
 56         ans=min(query(i,rt<<1,l,mid),query(i,rt<<1|1,mid+1,r));
 57     }
 58     return ans;
 59 }
 60 int main()
 61 {
 62     int t;
 63     scanf("%d",&t);
 64     int temp=1;
 65     while(t--)
 66     {
 67         int n,m;
 68         scanf("%d%d",&n,&m);
 69         for(int i=1; i<=n; i++)
 70             for(int j=1; j<=m; j++)
 71                 scanf("%lld",&a[i][j]);
 72         for(int i=1; i<=m; i++)
 73         {
 74             scanf("%lld",&d[i]);
 75         }
 76         for(int i=1; i<=n; i++)
 77         {
 78             sum[i][0]=0;
 79             for(int j=1; j<=m; j++)
 80             {
 81                 sum[i][j]=sum[i][j-1]+a[i][j];
 82             }
 83         }
 84
 85         for(int i=1; i<=n; i++)
 86             build(i,1,1,m);
 87
 88         long long int ans=0;
 89         long long int qq=0;
 90         d[0]=0;
 91         for(int i=0; i<=m; i++)
 92         {
 93             qq+=d[i];
 94             long long int jishu=0;
 95             long long int se=0;
 96             int fi=0;
 97             int st=0;
 98             for(int j=1; j<=n; j++)
 99             {
100                 long long int mm=query(j,1,i+1,m);
101                 jishu+=min(mm,sum[j][i]);
102                 if(mm==1e15+7||mm>=sum[j][i])
103                 {
104                     fi=1;
105                 }
106                 else
107                 {
108                     if(st==0)
109                         se=mm-sum[j][i];
110                     else
111                     se=max(se,mm-sum[j][i]);
112                     st++;
113                 }
114                 //printf("+++   %lld %lld\n",mm,se);
115             }
116             if(fi==1)
117             {
118                 se=0;
119             }
120             ans=max(ans,qq-(jishu-se));
121             //printf("****%lld %lld\n",ans,jishu);
122         }
123         printf("Case #%d: %lld\n",temp++,ans);
124     }
125 }

View Code