2025 10 08 模拟赛游记

Love_Star · 2025-10-08 14:33:48 · 生活·游记

2025 10 08 模拟赛游记

这次模拟赛有五题，难度偏高（对我来说）。

第一题：牛奶桶（blist）

题目大意：

• 有 N 头奶牛，第 i 头奶牛需要从时间 s_i 到时间 t_i 之间挤奶，并且挤奶过程中需要用到 b_i 个桶。
• 求出 FJ 需要在储藏室中存放多少个桶才能使得他能够顺利地给所有奶牛挤奶。

主要算法：

• 枚举
• 差分（可用可不用，优化算法）

正解：

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

const int N = 1005;
int n, ans, a[N];

int main() {
    cin >> n;
    for (int i = 1, s, t, b; i <= n; i++) {
        cin >> s >> t >> b;
        a[s] += b;
        a[t + 1] -= b;
    }
    for (int i = 1; i <= 1000; i++) {
        a[i] += a[i - 1];
        ans = max(a[i], ans);
    }
    cout << ans;
    return 0;
}

第二题：井字棋（tttt）

题目大意：

• Farmer John 有 26 头奶牛，恰好她们名字都以不同的字母开头，这些奶牛最近沉迷于井字游戏，这个游戏是在一块 3 \times 3 的棋盘上进行的。
• 判断有多少头奶牛或是两头奶牛组成的队伍可以获胜。注意棋盘上的同一个格子可能在不同奶牛或队伍的获胜中均被用到。

主要算法：

• 枚举
• 模拟

第三题：往返运奶（backforth）

题目大意：

• 有两个挤奶棚，每个挤奶棚里各有一个奶罐和一个装有 10 个各种尺寸的桶的储物柜。
• 测量了第一个挤奶棚的奶罐里的牛奶，总共可能得到多少种不同的读数？

• 主要算法：

• DFS
• 模拟

正解：

#include <bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int n[25],n1[25],ans;
int v[105],v1[105],vv[N][N];
int cnt,cnt1;
void dfs(int a,int d,int cmt,int cmt1){
    if(cmt>2||cmt1>2){
        return ;
    }
    if(cmt==2&&cmt1==2){
        if(!vv[a][d]){
            vv[a][d]=1;
            ans++;
        }
        return ;
    }
    for(int i=1;i<=cnt;i++){
        if(!v[n[i]])continue;
        v[n[i]]--;
        v1[n[i]]++;
        dfs(a-n[i],d+n[i],cmt+1,cmt1);
        v1[n[i]]--;
        v[n[i]]++;
    }
    for(int i=1;i<=cnt1;i++){
        if(!v1[n1[i]])continue;
        v1[n1[i]]--;
        v[n1[i]]++;
        dfs(a+n1[i],d-n1[i],cmt,cmt1+1);
        v1[n1[i]]++;
        v[n1[i]]--;
    }
}
int main(){
    for(int i=1,x;i<=10;i++){
        cin>>x;
        if(!v[x]){
            n[++cnt]=x;
            n1[++cnt1]=x;
        }
        v[x]++;
    }
    for(int i=1,x;i<=10;i++){
        cin>>x;
        if(!v1[x]){
            n[++cnt]=x;
            n1[++cnt1]=x;
        }
        v1[x]++;
    }
    dfs(1000,1000,0,0);
    cout<<ans;
    return 0;
}

第四题：挤奶顺序（milkorder）

题目大意：

• 由于奶牛们的社会阶层，某些奶牛会坚持要在其他奶牛之前挤奶，基于她们的社会地位等级。
• 有些奶牛只允许她们在排队顺序中一个特定的位置挤奶。
• 求出奶牛 1 可以在挤奶顺序中出现的最早位置。

基本算法：

• 贪心
• 双指针

正解：

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
const int N=105;
ll n,m,k;
ll l[N],p[N],a[N];
bool f;

int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        cin>>l[i];
        if(l[i]==1)f=1;
    }
    for(int i=1;i<=k;i++){
        ll x,y;
        cin>>x>>y;
        p[x]=y;
        a[y]=x;
    }
    if(p[1]){
        cout<<p[1];
    }else if(f){
            for(int i=1,j=1;i<=n&&j<=m;){
                if(p[l[j]]){
                    i=p[l[j++]]+1;
                }else if(!a[i]){
                    p[l[j]]=i;
                    a[i++]=l[j++];
                }else i++;
            }
            cout<<p[1];
    }else{
        for(int i=n,j=m;j&&i;){
            if(p[l[j]]){
                    i=p[l[j--]]-1;
                }else if(!a[i]){
                    p[l[j]]=i;
                    a[i--]=l[j--];
                }else i--;
        }
        for(int i=1;i<=n;i++){
            if(!a[i]){
                cout<<i;
                break;
            }
        }
    }

    return 0;
}

第五题：家谱（family）

题目大意：

• 如果 BESSIE 和 ELSIE 的母亲是同一头奶牛，输出 SIBLINGS 。
• BESSIE 可能是 ELSIE 的直系后代，也就是说 ELSIE 是 BESSIE 的母亲 mother ，外祖母 grand-mother ，外曾外祖母 great-grand-mother，外曾外曾外祖母 great-great-grand-mother ，等等。如果是这种情况，输出 ELSIE is the (relation) of BESSIE，其中 (relation) 是适当的关系，比如 great-great-grand-mother 。
• 如果 ELSIE 不是 BESSIE 的某个祖先或姐妹，但是是 BESSIE 的某个祖先的孩子，那么 ELSIE 就是 BESSIE 的姨母 aunt 。如果 ELSIE 是 BESSIE 的外祖母的孩子，输出 ELSIE is the aunt of BESSIE ；如果 ELSIE 是 BESSIE 的外曾外祖母的孩子，输出 ELSIE is the great-aunt of BESSIE ；如果 ELSIE 是 BESSIE 的外曾外曾外祖母的孩子，输出 ELSIE is the great-great-aunt of BESSIE ；以此类推。
• 如果 BESSIE 和 ELSIE 有任何其他的亲戚关系（也就是说，她们有共同的祖先），她们就是表姐妹，输出 COUSINS 。
• 如果 BESSIE 和 ELSIE 既没有共同的祖先，其中任何一头也不是另一头的直系后代，输出 NOT RELATED 。

基本算法：

• LCA(最近公共祖先)