2022秋季体验营C++试题-解析

2022/9/14 1:19:14

本文主要是介绍2022秋季体验营C++试题-解析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 2022秋季体验营C++试题-解析
    • 小学C++组:
      • T271184 挑水(water)
      • T271196 挖竹笋(bamboo)
      • T271182 建房子(home)
    • 初中C++组
      • T273321 足球赛(football)
      • T273322 倒酒(pourwine)
      • T273323 玩具(toy)

2022秋季体验营C++试题-解析

题目我已经上传到洛谷了,点击问题即可跳转。

小学C++组:

T271184 挑水(water)

思路:最少次数,那每次挑水就要最多,选择最大的桶mx。

\(ans = ceil(1.0*m/(2*mx))\)

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,a[N],mx=-1;

int main() {
    freopen("water.in","r",stdin);
    freopen("water.out","w",stdout);
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=n; i++) {
        if(mx < a[i]) mx=a[i]; //最大桶
    }
    int ans=ceil(1.0*m/(2*mx));
    cout<<ans;
    fclose(stdin), fclose(stdout);
    return 0;
}

T271196 挖竹笋(bamboo)

思路:采过就标记,计数。
image

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int a[N][N],n,k,ans=0;

int main() {
    freopen("bamboo.in","r",stdin);
    freopen("bamboo.out","w",stdout);
    cin>>n>>k;
    for(int i=1; i<=k; i++) {
        int x1,x2,y1,y2; cin>>x1>>y1>>x2>>y2;
        for(int x=x1; x<=x2; x++) {
            for(int y=y1; y<=y2; y++) {
                if(!a[x][y]) a[x][y]=1, ans++;// 采摘
            }
        }
    }
    cout<<ans;
    fclose(stdin), fclose(stdout);
    return 0;
}

T271182 建房子(home)

思路:枚举答案[1,1000000],判断合理性

  1. 要求最大值,那么可以逆序枚举答案 x
  2. check(x):判断是否能生产 m 根长度为 x 的竹子。

但是这样发现复杂度较高:1e6*1e6, 所以我们需要一个 O(nlogn)的算法,于是二分答案就可以了。

image

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
int n,m,a[N],b[N];

int main() {
    freopen("home.in","r",stdin);
    freopen("home.out","w",stdout);
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i]>>b[i];
    int l=1, r=1e6; // 答案区间 [l,r]
    while(l<r) {
        int mid=(l+r+1)/2; LL num=0; // 注意 long long
        for(int i=1; i<=n; i++) num += a[i]/mid*b[i];
        if(num>=m) l=mid;
        else r=mid-1;
    }
    cout<<l;
    fclose(stdin), fclose(stdout);
    return 0;
}

初中C++组

本次初中组三道题目都很考察代码能力,都是属于模拟类型的题目,细节较多。

T273321 足球赛(football)

  • 思路:最终的得分以及平局都比较容易计算, 但是要注意(初始比分0:0 也算作一次打平)。

  • 球赛中最大的「翻盘」:翻盘一定是出现在平局之后的,判断每个平局后会不会翻盘,如果会,就左右查找连续胜利次数,也就是翻盘量。

#include<bits/stdc++.h>
using namespace std;
const int N=310;
int n, a[N], p[10], b[N], cnt=0;
int main() {
    freopen("football.in", "r", stdin);
    freopen("football.out", "w", stdout);

    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];

    p[3]=1, p[4]=2;
    for(int i=1; i<=n; i++) {
        p[a[i]]++;
        if(p[1]==p[2]) p[3]++, b[++cnt]=i;
    }
    for(int i=1; i<=cnt; i++) {
       // 第 k 局为平局, f 为 第 k 局胜者,也就是翻盘者
        int k=b[i], f=a[b[i]], temp=0;
        if(k==n || f!=a[k+1]) continue; // 无法翻盘
        // 左右查找连续胜利次数,也就是翻盘量
        for(int j=k-1; j>=1; j--) {
            if(f==a[j]) temp++; else break;
        }
        for(int j=k; j<=n; j++) {
            if(f==a[j]) temp++; else break;
        }
        p[4] = max(p[4], temp); // 最大翻盘
    }
    cout<<p[1]<<" "<<p[2]<<endl;
    cout<<p[3]<<endl<<p[4]<<endl;

    fclose(stdin), fclose(stdout);
    return 0;
}

T273322 倒酒(pourwine)

思路:既然要让最多的杯子空,那么也就是尽量用容积大的杯子去装就行了。

  • 安照桶的容积升序排序,最后将前面小容积桶置空,就可以获得最大的空桶数量
  • 其实这个题目可以骗分 20~40,20%的数据,桶是一样的,求出最大空桶数量就有40分
  • 最后输出的时候需要按照ID排序
  • 当然,满分思路就是个模拟,不过细节较多
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
struct T {
    int id,t,z;
} p[N];
bool cmp1(T a, T b) {
    return a.z < b.z;
}
bool cmp2(T a, T b) {
    return a.id < b.id;
}
int main() {
    freopen("pourwine.in", "r", stdin);
    freopen("pourwine.out", "w", stdout);

    int n; cin>>n;
    for(int i=1; i<=n; i++) cin>>p[i].t>>p[i].z, p[i].id=i;

    // 安照桶的容积升序排序,最后将前面小容积桶置空,就可以获得最大的空桶数量
    sort(p+1, p+1+n, cmp1);
    int cnt=n;
    for(int i=1; i<=n; i++) {
        while(p[cnt].z-p[cnt].t==0) cnt--; // 第 cnt桶满了,换下一个最大桶装水
        if(cnt < 1 || i>=cnt) break;
        int pcntt=p[cnt].z-p[cnt].t;
        if(pcntt > 0) {
            if(pcntt >= p[i].t) p[cnt].t += p[i].t, p[i].t=0; // 第 i 桶水空了
            if(pcntt < p[i].t) p[cnt].t += pcntt, p[i].t -= pcntt, i--;// 没空
        }
    }
    int ans=0;
    for(int i=1; i<=n; i++) if(p[i].t==0) ans++;
    cout<<ans<<endl;
    sort(p+1, p+1+n, cmp2);
    for(int i=1; i<=n; i++) cout<<p[i].t<<" ";;

    fclose(stdin), fclose(stdout);
    return 0;
}

T273323 玩具(toy)

思路:好像没有思路,也是一个模拟题,直接看方案

  • 方案1:枚举区间 [l,r],O(n)判断,整体复杂度 \(O(n^3)\), score:7

  • 方案2: 枚举颜色数量 [1,26],双指针模拟,复杂度 26*O(n),AC
    double val=num/(r-l+1) 是浮点数,其实严格来讲是不准确的,最好还是用分数形式描述,如下:
    $\frac{x1}{y1} > \frac{x2}{y2} $ --> \(\frac{x2*y1}{y1*y2} > \frac{x1*y2}{y1*y2}\)

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10, INF=0x3f3f3f3f;
string a;
void slove1() { // 枚举区间 [l,r],O(n)判断,整体复杂度O(n^3), score:7
    double val=INF;
    int x=0, y=0;
    for(int l=0; l<a.size(); l++) {
        for(int r=l+1; r<a.size(); r++) {
            int vis[26]= {0}, num=0;
            for(int i=l; i<=r; i++) vis[a[i]-'a']++;
            for(int i=0; i<26; i++) if(vis[i]) num++;
            if(1.0*num/(r-l+1) < val) val=1.0*num/(r-l+1), x=l, y=r;
        }
    }
    cout<<x+1<<" "<<y+1<<endl;
}
void slove2() { // 枚举颜色数量[1,26],双指针模拟,复杂度 26*O(n), AC
    // double val=num/(r-l+1) 是浮点数,其实严格来讲是不准确的,最好还是用分数形式描述
    double val=INF;
    int x=0, y=0;
    for(int k=1; k<=26; k++) { // 26 * O(N)
        int vis[26]= {0}, num=0, l=0, r=0;
        while(1) {
            if(l==n && r==n) break;
            while(num<k && r<n) {
                if(vis[a[r]-'a']) r++;
                else vis[a[r]-'a']++, r++, num++;
            }
            while(num==k && r<n && vis[a[r]-'a']) {
                vis[a[r]-'a']++, r++;
            }
            if(num<k) break;
            double temp=1.0*num/(r-l);
            if(temp < val) val=temp, x=l, y=r-1;
            while(num==k && l<=r) {
                vis[a[l]-'a']--;
                if(vis[a[l]-'a']==0) num--;
                l++;
            }
            if(l>r) l=r;
        }
    }
    cout<<x+1<<" "<<y+1<<endl;
}
void slove3() { // 枚举颜色数量[1,26],双指针模拟,复杂度 26*O(n), AC
    double val=INF;
    long long x=0, y=0, x1=INF,y1=1,x2,y2;
    for(int k=1; k<=26; k++) { // 26 * O(N)
        int vis[26]= {0}, num=0, l=0, r=0;
        while(1) {
            if(l==n && r==n) break;
            while(num<k && r<n) {
                if(vis[a[r]-'a']) r++;
                else vis[a[r]-'a']++, r++, num++;
            }
            while(num==k && r<n && vis[a[r]-'a']) {
                vis[a[r]-'a']++, r++;
            }
            if(num<k) break;
            x2=num, y2=(r-l);
            if(x1*y2 > x2*y1) x1=x2, y1=y2, x=l, y=r-1;
            while(num==k && l<=r) {
                vis[a[l]-'a']--;
                if(vis[a[l]-'a']==0) num--;
                l++;
            }
            if(l>r) l=r;
        }
    }
    cout<<x+1<<" "<<y+1<<endl;
}
int main() {
    freopen("toy.in", "r", stdin);
    freopen("toy.out", "w", stdout);

    int n; cin>>n>>a;
    // slove1();
    // slove2();
    slove3();
    fclose(stdin), fclose(stdout);
    return 0;
}


这篇关于2022秋季体验营C++试题-解析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程