# 2019 牛客多校第六场

## Garbage Classification

64bit IO Format: %lld

#### 题目描述

On the CVBB planet, garbage classification has been gradually executed to help save resources and protect the environment. Nowadays people have to be equipped with knowledge of distinguishing different types of garbage. Now, given the waste compositions of a discarded product, you are asked to determine which category it belongs to.
The waste compositions are represented as a string s consisting of only lowercase letters, where each letter represents a waste composition and has an equal proportion. Each waste composition in that product is in one of the three situations, dry, wet or harmful.
The product can be classified by the following rules:

•  In case that at least 25% of its compositions is harmful, it is harmful garbage.
•  In case that at most 10% of its compositions is harmful, it is recyclable garbage.
•  In other cases, if the proportion of dry compositions in it is at least twice that of wet compositions, it is dry garbage, or otherwise, it is wet garbage.

#### 输入描述:

There are multiple test cases. The first line contains an integer T (1≤T≤501 \leq T \leq 501≤T≤50), indicating the number of test cases. Test cases are given in the following.For each test case, the first line contains a non-empty string s (1≤∣s∣≤20001 \le |s| \le 20001≤∣s∣≤2000) consisting of only lowercase letters.The second line contains a string t of length 26, consisting of only characters in {d,w,h}\lbrace d, w, h \rbrace{d,w,h}. The i-th character of t represents the situation of the waste composition denoted by the i-th lowercase letter, where 'd', 'w' and 'h' mean dry, wet or harmful respectively.

#### 输出描述:

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y (y∈{Harmful,Recyclable,Dry,Wet}y \in \lbrace \text{Harmful}, \text{Recyclable}, \text{Dry}, \text{Wet} \rbracey∈{Harmful,Recyclable,Dry,Wet}) denotes the garbage type of the product in this test case.

#### 输入

4
dqxxjefgctjgdbqxphff
hddhddhhhdhdhwwddhhdwwdhhw
iqdvfzzdqsbdevzebego
wdhddwwhwhdhhhwwdwdhwdwhhd
dwddddwdwdwhdwhhdhhwwhhwdh
mcxkwmxxlhbrymwawhio
ddhwhddhwwwdddwdwhwwwhdwdw


#### 输出

Case #1: Harmful
Case #2: Recyclable
Case #3: Dry
Case #4: Wet

#### 签到题

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+10;
char s[2020],c[27];
int ca=0;
void solve(){
scanf("%s",s+1);scanf("%s",c);
int a[4]={0,},n=strlen(s+1);
rep(i,1,n){
if(c[s[i]-'a']=='d') a[1]++;
else if(c[s[i]-'a']=='w') a[2]++;
else if(c[s[i]-'a']=='h') a[3]++;
}
printf("Case #%d: ",++ca);
if(a[3]*4>=n){puts("Harmful");return;}
if(a[3]*10<=n){puts("Recyclable");return;}
if(a[1]>=a[2]*2) puts("Dry");
else puts("Wet");
}
int main(){
int T;cin>>T;
while(T--) solve();
}


## Shorten IPv6 Address

64bit IO Format: %lld

#### 题目描述

You are given an IPv6 address which is a 128-bit binary string. Please determine its shortest representation according to the following rules:

• Express the address in hexadecimal representation and use a colon ‘:’ to split every four hex digits. Every four digits are called a field. For example, ‘0000:0000:0123:4567:89ab:0000:0000:0000’.
• Leading zeros in a field can be omitted. For example, the above IPv6 address can be shortened to ‘0:0:123:4567:89ab:0:0:0’.
• Consecutive zero fields (with colons near them) consisting of at least two fields can be replaced by a double colon ‘::’. Besides, no more than one double colon can be used in an address. For example, the above IPv6 address can be shortened to ‘0:0:123:4567:89ab::’ or ‘::123:4567:89ab:0:0:0’, but not ‘::123:4567:89ab::’.
• If there are multiple shortest forms of the same length, use the lexicographically (regard the shorten IPv6 address as string) smallest one.

If the above rules conflict with rules in the real world, please refer to the rules mentioned in this problem.

#### 输入描述:

There are multiple test cases. The first line contains an integer T (1≤T≤10001 \leq T \leq 10001≤T≤1000), indicating the number of test cases. Test cases are given in the following.Each test case consists of only one line, containing a 128-bit binary string.

#### 输出描述:

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.

#### 输入

3
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000010010001101000101011001111000100110101011000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000010010001100000000000000000000000000000000000000000000000001000101011001111000100110101011

#### 输出

Case #1: ::
Case #2: 0:0:123:4567:89ab::
Case #3: 0:0:123::4567:89ab

#### 签到题，注意删除中间的0和末尾的0对答案长度的影响不一样

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+10;
int ca=0;
char s[220];
void solve(){
scanf("%s",s+1);
printf("Case #%d: ",++ca);
int a[10][5]={0,},pos=0,f[10]={0,};
rep(i,1,8) rep(j,1,4) rep(k,1,4){
a[i][j]+=(s[++pos]-'0')*(int)pow(2,4-k);
}
rep(i,1,8){
int fl=1;
rep(j,1,4){
if(a[i][j]==0&&fl&&j<4) continue;
else{
if(a[i][j]==0&&fl&&j==4) f[i]=1;
fl=0;
}
}
}
int num=0,p=1,tmp=0,ind=0;
rep(i,1,8){
if(f[i]){
if(p==i-1) tmp++;
else tmp=1;
p=i;
if(tmp>=num&&tmp>=2){
num=tmp;
if(ind==0) ind=i-num+1;
else if(ind==1) ind=i-num+1;
else if(i!=8) ind=i-num+1;
}
}
}
int flag=1;
if(ind){
if(ind==1) printf(":");
rep(i,1,8){
int fl=1;
rep(j,1,4){
if(a[i][j]==0&&fl&&j<4) continue;
if(i>=ind&&i<=ind+num-1) continue;
else{
fl=0;
if(a[i][j]<10) printf("%d",a[i][j]);
else printf("%c",'a'+a[i][j]-10);
}
}
if(i>=ind&&i<=ind+num-1){
if(flag) printf(":"),flag=0;
}
else if(i<8) printf(":");
}

}
else{
rep(i,1,8){
int fl=1;
rep(j,1,4){
if(a[i][j]==0&&fl&&j<4) continue;
else{
fl=0;
if(a[i][j]<10) printf("%d",a[i][j]);
else printf("%c",'a'+a[i][j]-10);
}
}
if(i<8) printf(":");
}
}
puts("");
}
int main(){
int T;cin>>T;
while(T--) solve();
}


## Move

64bit IO Format: %lld

#### 题目描述

After the struggle of graduating from college, TangTang is about to move from a student apartment to his new home.

TangTang has n items to move, the i-th of which is of volume viv_ivi​. He can pack all these items into at most K boxes of the same volume.

TangTang is so clever that he uses the following strategies for packing items:
– Each time, he would put items into a box by the next strategy, and then he would try to fill another box. – For each box, he would put an unpacked item of the largest suitable volume into the box repeatedly until there is no such item that can be fitted in the box.
Now, the question is what is the minimum volume of these boxes required to pack all items.

#### 输入描述:

There are multiple test cases. The first line contains an integer T (1≤T≤201 \leq T \leq 201≤T≤20), indicating the number of test cases. Test cases are given in the following.For each test case, the first line contains two integers n, K (1≤n,K≤10001 \leq n, K \leq 10001≤n,K≤1000), representing the number of items and the number of boxes respectively.The second line contains n integers v1v_1v1​, v2v_2v2​, …\ldots…, vnv_nvn​ (1≤v1,v2,…,vn≤10001 \leq v_1, v_2, \ldots, v_n \leq 10001≤v1​,v2​,…,vn​≤1000), where the i-th integer viv_ivi​ represents the volume of the i-th item.

#### 输出描述:

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.

#### 输入

1
5 3
1 2 3 4 5


#### 输出

Case #1: 5

#### 暴力枚举答案判断，注意没有二分性比如：1539 39 39 39 39 60 60 60 60 60 100 100 100 100 100199 为一个合法的答案，但 200 不是，201 也不是。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
#define pii pair<int,int>
typedef long long ll;
int casd,l,r,mid,cas,z,x,n,m,w,h,a[1010],b[1010];
bool cmp(int yi,int er){
return yi>er;
}
bool kk(int u){
for (int i=1;i<=x;i++)
b[i]=u;
for (int i=1;i<=z;i++){
n=0;
for (int j=1;j<=x;j++)
if (b[j]>=a[i]) {n=j;break;}
if (!n) return 0;
b[n]-=a[i];
}
return 1;
}
int main(){
casd=0;
scanf("%d",&cas);
while (cas--){
printf("Case #%d: ",++casd);
scanf("%d%d",&z,&x);
int sum=0;
for (int i=1;i<=z;i++) scanf("%d",&a[i]),sum=max(sum,a[i]);
int low=sum;
sort(a+1,a+z+1,cmp);
l=low;r=10000000;int ans=1;
rep(i,1,log(z)){
while (l<=r){
mid=l+(r-l)/2;
if (kk(mid)) ans=mid,r=mid-1; else l=mid+1;
}
l=low;r=ans;
}
printf("%d\n",ans);
}
return 0;
}


## Androgynos

Special Judge, 64bit IO Format: %lld

#### 题目描述

In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H. The complement of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G.

Give a positive integer n, check whether there exists a simple undirected graph G having n vertices, which is isomorphic to its complement graph H. If the graphs G and H exist, report them with any possible isomorphism.

#### 输入描述:

There are multiple test cases. The first line contains an integer T (1≤T≤51 \leq T \leq 51≤T≤5), indicating the number of test cases. Test cases are given in the following.Each test case consists of only one line, containing an integer n (1≤n≤20001 \leq n \leq 20001≤n≤2000).

#### 输出描述:

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y (y∈{Yes,No}y \in \lbrace \text{Yes}, \text{No} \rbracey∈{Yes,No}) denotes whether or not the graphs exist in this test case.If the graphs exist, then output (n + 1) extra lines.The first n lines represent the graph G, where each line contains a binary string of length n. In the i-th line, the j-th character Gi,jG_{i, j}Gi,j​ is '1' when the i-th vertex and the j-th one are adjacent, or otherwise, in case they are not adjacent, Gi,jG_{i, j}Gi,j​ is '0'. Note that Gi,iG_{i, i}Gi,i​ must be '0' and Gi,jG_{i, j}Gi,j​ must be the same as Gj,iG_{j, i}Gj,i​.The last line contains n space-separated integers f1f_1f1​, f2f_2f2​, …\ldots…, fnf_nfn​, representing an isomorphism of graphs G and H in which the i-th vertex in the graph G is mapped to the fif_ifi​-th vertex in the complement graph H. Note that every two consecutive integers in one line should be separated by a single space, please do not add any tailing space in your output\text{please do not add any tailing space in your output}please do not add any tailing space in your output.

#### 输入

4
1
2
3
4

#### 输出

Case #1: Yes
0
1
Case #2: No
Case #3: No
Case #4: Yes
0100
1010
0101
0010
2 4 1 3

#### 首先两个图同构有个必要条件是边数要相同，也就是说n阶完全图的边数得是偶数若 n = 4k：先考虑一个更简单的情况，n=4，相信大家都会手构（如果你不会，还可以枚举映射关系跑个2sat）；观察n=4的情况，容易发现，可以将顶点分为两组，使得i和fi都来自不同组；容易想到：原图中的团在补图中会变成独立集。对于n=4k(>1)的情况，可以先把顶点分成4块，2块内部连成团，2块内部不连组成独立集，然后按n=4的情况连块之间的边即可若n = 4k + 1：多出的一个点向所有团连边即可若n = 4k + 2 或 4k + 3：无解

#include <bits/stdc++.h>
using namespace std;
int s[2050][2050];
int main(){
int T;
scanf("%d",&T);
int ca=0;
while(T--){
ca++;
int n;
scanf("%d",&n);
printf("Case #%d: ",ca);
if(n==1){
printf("Yes\n0\n1\n");
}
else if(n%4>1){
printf("No\n");
}
else{
int k=n/4;
printf("Yes\n");
memset(s,0,sizeof(s));
for(int i=0;i<k;i++){
for(int j=0;j<k;j++){
for(int l=0;l<=2;l++) s[i*4+l][j*4+l+1]=s[j*4+l+1][i*4+l]=1;
if(i==j) continue;
s[i*4][j*4]=s[i*4+3][j*4+3]=1;
}
}
if(n%4==1){
for(int i=0;i<k;i++) s[n-1][i*4]=s[n-1][i*4+3]=s[i*4+3][n-1]=s[i*4][n-1]=1;
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
printf("%d",s[i][j]);
}
printf("\n");
}
for(int i=0;i<k;i++){
if(i!=0) printf(" ");
printf("%d %d %d %d",i*4+2,i*4+4,i*4+1,i*4+3);
}
if(n%4==1) printf(" %d",n);
printf("\n");
}
}
return 0;
}


## Is Today Friday?

64bit IO Format: %lld

#### 题目描述

No, it’s not Friday 🙁

TangTang loves Friday and he has made up a list of n days which are all Friday! Each date in this list is formed as “yyyy/mm/dd”, where “yyyy” is a four-digit number representing the year, “mm” is a two-digit number representing the month and “dd” is a two-digit number representing the day. TangTang only considers years between 1600 and 9999 (inclusive), so each year in the list always has four digits, but the months and the days may have leading zeros when it’s necessary. For example, “August 3rd, 2019” should be formed as “2019/08/03”.

To store safely, TangTang ciphered the list using a simple substitution cipher. He substituted each digit by a letter between ‘A’ and ‘J’ such that the same digits correspond to the same letter and different digits to different letters.

Unfortunately, TangTang forgot which letter corresponds to which digit. Please help him restore the original list.

#### 输入描述:

There are multiple test cases. The first line contains an integer T (1≤T≤101 \leq T \leq 101≤T≤10), indicating the number of test cases. Test cases are given in the following.For each test case, the first line contains an integer n (1≤n≤1000001 \leq n \leq 1000001≤n≤100000), indicating the number of dates.Each of the next n lines contains a string in the form of "yyyy/mm/dd", representing a ciphered date, where each digit is substituted by an uppercase letter between 'A' and 'J'.

#### 输出描述:

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.If there is no way to restore the list, then y is "Impossible".Otherwise, y is a string consisting of ten distinct digits, representing the key to decipher the list. More specifically, the i-th digit in y corresponds to the i-th uppercase letter.If there are at least two ways, then y is the smallest possible string in the lexicographical order.

#### 输入

2
1
CABJ/AI/AC
5
CABJ/AI/AC
CABJ/AI/AE
CABJ/AI/AF
CABJ/AI/AG


#### 输出

Case #1: 0123456789
Case #2: Impossible

#### 蔡勒公式对于任何一个加密后的日期，只有几万个排列能将其映射到合法日期。只对前若干个日期求出所有合法的排列后，再依次检查是否对所有日期合法。坑点：有重复的日期，需要去重。

#include <bits/stdc++.h>
using namespace std;
char s[3630000][11],tmp[11];
int cnt=1,mk[10];
int lim[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
void init(int pos){
if(pos==10){
for(int i=0;i<pos;i++) s[cnt][i]=tmp[i];
cnt++;
return;
}
for(int i=0;i<10;i++){
if(!mk[i]){
mk[i]=1;
tmp[pos]='0'+i;
init(pos+1);
mk[i]=0;
}
}
return;
}
int judge(int pt,string& ss){
int y=0;
for(int i=0;i<=3;i++){
y*=10;
y+=s[pt][ss[i]-'A']-'0';
}
int mo=0;
for(int i=5;i<=6;i++){
mo*=10;
mo+=s[pt][ss[i]-'A']-'0';
}
int d=0;
for(int i=8;i<=9;i++){
d*=10;
d+=s[pt][ss[i]-'A']-'0';
}
if((y%4==0 && y%100!=0)|| y%400==0) lim[2]=29;
else lim[2]=28;
if(y<1600 || mo<=0 || mo>12 || d<=0 || d>lim[mo]) return 0;
if(mo<=2){
mo+=12;
y--;
}
int w=(d+2*mo+3*(mo+1)/5+y+y/4-y/100+y/400+1)%7;
return w==5;
}
int ju[3630000];
string q[100100];
int main(){
init(0);
int T;
int ca=0;
scanf("%d",&T);
while(T--){
ca++;
int n;
scanf("%d",&n);
memset(ju,0,sizeof(ju));int num=cnt;
for(int i=1;i<=n;i++) cin>>q[i];
sort(q+1,q+1+n);
n=unique(q+1,q+1+n)-q-1;
for(int i=1;i<=min(n,10);i++){
for(int j=1;j<cnt;j++){
if(ju[j]==1) continue;
if(judge(j,q[i])==0){
ju[j]=1;
num--;
}
}
}
vector<int> v,vv;
for(int i=1;i<cnt;i++){
if(ju[i]==0){
v.push_back(i);
vv.push_back(1);
}
}
int ccnt=(int)v.size();
for(int i=11;i<=n;i++){
for(int j=0;j<(int)v.size();j++){
if(vv[j]){
int fg = judge(v[j],q[i]);
if(!fg) vv[j]=0,ccnt--;
}
}
}
printf("Case #%d: ",ca);
if(ccnt==0){
printf("Impossible\n");
}
else{
for(int i=0;i<(int)v.size();i++){
if(vv[i]){
for(int j=0;j<10;j++){
printf("%c",s[v[i]][j]);
}
printf("\n");
break;
}
}
}
}
return 0;
}


64bit IO Format: %lld

#### 题目描述

Rowlet is playing a very popular game in the pokemon world. Recently, he has encountered a problem and wants to ask for your help.

In this game, there is a technology tree system. There are n kinds of technology in this game, each of them has m levels numbered from 1 to m. In the beginning, all technologies have no level (regard as level 0). When the i-th technology is at the (j – 1)-th level, the player can pay cijc_{i j}cij​ pokedollars (currency used in this game) to upgrade this technology into the j-th level. However, sometimes upgrading is so easy that the cost might be negative, which implies the player may gain profit from upgrading technologies.

Moreover, if all technologies have been upgraded to level j, the player will gain an additional profit of djd_{j}dj​ pokedollars. However, sometimes too many technologies of the same level might be confusing, hence the profit can be negative as well.

Rowlet wants to determine the optimal strategy that can bring him the most pokedollars. Help him to find the maximum gain. Note that Rowlet may upgrade nothing, and in that case, the profit is zero.

#### 输入描述:

There are multiple test cases. The first line contains an integer T (1≤T≤101 \leq T \leq 101≤T≤10), indicating the number of test cases. Test cases are given in the following.For each test case, the first line contains two integers n, m (1≤n,m≤10001 \leq n, m \leq 10001≤n,m≤1000), representing the number of technologies and the number of levels respectively.The i-th of the next n lines contains m integers, where the j-th number is cijc_{i j}cij​ (−109≤cij≤109-10^{9} \leq c_{i j} \leq 10^{9}−109≤cij​≤109).The last line contains m integers, where the j-th number is djd_{j}dj​ (−109≤dj≤109-10^{9} \leq d_{j} \leq 10^{9}−109≤dj​≤109).We ensure that the sum of n⋅mn \cdot mn⋅m in all test cases is at most 2×1062 \times 10^{6}2×106.

#### 输出描述:

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer(in pokedollars) to this test case.

#### 输入

2
2 2
1 2
2 -1
4 1
3 3
1 2 3
1 2 3
1 2 3
6 7 8


#### 输出

Case #1: 2
Case #2: 4


#### 说明

In the first example, Rowlet can upgrade the first technology to level 1 and the second technology to level 2, which costs 1 + 2 - 1 = 2 pokedollars, but Rowlet can get 4 pokedollars as the bonus of upgrading all technologies to level 1, so the answer is 4 - 2 = 2 pokedollars. In the second example, Rowlet can upgrade all technologies to level 2, which costs 1×3+2×3=91\times3 + 2\times3=91×3+2×3=9 pokedollars, but Rowlet can get 6 pokedollars as the bonus of upgrading all technologies to level 1 and 7 pokedollars as the bonus of upgrading all technologies to level 2, so the answer is 6 + 7 - 9 = 4 pokedollars.

#### 当然你也可以dp设 dp[i][j]表示前 i 种科技最小 levl 为 j 时，最小的 cost转移方程为 dp[i+1][j=min(dp[i]k+pre[i+1][u)，其中 k≥j，u≥j,且它们中至少有一个为j

#include <bits/stdc++.h>
using namespace std;
int n,m;
typedef long long ll;
ll pre[1050][1050],a[1050][1050];
ll d[1050],pd[1050];
ll ppt[1050][1050];
void init(){
for(int i=1;i<=n;i++){
ppt[i][m]=m;
for(int j=m-1;j>=0;j--){
if(pre[i][j]<pre[i][ppt[i][j+1]]){
ppt[i][j]=j;
}
else{
ppt[i][j]=ppt[i][j+1];
}
}
}
return;
}
int main(){
int T;
scanf("%d",&T);
int ca=0;
while(T--){
ca++;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
pre[i][0]=0;
for(int j=1;j<=m;j++){
scanf("%lld",&a[i][j]);
pre[i][j]=pre[i][j-1]+a[i][j];
}
}
for(int i=1;i<=m;i++){
scanf("%lld",&d[i]);
pd[i]=pd[i-1]+d[i];
}
ll ans=0;
init();
for(int i=0;i<=m;i++){
ll cnt=-pd[i];
int fg=0;
ll ma=-10000000000000000;
for(int j=1;j<=n;j++){
int pt=ppt[j][i];
if(pt==i) fg=1;
cnt+=pre[j][pt];
ma=max(ma,pre[j][pt]-pre[j][i]);
}
if(!fg) cnt-=ma;
ans=min(ans,cnt);
}
printf("Case #%d: %lld\n",ca,-ans);
}
return 0;
}