【题解】长沙理工大学ACMore编程协会2018年新生赛（重现赛）

「爱情、让人受尽委屈。」 2023-06-28 11:09 1阅读 0赞

### 文章目录 ###

*  A - 送气球.jpg（签到）
 *  B - 签到题（思维 + 暴力）
 *  D - 远神的高精度（大数）
 *  G - LLLYYY的数字思维（思维）
 *  J - 王者荣耀（动态规划）
 *  K - 三角形（贪心）
 *  L - 彪神666（模拟）
 *  M - 被打脸的潇洒哥（规律）

# A - 送气球.jpg（签到） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/318/A][https_ac.nowcoder.com_acm_contest_318_A]

*  **思路：** 用一个二维数组标记某个队伍某个题目是否 AC 过，直接模拟即可。

**Code（C++）：**

#include <iostream>
    #include <cstring>
    using namespace std;
    int vis[55][30],ans[55];
    int x,n,m;
    char y;
    string z;
    int main(){ 
        int t;    cin>>t;
        for(int i=1;i<=t;i++){ 
            memset(vis,0,sizeof(vis));
            memset(ans,0,sizeof(ans));
            cin>>n>>m;
            while(m--){ 
                cin>>x>>y>>z;
                if(z=="AC" && !vis[x][y-'A'+1]){ 
                    ans[x]++;
                    vis[x][y-'A'+1]=1;
                }
            }
            cout<<"Case #"<<i<<':'<<endl;
            for(int j=1;j<=n;j++)
                cout<<ans[j]<<' ';
            cout<<endl;
        }
    }

# B - 签到题（思维 + 暴力） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/318/B][https_ac.nowcoder.com_acm_contest_318_B]

*  **思路：** 枚举每一个元素作为左边界，然后再一层循环寻找右边界。用一个变量表示要寻找的区间内最大的数 maxn 。如果是第二层循环里的数比左边的数小就直接退出，表示后面已经不符合情况了。如果比最大数大就不断更新最大数以及最大区间长度。

**Code（C++）：**

#include <iostream>
    using namespace std;
    int a[1010];
    int main(){ 
        int t;    cin>>t;
        while(t--){ 
            int n;    cin>>n;
            for(int i=1;i<=n;i++)
                cin>>a[i];
            int ans=0;
            for(int i=1;i<=n;i++){ 
                int maxn=a[i];
                for(int j=i+1;j<=n;j++){ 
                    if(a[j]<a[i])    break;
                    if(a[j]>maxn){ 
                        maxn=a[j];
                        ans=max(ans,j-i);
                    }
                }
            }
            cout<<ans<<endl;
        }
        return 0;
    }

# D - 远神的高精度（大数） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/318/D][https_ac.nowcoder.com_acm_contest_318_D]

*  **思路：** 直接调用 Java 大数类可以直接输出小数点后所要求的位数，以及向下取整，四舍五入。

**Code（Java）：**

import java.util.*;
    import java.math.*;
    public class Main{ 
        public static void main(String[] args){ 
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){ 
                BigDecimal a = in.nextBigDecimal();
                BigDecimal b = in.nextBigDecimal();
                int n = in.nextInt();
                String str = in.next();
                if(str.compareTo("Xiang")==0)
                    System.out.println(a.divide(b,n,BigDecimal.ROUND_FLOOR));
                else
                    System.out.println(a.divide(b,n,BigDecimal.ROUND_HALF_UP));
            }
        }
    }

# G - LLLYYY的数字思维（思维） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/318/G][https_ac.nowcoder.com_acm_contest_318_G]

*  **思路：** 这道题就是要求将一个数拆成两个，使其各个位数之和尽可能大，那么就得尽可能使其有一个数含有很多个 9 ，比如 25500 = 9999 + 15501，所以问题的难点就是怎么找出像9999这样的数，可以先求出输入的数的位数减 1 ，然后取 10 的幂，再减1，即 pow(10,num ( c )-1)-1 。

**Code（C++）：**

#include <iostream>
    #include <cmath>
    using namespace std;
    typedef long long ll;
    ll f(ll x){     //计算输入的数各个位的数之和
        int tmp = 0;
        while(x){ 
            tmp += x % 10;
            x /= 10;
        }
        return tmp;
    }
    ll num(ll x){     //计算输入的数的位数
        ll sum=0;
        while(x){ 
            sum++;
            x/=10;
        }
        return sum;
    }
    int main(){ 
        ll c; 
        while(cin>>c){ 
            if(c<=10)    cout<<c<<endl;
            else{ 
                ll a=pow(10,num(c)-1)-1;
                ll b=c-a;
                cout<<f(a)+f(b)<<endl;
            }
        }
        return 0;
    }

# J - 王者荣耀（动态规划） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/318/J][https_ac.nowcoder.com_acm_contest_318_J]

*  **思路：** 01背包模板题。以时间间隔作为背包容量，熟练度作为物品价值。

**Code（C++）：**

#include <iostream>
    #include <algorithm>
    #define ll long long
    using namespace std;
    ll l[1010],v[1010],dp[1010];
    int main(){ 
        ll n,s,t;    cin>>n>>s>>t;
        ll m=t-s,a,b;
        for(int i=1;i<=n;i++){ 
            cin>>a>>b>>v[i];
            l[i]=b-a;
        }
        for(int i=1;i<=n;i++)
            for(int j=m;j>=l[i];j--)
                dp[j]=max(dp[j],dp[j-l[i]]+v[i]);
        cout<<dp[m]<<endl;
        return 0;
    }

# K - 三角形（贪心） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/318/K][https_ac.nowcoder.com_acm_contest_318_K]

*  **思路：** 对于每一个要取走的木棍，忽略它，没取走的存入一个新的数组，然后从小到大排序，从后面遍历，如果存在小的两根木棍之和大于大的那根，则跳出循环并输出答案。注意答案要初始化为 -1。

**Code（C++）：**

#include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int N=2010;
    typedef long long ll;
    ll a[N],b[N];
    int main(){ 
        int t;    cin>>t;
        for(int k=1;k<=t;k++){ 
            memset(a,0,sizeof(a));
            int n,q;    cin>>n>>q;
            for(int i=1;i<=n;i++)
                cin>>a[i];
            cout<<"Case #"<<k<<":"<<endl;
            while(q--){ 
                memset(b,0,sizeof(b));
                int x;    cin>>x;
                int cnt=0;
                for(int i=1;i<=n;i++){ 
                    if(i==x)    continue;
                    b[++cnt]=a[i];
                }
                sort(b+1,b+1+cnt);
                ll ans=-1;
                for(int i=cnt;i>=3;i--){ 
                    if(b[i-2]+b[i-1]>b[i]){ 
                        ans=max(ans,b[i]+b[i-1]+b[i-2]);
                        break;
                    }
                }
                cout<<ans<<endl;
            }
        }
        return 0;
    }

# L - 彪神666（模拟） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/318/L][https_ac.nowcoder.com_acm_contest_318_L]

*  **思路：** 写一个函数，判断一个数是否能被6整除，或者它的十进制表示法中是否存在某位上的数字为 6 。注意要用 long long 型，包括 for 循环里面的 i 也要用 long long 型的。

**Code（C++）：**

#include <iostream>
    #define ll long long
    using namespace std;
    bool check(ll x){ 
        int vis1=1,vis2=1;
        if(x%6==0)    vis1=0;
        while(x){ 
            if(x%10==6)    vis2=0;
            x/=10;
        }
        if(vis1 && vis2)    return false;
        return true;
    }
    int main(){ 
        int t;    cin>>t;
        while(t--){ 
            ll n;    cin>>n;
            ll ans=0;
            for(ll i=1;i<=n;i++){ 
                if(!check(i))
                    ans+=i*i;
            }
            cout<<ans<<endl;
        }
        return 0;
    }

# M - 被打脸的潇洒哥（规律） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/318/M][https_ac.nowcoder.com_acm_contest_318_M]

*  **思路：** 这道题的两两相交就是任意两个圆都要相交，但任意两个圆之间要有两个交点，然后就可以发现，划分出来的区域就是以2、4、6、8、10… 一直递增，规律式就是 n\*(n-1)+2 ，同时要特判 n==0 时，区域是 1。

**Code（C++）：**

#include <iostream>
    using namespace std;
    int main(){ 
        int t;    cin>>t;
        while(t--){ 
            int n;    cin>>n;
            if(n==0)    cout<<1<<endl;
            else    cout<<n*(n-1)+2<<endl;
        }
        return 0;
    }

[https_ac.nowcoder.com_acm_contest_318_A]: https://ac.nowcoder.com/acm/contest/318/A
[https_ac.nowcoder.com_acm_contest_318_B]: https://ac.nowcoder.com/acm/contest/318/B
[https_ac.nowcoder.com_acm_contest_318_D]: https://ac.nowcoder.com/acm/contest/318/D
[https_ac.nowcoder.com_acm_contest_318_G]: https://ac.nowcoder.com/acm/contest/318/G
[https_ac.nowcoder.com_acm_contest_318_J]: https://ac.nowcoder.com/acm/contest/318/J
[https_ac.nowcoder.com_acm_contest_318_K]: https://ac.nowcoder.com/acm/contest/318/K
[https_ac.nowcoder.com_acm_contest_318_L]: https://ac.nowcoder.com/acm/contest/318/L
[https_ac.nowcoder.com_acm_contest_318_M]: https://ac.nowcoder.com/acm/contest/318/M