原：24 年集训第十二场。

这里仅是题解。

A：区间求和

预估难度红到橙。

题意

原题意：

图

1

：A 题原题面。

简化题意：

有一个长度为

n

的数组

a

，求满足如下条件的

l,r

个数：

\sum_{i=l}^r a_i=m

m

为给定的数。数据范围：

1\le n \le 10^5,1\le a_i \le 10^9,1\le m \le 10^{14}

。

解法

可以用双指针跑一遍区间。边跑边用一个变量

sum

记录当前区间的区间和。如果

sum>m

那么

l+1

，如果

sum=m

，答案加一，如果

sum<m

，那么什么都不干，因为后面会帮你补上来的。时间复杂度

O(n)

。

如果存在

a_i<0

的情况，那么就只能

O(n^2)

暴力了，因为前缀和不存在单调性，而且上面的方法也不成立，因为如果大了的话后面来个负数这个算法就炸了。

代码

CPP

1234567891011121314151617181920212223242526272829303132333435#include <iostream>
#include <cstdio>
#define int long long
#define endl '\n'
using namespace std;

int n,m;
int a[100005];
signed main()
{
    freopen("sum.in","r",stdin);
    freopen("sum.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
    }
    int l = 1,r = 1;
    int sum = a[1];
    int ans = 0;
    if(sum==m) ans++;
    for(int i = 2;i<=n;i++){
        r++;
        sum+=a[r];
        while(sum>m&&l<=r){
            sum-=a[l];
            l++;
        }
        if(sum==m){
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

B：比赛

题意

这个题意简化不了，直接看吧。

图

2

：B 题原题面。

解法

我们考虑把整个方法倒过来。考虑归并排序，因为每次都是折半取，所以符合题目要求，而且区间内还是排序好的，于是直接修改答案即可。时间复杂度

O(n\log n)

。

代码

CPP

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include <iostream>
#include <utility>
#define int long long
using namespace std;

int n,k;
pair<int,int> a[1500005];
int ans[1500005];
pair<int,int> c[1500005];
void merge_sort(int l,int r){
    if(l==r) return ;
    int mid = (l+r)>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    int p1 = l,p2 = mid+1,p3 = l;
    while(p1<=mid&&p2<=r){
        if(a[p1].first>=a[p2].first){
            c[p3++] = a[p1++];
        }else{
            c[p3++] = a[p2++];
        }
    }
    while(p1<=mid){
        c[p3++] = a[p1++];
    }
    while(p2<=r){
        c[p3++] = a[p2++];
    }
    for(int i = l;i<=r;i++){
        a[i] = c[i];
    }//归并排序板子
    for(int i = l+k;i<=r;i++){
        if(ans[a[i].second]==0) ans[a[i].second] = n/(r-l+1)*k+1;//这一段的答案，前面是能够晋级的人数
    }
    return ;
}
signed main()
{
    freopen("gaming.in","r",stdin);
    freopen("gaming.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    n = (1<<n);
    for(int i = 1;i<=n;i++){
        cin>>a[i].first;
        a[i].second = i;
    }
    merge_sort(1,n);
    for(int i = 1;i<=k;i++) ans[a[i].second] = i;//前 k 个特殊处理
    for(int i = 1;i<=n;i++) cout<<ans[i]<<' ';
    return 0;
}

C：加乘运算

题意

图

3

：C 题原题面。

解法

假设我们现在有一个式子

[(a*^b c)*^e (d*^fg)]*^h

显然我们如果修改

a

，答案只会影响所有与

a

有关的系数，就是

b,e,h

三个系数。

于是，我们考虑像求后缀表达式的值一样把每个数的系数求出来，这里用一个栈就行。然后每次查询直接把差值与系数相乘并计算答案即可。时间复杂度

O(n\log n)

。但我并不确定，因为是 gdz 告诉我的。

代码

CPP

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122#include <iostream>
#include <cstdio>
// #include <stack>
#include <utility>
#define int long long
#define endl '\n'
using namespace std;

template <typename T> class stack{
    private:
        T sta[1000005];
        int tt = 0;
    public:
        void push(T x){
            sta[++tt] = x;
        }
        void pop(){
            tt--;
        }
        T top(){
            return sta[tt];
        }
        void clear(){
            tt = 0;
        }
        int size(){
            return tt;
        }
        bool empty(){
            return tt==0;
        }
};
int n,m;
stack<pair<int,int>  > stk;//pair 就是存区间的
int s[1000005];
int ac[1000005];
string a;
int b[1000005];
signed main()
{
    freopen("addmul.in","r",stdin);
    freopen("addmul.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i = 1;i<=n;i++) s[i] = 1;
    getline(cin,a);//防止读入 \n
    getline(cin,a);
    // cout<<a<<endl;
    // bool fflag = true;
    for(int i = 1;i<n;i++){
        cin>>b[i];
        // if(b[i]!=1) fflag = false;
    }
    int now = 1;
    int len = 1;
    int nownum = 0;
    bool flag = false;
    for(int i = 0;i<a.length();i++){
        if(a[i]>='0'&&a[i]<='9'){
            flag = true;
            nownum = nownum*10+(a[i]-'0');
        }else{
            if(a[i]=='*'){
                pair<int,int> fir,sec;
                fir = stk.top();
                stk.pop();
                sec = stk.top();
                stk.pop();
                swap(fir,sec);
                // cout<<fir.first<<' '<<fir.second<<' '<<sec.first<<' '<<sec.second<<' '<<b[now]<<endl;
                // s[fir.first]*=b[now];
                // s[sec.second+1]/=b[now];
                for(int j = fir.first;j<=sec.second;j++){//暴力计算就行
                    s[j]*=b[now];
                }
                now++;
                stk.push({fir.first,sec.second});
            }else if(flag){
                flag = false;
                stk.push({len,len});
                ac[len++] = nownum;
                nownum = 0;
            }
        }
    }
    // if(fflag){
    //     int sum = 0;
    //     for(int i = 1;i<=n;i++){
    //         sum+=ac[i];
    //     }
    //     while(m--){
    //         int l,r;
    //         cin>>l>>r;
    //         sum+=r-ac[l];
    //         cout<<sum<<endl;
    //     }
    //     return 0;
    // }
    // cout<<endl;
    int nowans = 0;
    // for(int i = 1;i<=n;i++){
    //     s[i]*=s[i-1];
    // }
    for(int i = 1;i<=n;i++){
        nowans+=ac[i]*s[i];
        // cout<<ac[i]<<' '<<s[i]<<endl;
    }
    // cout<<nowans<<endl;
    while(m--){
        int a,b;
        cin>>a>>b;
        if(b>ac[a]){
            nowans+=(b-ac[a])*s[a];
            ac[a] = b;
        }else{
            nowans-=(ac[a]-b)*s[a];
            ac[a] = b;
        }
        cout<<nowans<<endl;
    }
    return 0;
}

D：课程安排

题意

图

4

：D 题原题面

解法

显然，我们可以用 DP 求解。

设第

i

天有课的时间为

cnt_i

，最左边的是

ll_i

，最右边的是

rr_i

。我们枚举当前是第

i

天，要剩余

j

个课时，我们能够很快得到满足条件的最短区间。它的代价是

cnt_i-j

，价值是区间长度。

然后跑 01 背包板子就行了，但是需要注意的是：你不能一天搞两遍，所以这里再加一次循环跑枚举这一天砍哪个。

代码

CPP

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
#define endl '\n'
using namespace std;

const int N = 505;
int n,m,kkk;
int a[N][N];
int cnt[N],ll[N],rr[N],s[N][N];
int w[N][N],c[N][N];
int dp[N][N];
signed main()
{
    freopen("skip.in","r",stdin);
    freopen("skip.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>kkk;
    int nowans = 0;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]==1){
                cnt[i]++;
                s[i][cnt[i]] = j;
                if(ll[i]==0) ll[i] = j;
                rr[i] = j;
            }
        }
        nowans+=rr[i]-ll[i]+1;
    }
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<cnt[i];j++){
            if(j==0){
                w[i][j] = cnt[i];
                c[i][j] = rr[i]-ll[i]+1;
                continue;
            }
            int maxn = -1;
            for(int k = 1;k+j-1<=cnt[i];k++){
                maxn = max(maxn,rr[i]-ll[i]+1-s[i][k+j-1]+s[i][k]-1);
            }
            w[i][j] = cnt[i]-j;
            c[i][j] = maxn;
        }
    }
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<=kkk;j++){
            for(int k = 0;k<cnt[i];k++){
                dp[i][j] = max(dp[i][j],dp[i-1][j]);
                if(j>=w[i][k]){
                    dp[i][j] = max(dp[i][j],dp[i-1][j-w[i][k]]+c[i][k]);
                }
            }
        }
    }
    cout<<nowans-dp[n][kkk];
    return 0;
}

2025 年 10 月 21 日 J 组（CJ 集训）题解

文章操作