前言
您好亲爱的BLOG
还好你没炸
但是我炸了
原题地址，感谢 @cqrcqr 的无私付出让我们拥有了LATEX！
[T1]
(100/100)
终于看到可以做的题了，感动
毫无疑问可以直接维护两个数组，每次用 O(1) 的时间复杂度算出若操作 [l,l+m-1] 的总值。
时间复杂度 O(n)
算了放个代码水一水
#include
using namespace std;
const int N=2e5+5;
typedef long long LL;
int n,m;
LL k,sum,sp[N],cnt[N],res=0;
int main()
{
freopen("ghost.in","r",stdin);
freopen("ghost.out","w",stdout);
scanf("%d%d%lld",&n,&m,&k);
for(int i=1;i<=n;i++)
{
LL x;
scanf("%lld",&x);
if(x<k)
{
cnt[i]=1;
sp[i]=x;
}
sum+=x;
sp[i]+=sp[i-1];
cnt[i]+=cnt[i-1];
}
for(int l=1;l+m-1<=n;l++)
{
int r=l+m-1;
LL ans=sum-(sp[r]-sp[l-1])+(cnt[r]-cnt[l-1])*k;
res=max(res,ans);
}
printf("%lld",res);
return 0;
}
[T2]
(100/100)
赛时大样例怎么有错啊……
考虑原始的 01背包DP 方程式：
$f[i][j]=max(f[i-1][j],f[i-1][j-v]+w)$
考虑加入一维，代表有没有选择 i 这个物品
如果连续选择了 i-1 与 i 两个物品，就直接在计算贡献时减 k。
时间复杂度 O(nm) ，可通过滚动数组将空间复杂度降到 O(m) 。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=105,M=2e5+5;
typedef long long LL;
int n,m;
LL k;
LL f[2][M][2];
int main()
{
freopen("item.in","r",stdin);
freopen("item.out","w",stdout);
scanf("%d%d%lld",&n,&m,&k);
for(int i=1;i<=n;i++)
{
int v;
LL w;
scanf("%d%lld",&v,&w);
for(int j=0;j<=m;j++)
{
f[i&1][j][0]=f[i&1][j][1]=0;
f[i&1][j][0]=max(f[i-1&1][j][0],f[i-1&1][j][1]);
if(j>=v)f[i&1][j][1]=max(f[i-1&1][j-v][0]+w,f[i-1&1][j-v][1]+(w-k));
}
}
LL res=0;
for(int i=0;i<=m;i++)
{
if(res<f[n&1][i][0])res=f[n&1][i][0];
if(res<f[n&1][i][1])res=f[n&1][i][1];
}
printf("%lld",res);
return 0;
}
[T3]
(100/100)
二分绝佳好题。
由于修改操作并不影响原序列顺序，因此修改的二分是好写的。
但是查询的操作似乎不太好写。
这里，以下的下标值所有序列反转后的下标。
我们二分前 k-1 个中，在 x 中的有 t 个，在 y 中的有 k-t-1 个。
然后判断这样是否合法，不合法则继续二分。
由于我们发现其答案的合法性是形如一个开口向下的二次函数，因此具有单调性。
LXL老师的做法则是采用倍增式二分的写法。
每一次查询 x,y 序列中 \frac{k}{2} 的位置，对于较小者，舍弃前面位置，同时令 k=k-\frac{k}{2}，继续以上过程。
感觉听完后觉得自己的像是假做法。
两者时间复杂度均为 O(n \log n)
代码（我的做法）(是的我就是不要脸)
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,T;
int a[N][N];
void modify(int x,int w)
{
int l=1,r=m;
while(l<r)
{
int mid=l+r>>1;
if(a[x][mid]<=w)r=mid;
else l=mid+1;
}
if(a[x][l]<=w)a[x][l]=w;
}
int query(int x,int y,int k)
{
int l=0,r=k-1;
while(l<r)
{
int mid=l+r>>1;
//a[x] 有 mid a[y] 有 k-1-mid 个
//a[x] 最后被选为 a[x][mid] a[y]最后被选的为a[y][k-1-mid]
int apos=mid,bpos=k-mid-1;
if(bpos<0||apos>m)
{
r=mid-1;
continue;
}
if(apos<0||bpos>m)
{
l=mid+1;
continue;
}
if(1<=apos+1&&apos+1<=m&&a[x][apos+1]>a[y][bpos])
{
l=mid+1;
continue;
}
if(1<=bpos+1&&bpos+1<=m&&a[y][bpos+1]>a[x][apos])
{
r=mid-1;
continue;
}
int res=0;
if(1<=apos+1&&apos+1<=m)res=max(res,a[x][apos+1]);
if(1<=bpos+1&&bpos+1<=m)res=max(res,a[y][bpos+1]);
return res;
}
int apos=l,bpos=k-l-1;
int res=0;
if(1<=apos+1&&apos+1<=m)res=max(res,a[x][apos+1]);
if(1<=bpos+1&&bpos+1<=m)res=max(res,a[y][bpos+1]);
return res;
}
int main()
{
freopen("int.in","r",stdin);
freopen("int.out","w",stdout);
scanf("%d%d%d",&n,&m,&T);
for(int i=1;i<=n;i++)
{
for(int j=m;j;j--)scanf("%d",&a[i][j]);
}
while(T--)
{
int op,x,y,k;
scanf("%d%d%d",&op,&x,&y);
if(op==1)
{
scanf("%d",&k);
printf("%d\n",query(x,y,k));
}
else modify(x,y);
}
return 0;
}
[T4]
(0/100)
服了自己在考场上的失智行为，竟然直接开 unordered_map 当数组。
总体的思路没有大问题，其实就是每当一个数（设为 x）加入时，将答案乘以 (x+1) （可以由组合意义推）
然后像并查集式的维护 ne 指针，代表下一个未加入数的下标。
期望时间复杂度 O(n)
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+2,K=1e7;
typedef long long LL;
int n,cnt,ne[N],vis[N];
LL mod,res=1;
int find(int x)
{
if(!vis[x])return x;
else return ne[x]=find(ne[x]);
}
int main()
{
freopen("homework.in","r",stdin);
freopen("homework.out","w",stdout);
scanf("%d%lld",&n,&mod);
for(int i=1;i<=K;i++)ne[i]=i+1;
while(n--)
{
int l,r;
scanf("%d%d",&l,&r);
int cur=l;
while(cur<=r)
{
if(!vis[cur])
{
res=res*(cur+1)%mod;
vis[cur]=1;
}
int t=cur;
cur=find(cur);
ne[t]=find(ne[r]);
}
printf("%lld\n",((res-1)%mod+mod)%mod);
}
return 0;
}