2019牛客暑期多校训练营（第六场A,B,D（假二分）,G,J）

这场打的跟狗屎一样的惨

A Garbage Classification

签到题

/*简化版*/
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e5+10;
string s,t;
int a[30];
int getid(char x)
{
    if(x=='h') return 1;
    if(x=='d') return 2;
    return 3;
}
int main()
{
	int _;
	cin>>_;
	int cas=0;
	while(_--)
    {
        cin>>s>>t;
        for(int i=0;i<26;++i)
        {
            a[i]=getid(t[i]);
        }
        int num[4];
        num[1]=num[2]=num[3]=0;
        for(int i=0;i<s.size();++i)
        {
            num[a[s[i]-'a']]++;
        }
        //printf("s.z:%d\n",s.size());
        //for(int i=1;i<=3;++i) printf("i:%d num[i]:%d\n",i,num[i]);
        int n=s.size();
        if(100*num[1]>=25*n){
            printf("Case #%d: Harmful\n",++cas);
        }
        else if(100*num[1]<=10*n) printf("Case #%d: Recyclable\n",++cas);
        else if(num[2]>=2*num[3]) printf("Case #%d: Dry\n",++cas);
        else printf("Case #%d: Wet\n",++cas);
    }
}

B Shorten IPv6 Address

128位的二进制，化成16进制，每四位合在一起，四位与四位用"："分割，对单独四位而言m前导0可省略，四个0省略成一个0，

问现能将两个0合并成"::"问字典序最小的一个字符是什么？

暴力枚举0的位置变成"::"求字典序最小的即可

#include<bits/stdc++.h>
using namespace std;
string s,ans;
char tmx[20]="0123456789abcdef";
char cal1(int id)
{
    int tmp=0;
    int ans=0;
    for(int  i=id;i>=id-3;--i)
    {
        if(s[i]=='1') ans+=pow(2,tmp);
        ++tmp;
    }
    return tmx[ans];
}
struct node
{
    int x;
    string val;
}a[10000];
int main()
{
    int cas=0;
    int _;
    cin>>_;
    while(_--)
    {

        cin>>s;
        int l1=s.size();
        string t;
        for(int i=3;i<l1;i+=4)
        {
            t+=cal1(i);
        }
        //cout<<"t:"<<t<<endl;
        string t1;
        int cnt=0;
        ans="";
        for(int i=0;i<t.size();i+=4)
        {
            int j=i;
            ++cnt;
            while(j<=i+3&&t[j]=='0')++j;
            while(j<=i+3) a[cnt].val+=t[j],++j;
            if(t[i]=='0'&&t[i+1]=='0'&&t[i+2]=='0'&&t[i+3]=='0') a[cnt].x=1;
        }
        //printf("cnt:%d\n",cnt);
        for(int i=1;i<=cnt;++i)
        {
            if(a[i].x==1) ans+="0";
            else ans+=a[i].val;
            if(i!=cnt)ans+=":";
        }
        for(int i=1;i<=cnt;++i)
        {
            if(a[i].x==1)
            {
                int j=i;
                int num=0;
                while(j<=cnt&&a[j].x==1) ++j,num++;
                if(num<2) continue;
                string tmp="";
                //printf("i:%d j:%d\n",i,j);
                for(int k=1;k<i;++k)
                {
                    if(a[k].x==1) tmp+="0";
                    else tmp+=a[k].val;
                    tmp+=":";
                }
                if(i==1) tmp+=":";
                tmp+=":";
                for(int k=j;k<=cnt;++k)
                {
                    if(a[k].x==1) tmp+="0";
                    else tmp+=a[k].val;
                    tmp+=":";
                }
                //cout<<"tmp:  "<<tmp<<endl;
                if(tmp[tmp.size()-1]==':'&&tmp[tmp.size()-2]!=':') tmp.erase(tmp.size()-1);
                if(ans=="") ans=tmp;
                else
                {
                    if(tmp.size()<ans.size()) ans=tmp;
                    else if(tmp.size()==ans.size()&&tmp<ans) ans=tmp;
                }
                i=j;
            }
        }
        printf("Case #%d: ",++cas);cout<<ans<<endl;
        for(int i=0;i<=cnt;++i) a[i].val="",a[i].x=0;
    }
}

D Move

题意：给定n个物品，k个体积相等的盒子，求一个最小体积使得所有的物品都可以装到盒子里。装盒子要满足有大的就装大的，没有大的才能装小的的策略

不可二分

暴力枚举体积，然后从大到小二分插入容量即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
ll v[N];
int main()
{
    int _;cin>>_;
    int cas=0;
    while(_--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        multiset<ll>st;
        ll sum=0;
        ll mx=0;
        for(int i=1;i<=n;++i)
        {
            scanf("%lld",&v[i]);
            mx=max(mx,v[i]);
            sum+=v[i];
        }
        ll flag=0;
        if(sum%k!=0) flag=1;
        ll v1=max(mx,sum/k+flag);
        for(ll i=v1;;++i)
        {
            ll ans=i;
            int k0=1;
            st.clear();
            for(int j=1;j<=n;++j) st.insert(v[j]);
            while(k0<=k)
            {
                ll v2=ans;
                while(v2>0&&st.size())
                {
                    auto it=st.upper_bound(v2);
                    if(it==st.begin()) break;
                    --it;
                    v2-=*it;

                    st.erase(it);
                }
                ++k0;
            }
            if(st.size()==0)
            {
                printf("Case #%d: %lld\n",++cas,ans);
                break;
            }
        }
    }
}

G Is Today Friday?

蔡勒公式。

1582年10月4日后：w = (d + 1+ 2*m+3*(m+1)/5+y+y/4-y/100+y/400)%7;（包括当年）

1582年10月4日前：w = (d+1+2*m+3*(m+1)/5+y+y/4+5) % 7;

w：星期； w对7取模得：0-星期日，1-星期一，2-星期二，3-星期三，4-星期四，5-星期五，6-星期六

c：世纪（注：一般情况下，在公式中取值为已经过的世纪数，也就是年份除以一百的结果，而非正在进行的世纪，也就是现在常用的年份除以一百加一；不过如果年份是公元前的年份且非整百数的话，c应该等于所在世纪的编号，如公元前253年，是公元前3世纪，c就等于-3）

y：年（一般情况下是后两位数，如果是公元前的年份且非整百数，y应该等于cMOD100+100）

m：月（m大于等于3，小于等于14，即在蔡勒公式中，某年的1、2月要看作上一年的13、14月来计算，比如2003年1月1日要看作2002年的13月1日来计算）

d：日

[ ]代表取整，即只要整数部分。

此题做法：dfs暴力枚举每个数字用相应的字符对应的序列，然后依次判断所有字符是否合法（是星期五）

【代码】

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
string s[N];
int n;
bool flag;
int val[30];
int vis[30];
bool isyear(int x)
{
    if(x%4==0&&x%100!=0||x%400==0) return 1;
    return 0;
}
int Zeller(int y,int m,int d)
{
    if (m == 1 || m == 2)
    {
        y -= 1;
        m += 12;
    }
    /*只适用于1582年之后，不包括当年*/
    /*1582年之后之前：w = (d + 1+ 2*m+3*(m+1)/5+y+y/4-y/100+y/400)%7*/
    return (d+2*m+3*(m+1)/5+y+y/4-y/100+y/400+1)%7;
}

bool check()
{
    for(int i=0;i<n;++i)
    {
        int year=0,month=0,day=0;
        for(int j=0;j<=3;++j) year=year*10+val[s[i][j]-'A'];
        for(int j=5;j<=6;++j) month=month*10+val[s[i][j]-'A'];
        for(int j=8;j<=9;++j) day=day*10+val[s[i][j]-'A'];
        if(year<1600||month>12||month<1||day>31||day<1) return 0;
        if((month==4||month==6||month==9||month==11)&&day>30)  return 0;
        if(isyear(year)&&month==2&&day>29) return 0;
        if(!isyear(year)&&month==2&&day>28) return 0;
        if(Zeller(year,month,day)!=5) return 0;
    }
    return 1;
}

void dfs(int now)
{
    if(flag) return ;
    if(now==10)
    {
        if(check())
        {
            flag=1;
            for(int i=0;i<10;++i)
            {
                printf("%d",val[i]);
            }
            puts("");
        }
        return ;
    }
    for(int i=0;i<10;++i)
    {
        if(vis[i]==0)
        {
            vis[i]=1;
            val[now]=i;
            dfs(now+1);
            vis[i]=0;
        }
    }
}

int main()
{
    int _;
    cin>>_;
    int cas=0;
    while(_--)
    {
        memset(vis,0,sizeof(vis));
        scanf("%d",&n);
        for(int i=0;i<n;++i) cin>>s[i];
        sort(s,s+n);
        n=unique(s,s+n)-s;
        flag=0;
        printf("Case #%d: ",++cas);
        dfs(0);
        if(!flag) printf("Impossible\n");
    }
    return 0;
}

J Upgrading Technology

签到题

/*简化版*/
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e3+50;
const ll inf=0x3f3f3f3f3f3f3f;
int n,m;
ll d[N],a[N][N],b[N];
ll last[N][N],pre[N];
ll mx[N][N*4];
vector<ll>G;
void up(int id,int l,int r,int ty)
{
    if(l==r)
    {
        mx[ty][id]=last[ty][l];
        return ;
    }
    int mid=l+r>>1;
    up(id<<1,l,mid,ty);
    up(id<<1|1,mid+1,r,ty);
    mx[ty][id]=max(mx[ty][id<<1],mx[ty][id<<1|1]);
}
ll qu(int id,int l,int r,int ty,int ql,int qr)
{
    if(ql<=l&&r<=qr) return mx[ty][id];
    int mid=l+r>>1;
    ll ans=-inf;
    if(ql<=mid) ans=max(ans,qu(id<<1,l,mid,ty,ql,qr));
    if(qr>mid) ans=max(ans,qu(id<<1|1,mid+1,r,ty,ql,qr));
    return ans;
}
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    int _;
    cin>>_;
    int cas=0;
    while(_--)
    {
        scanf("%d %d",&n,&m);
        for(int i=0;i<=1010;++i)
        {
            b[i]=pre[i]=d[i]=0;
            for(int j=0;j<=1010;++j)
            last[i][j]=0;
        }

        for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            scanf("%lld",&a[i][j]);
            a[i][j]=-a[i][j];
        }
        for(int i=1;i<=m;++i){
            scanf("%lld",&d[i]);
            pre[i]=pre[i-1]+d[i];
        }

        for(int j=1;j<=m;++j)
        {
            ll tmp=0;
            for(int i=1;i<=n;++i)
            {
                tmp+=a[i][j];
            }
            b[j]=b[j-1]+tmp;
        }

        for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j) last[i][j]=last[i][j-1]+a[i][j];

        for(int i=1;i<=n;++i) up(1,1,m,i);

        ll ans=0;
        for(int j=0;j<=m;++j)
        {
            ll tmp=pre[j]+b[j];
            G.clear();
            for(int i=1;i<=n;++i)
            {
                if(j+1<=m)
                {
                    ll qut=qu(1,1,m,i,j+1,m);
                    if(qut-last[i][j]>0) G.push_back(qut-last[i][j]);
                    else G.push_back(0);
                }
                else G.push_back(0);
            }
            sort(G.begin(),G.end(),cmp);
            for(int i=0;i<n-1;++i){
                if(G[i]>0) tmp+=G[i];
            }
            ans=max(ans,tmp);
        }
        printf("Case #%d: %lld\n",++cas,ans);
    }
    return 0;
}