2025 年 10 月 21 日 J 组（CJ 集训）题解
GeorgeDeng
·
·
个人记录
原：24 年集训第十二场。
这里仅是题解。
A：区间求和
预估难度 红到橙。
题意
原题意：
:::align{center}
图 1：A 题原题面。
:::
简化题意：
有一个长度为 n 的数组 a，求满足如下条件的 l,r 个数：
\sum_{i=l}^r a_i=m
## 解法
可以用双指针跑一遍区间。边跑边用一个变量 $sum$ 记录当前区间的区间和。如果 $sum>m$ 那么 $l+1$，如果 $sum=m$，答案加一，如果 $sum<m$，那么什么都不干，因为后面会帮你补上来的。时间复杂度 $O(n)$。
如果存在 $a_i<0$ 的情况，那么就只能 $O(n^2)$ 暴力了，因为前缀和不存在单调性，而且上面的方法也不成立，因为如果大了的话后面来个负数这个算法就炸了。
## 代码
```cpp line-numbers
#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：比赛
## 题意
这个题意简化不了，直接看吧。
:::align{center}
图 $2$：B 题原题面。
:::
## 解法
我们考虑把整个方法倒过来。考虑归并排序，因为每次都是折半取，所以符合题目要求，而且区间内还是排序好的，于是直接修改答案即可。时间复杂度 $O(n\log n)$。
## 代码
```cpp line-numbers
#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：加乘运算
## 题意
:::align{center}
图 $3$：C 题原题面。
:::
## 解法
假设我们现在有一个式子
$$
[(a*^b c)*^e (d*^fg)]*^h
$$
显然我们如果修改 $a$，答案只会影响所有与 $a$ 有关的系数，就是 $b,e,h$ 三个系数。
于是，我们考虑像求后缀表达式的值一样把每个数的系数求出来，这里用一个栈就行。然后每次查询直接把差值与系数相乘并计算答案即可。时间复杂度 $O(n\log n)$。但我并不确定，因为是 gdz 告诉我的。
## 代码
```cpp line-numbers
#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：课程安排
## 题意
:::align{center}
图 $4$：D 题原题面
:::
## 解法
显然，我们可以用 DP 求解。
设第 $i$ 天有课的时间为 $cnt_i$，最左边的是 $ll_i$，最右边的是 $rr_i$。我们枚举当前是第 $i$ 天，要剩余 $j$ 个课时，我们能够很快得到满足条件的最短区间。它的代价是 $cnt_i-j$，价值是区间长度。
然后跑 01 背包板子就行了，但是需要注意的是：你不能一天搞两遍，所以这里再加一次循环跑枚举这一天砍哪个。
## 代码
```cpp line-numbers
#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;
}
```