10.3模拟赛

miller2014 · 2025-10-03 16:36:35 · 个人记录

分数

估分

T1:100pts
T2:100pts
T3:30pts
T4:30pts

实际

T1:100pts
T2:60pts
T3:20pts
T4:35pts

原因

T1:无
T2:没加快读和记忆化qwq
T3:骗分失败了qwq虽然我怀疑是数据问题但我没证据qwq
T4:Special Judge配rand给我多骗了5pts

题解

T1

太简单了

T2

太简单了

T3

一道经典的区间dp。

状态

设 dp_{l,r} 表示对于下标为 l,l+1,...,r-1,r 的所有数，先手最大能得到多少分。

答案

很明显，答案为 dp_{1,n} 。

边界

很明显，边界为 dp_{i,i}=a_i 。

方程

设s为原数组的前缀和，分别计算先手的两种方案，方程如下（其中 l+len 表示右端点）：

每次修改将区间内含有对应的数的值重新计算即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,_,x,answer,a[1005],s[1005],dp[1005][1005];
signed main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i],s[i]=s[i-1]+a[i];
    for(int i=1;i<=n;i++)dp[i][i]=a[i];
    for(int len=1;len<n;len++)
        for(int l=1;l+len<=n;l++)
            dp[l][l+len]=s[l+len]-s[l-1]-min(dp[l+1][l+len],dp[l][l+len-1]);
    for(_=1;_<=q;_++)
    {
        cin>>x;
        a[_]=x;
        for(int i=_;i<=n;i++)s[i]=s[i-1]+a[i];
        dp[_][_]=x;
        for(int len=1;len<n;len++)
            for(int l=max(1ll,_-len);l<=_;l++)
                dp[l][l+len]=s[l+len]-s[l-1]-min(dp[l+1][l+len],dp[l][l+len-1]);
        cout<<dp[1][n]<<"\n";
    }
    return 0;
}

T4

一道贪心题。

想要被质问人数最大，就让每个人选的尽量小,尽量贴边选数（ +1 ）。想要被质问的人数最小，就让每个人都选上限。

#include<bits/stdc++.h>
using namespace std;
int n,l,r,R,minn,maxx,ansmax,ansmin;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>l>>r;
        R=max(R,r);
        if(minn<l)ansmin++,minn=R;
        if(maxx<r)ansmax++,maxx=max(maxx+1,l);
    }
    return (cout<<ansmax<<"\n"<<ansmin)&&0;
}