T1
我们发现第一问很好解决，就直接按照从大到小的顺序排序，然后依次选就行了。
然后第一问的答案就出来了。
随后我们看第二问，我们发现和零一背包很相似。
解决这样一个问题, 我们可以使用 01 背包。用 f i , j , k f_{i, j, k} fi,j,k 表示在前 i 个瓶子中选择了 j 个瓶子, 总容积为 k 的最大不移动的液体体积和。我们可以得到：
f i , j , k = max ( f i − 1 , j , k , f i − 1 , j − 1 , k − b i + a i ) f_{i, j, k}=\max \left(f_{i-1, j, k}, f_{i-1, j-1, k-b_{i}}+a_{i}\right) fi,j,k=max(fi−1,j,k,fi−1,j−1,k−bi+ai)
然后我们用滚动数组优化，把i这维省去就可以了
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
const int N=110;
struct node {int a,b;
} e[N];
int sum[N];
int all;
bool cmp(node x,node y) {
// if(x.b==y.b) return x.a>y.a;return x.b>y.b;
}
int f[N][10010];
signed main() {
// freopen("3.in","r",stdin);int n=read();for(int i=1; i<=n; i++) {e[i].a=read();all+=e[i].a;}for(int i=1; i<=n; i++) {e[i].b=read();
// sum[i]=sum[i-1]+e[i].b;}sort(e+1,e+1+n,cmp);int id=0;for(int i=1; i<=n; i++) {sum[i]=sum[i-1]+e[i].b;if(sum[i]>=all) {id=i;break;}}int res=0,ans=0;for(int i=1;i<=id;i++){res+=e[i].b;}
// cout<<res<<endl;memset(f,-0x3f,sizeof(f));f[0][0]=0;for(int i=1; i<=n; i++){for(int j=id; j; j--){for(int k=res; k>=e[i].b; k--){f[j][k]=max(f[j][k],f[j-1][k-e[i].b]+e[i].a);}}}
// cout<<all<<" "<<res<<endl;for(int i=all; i<=res; i++){
// cout<<f[id][i]<<endl;ans=max(ans,f[id][i]);}
// cout<<"OP"<<sum;printf("%lld %lld",id,all-ans);return 0;
}T2
这道题目看到数学式子不能硬求，一般遇到都要进行化简。
我们进行化简： ∑ i = 1 n ( x i − x ˉ ) 2 n = ∑ i = 1 n x i 2 n − ( x ˉ ) 2 \frac{\sum_{i=1}^{n}\left(x_{i}-\bar{x}\right)^{2}}{n}=\frac{\sum_{i=1}^{n} x_{i}^{2}}{n}-(\bar{x})^{2} n∑i=1n(xi−xˉ)2=n∑i=1nxi2−(xˉ)2 。显然对于每个询问, 平均数是固定的, 所以题目相当于最小化平方和。假设一开始所有 a i 都取到 l i a_{i} 都取到 l_{i} ai都取到li , 只需要以此为基础将一些 a i a_{i} ai 的值增加。若将 x − 1 x-1 x−1 增加到 x x x , 平方和增加 x 2 − ( x − 1 ) 2 = x × 2 − 1 x^{2}-(x-1)^{2}=x \times 2-1 x2−(x−1)2=x×2−1 。所以显然每次将最小值增加 1 1 1 最优。
然后我们就是实现了：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e6+26,mx=1e6,mod=998244353;
struct Query {ll x,id,ans;friend bool operator<(Query xy,Query zb) {return xy.x<zb.x;}
} qq[maxn];
ll n,q,invn,l[maxn],r[maxn],cnt[maxn],ans,ansx;
ll read() {ll x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
inline ll Pow(ll x,ll y) {if(!y)return 1;if(y&1)return Pow(x,y^1)*x%mod;return Pow(x*x%mod,y>>1);
}
int main() {n=read(),q=read();invn=Pow(n,mod-2);for(ll i=1; i<=n; i++) {l[i]=read(),r[i]=read();ans+=l[i]*l[i];ansx+=l[i];cnt[l[i]+1]++;cnt[r[i]+1]--;}for(ll i=0; i<=mx; i++)cnt[i]+=cnt[i-1];for(ll i=1; i<=q; i++) {qq[i].x=read();qq[i].id=i;}sort(qq+1,qq+q+1);for(ll i=1,j=0; i<=q; i++) {while(ansx<qq[i].x) {if(qq[i].x-ansx<cnt[j]) {cnt[j]-=(qq[i].x-ansx);(ans+=(qq[i].x-ansx)*(j*2-1)%mod)%=mod;ansx=qq[i].x;break;}ansx+=cnt[j];(ans+=cnt[j]*(j*2-1)%mod)%=mod;j++;}qq[i].ans=ans;qq[i].x%=mod;}sort(qq+1,qq+q+1,[](Query xy,Query zb) {return xy.id<zb.id;});for(ll i=1; i<=q; i++)printf("%lld\n",(qq[i].ans*invn%mod-qq[i].x*qq[i].x%mod*invn%mod*invn%mod+mod)%mod);return 0;
}T3
这道题感觉和滑动窗口很像，然后我们往单调队列想，就不难得出正解。
我们用单调队列来维护给定区间的最大值。
设 f i , j f_{i,j} fi,j表示，前i个数已经选了j个数的最大值，单调队列里维护的是最大值点的位置，对转移进行优化，省去了不必要的转移
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}const int N=5050;
int f[N][N];
int q[N];
int a[N];
int ans;
signed main(){
// freopen("3.in","r",stdin);memset(f,0xcf,sizeof f);int n=read(),k=read(),x=read();for(int i=1;i<=n;i++){a[i]=read();}if(n/k>x){puts("-1");return 0;}f[0][0]=0;for(int j=1;j<=x;j++){int l=1,r=1;q[r]=0;for(int i=1;i<=n;i++){while(l<=r&&q[l]+k<i) l++;f[i][j]=f[q[l]][j-1]+a[i];while(l<=r&&f[i][j-1]>=f[q[r]][j-1]) r--;q[++r]=i;}}for(int i=n-k+1;i<=n;i++){ans=max(ans,f[i][x]);}printf("%lld",ans);return 0;
}
T4
说来也奇怪，我的贪心跑出来的最小值比答案的最小值还小，得分 17 p t s 17pts 17pts
先说一下我的假做法。
我们可以按高度进行排序，然后我们就依次进行判断就行了，这样肯定是假的，但是在写不出正解的情况下就得写一个这个。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
const int N=1e5+10;
struct node{int h,w;
}gf[N];//女朋友
bool cmp(node a,node b){return a.h>b.h;
}
signed main(){
// freopen("1.in","r",stdin);int n=read(),l=read();for(int i=1;i<=n;i++){gf[i].h=read(),gf[i].w=read();}sort(gf+1,gf+1+n,cmp);int ans=0,res=0;int maxn=0;for(int i=1;i<=n;i++){if(res+gf[i].w>l){res=0;
// cout<<maxn<<endl;ans+=maxn;maxn=0;}res+=gf[i].w;maxn=max(maxn,gf[i].h);}ans+=maxn;printf("%lld",ans);return 0;
}然后考虑正解
用线段树优化DP
f i f_{i} fi 表示第 i i i 本书结尾时高度和的最小值。
f i = min ( f j + max ( h j + 1 , … , h i ) ) ( w j + 1 + … + w i ≤ L ) f_{i}=\min \left(f_{j}+\max \left(h_{j+1}, \ldots, h_{i}\right)\right)\left(w_{j+1}+\ldots+w_{i} \leq L\right) fi=min(fj+max(hj+1,…,hi))(wj+1+…+wi≤L)
w w w 这个限制我们可以通过二分得到
现在我们把问题转化成：
f i = min ( f j + max ( h j + 1 , … , h i ) ) ( pos i ≤ j ) f_{i}=\min \left(f_{j}+\max \left(h_{j+1}, \ldots, h_{i}\right)\right)\left(\operatorname{pos}_{i} \leq j\right) fi=min(fj+max(hj+1,…,hi))(posi≤j)
其中 p o s i p o s_{i} posi 为第 i 个位置的最左端点。
然后是如何使用线段树优化
p o s i pos_i posi的值我们可以在一开始用双指针把区间存起来
而且我们还能用线段树二分来找到 p o s i pos_i posi 这个值，但设个我感觉就复杂了
首先, 我们先开一个单调栈, 对于每个位置找出第一个大于 h i h_{i} hi 的位置 l , 并将 [ l + 1 , i ] [l+1, i] [l+1,i] 这段区间内的 h h h 赋为 h i h_{i} hi 。单调栈可以直接找到需要更新区间的端点
我们发现每一个位置的 f f f 是确定的, 我们每次只需区间修改 h h h 的值, 然后维护 f + h f+h f+h 和 f f f 的最小值。
最后更新用区间查询就行了
#include <bits/stdc++.h>
#define ll long long
#define lson (rt<<1)
#define rson (rt<<1|1)
using namespace std;
const int maxn=100000+10;
const ll inf=1e18;
int n,L,w[maxn],h[maxn],pre[maxn],sta[maxn],top;
ll sum[maxn],f[maxn],Min[maxn<<2],val[maxn<<2],tag[maxn<<2];
// Min 为 f + h 的最小值
// val 为 f 的最小值inline int read() {register int x=0,f=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)) {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return (f==1)?x:-x;
}inline void pushup(int rt) {Min[rt]=min(Min[lson],Min[rson]);val[rt]=min(val[lson],val[rson]);
}inline void pushdown(int rt) {if(tag[rt]!=inf) {Min[lson]=val[lson]+tag[rt];Min[rson]=val[rson]+tag[rt];tag[lson]=tag[rson]=tag[rt];tag[rt]=inf;}
}void build(int l,int r,int rt) {Min[rt]=val[rt]=tag[rt]=inf;if(l == r) return ;int mid=(l+r)>>1;build(l,mid,lson);build(mid+1,r,rson);
}void update(int L,int R,int C,int l,int r,int rt) {if(L <= l && r <= R) {Min[rt]=val[rt]+C;tag[rt]=C;return ;}pushdown(rt);int mid=(l+r)>>1;if(L <= mid) update(L,R,C,l,mid,lson);if(R > mid) update(L,R,C,mid+1,r,rson);pushup(rt);
}void modify(int x,int l,int r,int rt) {if(l == r) {Min[rt]=inf;val[rt]=f[l-1];return ;}pushdown(rt);int mid=(l+r)>>1;if(x <= mid) modify(x,l,mid,lson);else modify(x,mid+1,r,rson);pushup(rt);
}ll query(int L,int R,int l,int r,int rt) {if(L <= l && r <= R) return Min[rt];pushdown(rt);int mid=(l+r)>>1;ll ans=inf;if(L <= mid) ans=min(ans,query(L,R,l,mid,lson));if(R > mid) ans=min(ans,query(L,R,mid+1,r,rson));return ans;
}int main() {n=read(),L=read();for(int i=1; i<=n; i++) {h[i]=read(),w[i]=read();sum[i]=sum[i-1]+w[i];}sta[++top]=1;for(int i=2; i<=n; i++) {while(top&&h[i]>h[sta[top]]) top--;if(top) pre[i]=sta[top];sta[++top]=i;}build(1,n,1);for(int i=1; i<=n; i++) {modify(i,1,n,1);if(pre[i]+1<=i) update(pre[i]+1,i,h[i],1,n,1);int l=lower_bound(sum,sum+i+1,sum[i]-L)-sum;if(l<i) f[i]=query(l+1,i,1,n,1);}printf("%lld\n",f[n]);return 0;
}
这次比赛全是DP，差评完全不像模拟赛