2024-11-4 MX NOIP 模拟

ps：四道题都找到了原题 xwx
T1 T2 T3 T4

T1

思路

贪心，我现在依然不会证明（
考虑凑出所有位都是 \(1\)，然后计算有多少个，算一下就好了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
    int res=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    return res*f;
}
const int MAXN=1e5+10;
const int mod=1e9+7;
const int inv2=500000004;

int n,m,t;

signed main(){
    freopen("testdata.in","r",stdin);
    freopen("testdata.out","w",stdout);
//  freopen("t1_2.in","r",stdin);
//  freopen("t1_2.out","w",stdout);
    t=read();
    while(t--){
        m=read();n=read();
        if(m==1) cout<<0<<'\n';
        else{
            for(int i=1;i<=40;i++) m|=(m>>1);
            m%=mod;
            int val=n-1-(n%2==0);
            val+=2;
            val=val*((n-1)/2)%mod*inv2%mod;
            if(n%2==0) val=(val+n/2)%mod;
            cout<<val*m%mod<<'\n';
        }
    }
    return 0;
}

T2

思路

首先可以证明，多个人一起干一件事情，会比分开干更优。
这个我当时稍微小小的算了一下，更多的是感性证明 xwx。

然后可以想到去枚举最后有几个帮手，假设枚举的是 \(i\)。而且我们肯定是先得到这几个帮手，再去完成剩下的任务。

考虑按照 \(b_{i}\) 来排序，不一定选前 \(i\) 个的 \(b_{i}\) 是最优的，因此可以考虑 DP。
设 \(dp_{i,j,k}\) 表示当前在考虑第 \(i\) 个，算上这个位置已经选了 \(j\) 个没有帮手的，和 \(k\) 个有帮手的。转移是简单的。状态 \(O(n^{3})\)，转移 \(O(1)\)，要做 \(O(n)\) 次 DP，时间复杂度 \(O(n^{4})\)

这样的时间复杂度是没有办法接受的。我们需要优化。

我们可以发现，按照 \(b_{i}\) 来排序后，最后一个 \(b_{i}\) 之前的所有位置，肯定至少是会选上的，不一定会选上帮手。那么我们可以优化掉第二维，因为我们在确定了哪一个位置，前面已经有多少个是选了帮手的，可以直接确定后面还需要的时间的。
而这个时间是可以预处理的。
那么时间复杂度就成功地优化到了 \(O(n^{3})\)，可以通过。

代码

注意，像我这么预处理一定要用 stable_sort！！！！！
具体原因可以自己思考一下，我因为这个调了好久呜呜qwq。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=500+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,sum[MAXN][MAXN];
double ans,dp[MAXN][MAXN];
struct node{
    int a,b;
}p[MAXN];

bool cmp1(node n1,node n2){
    return n1.b<n2.b;
}

bool cmp2(node n1,node n2){
    return n1.a<n2.a;
}

signed main(){
    // freopen("mechanic.in","r",stdin);
    // freopen("mechanic.out","w",stdout);
    read(n,m);
    for(int i=1;i<=n;i++) read(p[i].a,p[i].b);
    for(int i=1;i<=n;i++) p[i].b=(p[i].b==-1?1e9:p[i].b);
    for(int i=1;i<=n;i++){
        stable_sort(p+1,p+n+1,cmp1);
        stable_sort(p+i,p+n+1,cmp2);
        for(int j=i;j<=n;j++) sum[i][j-i+1]=sum[i][j-i]+p[j].a;
    }
    ans=1e9;
    sort(p+1,p+n+1,cmp1);
    for(int i=0;i<n;i++){
        memset(dp,0x7f,sizeof(dp));
        dp[0][0]=0;
        for(int j=1;j<=n;j++){
            for(int k=0;k<=i;k++){
                dp[j][k]=dp[j-1][k]+1.0*p[j].a/(i+1);
                if(k) dp[j][k]=min(dp[j][k],dp[j-1][k-1]+1.0*p[j].b/k);
            }
        }
        for(int j=i;j<=m;j++) ans=min(ans,dp[j][i]+1.0*sum[j+1][m-j]/(i+1));
    }
    printf("%.9f",ans);
    return 0;
}

T3

全场唯一有分的捏 awa

思路

暴力

先说暴力，因为暴力都是需要思考一下的（
如果纯粹地去枚举每个位置填什么字母的话，再暴力判断是否合法，时间复杂度是 \(O(nm26^{n})\) 的。连暴力分都拿不到……

观察一下题目的性质，发现如果 \(a_{i} < b_{i}\)，那么这个区间要合法，需要满足以下两个条件任一：

• 存在一个 \(pos \in [a_{i},b_{i})\)，使得 \(s_{pos}> s_{pos+1}\)，并且在 \([a_{i},pos)\) 间都为 \(s_{pos}=s_{pos+1}\)，
• 所有的 \(pos \in [a_{i},b_{i})\) 均满足 \(s_{pos}=s_{pos+1}\)，

若 \(a_{i} > b_{i}\) 其实类似，对于 \(a_{i} = b_{i}\) 的情况不用管。

\(a_{i} > b_{i}\) 称为第一类区间。 \(a_{i} < b_{i}\) 称为第二类区间。

那么我们就可以只需要枚举 \(3\) 种状态即可。最后用一个 DP 统计方案数，时间复杂度 \(O(3^{n}n26)\)。

正解

我们把所有可以放 大于号 或者 小于号 的位置拿出来，发现假如 \(pos\) 位置可以放。设上一个可以放的最远位置为 \(pos'\)，那么在 \([pos',pos)\) 这个区间内都是可以放的。

设 \(dp_{i,j}\) 表示 \(i\) 这个位置放 \(j\) 这个字符，然后枚举这一段是 大于，等于，还是小于 前一段。使用前缀和优化，可以做到 \(O(26)\) 转移。

• 等于：直接转移即可。
• 小于：那么这一个点可以满足所有约束区间，并且不能存在包含了这个点第二类区间。因此其实 \(pos\) 就是当前最右的第二类区间的左端点。这个可以使用 set 维护。
• 大于：类似于小于。

最终时间复杂度 \(O(26n\log n )\)。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=5e5+10;
const int mod=1e9+7;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,ans,dp[MAXN][26],z[26];
vector<int> l1[MAXN],r1[MAXN],l2[MAXN],r2[MAXN];
multiset<int> s1,s2;

signed main(){
    freopen("girl.in","r",stdin);
    freopen("girl.out","w",stdout);
    read(n,m);
    for(int i=1;i<=m;i++){
        int a,b;
        read(a,b);
        //话说a=b的时候应该没影响的吧……continue了就行了吧？
        if(a==b) continue;
        if(a<b){
            l1[a].push_back(b-1);
            r1[b-1].push_back(a);
        }
        else{
            l2[b].push_back(a-1);
            r2[a-1].push_back(b);
        }//左右端点一一对应
    }
    s1.insert(0);s2.insert(0);
    for(int i:l1[1]) s1.insert(1);
    for(int i:l2[1]) s2.insert(1);
    for(int i=0;i<26;i++) dp[1][i]=1;
    for(int i=2;i<=n;i++){
        for(int j=0;j<26;j++) dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
        // <
        int pos=*prev(s1.end()),sum=0;
        for(int j=0;j<26;j++) z[j]=(dp[i-1][j]-dp[pos][j]+mod)%mod;
        for(int j=0;j<26;j++){//靠，上面这里j打成i看了好久
            dp[i][j]=(dp[i][j]+sum)%mod;
            sum=(sum+z[j])%mod;
        }
        // >
        pos=*prev(s2.end()),sum=0;
        for(int j=0;j<26;j++) z[j]=(dp[i-1][j]-dp[pos][j]+mod)%mod;
        for(int j=25;j>=0;j--){
            dp[i][j]=(dp[i][j]+sum)%mod;
            sum=(sum+z[j])%mod;
        }
        for(int j:r1[i-1]) s1.erase(s1.find(j));
        for(int j:r2[i-1]) s2.erase(s2.find(j));
        for(int j:l1[i]) s1.insert(i);
        for(int j:l2[i]) s2.insert(i);
    }
    for(int i=0;i<26;i++) ans=(ans+dp[n][i])%mod;
    cout<<ans;
    return 0;
}

T4

考试是想到了 \(55pts\) 的一种复杂做法，但是其实只需要把过程倒过来就很容易了。最后写了一个 \(O(n^{4})\) 的暴力，本来只能拿 \(15pts\) ，但不知道为什么拿到了和 \(O(n^3)\) 一样的 \(30pts\)（乐

正解比较抽象，就不说了xwx

可以自行查阅题解，题目链接放在最开始那里的。