L1-1 I LOVE WIT

直接用raw string语法输出答案即可

#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout<<R"(I

  L
   O
    V
     E

       W
        I
         T)";
    return 0;
}

L1-2 单位换算

赛时搞反关系了……其实直接乘就完事了。注意当floor(x)==x时需要保留到小数点后 $0$ 位。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    double n;
    cin>>n;
    double a=n*12;
    a*=2.54;
    a*=10;
    if(floor(a)==a)printf("%.0lf",a);
    else printf("%.1lf",a);
    return 0;
}

L1-3 Pokémon

~~日常被审题所坑~~注意如果要闪光的，则乘 $1 \%$ ，否则乘 $99 \%$ 。蒟蒻正是因为没有乘 $99 \%$ 而 $12$ 分滚粗的。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a[7]={0};
    string s;
    for(int i=0;i<=6;++i){
        cin>>s;
        int b=0;
        for(int j=0;j<s.size()-1;++j){
            if(s[j]=='.')continue;
            b=b*10+(s[j]-'0');
        }
        a[i]=b;
    }
    int n,m;
    cin>>n>>m;
    double ans=a[n]*0.0001;
    if(m==0)ans=ans*99.0;
    printf("%.2lf%%",ans);
    return 0;
}

L1-4 颠倒阴阳

读入的数应当是一个无符号整型变量。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ul;
int main()
{
    ul n;
    cin>>n;
    if(n==0){
        puts("0");
        return 0;
    }
    bitset<32> b(n);
    int top=0;
    for(int i=31;i>=0;--i){
        if(b[i]){
            top=i;
            break;
        }
    }
    for(int i=top;i>=0;--i){
        b.flip(i);
    }
    string s=b.to_string();
    reverse(s.begin(),s.end());
    bitset<32> c(s);
    cout<<c.to_ulong();
    return 0;
}

L1-5 演唱会

直接转换成秒单位制，省时省力，~~比官方题解不知道高到哪里去了。~~不过在比赛的时候，还是被判断条件的等于号坑了。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int h,m,s;
    int start=19*3600,end=21*3600;
    scanf("%d:%d:%d",&h,&m,&s);
    int time=h*3600+m*60+s;
    time+=3600+22*60+33;
    if(time<start)puts("arrive on time");
    else if(time<end)puts("arrive late");
    else puts("too late");
    return 0;
}

L1-6 分鸽子

赛场上想不到居然可以二分。现在发现，只要能保证数组的一边满足某种性质，另一边不满足，那么就可以二分出边界。比如，这里不妨设 $x$ 为每个人可以分到的鸽子肉数， $f(x)$ 是如果每个人分到 $x$ 个鸽子肉，最多可以分给多少人。显然存在 $x_0$ 使得当 $x \leq x_0$ 时， $f(x) \ge m$ ， $m$ 是待分的人数。那么我们就可以二分搜索出 $x_0$ 出来。官方题解用的是非递归，这里本人觉得递归更好理解些。
注意特判 $x=0$ 的情况。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6;
int n,m;
int a[N];
ll solve(ll l,ll r)
{
    if(l>=r)return r-1;
    ll mid=l+r>>1;
    ll num=0;
    for(int i=1;i<=n;++i){
        num+=a[i]/mid;
    }
    if(num>=m)return solve(mid+1,r);
    return solve(l,mid);
}
int main()
{
    cin>>n>>m;
    ll sum=0;
    for(int i=1;i<=n;++i)cin>>a[i],sum+=a[i];
    if(sum<m)cout<<0;
    else cout<<solve(1,100000000000000ll);
    return 0;
}

L1-7 拼接梯子

一开始审题不清，以为梯子的长度可以任意选取 $2$ 的自然数次方，~~最后知道真相的我眼泪掉下来。~~这题坑点有二，一是当 $l$ 为奇数的时候，由于最短的长度是 $2$ ，因此一定不可能拼成。二是，如果梯子碎片总长度小于目标的梯子长度，那也不成立。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll k,l;
    cin>>k>>l;
    if(l&1){puts("No");return 0;}
    if((1ll<<k+1)-2<=l){
        puts("No");
        return 0;
    }
    bitset<64> b(l);
    if(b.count()>k)puts("No");
    else{
        puts("Yes");
        int top;
        for(int i=0;i<64;++i)if(b[i])top=i;
        cout<<(1ll<<top);
    }
    return 0;
}

L1-8 幻想乡炼金学

~~打磨你~~待填坑。~~考场上再遇到也不会去做。~~
以上写于2020年5月4日。
今天（2020年5月11日），我终于把大模拟题写出来了。

#include<bits/stdc++.h>
using namespace std;
vector<string> split(string s)
{
    vector<string> ans;
    for(int i=0;i<s.size();){
        string atom;
        if(s[i]>='A'&&s[i]<='Z'){
            atom+=s[i];
            ++i;
            while(i<s.size()&&(s[i]<'A'||s[i]>'Z')){
                atom+=s[i];
                ++i;
            }
            ans.push_back(atom);
            atom="";
        }
    }
    return ans;
}
int main()
{
    string str,ans,tmp;
    getline(cin,str);
    for(int i=0;i<str.size();++i){
        if(str[i]!=' ')tmp+=str[i];
    }
    str=tmp;
    for(int i=0;i<str.size();){
        //cout<<i<<endl;
        if(str[i]==' ')continue;//delete spaces
        vector<string> atoms;
        if(str[i]=='('){
            ++i;
            string tmp;
            while(str[i]!=')'){//get the whole molecule in brankets
                tmp+=str[i++];
            }
            ++i;
            atoms=split(tmp);
        }
        string atom;
        if(str[i]>='A'&&str[i]<='Z'){
            atom+=str[i];
            ++i;
            while(str[i]>='a'&&str[i]<='z'){
                atom+=str[i];
                ++i;
            }
        }
        int number=1;//default number of atom is 1
        if(str[i]=='{'){
            ++i;
            number=0;
            while(str[i]!='}'){
                number=number*10+str[i]-'0';
                ++i;
            }
            ++i;
        }
        if(atoms.size()){
            for(auto str:atoms){
                for(int i=0;i<number;++i){
                    ans+=str;
                }
            }
            atoms.clear();
        }
        if(atom.size()){
            for(int i=0;i<number;++i){
                ans+=atom;
            }
        }
    }
    cout<<ans;
    return 0;
}

L2-1 特殊的沉重球

考场上用贪心骗的分。后面补题的时候根据官方题解，直接dfs搜索即可，注意搜索需要剪枝，并且预处理时需要排序，以便在递归层数尽可能小的时候被剪枝。

#include<bits/stdc++.h>
using namespace std;
int c[50],n,w,sum[50],ans;
void dfs(int x,int cnt)
{
    if(cnt>=ans)return;
    if(x>n){
        ans=min(ans,cnt);
        return;
    }
    for(int i=1;i<=cnt;++i){
        if(c[x]+sum[i]<=w){
            sum[i]+=c[x];
            dfs(x+1,cnt);
            sum[i]-=c[x];
        }
    }
    sum[cnt+1]=c[x];
    dfs(x+1,cnt+1);
    sum[cnt+1]=0;
}
int main()
{
    scanf("%d%d",&n,&w);
    for(int i=1;i<=n;++i){
        scanf("%d",c+i);
    }
    ans=n;
    sort(c+1,c+n+1,greater<int>());
    dfs(1,0);
    printf("%d",ans);
    return 0;
}

L2-2 又见火车入栈

考场上我强行存储栈在每一次操作的状态，果不其然MLE了。实际上离线处理询问会好很多。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+50;
int stk[N],tt,n,q,cnt;
bool op[N];
struct Query
{
    int x,y,id,ans;
}queries[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        char s[4];
        scanf("%s",s);
        if(s[0]=='i')op[i]=true;
    }
    scanf("%d",&q);
    for(int i=1;i<=q;++i){
        scanf("%d%d",&queries[i].x,&queries[i].y);
        queries[i].id=i;
    }
    sort(queries+1,queries+q+1,[](const Query &a,const Query &b){return a.x<b.x;});
    int ptr=0;
    for(int i=1;i<=q;++i){
        while(queries[i].x!=ptr){
            ++ptr;
            if(op[ptr])stk[++tt]=++cnt;
            else --tt;
        }
        queries[i].ans=stk[queries[i].y];
    }
    sort(queries+1,queries+q+1,[](const Query &a,const Query &b){return a.id<b.id;});
    for(int i=1;i<=q;++i){
        printf("%d\n",queries[i].ans);
    }
    return 0;
}

L2-3 新旷野地带

组合数学题。首先选取 $k$ 行 $k$ 列，然后在这 $k$ 行 $k$ 列里面进行全排列。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7,N=1e6+500;
ll inv[N],f[N],n,m,k;
ll qpow(ll a,ll n)
{
    ll ans=1;
    while(n){
        if(n&1)ans=ans*a%MOD;
        a=a*a%MOD;
        n>>=1;
    }
    return ans;
}
ll c(ll n,ll m)
{
    if(n<m)return 0;
    return f[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int main()
{
    f[0]=inv[0]=1,f[1]=1,inv[1]=1;
    for(ll i=2;i<=(ll)1e6+50;++i){
        f[i]=f[i-1]*i%MOD;
        inv[i]=qpow(f[i],MOD-2);
    }
    cin>>n>>m>>k;
    ll res=0;
    for(ll i=1;i<=min(k,min(n,m));++i){
        res=(res+c(n,i)*c(m,i)%MOD*f[i])%MOD;
    }
    cout<<res;
    return 0;
}

L2-4 缘之空

考前不会倍增求LCA，考后恶补了一下，发现是***题。

#include<bits/stdc++.h>
using namespace std;
const int N=1e7,M=1e5+100;
int h[N],e[N],ne[N],idx,n,m,degree[N],depth[N],q[N],hh,tt;
int fa[M][20];
void bfs(int root)
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[root]=1;
    q[0]=root;
    while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];i;i=ne[i]){
            int j=e[i];
            if(depth[j]>depth[t]+1){
                depth[j]=depth[t]+1;
                q[++tt]=j;
                fa[j][0]=t;
                for(int k=1;k<=19;++k){
                    fa[j][k]=fa[fa[j][k-1]][k-1];
                }
            }
        }
    }
}
int lca(int a,int b)
{
    if(depth[a]<depth[b])swap(a,b);
    for(int i=19;i>=0;--i){
        if(depth[fa[a][i]]>=depth[b])a=fa[a][i];
    }
    if(a==b)return a;
    for(int i=19;i>=0;--i){
        if(fa[a][i]!=fa[b][i]){
            a=fa[a][i];
            b=fa[b][i];
        }
    }
    return fa[a][0];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n-1;++i){
        int a,b;
        scanf("%d%d",&a,&b);
        e[++idx]=b,ne[idx]=h[a],h[a]=idx;
        ++degree[b];
    }
    int root;
    for(int i=1;i<=n;++i)if(!degree[i]){root=i;break;}
    bfs(root);
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        int t=lca(a,b);
        int dis=depth[a]+depth[b]-2*depth[t];
        if(t==a||t==b||dis<=4)puts("NO");
        else puts("YES");
        printf("%d\n",dis);
    }
    return 0;
}

后记

根据出题人透露，他们认定的及格分数线是 $220$ 分。~~考场上只能做156分的蒟蒻。~~

武汉工程大学2020GPLT选拔赛解题报告