8.23 膜 $n^2$ 过50000赛

这篇文章上次修改于 464 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

本文共 3159 个字，阅读时长 ≈ 8 分钟

题目的名称真是蕴意深刻呢

T1：372. 认真读题很重要

本场主角，赛时脑抽没想到正解糊了个理论时间复杂度 $O(n^2)$ 的暴力，理论上来说只能过前 $60\% n\leq 5000$ 的数据，但是为啥说T1是本场主角呢，因为赛后发现我的这个暴力过了 $100\% n\leq 50000$ 的数据。啪的一下很快啊，我这个人就傻了，点开数据一看发现答案都贼小没有一个大于100的，而我的暴力是直接从小到大枚举答案然后判断是否合法，如果合法直接输出然后return 0;。遇上这种数据直接跑的飞快最慢一个点只用了75ms。

言归正传，这个题正解是个单调队列优化dp，为啥捏，我也不知道（逃）通过二分固定最小的指标，然后用dp检查是否能在花费m个单位时间内种好这些树。既然要在m个单位时间内，那我们自然考虑到选花费时间最少的树种，这里就可以用单调队列优化一下。~~成功说了一堆废话~~

code：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=50004;
int n,m,h,t;
int a[N],f[N],q[N];
bool check(int x){
    int ans=1145141919;
    for(int i=0;i<=n;++i) f[i]=q[i]=0;
    h=t=0;
    //单调队列优化dp，确定这个指标能不能被达到
    for(int i=1;i<=n;i++)
    {
        while(h<t&&q[h+1]<i-x) ++h;
        while(h<t&&f[q[t]]>f[i-1]) --t;
        q[++t]=i-1;
        f[i]=f[q[h+1]]+a[i];
        if(i+x>n)
            ans=min(f[i],ans);
    }
    if(ans<=m) return 1;
    else return 0;
}
int main()
{
    n=read();
    m=read();
    for(int i=1;i<=n;++i) a[i]=read();
    int l=0,r=n,mid;
    while(l<r){
        //二分固定指标
        mid=(l+r)>>1;
        if(check(mid+1)) r=mid;
        else l=mid+1;
    }
    printf("%d\n",r);
    return 0;
}

T2：1324. 打暴力也能得分

洛谷原题

膜拜机房大佬Orz

大佬将这个题目转化了亿下，因为是对 ${a_i}^2$ 求和，可以转化为两个人每人都有一个A串一个B串，从后面取数所构成的串一样的方案数。

先推出来一个暴力的dp式子，设 $f[i][j][k][l]$ 表示第一个人取了A串的后i个B串的后j个，第二个人取了A串的后k个B串的后l个时两个人的串一样的方案数，转移方程就是判断枚举到的位置是否相同如果相同那就将方案数相加即可。但是四维显然会T飞，考虑优化，两个人在同一时间所取的数的个数一定是相同的，我们可以把最后一维省掉，因为最后一维l可以通过前三维算出来，就是 $l=i+j-k$，然后看一下转移方程发现i只跟前一维有关，毫不犹豫滚动数组。

code：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=600,mod=1e9+7;
int n,m;
int a[N],b[N];
long long f[2][N][N];
inline void add(int x,long long &y){
    y+=(long long)x;
    if(y>=mod) y-=mod;
}
int main()
{
    n=read();
    m=read();
    for(int i=1;i<=n;++i) a[i]=getchar()-'0';
    getchar();
    for(int i=1;i<=m;++i) b[i]=getchar()-'0';
    int t,cur=0;
    f[0][0][0]=1;
    for(int i=0;i<=n;++i,cur^=1){
        for(int j=0;j<=m;++j){
            for(int k=0;k<=n;++k){
                t=f[cur][j][k];
                if(i+j-k>m||i+j-k<0) continue;
                //判断枚举到的位置是否相同，相同就把方案数加起来
                if(a[i+1]==a[k+1]) add(t,f[cur^1][j][k+1]);
                if(b[j+1]==b[i+j-k+1]) add(t,f[cur][j+1][k]);
                if(a[i+1]==b[i+j-k+1]) add(t,f[cur^1][j][k]);
                if(b[j+1]==a[k+1]) add(t,f[cur][j+1][k+1]);
                f[cur][j][k]=0;
            }
        }
    }
    printf("%lld\n",f[cur][m][n]);
    return 0;
}

T4：1664. 贪心只能过样例

继续膜拜机房大佬Orz

一种状压dp的思想，$f[i][j]$ 表示到了第 $i$ 行时 $j$ 这个数能不能被拼出来，转移方程就是 $f[i][j]|=f[i-1][j-x*x]$，$j$ 不是很大可以直接开到数组里。同机房大佬用了bitset优化空间，%%%%%。开100个1e6的01串，每个串的第 $i$ 位代表第 $i$ 个数字是否能被拼出来，如果第 $i-1$ 个数的第 $j$ 位是1，那么左移 $x*x$ 位后依旧是1，就代表枚举到第 $i$ 位时第 $j+x*x$ 这个数可以被拼出来，转移方程就变为 $f[i]|=(f[i-1]<<(x*x))$。代码是bitset版。

code：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<bitset>
using namespace std;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=102;
int n;
int l[N],r[N];
bitset<1000006> f[N];
int main()
{
    n=read();
    for(int i=1;i<=n;++i){
        l[i]=read();
        r[i]=read();
    }
    f[0].set(0);//相当于是f[0][0]=1
    for(int i=1;i<=n;++i){
        f[i]|=f[i-1]<<(l[i]*l[i]);
        f[i]|=f[i-1]<<(r[i]*r[i]);
    }
    printf("%d\n",f[n].count());
    return 0;
}

~~这篇文章其实是8.24发布的，而且还没写完，但是为了装出一副我很勤奋的样子，我动用op的力量把它的发布时间设置到了比完赛后六个小时~~

没有楼的楼长