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

左手的ㄟ右手 2022-11-26 11:59 161阅读 0赞

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

### 整体分析： ###

签到题：A、F、B、G、C 、H

简单题：D、I

正常题：E、J

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

### A：Num ###

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

#### 题意 ####

编一程序，输入正整数N（N在2～32767之间）， 求它的最大质因子（包括它本身）。

#### 题解 ####

直接遍历它的因子，因为求最大，所以从它本身往前开始遍历相对会更优的，当遇到既是它的因子又刚好是质数的话，则：输出，并跳出循环。

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

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const int inf=0x3f3f3f3f;
    int check(int x){
        
        for(int i=2;i<=x/2;i++){
        
            if(x%i==0) return 0;
        }
        return 1;
    }
    int main(){
        
        int n;
        scanf("%d",&n);
        for(int i=n;i>=2;i--){
        
            if(check(i)&&n%i==0){
        
                printf("%d\n",i);break;
            }
        }
        return 0;
    }

### F：up ###

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

#### 题意 ####

某高楼有n阶楼梯，上楼时，可以一步上一个阶，也可以一步上二阶。编一程序，从输入n（1<=n<=20）值，然后求出所有的上楼的不同方案数。

#### 题解 ####

n < = 2 ： f \[ 1 \] = 1 , f \[ 2 \] = 2 ; n > 2 ： f \[ n \] = f \[ n − 1 \] + f \[ n − 2 \] n<=2：f\[1\]=1,f\[2\]=2;\\\\ n>2：f\[n\]=f\[n-1\]+f\[n-2\] n<=2：f\[1\]=1,f\[2\]=2;n>2：f\[n\]=f\[n−1\]\+f\[n−2\]

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

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const int inf=0x3f3f3f3f;
    int f[25];
    int main(){
        
        f[1]=1,f[2]=2;
        int n;
        scanf("%d",&n);
        if(n<=2){
        
            printf("%d\n",f[n]);
        }else{
        
            for(int i=3;i<=n;i++){
        
                f[i]=f[i-1]+f[i-2];
            }
            printf("%d\n",f[n]);
        }
        return 0;
    }

### B：Words ###

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

#### 题意 ####

编写程序，读入一行文本，文本是一个长度不超过255的英文句子，单词之间有一个或一个以 上的空格，输出： ①统计单词的个数； ②一个对应的英文句子，其中原句中的所有小写字母均转换成大写字母，大写字母转换成小写字母； ③删除所有空格符后对应的句子。

#### 题解 ####

直接模拟即可，需要注意的是可能有多个空格，而且可能第一个字符就是空格。

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

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const int inf=0x3f3f3f3f;
    string s,ss;
    int main(){
        
        getline(cin,s);
        int len=s.length();
        int cnt=0;
        ss="";
        for(int i=0;i<len;i++){
        
            if(s[i]==' '){
        
                while(s[i]==' ') i++;
                i--;
                cnt++;
            }else{
        
                ss+=s[i];
            }
        }
        if(s[0]==' ') cnt--;
        if(s[len-1]!=' ') cnt++;
        printf("%d\n",cnt);
        for(int i=0;i<len;i++){
        
            if(s[i]>='a'&&s[i]<='z') s[i]-=32;
            else if(s[i]>='A'&&s[i]<='Z') s[i]+=32;
        }
        cout<<s<<'\n';
        cout<<ss<<'\n';
        return 0;
    }

### G：bag ###

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

#### 题意 ####

一个旅行者有最多能装m(0<m<=30)公斤的背包，现在有n(0<n<=20)件物品，它们的重量分别为W1，W2，…，Wn，它们的价值分别为C1，C2，…，Cn，求旅行者应选取哪几种物品装入背包，使包内的物品的总价值最大。若无法选取，则输出“NO ANSWER！”。

#### 题解 ####

裸0-1背包，不会的同学好好明天好好听晖晖学长的课（hhh）

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

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const int inf=0x3f3f3f3f;
    int w[35],v[25],dp[35];
    int n,m;
    int main(){
        
        scanf("%d%d",&m,&n);
        for(int i=1;i<=n;i++) scanf("%d",&w[i]);
        for(int i=1;i<=n;i++) scanf("%d",&v[i]);
        for(int i=1;i<=n;i++){
        
            for(int j=m;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
        printf("%d\n",dp[m]);
        return 0;
    }

代码是空间O(n)的优化版

### C：Jophs ###

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

#### 题意 ####

编号为1、2、3、…、n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。从指定编号 为1的人开始，按顺时针方向自1开始报数，报到指定值m时停止报数，报第m的人出列，并将他的密码作 为新的m值，从他在顺时针方向的下一个人开始，重新从1开始报数，如此类推，直至所有的人全部出列 为止。输入n（n<=1000），m（m<=30000）及密码值（<=10000），试设计一个程序求出列顺序 。

#### 题解 ####

类似于约瑟夫环，可以直接用数组模拟，当然vector等容器模拟也是完全没问题的。

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const int inf=0x3f3f3f3f;
    int a[1010],vis[1010],n,m;
    vector<int>ve;
    int main(){
        
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        int cnt=0;ve.clear();
        for(int i=1;i<=n;i++){
        
            if(ve.size()==n-1){
        
                for(int j=1;j<=n;j++) if(!vis[j]) ve.push_back(j);
                break;
            }
            if(!vis[i]){
        
                cnt++;
                if(cnt==m){
        
                    m=a[i];vis[i]=1;ve.push_back(i);cnt=0;
                }
            }
            if(i==n) i=0;
        }
        for(int i=0;i<ve.size();i++){
        
            if(i==0) printf("%d",ve[i]);
            else printf(" %d",ve[i]);
        }
        printf("\n");
        return 0;
    }

### H：hunan ###

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

#### 题意 ####

有一个含有N×N(N<=20)的大写字母方阵，试编程找出其中隐含的所有“HUNAN”字样，五个字母只能以上下左右方向连续.

#### 题解 ####

搜索裸题，比我之前在vjudge的基础题还要简单。

遍历整个字符矩阵，当遍历到的字符恰好为’H’时，进行深搜，当遍历的连续5个字符恰好为"HUNAN"时，则个数加一，最后输出总个数即可。

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

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const int inf=0x3f3f3f3f;
    char mp[25][25];
    int vis[25][25],dir[4][2]={
        -1,0,1,0,0,-1,0,1},n,ans;
    string s="HUNAN";
    void dfs(int x,int y,int now){
        
        if(now==5){
        
            ans++;return ;
        }
        for(int i=0;i<4;i++){
        
            int fx=x+dir[i][0];
            int fy=y+dir[i][1];
            if(fx>=1&&fx<=n&&fy>=1&&fy<=n&&vis[fx][fy]==0&&mp[fx][fy]==s[now]){
        
                vis[fx][fy]=1;
                dfs(fx,fy,now+1);
                vis[fx][fy]=0;
            }
        }
    }
    int main(){
        
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
        
            scanf("%s",mp[i]+1);
        }
        ans=0;
        for(int i=1;i<=n;i++){
        
            for(int j=1;j<=n;j++){
        
                if(mp[i][j]=='H'){
        
                    memset(vis,0,sizeof(vis));vis[i][j]=1;
                    dfs(i,j,1);
                }
            }
        }
        if(ans==0) printf("NO ANSWER!\n");
        else printf("%d\n",ans);
        return 0;
    }

### D：cover ###

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

#### 题意 ####

给定x轴上的N（0<N<100）条线段，每个线段由它的二个端点ai和bi确定，i=1,2,……N.这些坐标都是区间（－999，999）的整数。有些线段之间会相互交叠或覆盖。请你编写一个程序，从给出的线段中去掉尽量少的线段，使得剩下的线段两两之间没有内部公共点。所谓的内部公共点是指一个点同时属于两条线段且至少在其中一条线段的内部（即除去端点的部分）。

#### 题解 ####

贪心，大家的贪心策略大部分都比我的好，但是这里还是讲下最容易想到的。

由于要使得剩下的线段没有内部公共点，于是我们优先删除公共点最多的线段，直到所有线段都没内部公共点时，则结束。可以开一个数组用来表示每个线段的公共内部点个数，同时将每条线段缩点，进而线段之间构成一无向图，然后按照刚刚所说的贪心策略解即可，具体见代码。

这个贪心策略还是很好想到，但是并不是最优的。正如开头所说，大部分AC的代码都比我的要优。

tip：注意输入的线段，并不是按照起点在前、终点在后的顺序，所以需要预处理。

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

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const int inf=0x3f3f3f3f;
    int n,mp[110][110],deg[110];     //deg[]用来存每条线段与其他线段存在内部公共点的线段条数
    struct node{
        
        int l,r;
    };
    node a[110];
    int check(node x,node y){
        
        if(x.l>y.l&&x.l<y.r) return 1;
        if(x.r>y.l&&x.r<y.r) return 1;
        if(y.l>x.l&&y.l<x.r) return 1;
        if(y.r>x.l&&y.r<x.r) return 1;
        if(x.l==y.l&&x.r==y.r) return 1;
        return 0;
    }
    int main(){
        
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
        
            scanf("%d%d",&a[i].l,&a[i].r);
            if(a[i].l>a[i].r) swap(a[i].l,a[i].r);
        }
        for(int i=1;i<=n;i++){
        
            for(int j=i+1;j<=n;j++){
        
                if(check(a[i],a[j])){
        
                    mp[i][j]=mp[j][i]=1,deg[i]++,deg[j]++;
                }
            }
        }
        int cnt=0;
        while(1){
        
            int maxnum=deg[1],pos=1;
            for(int i=2;i<=n;i++){
        
                if(deg[i]>maxnum) maxnum=deg[i],pos=i;
            }
            if(maxnum==0) break;
            for(int i=1;i<=n;i++){
        
                if(mp[pos][i]){
        
                    mp[pos][i]=mp[i][pos]=0,deg[i]--;
                }
            }
            deg[pos]=0,cnt++;
        }
        printf("%d\n",n-cnt);
        return 0;
    }

### I：oil ###

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

#### 题意 ####

设有大小不等的３个无刻度的油桶，分别能盛满X、Y、Z(都小于等于100)升油，初始时第一个油桶盛满，另外两个为空。现在，要想在某一瓶中分出T升油。分油时可把一个桶里的油倒入另外的桶中，或者将桶中的油倒空。设计一种以最少步骤的分油方案。

#### 题解 ####

比较简单的搜索题。没有思维，只不过搜索过程代码会稍许有点长，但相比之前在vjudge安排的题目而言，还是比较简单的。

由于要求最少步骤，所以优先考虑用bfs。对于每一状态我们有9种方案：

1.  瓶1—>瓶2，（如果不足以装满瓶2，则瓶1空，瓶2容量为两者之和；如果能装满瓶2，则瓶2满，瓶1容量减去倒入瓶2的）
2.  瓶1—>瓶3，与瓶1倒入瓶2类似
3.  瓶1倒空
4.  瓶2—>瓶1，与瓶1倒入瓶2类似
5.  瓶2—>瓶3，与瓶1倒入瓶2类似
6.  瓶2倒空
7.  瓶3—>瓶1，与瓶1倒入瓶2类似
8.  瓶3—>瓶2，与瓶1倒入瓶2类似
9.  瓶3倒空

于是直接按照这个思路搜索即可，每个结点存储当前三个瓶子的容量状况。

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

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const int inf=0x3f3f3f3f;
    int x,y,z,maxx,maxy,maxz,t,ans;
    int vis[110][110][110];
    struct node{
        
        int x,y,z,step;
        node(int xx,int yy,int zz,int d){
        
            x=xx,y=yy,z=zz,step=d;
        }
    };
    void bfs(){
        
        queue<node>q;
        q.push(node(x,y,z,0));vis[x][y][z]=1;
        while(!q.empty()){
        
            node now=q.front();q.pop();
            if(now.x==t||now.y==t||now.z==t){
        
                ans=now.step;break;
            }
            //cout<<now.x<<' '<<now.y<<' '<<now.z<<endl;
            int fx,fy,fz;
            //1->2
            if(now.x>=(maxy-now.y)) fx=now.x-(maxy-now.y),fy=maxy;
            else fx=0,fy=now.y+now.x;
            fz=now.z;
            if(!vis[fx][fy][fz]) vis[fx][fy][fz]=1,q.push(node(fx,fy,fz,now.step+1));
            //1->3
            if(now.x>=(maxz-now.z)) fx=now.x-(maxz-now.z),fz=maxz;
            else fx=0,fz=now.z+now.x;
            fy=now.y;
            if(!vis[fx][fy][fz]) vis[fx][fy][fz]=1,q.push(node(fx,fy,fz,now.step+1));
            //1->0
            fx=0,fy=now.y,fz=now.z;
            if(!vis[fx][fy][fz]) vis[fx][fy][fz]=1,q.push(node(fx,fy,fz,now.step+1));
     
            //2->1
            if(now.y>=(maxx-now.x)) fx=maxx,fy=now.y-(maxx-now.x);
            else fx=now.x+now.y,fy=0;
            fz=now.z;
            if(!vis[fx][fy][fz]) vis[fx][fy][fz]=1,q.push(node(fx,fy,fz,now.step+1));
            //2->3
            if(now.y>=(maxz-now.z)) fy=now.y-(maxz-now.z),fz=maxz;
            else fy=0,fz=now.z+now.y;
            fx=now.x;
            if(!vis[fx][fy][fz]) vis[fx][fy][fz]=1,q.push(node(fx,fy,fz,now.step+1));
            //2->0
            fx=now.x,fy=0,fz=now.z;
            if(!vis[fx][fy][fz]) vis[fx][fy][fz]=1,q.push(node(fx,fy,fz,now.step+1));
     
            //3->1
            if(now.z>=(maxx-now.x)) fx=maxx,fz=now.z-(maxx-now.x);
            else fx=now.x+now.z,fz=0;
            fy=now.y;
            if(!vis[fx][fy][fz]) vis[fx][fy][fz]=1,q.push(node(fx,fy,fz,now.step+1));
            //3->2
            if(now.z>=(maxy-now.y)) fy=maxy,fz=now.z-(maxy-now.y);
            else fy=now.y+now.z,fz=0;
            fx=now.x;
            if(!vis[fx][fy][fz]) vis[fx][fy][fz]=1,q.push(node(fx,fy,fz,now.step+1));
            //3->0
            fx=now.x,fy=now.y,fz=0;
            if(!vis[fx][fy][fz]) vis[fx][fy][fz]=1,q.push(node(fx,fy,fz,now.step+1));
        }
    }
    int main(){
        
        scanf("%d%d%d",&maxx,&maxy,&maxz);
        scanf("%d",&t);
        x=maxx,y=0,z=0;
        ans=0;memset(vis,0,sizeof(vis));
        bfs();
        if(ans==0) printf("NO ANSWER!\n");
        else printf("%d\n",ans);
        return 0;
    }

代码只不过是写的有点紧凑，并不是很夸张。

### E：fan ###

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

#### 题意 ####

有一个圆，当输入一个整数n(1≤n≤10)后，它被分成n个扇区，请你为每一扇区选择一个自然数(大于0的整数)。

向各个扇区放入数之后，你可以从单个扇区中选出一个数，也可以从相邻的两个或多个扇区中各选一个数，相加后形成一个新的数，请使用这些整数形成一个连续的整数序列：1，2，3，…，i，你的任务是使i尽可能地大。

#### 题解 ####

首先，需要知道一个结论（或者叫规律）：

在n个扇区中填好数字，可以有 n\*(n-1)+1 种和，所以最大连续数的上界为 n\*(n-1)+1

这题原型是n<=6,知道上述结论（规律）之后，数字比较小，就可以考虑直接暴搜了。

想到这一步之后就解决90%了，当然这题似乎也并没有人走到这一步…

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

这题数据从原型的6改成了8，其中7是无解的，可以通过上述思路求出，然后8如果直接暴搜的话肯定是会超时的。于是可以对8单独输出。

当然如果正式比赛的话，建议所有情况都直接先在本地打表后，直接输出，不必像下面代码一样。这里只是让大家理解前面的数据用搜索的求法。

tip：需要注意由于是环形，所以需要对结果去重，具体见代码中map<string,int>ss的使用。

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

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const int inf=0x3f3f3f3f;
    int n,num;
    int a[200],sum[200],vis[200],mp[200],t;
    map<string,int>ss;
    int check(){
        
        memset(mp,0,sizeof(mp));
        for(int i=1;i<=n;i++) a[i+n]=a[i];
        sum[0]=0;
        for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i];
        for(int i=1;i<=n;i++){
        
            for(int j=i;j<=n+i-1;j++) mp[sum[j]-sum[i-1]]=1;
        }
        for(int i=1;i<=num;i++) if(!mp[i]) return 0;
        return 1;
    }
    void dfs(int cnt,int s){
        
        if(cnt==n+1){
        
            if(s==num&&check()){
        
                t++;
                string str="";
                for(int i=1;i<=n;i++) str+=a[i]+'0';
                sort(str.begin(),str.end());
                if(!ss[str]){
        
                    ss[str]=1;
                    for(int i=1;i<=n;i++){
        
                        if(i==1) printf("%d",a[i]);
                        else printf(" %d",a[i]);
                    }
                    printf("\n");
                }
            }
            return ;
        }
        for(int i=1;i<=num;i++){
        
            if(vis[i]||s+i>num) continue;
            vis[i]=1;a[cnt]=i;
            dfs(cnt+1,s+i);
            vis[i]=0;
        }
    }
    void solve(){
        
        printf("1 2 10 19 4 7 9 5\n");
        printf("1 3 5 11 2 12 17 6\n");
        printf("1 3 8 2 16 7 15 5\n");
        printf("1 4 2 10 18 3 11 8\n");
        printf("1 4 22 7 3 6 2 12\n");
        printf("1 6 12 4 21 3 2 8\n");
        return ;
    }
    int main(){
        
        scanf("%d",&n);
        num=n*(n-1)+1;
        printf("%d\n",num);
        if(n==8){
        
            solve();return 0;
        }
        t=0;a[1]=1;
        dfs(2,1);
        return 0;
    }

### J：Calc ###

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

#### 题意 ####

给定一个序列 a，a 中任意两个元素都不等。如果 i<j，且 a\[i\] < a\[j\]，则我们称 a\[i\],a\[j\] 为一个顺序对，这个顺序对的值是指 a\[i+1\],a\[i+2\],…,a\[j-1\] 中比 a\[i\] 大，且比 a\[j\] 小的数的个数。

求一个序列中所有顺序对的值的和。

#### 题解 ####

计算每一对点之间大于a\[i\]小于a\[j\]的话太费时，单枚举点对就不够时间

那可以转变为求每一个点左边小于它的和右边大于它的点对数

然后就是用树状数组或者线段树维护区间和了

下面用树状数组维护的区间和，一些操作均在代码中了。

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

#include<bits/stdc++.h>
    #define ll long long
    #define lowbit(x) x&(-x)
    using namespace std;
    const int maxn=3e5+5;
    const int inf=0x3f3f3f3f;
    int a[maxn],b[maxn],c[maxn],n;
    ll sum[maxn];
    void add(int x,int v){
        
        for(int i=x;i<=n;i+=lowbit(i)) c[i]+=v;
    }
    int querySum(int x){
        
        int ans=0;
        for(int i=x;i;i-=lowbit(i)) ans+=c[i];
        return ans;
    }
    int main(){
        
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
        
            scanf("%d",&a[i]);b[i]=a[i];
        }
        sort(b+1,b+n+1);
        int m=unique(b+1,b+n+1)-(b+1);
        for(int i=1;i<=n;i++){
        
            int x=lower_bound(b+1,b+m+1,a[i])-b;
            sum[i]=querySum(x-1);
            add(x,1);
        }
        memset(c,0,sizeof(c));
        for(int i=n;i>=1;i--){
        
            int x=lower_bound(b+1,b+m+1,a[i])-b;
            sum[i]=sum[i]*(n-i-querySum(x));
            add(x,1);
        }
        ll ans=0;
        for(int i=2;i<=n-1;i++) ans+=sum[i];
        printf("%lld\n",ans);
        return 0;
    }

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