QYcode QYcode
编程

7月day5

· 2026-7-16 19:01:40

总结：

本次考试前三道题比较简单，主要用了前缀和二分，但后三道较难，也用到了ST表和其他的一些思想。

题目解析：

T1：Worms

题意：

有n条蚯蚓，第i堆有ai条，所有的蚯蚓都按连续数字贴标签:

第一堆：1~a1

第二堆：a1+1~a1+a2

第三堆：a1+a2+1~a1+a2+a3

给出 m 个查询数字 q，对每个q，输出它属于第几堆。

思路：

本题因为上限是10的6次方，所以可以用暴力来解决， 开一个大数组 lo，下标代表蚯蚓标签，数组值代表该标签属于第几堆，遍历每一堆 i，这堆有 a 条蚯蚓，循环 a 次，计数器 cnt 依次 + 1，lo[cnt] = i，查询：每次读入q，直接输出lo[q]，单次查询O(1)所以不会超时

代码：
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000010; 
int lo[MAX];      
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int cnt = 0;//编号
    for (int i = 1; i <= n; i++) 
    {
        int a;
        cin >> a;
        //全部
        for (int j = 0; j < a; j++) 
        {
            cnt++;
            lo[cnt] = i;
        }
    }  
    int m;
    cin >> m;
    while (m--) 
    {
        int q;
        cin >> q;
        cout << lo[q] << "\n";
    }  
    return 0;
}

T2：Queries about less or equal elements

题意：

给定数组a和数组b,求a中小于等于bib_i的数字有多少个。

思路：

先按升序排序，然后用二分函数 upper_bound在数组中找到第一个大于x的元素下标，用这个地址减去数组起始地址a。

代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 10;
int a[MAXN], b[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n;i++)
    {
        cin >> a[i];
    }    
    sort(a, a + n); 
    for(int i = 0; i < m;i++)
    {
        cin >> b[i];
        int cnt = upper_bound(a, a + n, b[i]) - a;
        cout << cnt << " ";
    }
    return 0;
}

T3：Producing Snow

题意： 一共 nn 天，每天固定的有两个步骤： 新增一堆体积 viv_i 的雪和场上所有雪堆每堆融化 tit_i 剩余体积>0>0：融化 tit_i； 剩余体积≤0\le0：融化全部，雪堆消失。 思路： viv_i：第 ii 天新堆雪的体积 tit_i：第 ii 天每堆雪融化量 sis_i：tt 的前缀和 d[]d[ ]：差分数组，记录完整融化全程的雪堆数量变化 rem[]rem[ ]：记录某天最后一批雪堆不足一天融化量的残余融化量 第一步：前缀和预处理 sis_i 快速算出从第k天到第mid天累计融化总量 smid−sk−1s_{mid}-s_{k-1}。

第二步：对第 kk 天新建的雪堆二分求消失的天数 目标：找到最小 resres 满足 sres≥vk+sk−1s_{res}\ge v_k+s_{k-1}

k~ res-1：这堆雪完整存在，每天融化 tit_i res这天：雪不够完整融化，只融化剩余少量。 然后差分统计完整堆数量

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
ll v[N], t[N], s[N];
ll d[N];      //记录完整的
ll rem[N];    //残缺的
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int i = 1; i <= n; i++) cin >> t[i];
    for (int i = 1; i <= n; i++)
    {
        s[i] = s[i - 1] + t[i];
    } 
    for (int k = 1; k <= n; k++) 
    {
        ll g = v[k] + s[k - 1];
        //二分
        int l = k, r = n, res = n + 1; 
        while (l <= r) 
        {
            int mid = (l + r) / 2;
            if (s[mid] >= g) 
            {
                res = mid;
                r = mid - 1;
            } 
            else 
            {
                l = mid + 1;
            }
        }
        d[k] += 1;
        d[res] -= 1;
        if (res <= n) 
        {
            ll be = s[res - 1] - s[k - 1];
            ll la = v[k] - be;
            rem[res] += la;
        }
    }
    ll now = 0;
    for (int i = 1; i <= n; i++) 
    {
        now += d[i];
        ll ans = now * t[i] + rem[i];
        cout << ans << " ";
    }
    cout << "\n";
    
    return 0;
}

T4：Rorororobot

题意： 网格有 nn 行 mm 列，行自下而上编号 1∼n1\sim n，列从左到右 1∼m1\sim m。 第 ii 列底部 aia_i 行全部封锁，仅行号 >ai>a_i 的格子可以通行。

移动规则： 每次发送上下左右指令，机器人会一次性连续走 kk 格，移动途中碰到封锁格子或走出网格就爆炸，路线只有走完完整的kk格停下的位置才算抵达，中途路过终点不算。

每组询问给出起点和终点、kk，可发送无限条指令，也可以不发送指令，判断是否存在合法路径使机器人恰好停在终点的位置上。

思路： 一共三个步骤： 1.整除 机器人每次固定走k步，所以起点和终点的行差和列差必须是k的倍数，否则就无解。

2.计算最高可行高度 为了跨越障碍，机器人会尽可能向上爬，因此它能到达的最高行数是：

max_h = 起点行 + ((总行数 - 起点行) / k) * k

3.区间最值查询 因为机器人横向移动时，必须经过起点和终点列之间的所有列。所以只要最高可达高度 > 这段区间内最高的障碍物，机器人就能顺利过去。 提示：最大值可以用ST表查询

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXM = 200010;
const int LOG = 20;
ll a[MAXM];
ll st[MAXM][LOG];
int Log[MAXM];
void build(int m)
{
    for (int i = 1; i <= m; i++)
        st[i][0] = a[i];
    for (int j = 1; j < LOG; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= m; i++)
        {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}
ll query(int l, int r)
{
    int len = r - l + 1;
    int k = Log[len];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Log[1] = 0;
    for (int i = 2; i < MAXM; i++)
        Log[i] = Log[i / 2] + 1;
    ll n;
    int m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> a[i];
    build(m);
    int q;
    cin >> q;
    while (q--)
    {
        ll xs, ys, xf, yf, k;
        cin >> xs >> ys >> xf >> yf >> k;
        if (xs == xf && ys == yf)
        {
            cout << "YES\n";
            continue;
        }
        ll dx = abs(xs - xf);
        ll dy = abs(ys - yf);
        if (dx % k != 0 || dy % k != 0)
        {
            cout << "NO\n";
            continue;
        }
        if (ys == yf)
        {
            cout << "YES\n";
            continue;
        }
        int L = min((int)ys, (int)yf);
        int R = max((int)ys, (int)yf);
        ll M = query(L, R);
        ll rem = xs % k;
        ll b = M + 1;
        ll d = (rem - b % k + k) % k;
        ll s = b + d;
        if (s <= n)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

T5：Integers Have Friends

题意： 给定一个数组，寻找最长的连续子数组，使得存在一个整数 m≥2m \ge 2，子数组里的所有数字对m取余的结果都相同。

思路： 1.转换成差分数组： 如果一段连续的数字对m取余相同，那么它们之间的差值肯定都是 mm 的倍数。因此，问题等价于在差分数组中寻找一段最长的连续子数组，使得这些差值的最大公约数大于等于2。 2.ST表预处理 为了快速求出任意区间的 gcd⁡\gcd，所以要提前用ST表预处理差分数组。 3.双指针 利用 gcd⁡\gcd 的单调性（区间越长，gcd⁡\gcd 只会变小或不变），右指针不断向右扩张，一旦发现当前窗口的 gcd⁡\gcd 为 1（说明不合法），就不断向右移动左指针缩小窗口，然后记录此间窗口的最大长度。 4. 输出差分数组中最长合法子数组的长度+1

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll g(ll a, ll b) 
{
    while (b) 
    {
        a %= b;
        swap(a, b);
    }
    return a;
}
int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) 
    {
        int n;
        cin >> n;
        vector<ll> a(n);
        for(int i = 0; i < n; i++) 
        {
            cin >> a[i];
        }
        if(n == 1) 
        {
            cout << "1\n";
            continue;
        }
        vector<ll> d;
        for(int i = 0; i < n - 1; i++) 
        {
            ll x = a[i + 1] - a[i];
            if(x < 0)
            {
                x = -x;
            }
            d.push_back(x);
        }
        int s = d.size();
        int k = log2(s) + 1;//二进制
        vector<vector<ll>> st(k, vector<ll>(s));
        for(int i = 0; i < s; i++) 
        {
            st[0][i] = d[i];
        }
        for(int j = 1; j < k; j++) 
        {
            for(int i = 0; i + (1 << j) <= s; i++) 
            {
                st[j][i] = g(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
            }
        }
        auto q = [&](int l, int r) -> ll 
        {
            int w = r - l + 1;
            int p = log2(w);
            return g(st[p][l], st[p][r - (1 << p) + 1]);
        };
        int m = 0;
        int l = 0;
        for (int r = 0; r < s; r++) 
        {
            while (l <= r && q(l, r) == 1) 
            {
                l = l + 1;
            }
            if (l <= r) 
            {
                int cur = r - l + 1;
                if (cur > m) 
                {
                    m = cur;
                }
            }
        }
        cout << m + 1 << '\n';
    }
    return 0;
}

T6：The Treasure of The Segments

题意：

思路： 1.贪心枚举 “好集合”肯定会存在一个过度的区间与其他区间相交，因此，只需枚举每个区间作为桥梁，求最少需要删除多少个与它不相交的区间，然后取个最小值。

2.排序 将所有区间的左端点l和右端点r分别排序。 如果左端点 > y，就用upper_bound查找，数量为n-dl 如果右端点 < x，就用lower_bound查找，数量为dr

左右不相交数量之和即为当前桥梁需删除的区间数，遍历所有区间取最小值即可。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
struct node 
{
    int x, y;
} 
a[N];
vector<int> l, r;

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) 
    {
        int n;
        cin >> n;
        l.clear();
        r.clear();
        for (int i = 0; i < n;i++) 
        {
            cin >> a[i].x >> a[i].y;
            l.push_back(a[i].x);
            r.push_back(a[i].y);
        }
        sort(l.begin(), l.end());
        sort(r.begin(), r.end());
        int ans = 1e9;
        for (int i = 0; i < n;i++) 
        {
            int res = 0;
            // 找第一个左端点到当前右端点的位置
            int dl = upper_bound(l.begin(), l.end(), a[i].y) - l.begin();
            res += (n - dl);
            // 找第一个右端点到当前左端点的位置
            int dr = lower_bound(r.begin(), r.end(), a[i].x) - r.begin();
            res += dr;
            ans = min(ans, res);
        }
        cout << ans << "\n";
    }
    return 0;
}
已修改 3 次查看 举报

0 条评论

目前还没有评论...

Be the first to comment!

返回讨论列表
温张鑫
161
通过题目
6
发帖数