风竹曦

2020-05-03 17:10 已编辑武汉工程大学 golang

关注

【武汉工程大学2020GPLT选拔赛】题解

Sundries

这场比赛是由武汉工程大学算法协会ACM-ICPC队伍-“江湖夜雨十年WA”，按照GPLT模式出的题。出题人水平有限，题目难免有很多疏漏和不足，希望各位多多包涵。

~~题目难度适中，覆盖知识点广，有着切合实际的背景，解法比较自然，特别适合算法竞赛入门选手。~~

整套题目相对比较简单，只有 L1-8 和 L2-4 的标程代码超过了 50 行（但没有超过100行）。出题人认同的及格线大约为 240 分。

L1-1 I LOVE WIT (10)

思路

两重循环输出。

Code

#include<bits/stdc++.h>
using namespace std;

int main()
{
    char s[]="I LOVE WIT";
    for (int i=0;i<strlen(s);i++) {
        for (int j=0;j<i;j++) {
            printf(" ");
        }
        printf("%c\n",s[i]);
    }

    return 0;
}

L1-2 单位换算 (10)

思路

直接计算答案，需要判断是否为整数。

Code

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;

    double ans=(double)n*12*2.54*10;
    if (ans-(int)ans<1e-6) {
        printf("%d\n",(int)ans);
    } else {
        printf("%.1f\n",ans);
    }

    return 0;
}

L1-3 Pokémon (20)

思路

直接计算。

Code

#include<bits/stdc++.h>
using namespace std;

int main()
{
    double p[7];
    for (int i=0;i<7;i++) {
        scanf("%lf%%",p+i);
    }
    int c,f;
    cin>>c>>f;

    double ans=p[c];
    if (f==1) {
        ans*=0.01;
    } else {
        ans*=0.99;
    }

    printf("%.2f%%\n",ans);

    return 0;
}

L1-4 颠倒阴阳 (20)

思路

位操作基础，也可以按位取出来存在数组中。

Code

#include<bits/stdc++.h>
using namespace std;

int main()
{
    unsigned int n;
    cin>>n;

    unsigned int ans=0;
    for (int i=0;i<32;i++) {
        ans<<=1;
        if (n && ((n&1)==0)) {
            ans++;
        }
        n>>=1;
    }
    cout<<ans<<endl;

    return 0;
}

L1-5 演唱会 (30)

思路

把时间转换成秒数判断。

~~愚蠢的验题人写了个time类。~~

Code

#include<bits/stdc++.h>
using namespace std;

struct Time{
    int h,m,s;
    Time(int hh,int mm,int ss) {
        h=hh,m=mm,s=ss;
        m+=s/60,s%=60;
        h+=m/60,m%=60;
    }
    bool operator == (const Time t) const {
        return h==t.h && m==t.m && s==t.s;
    }
    bool operator < (const Time t) const {
        if (h==t.h) {
            if (m==t.m) {
                return s<t.s;
            } else {
                return m<t.m;
            }
        } else {
            return h<t.h;
        }
    }
};

int main()
{
    int hh,mm,ss;
    scanf("%d:%d:%d",&hh,&mm,&ss);

    Time arriveTime(hh+1,mm+22,ss+33);
    Time startTime(19,0,0);
    Time endTime(21,0,0);

    if (arriveTime<startTime) {
        puts("arrive on time");
    } else if (endTime<arriveTime || endTime==arriveTime) {
        puts("too late");
    } else {
        puts("arrive late");
    }

    return 0;
}

L1-6 分鸽子 (30)

思路

暴力枚举答案可以过 30% 的数据。二分答案然后验证，复杂度 $O(n \log w)$ .

Code

#include<bits/stdc++.h>
using namespace std;

const int N=(int)1e5+10;
int a[N];
int n,m;

bool check(int x);

int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        scanf("%d",a+i);
    }

    int l=1,r=0x3f3f3f3f,ans=0;
    while (l<=r) {
        int mid=(l+r)/2;
        if (check(mid)) {
            ans=mid;
            l=mid+1;
        } else {
            r=mid-1;
        }
    }
    cout<<ans<<endl;

    return 0;
}

bool check(int x)
{
    int cnt=0;
    for (int i=1;i<=n;i++) {
        cnt+=a[i]/x;
        if (cnt>=m) {
            return true;
        }
    }
    return false;
}

L1-7 拼接梯子 (40)

思路

考虑 L 的二进制，每一位 1 都需要一块木板，模拟一下就好。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int k;
    ll L;
    cin>>k>>L;

    int cnt=0;
    ll ans=0,res=1;
    while (L) {
        if (L&1) {
            if (cnt!=0 && cnt<=k) {
                ans=res;
            } else {
                break;
            }
        }
        L>>=1;
        res*=2;
        cnt++;
    }

    if (L==0) {
        puts("Yes");
        cout<<ans<<endl;
    } else {
        puts("No");
    }

    return 0;
}

L1-8 幻想乡炼金学 (40)

思路

唯二代码超过 50 行的题之一。按照规则处理字符串即可，考验码力。

Code

#include<bits/stdc++.h>
using namespace std;

string atom(const string &s,int &st);
int num(const string &s,int &st);

int main()
{
    string str,s;
    getline(cin,str);
    for (int i=0;i<(int)str.size();i++) {
        if (str[i]!=' ') {
            s+=str[i];
        }
    }

    int n=s.size();
    string ans;
    for (int i=0;i<n;) {
        if (s[i]>='A' && s[i]<='Z') {
           string a=atom(s,i);
            if (i<n && s[i]=='{') {
                i++;//{
                int m=num(s,i);
                i++;//}
                for (int j=0;j<m;j++) {
                    ans+=a;
                }
            } else {
                ans+=a;
            }
        } else if (s[i]=='(') {
            vector<string> v;
            i++;//(
            while (i<n && s[i]!=')') {
                v.push_back(atom(s,i));
            }
            i+=2;//){
            int m=num(s,i);
            i++;//}
            for (int j=0;j<(int)v.size();j++) {
                for (int k=0;k<m;k++) {
                    ans+=v[j];
                }
            }
        }
    }
    cout<<ans<<endl;

    return 0;
}

string atom(const string &s,int &st)
{
    string t;
    t+=s[st++];//upper
    while (st<(int)s.size() && s[st]>='a' && s[st]<='z') {
        t+=s[st++];//lower
    }
    return t;
}
int num(const string &s,int &st)
{
    int n=0;
    while (st<(int)s.size() && s[st]>='0' && s[st]<='9') {
        n=n*10+s[st++]-'0';
    }
    return n;
}

L2-1 特殊的沉重球 (50)

思路

~~验题人验题的时候，排个序贪心一下居然就过了，于是出题人加强了后 50% 的数据。~~

枚举每个宝可梦放的位置，即已有的球和新加一个球，暴力dfs，即可过 50% 的数据。

然后需要一些剪枝优化，比如按照重量从大到小放，当前球的个数大于等于已经得到的最优解就剪掉。

复杂度玄学。

Code

#include<bits/stdc++.h>
using namespace std;

int a[30],sum[30];
int n,w,ans;

void dfs(int x,int cnt);

int main()
{
    cin>>n>>w;
    for (int i=1;i<=n;i++) {
        scanf("%d",a+i);
    }

    sort(a+1,a+1+n,greater<int>());
    ans=n;
    dfs(1,0);
    cout<<ans<<endl;

    return 0;
}

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 (a[x]+sum[i]<=w) {
            sum[i]+=a[x];
            dfs(x+1,cnt);
            sum[i]-=a[x];
        }
    }
    sum[cnt+1]=a[x];
    dfs(x+1,cnt+1);
    sum[cnt+1]=0;
}

L2-2 又见火车入栈 (50)

思路

手写一个栈，实现访问栈中第 k 个元素。把询问按照 x 升序排序，然后模拟一遍就行。
复杂度 $O(q \log q)$ .

Code

#include<bits/stdc++.h>
using namespace std;

const int N=(int)1e6+10;
int rec[N],stk[N];
struct Query {
    int x,y,id,ans;
} qry[N];

int main()
{
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) {
        char s[8];
        scanf("%s",s);
        if (s[0]=='i') rec[i]=1;
        else rec[i]=0;
    }

    int q;
    cin>>q;
    for (int i=1;i<=q;i++) {
        scanf("%d%d",&qry[i].x,&qry[i].y);
        qry[i].id=i;
    }

    sort(qry+1,qry+1+q,[](const Query &q1,const Query &q2){return q1.x<q2.x;});

    int idx=0,top=0,cnt=0;
    for (int i=1;i<=q;i++) {
        while (idx!=qry[i].x) {
            idx++;
            if (rec[idx]) {
                stk[++top]=++cnt;
            } else {
                top--;
            }
        }
        qry[i].ans=stk[qry[i].y];
    }

    sort(qry+1,qry+1+q,[](const Query &q1,const Query &q2){return q1.id<q2.id;});
    for (int i=1;i<=q;i++) {
        printf("%d\n",qry[i].ans);
    }

    return 0;
}

L2-3 新旷野地带 (50)

思路

放 k 个坑的时候需要挑选 k 行 k 列，然后在 k*k 的网格里面放 k 个坑，显然方案数是 $k!$ ，所以答案是 $\sum_{i=1}^{k}\binom{n}{i}\binom{m}{i}i!$ .

利用费马小定理预处理阶乘的逆元。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=(int)1e6+10;
const ll mod=(ll)1e9+7;
ll fct[N],inv[N];
void init(int n);
ll comb(int n,int m);
ll qPow(ll a,ll n,ll m);

int main()
{
    int n,m,k;
    cin>>n>>m>>k;

    init(max(n,m));
    ll ans=0;
    for (int i=1;i<=k;i++) {
        if (i>n || i>m) break;
        ll tmp=comb(n,i)*comb(m,i)%mod*fct[i]%mod;
        ans=(ans+tmp)%mod;
    }
    cout<<ans<<endl;

    return 0;
}
void init(int n)
{
    fct[0]=1,inv[0]=qPow(1,mod-2,mod);
    for (int i=1;i<=n;i++) {
        fct[i]=fct[i-1]*i%mod;
        inv[i]=qPow(fct[i],mod-2,mod);
    }
}
ll comb(int n,int m)
{
    if (m>n) return 0;
    return fct[n]*inv[m]%mod*inv[n-m]%mod;
}
ll qPow(ll a,ll n,ll m)
{
    ll ans=1,res=a%m;
    while (n) {
        if (n&1) ans=ans*res%m;
        res=res*res%m;
        n>>=1;
    }
    return ans;
}

L2-4 缘之空 (50)

思路

第二个代码超过 50 行的题。

我们知道树上距离可以通过 LCA(最近公共祖先) 来求，即 $dis(x,y)=dep(x)+dep(y)-2dep(lca(x,y))$ .

暴力往上爬找 LCA 的单次复杂度是 $O(n)$ ，可以过 30% 的数据。

利用树上倍增，可以把单次查询降到 $O(\log n)$ ，总复杂度 $O(n\log n)$ .

Code

#include<bits/stdc++.h>
using namespace std;

const int N=(int)1e5+10;
vector<int> G[N];
int dep[N],fa[N][20];

void bfs(int st,int n);
int lca(int u,int v);

int main()
{
    int n,q;
    cin>>n>>q;
    for (int i=0;i<n-1;i++) {
        int f,c;
        scanf("%d%d",&f,&c);
        G[f].push_back(c);
        fa[c][0]=f;
    }

    int st=0;
    for (int i=1;i<=n;i++) {
        if (fa[i][0]==0) {
            st=i;
            break;
        }
    }
    bfs(st,n);

    while (q--) {
        int x,y;
        scanf("%d%d",&x,&y);
        int l=lca(x,y),dis=dep[x]+dep[y]-dep[l]*2;

        if (l==x || l==y || dis<=4) {
            puts("NO");
        } else {
            puts("YES");
        }
        printf("%d\n",dis);
    }

    return 0;
}

void bfs(int st,int n)
{
    queue<int> q;
    q.push(st);
    dep[st]=1;
    while (!q.empty()) {
        int x=q.front();
        q.pop();

        for (int i=0;i<(int)G[x].size();i++) {
            int y=G[x][i];
            if (dep[y]) continue;
            dep[y]=dep[x]+1;
            for (int j=1;j<20;j++) {
                fa[y][j]=fa[fa[y][j-1]][j-1];
            }
            q.push(y);
        }
    }
}

int lca(int x,int y)
{
    if (dep[x]>dep[y]) swap(x,y);
    for (int i=19;i>=0;i--) {
        if (dep[fa[y][i]] >= dep[x]) {
            y=fa[y][i];
        }
    }
    if (x==y) return x;
    for (int i=19;i>=0;i--) {
        if (fa[x][i]!=fa[y][i]) {
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}