2020年ACM集训队暑假热身赛2-题解

我不是女神ヾ 2022-11-28 00:49 115阅读 0赞

# 2020年ACM集训队暑假热身赛2-题解 #

## 整体分析 ##

签到题：I、D、H、F、A、E  
简单题：J、C  
正常题：G、B

**tip：以下题解按照难度排列**

## I：good ##

[**题目链接**][Link 1]

#### 题意 ####

输入一段短文，统计其中包含多少个good，不区分单词的大小写。

#### 题解 ####

首先直接将字符串全都转化为小写（或大写），然后在遍历整个字符串判断是否有"good"即可。

部分同学这题wa那么多发还是有点不应该，hhh

#### AC代码（cpp） ####

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll inf=1e18;
    char s[1010];
    int main() {
        
        while(gets(s+1)) {
        
            int len=strlen(s+1);
            int ans=0;
            for(int i=1; i<=len; i++) s[i]=tolower(s[i]);
            for(int i=1; i<=len; i++) {
        
                if(s[i]=='g'&&s[i+1]=='o'&&s[i+2]=='o'&&s[i+3]=='d') {
        
                    ans++;
                    i+=3;
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

## D：Shang ##

[**题目链接**][Link 2]

#### 题意 ####

编一个程序求A/B的值，要求精确到小数点后N位（N<=80的自然数，并且A<B，A和B是整型  
数范围），不足N位的用“0”补齐。例如：精确到小数点后9位：6/7＝0.857142857。输入A、B、N，  
求A/B。

#### 题解 ####

模拟除法。如果考虑直接用double存结果的话肯定是不行的，因为double也就只能存15位精确小数，于是我们直接对除法模拟，具体见代码。

#### AC代码（cpp） ####

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll inf=1e18;
    int a,b,n;
    int main(){
        
        scanf("%d%d%d",&a,&b,&n);
        printf("0.");
        while(n--){
        
            a*=10;
            printf("%d",a/b);
            a%=b;
        }
        printf("\n");
        return 0;
    }

## H：find ##

[**题目链接**][Link 3]

#### 题意 ####

从N个数中找出其和为M的若干数。从文件中读入正整数M和N及N个整数（都小于M），在这N个数中找出若干数，使它们的和是M，把满足条件的数组都找出来，并统计个数。其中M<=1000，N<=30。

#### 题解 ####

动态规划。只需要找到和为M，于是可以直接对这n个数进行0-1背包，具体见代码。

#### AC代码（cpp） ####

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll inf=1e18;
    int dp[1010],a[35];
    int main(){
        
        int m,n;
        scanf("%d%d",&m,&n);
        dp[0]=1;
        for(int i=1;i<=n;i++){
        
            scanf("%d",&a[i]);
            for(int j=m;j>=a[i];j--) dp[j]+=dp[j-a[i]];
        }
        if(dp[m]) printf("%d\n",dp[m]);
        else printf("NO ANSWER!\n");
        return 0;
    }

## F：storage ##

[**题目链接**][Link 4]

#### 题意 ####

磁带等存储介质存储信息时基本上都是一种线性存储的方式，线性存储方式虽然简单，但查询检索时往往要经过一些其它信息，不象磁盘等存储介质在目录区找到后可直接定位到某一区域，因此线性存储总有它的局限性。但是由于磁带等线性存储有简单、保存时间相对较长等优点，现在仍然在使用。

如果有n段信息资料要线性存储在某种存储介质上，它们的长度分别是L1，L2,…，Ln，存储介质能够保存下所有这些信息，假设它们的使用(查询检索)的频率分别是F1，F2，…，Fn，要如何存储这些信息资料才能使平均检索时间最短。

你的任务就是编程安排一种平均检索时间最短的方案。

#### 题解 ####

这题其实很简单，但是居然没有人开这题…

由于需要求平均检索时间最短，那当然（长度\*使用频率）最大的应该排在最前面。于是直接贪心排下序即可。

但是需要注意：快排是不稳定排序，如果自定义排序函数的话是会wa的，如果重载运算符是没问题的。为了保险起见，还是建议用稳定排序，虽然时间复杂度会比像快速排序、归并排序这个高效算法要大点。

#### AC代码（cpp） ####

**稳定排序（冒泡排序）解法**

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll inf=1e18;
    struct node{
        
        int num,cnt;
    };
    node a[10010];
    int main(){
        
        int n;
        scanf("%d",&n);
        int len,bit;
        for(int i=1;i<=n;i++){
        
            scanf("%d%d",&len,&bit);
            a[i].num=len*bit;a[i].cnt=i;
        }
        for(int i=1;i<=n;i++){
        
            for(int j=1;j<=n-i+1;j++){
        
                if(a[j].num<a[j+1].num){
        
                    swap(a[j],a[j+1]);
                }
            }
        }
        for(int i=1;i<=n;i++){
        
            if(i==1) printf("%d",a[i].cnt);
            else printf(" %d",a[i].cnt);
        }
        printf("\n");
        return 0;
    }

**重载运算符写法（晖晖学长代码）**

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const int inf=0x3f3f3f3f;
    struct node{
        
        int v,id;
        bool operator<(const node p)const{
        
            if(v!=p.v)return v>p.v;
            return id<p.id;
        }
    }w[maxn];
    int main(){
        
        int n,a,b;
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
        
            scanf("%d %d",&a,&b);
            w[i].v=a*b;
            w[i].id=i;
        }
        sort(w+1,w+n+1);
        for(int i=1;i<=n;++i){
        
            printf("%d%c",w[i].id,i==n?'\n':' ');
        }
        return 0;
    }

## A：Root ##

[**题目链接**][Link 5]

#### 题意 ####

一个正整数的数字的乘积N 的定义是：这个整数中非零数字的乘积。例如，整数999的数字乘积为9×9×9，即729。729的数字乘积 为7×2×9， 即126。126的数字乘积为1×2×6，即12。12的数字乘积为1×2，即2。一个正整数的数字乘积根N是 这样得到的：反复取该整数的数字乘积， 直到得到一位数字为止。例如，在上面的例子中数字的乘积根是2。 编一个程序，输入一个正整数（长度不超过200位数字）， 输出计算其数字乘积根的每一步结果。

#### 题解 ####

直接按照题意模拟即可，唯一难点可能是高精度问题。但是Java or Python 它不香嘛。

#### AC代码（java && cpp） ####

**Java BigInteger解法**

import java.math.BigInteger;
    import java.util.*;
     
    public class Main {
        
        public static void main(String args[]) {
        
            Scanner scan=new Scanner(System.in);
            BigInteger n=scan.nextBigInteger();
            while(n.compareTo(BigInteger.valueOf(10))>=0){
        
                BigInteger num=BigInteger.valueOf(1);
                while(n.compareTo(BigInteger.valueOf(0))>0){
        
                    BigInteger x=n.mod(BigInteger.valueOf(10));
                    if(x.compareTo(BigInteger.valueOf(0))!=0) num=num.multiply(x);
                    n=n.divide(BigInteger.valueOf(10));
                }
                n=num;
                System.out.println(n);
            }
        }
    }

**C++数组存大整数（晖晖学长代码）**

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e6+5;
    const int inf=0x3f3f3f3f;
    char s[205];
    int x[205],y[205],lx,ly;
    void mul(int p){
        
        for(int i=1;i<=ly;++i)y[i]*=p;
        for(int i=1;i<=ly;++i){
        
            y[i+1]+=y[i]/10;
            y[i]%=10;
        }
        while(y[ly+1]){
        
            ++ly;
            y[ly+1]+=y[ly]/10;
            y[ly]%=10;
        }
    }
    int main(){
        
        scanf("%s",s+1);
        int ls=strlen(s+1);
        for(int i=ls;i>=1;--i)x[ls-i+1]=s[i]-'0';
        lx=ls;
        while(1){
        
            memset(y,0,sizeof(y));
            ly=1,y[1]=1;
            for(int i=1;i<=lx;++i)if(x[i])mul(x[i]);
            for(int i=ly;i>=1;--i)printf("%d",y[i]);
            putchar('\n');
            memset(x,0,sizeof(x));
            lx=ly;
            for(int i=1;i<=lx;++i)x[i]=y[i];
            if(ly==1)break;
        }
    }

## E：word ##

[**题目链接**][Link 6]

#### 题意 ####

输入一个含有括号的四则运算表达式，可能含有多余的括号，编程整理该表达式，去掉所有多余的括号，原表达式中所有变量和运算符号相对位置保持不变，并保持与原表达式等价。  
输入表达式 输出表达式  
a+(b+c) a+b+c  
(a\* b)+c/(d\* e) a\* b+c/(d\* e)  
a+b/(c-d) a+b/(c-d)  
a-(b+c) a-(b+c)  
注意：输入为a+b时，输出不能是b+a，即相对位置不能变。表达式以字符串输入，长度不超过255，不需要对输入表达式判断是否格式正确（即，程序应该默认输入表达式是格式正确的），所有变量均为单个小写字母，只要去掉所有多余括号，不要求对表达式简化。

#### 题解 ####

一道中等难度的模拟题。其实也并不是很难。

以下几种情况是不能删除的：

1.  括号前面是"-" ，括号中为"+" 或者 “-”
2.  括号前面是"/"
3.  括号后面是"\*"，括号中是"+" 或者 “-”

#### AC代码（cpp） ####

我代码写的有点丑，贴一份网上大佬的代码…

#include<stdio.h>
    
    //检测括号是否可以删除
    int check(char s[], int left, int right)
    {
        
        int i;            //下标
        int leftCount;    //左括号统计
    
        //处理 ' -(a +|- b) '
        if (s[left-1] == '-')
        {
        
            i = left;
            leftCount = 1;
            while (++i < right) {
        
                if (s[i] == '(')
                {
        
                    leftCount++;
                }
                else if ((s[i] == '+' || s[i] == '-' ) && leftCount == 1)
                {
        
                    return 0;
                }
            }
        }
    
        //处理 ' /(a +|-|*|/ b) '
        if (s[left-1] == '/')
        {
        
            return 0;
        }
    
        //处理 ' +(a +|-|*|/ b) +|- '
        if (s[left-1] != '*' && s[left-1] != '/' &&
            s[right+1] != '*' && s[right+1] != '/')
        {
        
            return 1;
        }
    
        //处理 ' *(a *|/ b) +|-|*|/ '
        i = left;
        leftCount = 1;
        while (++i < right) {
        
            if (s[i] == '(')
            {
        
                leftCount++;
            }
            else if ((s[i] == '*' || s[i] == '/' ) && leftCount == 1)
            {
        
                return 1;
            }
        }
        return 0;
    }
    
    //删除多余的括号
    int delExcessBrackets(char s[], int index)
    {
        
        int left, right;
        while (s[index] != '\0') {
        
            if (s[index] == ')')     //如果为右括号，返回下标
            {
        
                return index;
            }
            if (s[index] == '(')     //如果为左括号，找到右括号的下标
            {
        
                left = index;
                index = right =  delExcessBrackets(s, index+1);
    
                if (check(s, left, right))    //若检测结果为可以删除，那么把括号位置换成空
                {
        
                    s[left] = s[right] = ' ';
                }
            }
            index++;
        }
    }
    
    int main()
    {
        
        char exp[256];
        scanf("%s", exp);
    
        delExcessBrackets(exp, 0);
    
        int i = -1;
        while (exp[++i] != '\0') {
        
            if (exp[i] != ' ')
            {
        
                printf("%c", exp[i]);
            }
        }
    
        return 0;
    }

## J：prime ##

[**题目链接**][Link 7]

#### 题意 ####

回文素数是指一个素数同时又是一个回文数。请编写一个程序，统计指定区间中包含多少个回文素数。

#### 题解 ####

看到数据范围后，应该想到预处理的（也就是打表，当然我看到一位同学直接是把所有结果保存到数组里面的，这也太厉害了，哈哈哈，这大可不必）

这题本意是打算考下小思维+六素数法判素数的，但是这样处理的话，时间复杂度比一部分AC代码的时间复杂度还要高点。

--------------------

首先判断回文和判断素数间，我们优先判断回文。

判断回文我们可以先只考虑一边，例如：123->123321 或 12321，我们只考虑左边123，然后构造右边即可。

这样就只需对1~10000遍历即可。

接着判断该回文数是否为素数：采用六素数法。可以知道，除了2,3以外，其他所有素数都在6\*i(i为变量)的左右两侧。例如：5,7,11,13…用这个方法判断素数比普通判断素数方法，速度要快6倍。

知道这两个后，就可以预处理了。

#### AC代码（cpp） ####

#include<bits/stdc++.h>
    #include<stack>
    #define ll long long
    using namespace std;
    const int maxn=1e4;
    const int maxsize=1e8+5;
    const int inf=0x3f3f3f3f;
    bool vis[maxsize];
    ll getnum1(int x){
        
        ll num=x;
        while(x){
        
            num=num*10+x%10;
            x/=10;
        }
        return num;
    }
    ll getnum2(int x){
        
        ll num=x;x/=10;
        while(x){
        
            num=num*10+x%10;
            x/=10;
        }
        return num;
    }
    //六素数法判断素数
    int check(ll x){
        
        if(x<=3) return x>1;   //特判2,3
        if(x%2==0||x%3==0) return 0;
        if(x%6==1||x%6==5){
        
            for(int i=5;i*i<=x;i+=6){
        
                if(x%i==0||x%(i+2)==0) return 0;
            }
            return 1;
        }
        return 0;
    }
    //打表
    void init(){
        
        memset(vis,0,sizeof(vis));
        //先判断回文。枚举回文数左边，例如：123321->123,12321->123
        ll num;
        for(int i=1;i<maxn;i++){
        
            if(i>10000){
        
                num=getnum2(i);
                if(check(num)) vis[num]=1;
            }else{
        
                num=getnum1(i);
                //cout<<num<<endl;
                if(check(num)) vis[num]=1;
     
                num=getnum2(i);
                //cout<<num<<endl;
                if(check(num)) vis[num]=1;
     
            }
        }
    }
    int main(){
        
        //freopen("data/1.in","r",stdin);
        //freopen("data/1.out","w",stdout);
        init();
        int m,n;
        while(~scanf("%d%d",&m,&n)){
        
            int ans=0;
            for(int i=m;i<=n;i++){
        
                if(vis[i]) ans++;
            }
            printf("%d\n",ans);
        }
        return 0;
    }

## C：Number ##

#### 题意 ####

一个排列，求出了 a 数组，其中 ai 表示第 i个数左边有多少个数比它小。

计算出原来的排列。

#### 题解 ####

一道比较经典的线段树题目的改编。其实《算法竞赛入门到进阶》这本书85页有原题，建议看看。

当然这题除了线段树外，还可以用思维解，但是还是建议用线段树写，熟悉熟悉线段树。

#### AC代码 ####

**线段树解法（欧阳亨杰的代码）**

#include<bits/stdc++.h>
     
    using namespace std;
    int pre[100005],ans[100005];
    struct node
    {
        
        int l,r,len;//len是区间的数字个数
    };
    node tree[400020];
    void build(int l,int r,int rt)
    {
        
        tree[rt].l=l;
        tree[rt].r=r;
        tree[rt].len=r-l+1;
        if(l==r)
        {
        
            return ;
        }
        int mid=(l+r)/2;
        build(l,mid,rt*2);
        build(mid+1,r,rt*2+1);
    }
    int fun(int rt,int num)
    {
        
        tree[rt].len--;
        if(tree[rt].l==tree[rt].r)
            return tree[rt].l;
        if(tree[rt*2].len<num)
            return fun(rt*2+1,num-tree[rt*2].len);
        else if(tree[rt*2].len>=num)
            return fun(rt*2,num);
    }
    int main()
    {
        
        int n;
        while(~scanf("%d",&n))
        {
        
            for(int i=2;i<=n;i++)
                scanf("%d",&pre[i]);
            pre[1]=0;
            build(1,n,1);
            for(int i=n;i>=1;i--)
                ans[i]=fun(1,pre[i]+1);
            for(int i=1;i<=n;i++)
                printf("%d\n",ans[i]);
        }
        return 0;
    }

#### 思维解法 ####

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll inf=1e18;
    int a[maxn],b[maxn];
    int main(){
        
        int n;
        scanf("%d",&n);
        for(int i=2;i<=n;i++) scanf("%d",&a[i]);
        vector<int>ve;
        for(int i=1;i<=n;i++) ve.push_back(i);
        for(int i=n;i>=1;i--){
        
            b[i]=ve[a[i]];
            ve.erase(ve.begin()+a[i]);
        }
        for(int i=1;i<=n;i++){
        
            printf("%d\n",b[i]);
        }
        return 0;
    }

## G：stamp ##

#### 题意 ####

邮局发行一套票面有n(0<n<=10)种不同面值的邮票。若限每封信所贴的邮票张数不得超过m枚，存在整数r使得用不超过m(0<m<=2n)枚的邮票，可以贴出连续整数1，2，3，…，r值来，找出这种面值数，使得r值最大。

#### 题解 ####

看到这个数据范围后，还是可以往搜索方向想想的，但是这题考点思维，所以就有点小难了。

首先写一个getmaxnum()函数，来找出最大能拼出的数，然而要找到这个数，我们需要知道n种邮票分别是多少，这个过程就可以用dfs深搜。

另外我们需要几个辅助数组。a\[\]：保存每种邮票的面值；f\[\]：表示要凑出总值为i的最少需要的邮票数。具体深搜过程见代码。

#### AC代码（cpp） ####

#include<bits/stdc++.h>
    #include<stack>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const int inf=0x3f3f3f3f;
    int a[15],f[maxn];
    //a[i]:表示每种不同的面值邮票;f[i]:价值为i所需要的最少邮票数
    int n,m,ans;
    //最大能拼出来的数
    int getmaxnum(int n){
        
        f[0]=0;
        for(int i=1;;i++){
        
            f[i]=-1;
            for(int j=1;j<=n;j++){
        
                if(i-a[j]>=0&&f[i-a[j]]+1<=m&&(f[i]==-1||f[i-a[j]]+1<=f[i])) f[i]=f[i-a[j]]+1;
            }
            if(f[i]==-1) return i-1;
        }
    }
    void dfs(int now){
        
        if(now>n){
        
            int num=getmaxnum(n);
            if(num>ans) ans=num;
            return ;
        }
        for(int i=a[now-1]+1;i<=getmaxnum(now-1)+1;i++){
        
            a[now]=i;
            dfs(now+1);
        }
    }
    int main(){
        
        scanf("%d%d",&n,&m);
        a[1]=1;ans=0;
        dfs(2);
        printf("%d\n",ans);
    }

## B：Beautiful ##

[**题目链接**][Link 8]

#### 题意 ####

Mavis 有一个序列，对于每个数都有一个在序列中的优美值，这个优美值的定义是：找到序列中最长的一段，满足包含这个数并且这个数是这一段的中位数（以数值为第一关键字，下标为第二关键字排序, 这样的话这一段的长度只有可能是奇数），那么这一段的长度就是它的优美值。Mavis 说：“对于我每次手贱点出的左右端点 \[l, r\]，我都要找到 \[l,r\] 中的所有数中，最大的优美值”。

但是 Mavis 只会喊口号，不能解决问题，所以这个问题就交给你了。

#### 题解 ####

可能是全场最难的一道题了。首先由于有q次询问，如果每次询问都查询一次的话，肯定比较耗时的，于是可以预处理。

首先枚举左右端点，然后对每个区间取最大优美值，保存到数组中，最后查询时，取区间最大w\[i\]即可，具体见代码（有点小思维，需要自己理解）。

#### AC代码（cpp） ####

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const int inf=0x3f3f3f3f;
    int n,a[2010],l[4010],r[4010],w[2010];
    void init(){
        
        memset(w,0,sizeof(w));
        for(int i=1;i<=n;i++){
        
            memset(l,-1,sizeof(l));
            memset(r,-1,sizeof(r));
            l[n]=0,r[n]=0;
            int cnt=0;
            for(int j=i-1;j>=1;j--){
        
                if(a[j]>a[i]) cnt++;
                else cnt--;
                l[n+cnt]=i-j;
            }
            cnt=0;
            for(int j=i+1;j<=n;j++){
        
                if(a[j]>=a[i]) cnt++;
                else cnt--;
                r[n+cnt]=j-i;
            }
            for(int j=1-i;j<=i-1;j++){
        
                if(l[n-j]>=0&&r[n+j]>=0){
        
                    w[i]=max(w[i],l[n-j]+r[n+j]+1);
                }
            }
        }
    }
    int main(){
        
        //freopen("data/1.in","r",stdin);
        //freopen("data/1.out","w",stdout);
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
        
            scanf("%d",&a[i]);
        }
        init();
        int q,l,r;
        scanf("%d",&q);
        while(q--){
        
            scanf("%d%d",&l,&r);
            int ans=0;
            for(int i=l;i<=r;i++) ans=max(ans,w[i]);
            printf("%d\n",ans);
        }
        return 0;
    }

[Link 1]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1129&pid=8
[Link 2]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1129&pid=3
[Link 3]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1129&pid=7
[Link 4]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1129&pid=5
[Link 5]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1129&pid=0
[Link 6]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1129&pid=4
[Link 7]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1129&pid=9
[Link 8]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1129&pid=1