2025牛客寒假算法训练营2

A. 一起奏响历史之音

题意：

给你一个长度为7的序列，检查序列里面是否有1、2、3、5、6这五个数字，如果有输出YES，没有输出NO。

数据范围

$$1 \leq a_i \leq 7$$

题解：模拟

代码：

void JiuCherish() {
    for(int i=0;i<7;i++) std::cin >> a[i];
    std::set<int> f = {1,2,3,5,6};
    for(int i=0;i<7;i++) {
        if(f.find(a[i]) == f.end()) {
            std::cout << "NO" << endl;
            return;
        }
    }
    std::cout << "YES" << endl;
}

B.能去你家蹭口饭吃吗

题意：

B有n个碗，第i个碗容量为ai。

B要求：A的碗至少要比B家一半数量的碗容量更小，为了装更多的饭，A想带尽可能大的碗，问最大能带多大的碗。

数据范围

$$1\leq n\leq 5 \times 10^5$$

$$1 \leq a_i \leq 10^6$$

题解：排序

代码：

void JiuCherish() {
    int n;
    std::cin >> n;
    std::vector<int> f(n);
    for(int i=0;i<n;i++) std::cin >> f[i];
    std::sort(f.begin(),f.end());
    std::cout << f[n / 2] - 1 << endl;
}

C.兢兢业业之移

题意：

好矩阵的定义需要满足以下两个条件：

1.矩阵的行数和列数都是偶数。

2.将左上角的区域全部变为1，右上右下左下的区域变成0。

现在给你一个n行n列的01矩阵，你每次操作只能交换两个相邻字符，请你将矩阵变成好矩阵，保证给出的矩阵一定有解，需要给出的操作次数不超过n³/2，可以证明，在该范围内至少存在一种合法解。

输出操作次数，以及每一次的交换方案。

数据范围

$$1\leq T\leq 20$$

$$2 \leq n \leq 100$$

$$保证1的数量恰好为\frac{n^2}{4}$$

题解：模拟

确定左上方有没有1，找最近的1让他移动过去。

代码：（学习konbi的）

void JiuCherish() {
    int n;
    std::cin >> n;
    std::vector<std::vector<int>> f(n + 5,std::vector<int>(n + 5));
    for(int i=1;i<=n;i++) {
        std::string s;
        std::cin >> s;
        for(int j=1;j<=n;j++) {
            f[i][j] = s[j - 1] - '0';
        }
    }
    int m = n / 2;
    for(int i=1;i<=101;i++) {
        for(int j=1;j<=101;j++) {
            st[i][j] = false;
        }
    }
    std::vector<std::array<int,4>> ans;
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=m;j++) {
            st[i][j] = true;
            if(f[i][j]) continue;

            int ok = 0;
            for(int x=1;!ok and x<=n;x++) {
                for(int y=1;!ok and y<=n;y++) {
                    if(!f[x][y] or st[x][y]) continue;
                    ok = 1;
                    while(y < j) {
                        std::swap(f[x][y],f[x][y + 1]);
                        ans.pb({x,y,x,y + 1});
                        y += 1;
                    }
                    while(x < i) {
                        std::swap(f[x][y],f[x + 1][y]);
                        ans.pb({x,y,x + 1,y});
                        x += 1;
                    }
                    while(y > j) {
                        std::swap(f[x][y],f[x][y - 1]);
                        ans.pb({x,y,x,y - 1});
                        y -= 1;
                    }
                    while(x > i) {
                        std::swap(f[x][y],f[x - 1][y]);
                        ans.pb({x,y,x - 1,y});
                        x -= 1;
                    }
                }
            }
        }
    }
    std::cout << ans.size() << endl;
    for(auto [a,b,c,d] : ans) {
        std::cout << a << ' ' << b << ' ' << c << ' ' << d << endl;
    }
}

D.双生双宿之决

题意：

我们定义双生数组：数组大小为偶数，且只有2种数组元素，并且这两种元素的出现次数相同。

现在给你一个数组，判断他是不是双生数组。

数据范围

$$1\leq T \leq 10^4$$

$$1 \leq n \leq 10^5$$

$$1 \leq a_i \leq 10^{9}$$

题解：模拟，stl

题意。

代码：

void JiuCherish() {
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];

    if(n % 2 != 0) {
        std::cout << "No" << endl;
        return;
    }
    std::map<int,int> mp;
    for(int i=1;i<=n;i++) mp[a[i]] += 1;
    if(mp.size() != 2) {
        std::cout << "No" << endl;
        return;
    } else {
        auto it = mp.begin();
        int fc = it->se;
        ++it;
        int sc = it->se;
        if(fc == sc) {
            std::cout << "Yes" << endl;
        } else {
            std::cout << "No" << endl;
        }
    }

}

E.双生双宿之错

题意：

我们定义双生数组：数组大小为偶数，且只有2种数组元素，并且这两种元素的出现次数相同。

现在给你一个长度为偶数的数组，你可以进行若干次操作，每次操作选择一个元素，使其加1或者减1，小红希望这个数组变成双生数组的最小操作次数。

数据范围

$$1\leq T \leq 10^4$$

$$2 \leq n \leq 10^5$$

$$1 \leq a_i \leq 10^{9}$$

题解：模拟/二分/三分

将数组排序后分成两段，前n/2小的数变成x，后n/2大的数变成y，x和y通过二分/三分的形式找出来，x和y相同的情况下直接计算操作次数即可，否则分别计算(x+1,y)、(x-1,y)、(x,y+1)、(x,y-1)四种情况操作次数的最小值。

代码：

void JiuCherish() {
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    std::sort(a + 1,a + n + 1);
    for(int i=1;i<=n/2;i++) {
        b[i] = a[i + n / 2];
    }
    int m = n / 2;
    int l = 0,r = 8e18;
    int f1 = 0;
    int f2 = 0;
    auto check = [&](int mid,int a[]) {
        int res = 0;
        for(int i=1;i<=m;i++) {
            res += std::abs(mid - a[i]);
        }
        return res;
    };
    while(l < r) {
        int mid = l + (r - l) / 2;
        int x1 = check(mid,a);
        int x2 = check(mid + 1,a);
        if(x1 <= x2) {
            r = mid;
            f1 = mid;
        } else {
            l = mid + 1;
            f1 = mid + 1;
        }
    }
    l = 0,r = 8e18;
    while(l < r) {
        int mid = l + (r - l) / 2;
        int x1 = check(mid,b);
        int x2 = check(mid + 1,b);
        if(x1 <= x2) {
            r = mid;
            f2 = mid;
        } else {
            l = mid + 1;
            f2 = mid + 1;
        }        
    }
    if(f1 == f2) {
        int x1 = check(f1,a);
        int x2 = check(f2 - 1,b);
        int ans = x1 + x2;
        
        x1 = check(f1,a);
        x2 = check(f2 + 1,b);
        ans = std::min(ans,x1 + x2);
        
        x1 = check(f1 - 1,a);
        x2 = check(f2,b);
        ans = std::min(ans,x1 + x2);   
        
        x1 = check(f1 + 1,a);
        x2 = check(f2,b);
        ans = std::min(ans,x1 + x2);   
        
        std::cout << ans << endl;
    } else {
        int x1 = check(f1,a);
        int x2 = check(f2,b);       
        std::cout << x1 + x2 << endl;
    }
}

F. 一起找神秘的数

题意：

给定区间**[l,r]**，从中选取两个整数x和y，使得下式成立：

$$x + y = (x or y) + (x and y) + (x xor y)$$

有多少对不同的x,y满足条件。

其中or表示按位或运算，and表示按位与运算，xor表示按位异或运算。

数据范围

$$1 \leq T \leq 2\times10^5$$

$$0 \leq l \leq r \leq 10^{18}$$

题解：打表、位运算、结论

打表任意一个区间可以知道本质就是问[l,r]区间上有多少个数，

代码：

void JiuCherish() {
   int l,r;
   std::cin >> l >> r;
   std::cout << r - l + 1 << endl;
}

G.一起铸最好的剑

题意：

定义：铸剑的温度越接近 n 度，剑的品质越好。

现在启动炉子时，A已经添过一次柴了，所以铸剑炉的初始温度为 m 度，此后每次添柴可以使得铸剑炉的温度提高到原来的 m 倍。

A想知道，最少需要添多少次柴，才能使得铸剑炉的温度最接近 n 度。

数据范围

$$1 \leq T \leq 10^5$$

$$1 \leq n,m \leq 10^{9}$$

题解：模拟

模拟每次添加的温度，注意需要计算最接近n的操作（是从小于n靠近还是从大于n靠近）。

特判m为1的时候只有最初第1次添柴。

代码：

void JiuCherish() {
    int n,m;
    std::cin >> n >> m;
    if(m == 1) {
        std::cout << 1 << endl;
        return;
    }
    int ans = 1;
    int f1 = m;
    int add = std::abs(m - n);
    while(666) {
        if(add <= std::abs(n - m * f1)) {
            break;
        }
        ans += 1;
        m *= f1;
        add = std::abs(m - n);
    }
    std::cout << ans << endl;
}

H. 一起画很大的圆！

题意：

划定一个矩形区域，左侧边界为x=a,右侧边界为x=b，下侧边界为y=c,上侧边界为y=d,希望在四条直线所围成的矩形的边界上找到三个不同的整数点A,B,C，使得过这三个点画出的圆半径最大。

原题弱化版：整整齐齐

数据范围

$$1 \leq n \leq 10^5$$

$$1 \leq l_i \leq r_i \leq n$$

题解：贪心

我们先将所有区间排序，用一个优先队列来维护“可选的区间右端点”。当我们指定某个区间为 i 的时候，我们首先将所有以 i 为左端点的区间加入优先队列，然后尽量选择目前最小的那个右端点即可。

代码：

void JiuCherish() {
    int n;
    std::cin >> n;
    std::vector<std::vector<int>> a;
    for(int i=0;i<n;i++) {
        int x,y;
        std::cin >> x >> y;
        x -= 1;
        y -= 1;
        a.pb({x,y,i});
    }
    std::sort(a.begin(),a.end());
    std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int>>,std::greater<std::pair<int,int>>> pq;
    std::vector<int> ans(n);
    int p = 0;    
    for(int i=0;i<n;i++) {
        while(p < n and a[p][0] <= i) {
            pq.push({a[p][1],a[p][2]});
            p += 1;
        }
        if(pq.size() == 0) {
            std::cout << -1 << endl;
            return;
        }
        auto tp = pq.top();
        pq.pop();
        if(tp.fi < i) {
            std::cout << -1 << endl;
            return;
        }
        ans[tp.se] = i;
    }
    for(auto x : ans) std::cout << x + 1 << ' ';
}

I. 数据时间？

题意：

数据范围

$$1 \leq n \leq 10^5$$

$$2000 \leq h \leq 2030$$

$$1 \leq m \leq 12$$

$$1 \leq user_{id} \leq 10^{20}$$

YYYY-MM-DD表示登录日期。

hh:mm:ss表示登录时间。

题解：模拟，set，字符串。

按题意模拟就好，同个人同个时间段登录用set去重即可。

代码：（我比较懒）

def check(time, start, end):
    return start <= time <= end

def JiuCherish():
    n, h, m = map(int, input().split())
    mc = set()
    ec = set()
    lb = set()
    bd = set()
    for i in range(n):
        ui, ld, lt = input().split()
        ye, mo, day = ld.split('-')
        if int(ye) == h and int(mo) == m:
            if check(lt, "07:00:00", "09:00:00"):
                mc.add(ui)
            elif check(lt, "18:00:00", "20:00:00"):
                mc.add(ui)
            elif check(lt, "11:00:00", "13:00:00"):
                lb.add(ui)
            elif check(lt, "22:00:00", "23:59:59") or check(lt, "00:00:00", "01:00:00"):
                bd.add(ui)
    print(len(mc), len(lb), len(bd))

if __name__ == "__main__":
    JiuCherish()

J. 数据时间？

题意：

有一个APP，其中的数据由三个字段构成，分别是user_id表示用户id，login_date表示登陆日期，login_time表示登陆时间。

现在需要帮忙统计h年m月份通勤、午休、临睡这三个时段各有多少人登陆过APP。特别地，同一个人在同一个时间段多次登录只认定为1次。

约定通勤时间为：7点到9点，18点到20点。

午休时间段为：11点到13点。

临睡时间段为：22点到第二天1点。

时间段均包含左右边界值。

数据范围

$$1 \leq n \leq 10^5$$

$$2000 \leq h \leq 2030$$

$$1 \leq m \leq 12$$

$$1 \leq user_{id} \leq 10^{20}$$

YYYY-MM-DD表示登录日期。

hh:mm:ss表示登录时间。

题解：模拟，set，字符串。

按题意模拟就好，同个人同个时间段登录用set去重即可。

代码：（我比较懒）

def check(time, start, end):
    return start <= time <= end

def JiuCherish():
    n, h, m = map(int, input().split())
    mc = set()
    ec = set()
    lb = set()
    bd = set()
    for i in range(n):
        ui, ld, lt = input().split()
        ye, mo, day = ld.split('-')
        if int(ye) == h and int(mo) == m:
            if check(lt, "07:00:00", "09:00:00"):
                mc.add(ui)
            elif check(lt, "18:00:00", "20:00:00"):
                mc.add(ui)
            elif check(lt, "11:00:00", "13:00:00"):
                lb.add(ui)
            elif check(lt, "22:00:00", "23:59:59") or check(lt, "00:00:00", "01:00:00"):
                bd.add(ui)
    print(len(mc), len(lb), len(bd))

if __name__ == "__main__":
    JiuCherish()

K.可以分开吗？

题意：

给你一个n行m列的数表，需要记录每一个边界0的个数取最小值。

数据范围

$$1 \leq n,m \leq 500$$

$$s_{i,j}不是0就是1$$

题解：DFS，BFS，搜索

记录每一个边界0的个数取最小值就是答案。

代码：

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int f[550][550];
bool vis[550][550];
std::set<std::pair<int,int>> s;
int n,m;
void dfs(int x,int y) {
    for(int i=0;i<4;i++) {
        int xx = x + dx[i],yy = y + dy[i];
        if(xx < 1 or xx > n or yy < 1 or yy > m or vis[xx][yy]) {
            continue;
        }
        if(f[xx][yy] == 0) {
            s.insert({xx,yy});
            continue;
        }
        vis[xx][yy] = 1;
        dfs(xx,yy);
    }
}
void JiuCherish() {
    std::cin >> n >> m;
    for(int i=1;i<=n;i++) {
        std::string x;
        std::cin >> x;
        x = ' ' + x;
        for(int j=1;j<=m;j++) {
            f[i][j] = x[j] - '0';
        }
    }
    int ans = n * m;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(f[i][j] == 1 and !vis[i][j]) {
                s.clear();
                dfs(i,j);
                ans = std::min(ans,(int)s.size());
            }
        }
    }
    std::cout << ans << endl;
}

L.一念神魔之耀

题意：

数据范围

$$1\leq T\leq 500$$

$$1 \leq l \leq 500,1 \leq x,y \leq \frac{l}{3}$$

$$保证字符串仅由0，1构成$$

题解：数学，裴蜀定理，gcd

首先考虑 x = y 的情况，很明显是做一个递推的过程，找到每一个‘0’的位置进行翻转，如果能转换到最后一个数的话，那么就是成立的，否则输出-1。

其次考虑 x ≠ y 的情况，那么一定存在 x,y 不覆盖的一段使得他们翻转，考虑gcd(x,y)为x与y不覆盖能构造成最小的一段连续区间，通过gcd(x,y) 与 x 和 y组合，可以延伸出很多种区间分法，即裴蜀定理（ax + by = (a,b)），如果能有限次操作次数完成，即有解。

代码：

void JiuCherish() {
    int n,x,y;
    std::cin >> n >> x >> y;
    std::string s;
    std::cin >> s;
    s = '?' + s;
    std::vector<int> a(n + 5);
    for(int i=1;i<=n;i++) a[i] = s[i] - '0';
    auto b = a;
    int g = std::gcd(x,y);
    std::vector<std::pair<int,int>> ans;
    for(int i=1;i+g-1<=n;i++) {
        if(a[i]) continue;
        int l,r;
        auto b = ans;
        ans.clear();
        if(i + x - 1 <= n) {
            ans.pb({i,i + x - 1});
            l = i + g;
            r = i + x - 1;
        } else {
            ans.pb({i + g - 1 - x + 1,i + g - 1});
            l = i + g - 1 - x + 1;
            r = i - 1;
        }
        while(l <= r) {
            if(r - l + 1 >= y) {
                ans.pb({l,l + y - 1});
                l += y;
            }
            else if(r + x <= n) {
                ans.pb({r + 1,r + x});
                r += x;
            } 
            else {
                ans.pb({l - x,l - 1});
                l -= x;
            }
        }
        for(auto [l,r] : ans) {
            for(int i=l;i<=r;i++) a[i] ^= 1;
            b.pb({l,r});
        }
        ans = b;
    }
    for(int i=1;i<=n;i++) {
        if(a[i] == 0) {
            std::cout << -1 << endl;
            return;
        }
    }
    std::cout << ans.size() << endl;
    for(auto [l,r] : ans) std::cout << l << ' ' << r << endl;
}

M. 数值膨胀之美

题意：

给你一个数组，需要操作一次：选择一个非空区间，将其中所有元素都乘2，问最小化数组的极差（最大值-最小值）。

数据范围

$$1\leq n\leq 10^5$$

$$1 \leq a_i \leq 10^9$$

题解：模拟，结论

首先统计右移有多少次，如果不能整除6那么说明有一次是特殊的移动。

然后再算左移有多少次。

代码：

void JiuCherish() {
    int n;
    std::cin >> n;
    int ans = n / 6;
    if(n % 6) ans += 1;
    n = n - 6;
    if(n % 6 == 0) {
        std::cout << ans << endl;
        return;
    }
    ans += n / 6;
    std::cout << ans << endl;
}