2019牛客多校第6场

比赛总结

@lfw 不要总是比赛吹水，想好了就赶快写，不然导致后面还有会写的题没时间写

这场暴力出奇迹，G题n!*len完全不虚

题解

比赛链接：https://ac.nowcoder.com/acm/contest/886#question

A Garbage Classification

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int val[30];
 4 char ty[30];
 5 char s[2005];
 6 int main()
 7 {
 8     int t;
 9     scanf("%d",&t);
10     for(int kace=1;kace<=t;kace++)
11     {
12         scanf("%s",s);
13         scanf("%s",ty);
14         int len=strlen(s);
15         int cntd=0,cntw=0,cnth=0;
16         for(int i=0;i<len;i++)
17         {
18             char c=ty[s[i]-'a'];
19             if(c=='d') cntd++;
20             if(c=='w') cntw++;
21             if(c=='h') cnth++;
22         }
23         printf("Case #%d: ",kace);
24         if(cnth*4>=len) puts("Harmful");
25         else if(cnth*10<=len) puts("Recyclable");
26         else if(cntd>=cntw*2) puts("Dry");
27         else puts("Wet");
28     }
29 }
View Code

B Shorten IPv6 Address

模拟题

  1 #include<bits/stdc++.h>
  2 #define maxl 1010
  3 using namespace std;
  4 
  5 int len,cas,anslen,tmplen;
  6 int slen[10],mi[5];
  7 char s[10][10],c[17];
  8 char ch[maxl],ans[maxl],tmp[maxl];
  9 
 10 inline void prework()
 11 {
 12     scanf("%s",ch+1);
 13     for(int i=1;i<=8;i++)
 14         slen[i]=0;
 15     for(int i=1;i<=8;i++)
 16     {
 17         for(int j=4;j>=1;j--)
 18         {
 19             int cc=0,id;
 20             for(int k=1;k<=4;k++)
 21             {
 22                 id=(i-1)*16+(j-1)*4+k;
 23                 if(ch[id]=='1')
 24                     cc+=mi[k];
 25             }
 26             s[i][++slen[i]]=c[cc];
 27         }
 28         while(s[i][slen[i]]=='0' && slen[i]>1)
 29             slen[i]--;
 30     }
 31 }
 32 
 33 inline bool jug()
 34 {
 35     for(int i=1;i<=tmplen;i++)
 36     if(tmp[i]<ans[i])
 37         return true;
 38     else if(tmp[i]>ans[i])
 39         return false;
 40     return false;
 41 }
 42 
 43 inline void mainwork()
 44 {
 45     anslen=128;int nxt;bool flag;
 46     for(int i=1;i<=8;i++)
 47     {
 48         tmplen=0;
 49         for(int j=1;j<i;j++)
 50         {
 51             for(int k=slen[j];k>=1;k--)
 52                 tmp[++tmplen]=s[j][k];
 53             tmp[++tmplen]=':';
 54         }
 55         nxt=i;
 56         while(slen[nxt]==1 && s[nxt][1]=='0' && nxt<=8)
 57             nxt++;
 58         if(nxt>=i+2)
 59         {
 60             if(tmplen>1)
 61                 tmp[++tmplen]=':';
 62             else
 63                 tmp[++tmplen]=':',tmp[++tmplen]=':';
 64         }
 65         else if(nxt==i+1)
 66         {
 67             tmp[++tmplen]='0';
 68             if(i<8)
 69                 tmp[++tmplen]=':';
 70         }
 71         for(int j=nxt;j<=8;j++)
 72         {
 73             for(int k=slen[j];k>=1;k--)
 74                 tmp[++tmplen]=s[j][k];
 75             if(j<8)
 76                 tmp[++tmplen]=':';
 77         }
 78         if(tmplen<anslen)
 79         {
 80             anslen=tmplen;
 81             for(int j=1;j<=tmplen;j++)
 82                 ans[j]=tmp[j];
 83         }
 84         else if(tmplen==anslen)
 85         {
 86             if(jug())
 87                 for(int j=1;j<=tmplen;j++)
 88                     ans[j]=tmp[j];
 89         }
 90     }
 91 }
 92 
 93 inline void print()
 94 {
 95     printf("Case #%d: ",cas);
 96     for(int i=1;i<=anslen;i++)
 97         printf("%c",ans[i]);
 98     puts("");
 99 }
100 
101 int main()
102 {
103     for(int i=0;i<=9;i++)
104         c[i]=i+'0';
105     for(int i=10;i<=15;i++)
106         c[i]=i-10+'a';
107     mi[1]=8;mi[2]=4;mi[3]=2;mi[4]=1;
108     int t;
109     scanf("%d",&t);
110     for(cas=1;cas<=t;cas++)
111     {
112         prework();
113         mainwork();
114         print();
115     }
116     return 0;
117 }
View Code

C Palindrome Mouse

题解：给一个串，问这个串里所有本质不同的回文子串，有多少对满足一个串是另一个的子串。

首先是next边，很显然，一条next链上，除奇根偶根，所有父亲都是儿子的子串。
其次是fail边，又又又很显然，一条fail链上，父亲是儿子的后缀，所以除奇根偶根所有父亲都是儿子的子串

对于每个节点，答案就是其next链上除根外的父亲个数+fail链上除根外的父亲个数。

于是还要想办法去个重。在dfs并且对每个节点跳fail树统计的时候，打个vis标记（当前节点也要标记，next链和fail链重的时候就可能会跳到这里），如果下次跳的时候发现了vis，就可以停止了，这样就简单的保证了不交叉，并且防止了fail树重复跳带来的复杂度。

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int T;
char s[maxn];
ll ans;

struct PAM{
    int nxt[maxn][26];
    int fail[maxn];
    int len[maxn];
    int S[maxn];
    int dp[maxn];
    bool vis[maxn];
    int last,n,p;
    
    int NewNode(int l) 
    {
        memset(nxt[p],0,sizeof(nxt[p]));
        len[p]=l;
        dp[p]=0;
        return p++;
    }

    void Init() 
    {
        ans=0;
        n=last=p=0;
        NewNode(0);
        NewNode(-1);
        S[n]=-1;
        fail[0]=1;
    }

    int GetFail(int x) 
    {
        while(S[n-len[x]-1]!=S[n]) x=fail[x];
        return x;
    }

    void add(int c) 
    {
        S[++n]=c;
        int cur=GetFail(last);
        if(!nxt[cur][c]) 
        {
            int now=NewNode(len[cur]+2);
            fail[now]=nxt[GetFail(fail[cur])][c];
            nxt[cur][c]=now;
        }
        last=nxt[cur][c];
    }

    void dfs(int x,int fa) 
    {
        int cnt=0,cx=x; vis[x]=1;
        while(fail[cx]!=0&&fail[cx]!=1&&!vis[fail[cx]]) 
            cx=fail[cx],vis[cx]=1,++cnt;
        dp[x]=cnt;
        if(x!=1&&x!=0&&fa!=0&&fa!=1) 
            dp[x]=dp[fa]+cnt+1;
        ans+=dp[x];
        for(int i=0;i<26;++i){if(nxt[x][i]) dfs(nxt[x][i],x);}
        vis[x]=0; cx=x;
        while(cnt--) cx=fail[cx],vis[cx]=0;
    }

    void work()
    {
        Init();
        for(int i=1,len=strlen(s+1);i<=len;i++) add(s[i]-'a');
        dfs(1,1);
        dfs(0,0);
    }

} pam;


int main() 
{
    scanf("%d", &T);
    for(int cas=1;cas<=T;++cas) 
    {
        scanf("%s",s+1);
        pam.work();
        printf("Case #%d: %lld
",cas,ans);
    }
    return 0;
}
View Code

D Move

题解：https://blog.csdn.net/liufengwei1/article/details/98352448

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int v[1005];int n,k;
 4 struct p{
 5     int x;
 6     p(){}
 7     p(int x):x(x){}
 8     friend bool operator<(p a,p b)
 9     {
10         return a.x>b.x;
11     }
12 }pp[1005];
13 set<p> s;
14 set<p> :: iterator it;
15 int num[1006];
16 bool check(int vol)
17 {
18     int tol=k,d;
19     s.clear();
20     for(int i=1;i<=n;i++)
21     {   
22         if(num[pp[i].x]==0)
23             s.insert(pp[i]);
24         num[pp[i].x]++;
25     }
26     while(tol&& ((int)s.size())>0)
27     {
28         tol--;
29         p res(vol);
30         it=s.lower_bound(res);
31         while(it!=s.end())
32         {
33             d=(*it).x;
34             res.x-=d;
35             num[d]--;
36             if(num[d]==0)
37                 s.erase(it);
38             it=s.lower_bound(res);
39         }
40     }
41     for(int i=1;i<=n;i++)
42         num[pp[i].x]=0;
43     if(s.size()>0) return false;
44     return true;
45 }
46 int main()
47 {
48     int t;
49     scanf("%d",&t);
50      
51     for(int kace=1;kace<=t;kace++)
52     {
53         scanf("%d%d",&n,&k);
54         int r=0;
55         for(int i=1;i<=n;i++) scanf("%d",&v[i]),r+=v[i];
56         for(int i=1;i<=n;i++) pp[i].x=v[i];
57         int l=0,mid;
58         int ans=r;
59         bool flag;
60         while(l+1<r)
61         {
62             mid=(l+r)>>1;
63             flag=false;
64             for(int j=max(l+1,mid-25);j<=mid;j++)
65             if(check(j))
66                 flag=true;
67             if(flag)
68                 r=mid;
69             else
70                 l=mid;
71         }
72         for(int j=max(1,r-100);j<=r;j++)
73         if(check(j))
74         {
75             ans=j;
76             break;
77         }
78         printf("Case #%d: %d
",kace,ans);
79     }
80 }
View Code

E Androgynos

题解：https://blog.csdn.net/liufengwei1/article/details/98388543

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 int f[2005];
  4 int g[2005][2005];
  5 int main()
  6 {
  7     int t;
  8     scanf("%d",&t);
  9     for(int kace=1;kace<=t;kace++)
 10     {
 11         int n;scanf("%d",&n);
 12         int ty=n%4;int id;
 13         if(ty==2||ty==3)
 14         {
 15             printf("Case #%d: No
",kace);
 16             continue;
 17         }
 18         for(int i=1;i<=n;i++)
 19             for(int j=1;j<=n;j++)
 20                 g[i][j]=0;
 21         if(ty==1)
 22         {
 23             for(int i=ty;i<=n-4;i+=4)
 24             {
 25                 for(int j=1;j<=i;j++)
 26                 {
 27                     g[i+2][j]=1;
 28                     g[j][i+2]=1;
 29                     g[i+3][j]=1;
 30                     g[j][i+3]=1;
 31                 }
 32                 g[i+1][i+2]=g[i+2][i+1]=1;
 33                 g[i+2][i+3]=g[i+3][i+2]=1;
 34                 g[i+3][i+4]=g[i+4][i+3]=1;
 35             }
 36             printf("Case #%d: Yes
",kace);
 37             for(int i=1;i<=n;i++)
 38             {
 39                 for(int j=1;j<=n;j++)
 40                 {
 41                     printf("%d",g[i][j]);
 42                 }
 43                 puts("");
 44             }
 45             for(int i=1;i<=n;i++)
 46                 f[i]=i;
 47             for(int i=1;i<=n/4;i++)
 48             {
 49                 id=(i-1)*4+1;
 50                 swap(f[id+2],f[id+3]);
 51                 swap(f[id+1],f[id+2]);
 52                 swap(f[id+3],f[id+4]);
 53             }
 54             for(int i=1;i<=n;i++)
 55                 printf("%d%c",f[i],(i==n)?'
':' ');
 56             /*bool flag=true;
 57             for(int i=1;i<=n;i++)
 58                 for(int j=1;j<=n;j++)
 59                 if(i!=j)
 60                 if(g[f[i]][f[j]]!=(g[i][j]^1))
 61                     flag=false;
 62             if(flag)
 63                 puts("Yes");*/
 64             //变换顺序
 65         }
 66         else
 67         {
 68             ty=4;
 69             g[1][2]=g[2][1]=g[2][3]=g[3][2]=g[3][4]=g[4][3]=1;
 70             for(int i=ty;i<=n-4;i+=4)
 71             {
 72                 for(int j=1;j<=i;j++)
 73                 {
 74                     g[i+2][j]=1;
 75                     g[j][i+2]=1;
 76                     g[i+3][j]=1;
 77                     g[j][i+3]=1;
 78                 }
 79                 g[i+1][i+2]=g[i+2][i+1]=1;
 80                 g[i+2][i+3]=g[i+3][i+2]=1;
 81                 g[i+3][i+4]=g[i+4][i+3]=1;
 82             }
 83             printf("Case #%d: Yes
",kace);
 84             for(int i=1;i<=n;i++)
 85             {
 86                 for(int j=1;j<=n;j++)
 87                 {
 88                     printf("%d",g[i][j]);
 89                 }
 90                 puts("");
 91             }
 92             for(int i=1;i<=n;i++)
 93                 f[i]=i;
 94             for(int i=1;i<=n/4;i++)
 95             {
 96                 id=(i-1)*4;
 97                 swap(f[id+2],f[id+3]);
 98                 swap(f[id+1],f[id+2]);
 99                 swap(f[id+3],f[id+4]);
100             }
101             for(int i=1;i<=n;i++)
102                 printf("%d%c",f[i],(i==n)?'
':' ');
103             /*bool flag=true;
104             for(int i=1;i<=n;i++)
105                 for(int j=1;j<=n;j++)
106                 if(i!=j)
107                 if(g[f[i]][f[j]]!=(g[i][j]^1))
108                     flag=false;
109             if(flag)
110                 puts("Yes");*/
111         }
112     }
113 }
View Code

F K-ary Heap

unsolved

G Is Today Friday?

unsolved

H Train Driver

unsolved

I Can They Go to Galar?

unsolved

J Upgrading Technology

单调队列维护一下，但是枚举获得d1--dj的时候要注意一定要保证有一个技能只严格升级到了j

 1 #include<bits/stdc++.h>
 2 #define maxl 1010
 3 using namespace std;
 4 
 5 int n,m,cas;
 6 long long ans=0;
 7 int c[maxl][maxl];
 8 long long q[maxl][maxl];
 9 int qtop[maxl],qhead[maxl];
10 long long sum[maxl][maxl];
11 long long d[maxl];
12 
13 inline void prework()
14 {
15     scanf("%d%d",&n,&m);
16     for(int i=1;i<=n;i++)
17         for(int j=1;j<=m;j++)
18         {
19             scanf("%lld",&sum[i][j]);
20             sum[i][j]=-sum[i][j];
21         }
22     for(int i=1;i<=m;i++)
23         scanf("%lld",&d[i]);
24     for(int i=1;i<=n;i++)
25         qtop[i]=0,qhead[i]=1;
26     for(int i=1;i<=n;i++)
27         for(int j=0;j<=m;j++)
28         {
29             if(j>0)
30                 sum[i][j]+=sum[i][j-1];
31             while(qtop[i]>0 && sum[i][j]>=sum[i][q[i][qtop[i]]])
32                 qtop[i]--;
33             q[i][++qtop[i]]=j;    
34         }
35 }
36 
37 inline void mainwork()
38 {
39     long long sumd=0,sumt;ans=0;
40     for(int j=0;j<=m;j++)
41     {
42         sumd+=d[j];sumt=0;
43         for(int i=1;i<=n;i++)
44         {
45             while(q[i][qhead[i]]<j)
46                 qhead[i]++;
47             sumt+=sum[i][q[i][qhead[i]]];    
48         }
49         ans=max(sumd+sumt,ans);
50     }
51 }
52 
53 inline void print()
54 {
55     printf("Case #%d: %lld
",cas,ans);
56 }
57 
58 int main()
59 {
60     int t;
61     scanf("%d",&t);
62     for(cas=1;cas<=t;cas++)
63     {
64         prework();
65         mainwork();
66         print();
67     }
68     return 0;
69 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/csushl/p/11301496.html