LOJ515 贪心只能过样例 解题报告

#515. 「LibreOJ β Round #2」贪心只能过样例

内存限制：256 MiB

时间限制：1000 ms标准输入输出

题目类型：传统

评测方式：文本比较

题目描述

一共有$n$个数，第$i$个数$xi$可以取$[a_i , b_i]$中任意值。
设$S = \sum{{x_i}^2}$，求$S$种类数。

输入格式

第一行，一个数$n$。
然后$n$行，每行两个数表示$a_i,b_i$。

输出格式

输出一行，一个数表示答案。

样例

样例输入

5

1 2

2 3

3 4

4 5

5 6

样例输出

26

数据范围与提示

$1 \le n , a_i , b_i \le 100$

解析

这是一道很好的卡常数题。

核心思想就是枚举，设${\mathrm S}_i$为前$i$个数字的平方和的所有取值构成的集合。计算${\mathrm S}_{i+1}$时，我们可以遍历${\mathrm S}_i$，对于$x_i$的每一个取值$x$，尝试将${\mathrm S}_i+x^2$加入集合${\mathrm S}_{i+1}$，即： $${\mathrm S}_{i+1}=\bigcup\nolimits_{s\in{\mathrm S}_i,x\in\left[a_{i+1},b_{i+1}\right]}(s+x^2)$$

       分析最坏情况复杂度：

       设$m$为$x_i$的取值范围，$card({\mathrm S}_i)\leqslant nm^2$，也就是每一次递推将枚举$O(nm^2)$个${\mathrm S}_i$集合的元素，每次递推的复杂度为$O(m)\cdot O(nm^2)=O(nm^3)$，而总共需要递推$n$次，因此总的复杂度为$O(n^2m^3)$。

       刚才的分析成立的前提条件是，我们可以在$O(n)$的时间复杂度内遍历一个大小为$n$的动态集合，同时在$O(1)$的复杂度内向动态集合中插入元素。可这样的数据结构是不存在的。

       接下来我们将测试该算法的不同的实现方式的具体运行时间。

       测试数据：$n=100$，$a_i=1$，$b_i=100$。

       编译器版本：MinGW64 8.1.0

       编译指令：g++ -e100wt.cpp -o e100wt.ext -Wl,--stack=2147483648 -std=c++98 -O0

       连接指令：-static-libgcc

       运行处理器：Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz

实现一：std::set

       用set::insert()插入，set::iterator遍历，时间复杂度为$O(n^2m^3\log(nm^2))=O(n^2m^3\log n+n^2m^3\log m)$。

       代码实现：

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <algorithm>

#include <vector>

#include <utility>

#include <set>

using namespace std;

namespace Solution

{

    template<typename tp>

    void read(tp &x)

    {

        x=0;char ch=getchar();

        while(ch>'9'||ch<'0'){ ch=getchar(); }

        while(ch>='0'&&ch<='9'){ x=x*10+ch-48;ch=getchar(); }

    }

    unsigned int l[101],r[101];

    unsigned int n;

    set<unsigned int> S[101];

    int main()

    {

        read(n);

        for(register unsigned int i=1;i<=n;i++)

        {

            read(l[i]);

            read(r[i]);

        }

        S[0].insert(0);

        for(unsigned int i=1;i<=n;i++)

        {

            cerr<<i<<endl;

            for(set<unsigned int>::iterator j=S[i-1].begin();j!=S[i-1].end();j++)

            {

                for(unsigned int k=l[i];k<=r[i];k++)

                {

                   S[i].insert((*j)+k*k);

                }

            }

        }

        cout<<S[n].size();

        return 0;

    }

}

int main()

{

    freopen("e100wt.in","r",stdin);

    freopen("e100wt.out","w",stdout);

    return Solution::main();

}

       运行结果：Process exited after 2383 seconds with return value 0

       如此长的用时堪比未来程序的第一个测试点的程序。

实现二：std::vector

       vector::push_back()的时间复杂度可视为$O(1)$，但无法判重，因此全部插入之后需要用sort()和unique()去重，插入的摊还代价仍然是$O(logn)$，但遍历集合的代价为$O(n)$，总的时间复杂度为仍然为$O(n^2m^3\log n+n^2m^3\log m)$，常数稍微小了一些。

       代码实现：

unsigned int l[101],r[101];

unsigned int n;

vector<unsigned int> S[101];

int main()

{

    read(n);

    for(register unsigned int i=1;i<=n;i++)

    {

        read(l[i]);

        read(r[i]);

    }

    S[0].push_back(0);

    for(unsigned int i=1;i<=n;i++)

    {

        cerr<<i<<endl;

        for(vector<unsigned int>::iterator j=S[i-1].begin();j!=S[i-1].end();j++)

        {

            for(unsigned int k=l[i];k<=r[i];k++)

            {

                S[i].push_back((*j)+k*k);

            }

        }

        sort(S[i].begin(),S[i].end());

        S[i].erase(unique(S[i].begin(),S[i].end()),S[i].end());

    }

    cout<<S[n].size();

    return 0;

}

       运行结果：Process exited after 1807 seconds with return value 0

       时间虽然明显缩短了，可是与1秒的时限还有极大的距离。

实现三：bool[]

   集合$S_i$中的元素最大只有$1000000$，为什么不直接用布尔数组表示集合呢？这样插入的复杂度变成了$O(1)$，遍历的复杂度变成了$nm^2$（没有渐进记号），总的时间复杂度为$O(n^2m^3)$，复杂度终于达到了最初分析的值，可常数略微增大了（$card( {\mathrm S}_i)$小于$nm^2$）。

       代码实现：

unsigned int l[101],r[101];

unsigned int n;

bool S[101][1000001];

int main()

{

    read(n);

    for(register unsigned int i=1;i<=n;i++)

    {

        read(l[i]);

        read(r[i]);

    }

    S[0][0]=true;

    for(unsigned int i=1;i<=n;i++)

    {

        //  cerr<<i<<endl;

        for(unsigned int j=0;j<=1000000;j++)

        {

            for(unsigned int k=l[i];k<=r[i];k++)

            {

                if(S[i-1][j])S[i][j+k*k]=true;

            }

        }

    }

    unsigned int ans=0;

    for(int i=0;i<=1000000;i++)

    {

        if(S[n][i])ans++;

    }

    cout<<ans;

    return 0;

}

       用时：Process exited after 25.45 seconds with return value 0

       时间大幅缩短了，我们看到了卡进1秒的曙光。

实现四：std::bitset ①

       直接把布尔数组换成bitset，改用bitset::count()统计答案，其他部分不变。

       运行结果：Process exited after 242.8 seconds with return value 0

       非但没有改善，反而慢了不少，传说中的$\frac1{32}$常数呢？

实现五：std::bitset ②

       把bitset当bool数组用当然不会减小时间常数，而且，CPU计算除法和取模的时间远大于从L3高速缓存读取数据，bitset的实现中大量使用了除法和取模，速度降低也就再正常不过了。为什么不能跳过元素的枚举，直接为整个集合加上$x^2$呢？从bitset的角度看，这就是左移$x^2$。这样常数真正变成了原来的$\frac1{32}$。

       代码实现：

unsigned int l[101],r[101];

unsigned int n;

bitset <1000001> S[101];

int main()

{

    read(n);

    for(register unsigned int i=1;i<=n;i++)

    {

        read(l[i]);

        read(r[i]);

    }

    S[0]=1;

    for(register unsigned int i=1;i<=n;i++)

    {

        for(register unsigned int k=l[i];k<=r[i];k++)

        {

            S[i]|=S[i-1]<<(k*k);

        }

    }

    cout<<S[n].count();

    return 0;

}

       运行结果：Process exited after 1.83 seconds with return value 0

       1秒已经近在咫尺了，可这$\frac12$的常数从哪去掉呢？

实现六：std::bitset ③

       注意到，$\mathrm S$集合之间的递推只存在于相邻的两个集合中，于是想到可以将$\mathrm S$改成滚动数组。

       运行结果：Process exited after 1.783 seconds with return value 0

       稍微快了一点。

实现七：手写bitset

       std::bitset的采用unsigned long储存，所以称它的常数是$\frac1{32}$，如果手写一个bitset并采用unsigned long long 储存，常数是否可以进一步缩小呢？答案是肯定的。实现按位或并不难，只要将每一个unsigned long long分别按位或就可以了（请原谅，为了卡常数我写了循环展开）：

bitset2& operator|=(const bitset2 &a)

{

    for(int i=0;i<15628;i+=4)

    {

        data[i]|=a.data[i];

        data[i+1]|=a.data[i+1];

        data[i+2]|=a.data[i+2];

        data[i+3]|=a.data[i+3];

    }

    return *this;

}

       左移运算比较复杂，参考STL的实现，对于运算a<<k，我们先将a.data[]整体左移$\frac k{64}$位，然后将a.data[i]局部左移$k\mod64$位：

bitset2 operator<<(int k)const

{

    int k1=k/64;

    bitset2 b,c;

    //c=(*this)<<k/64

    //整体左移

    for(int i=0;i<k1;i+=2)

    {

        c.data[i]=0;

        c.data[i+1]=0;

    }

    for(int i=k1;i<15628;i+=2)

    {

        c.data[i]=data[i-k1];

        c.data[i+1]=data[i-k1+1];

    }

    k%=64;

    if(!k)return c;

    //局部左移

    const int k2=64-k;

    b.data[0]=c.data[0]<<k;

    b.data[1]=(c.data[1]<<k)|(c.data[0]>>k2);

    for(int i=2;i<15628;i+=2)

    {

        b.data[i]=(c.data[i]<<k)|(c.data[i-1]>>k2);

        b.data[i+1]=(c.data[i+1]<<k)|(c.data[i]>>k2);

    }

    return b;

}

       运行结果：Process exited after 0.8867 seconds with return value 0

参考程序

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <algorithm>

#include <vector>

#include <utility>

#include <bitset>

using namespace std;

namespace Solution

{

    template<typename tp>

    void read(tp &x)

    {

        x=0;char ch=getchar();

        while(ch>'9'||ch<'0'){ ch=getchar(); }

        while(ch>='0'&&ch<='9'){ x=x*10+ch-48;ch=getchar(); }

    }

    unsigned int l[101],r[101];

    unsigned int n;

    class bitset2

    {

    public:

        void clear()

        {

            for(int i=0;i<15628;i+=4)

            {

                data[i]=0;

                data[i+1]=0;

                data[i+2]=0;

                data[i+3]=0;

            }

        }

        void setone()

        {

            data[0]=1;

        }

        bitset2& operator|=(const bitset2 &a)

        {

            for(int i=0;i<15628;i+=4)

            {

                data[i]|=a.data[i];

                data[i+1]|=a.data[i+1];

                data[i+2]|=a.data[i+2];

                data[i+3]|=a.data[i+3];

            }

            return *this;

        }

        bitset2 operator<<(int k)const

        {

            int k1=k/64;

            bitset2 b,c;

            for(int i=0;i<k1;i+=2)

            {

                c.data[i]=0;

                c.data[i+1]=0;

            }

            for(int i=k1;i<15628;i+=2)

            {

                c.data[i]=data[i-k1];

                c.data[i+1]=data[i-k1+1];

            }

            k%=64;

            if(!k)return c;

            const int k2=64-k;

            b.data[0]=c.data[0]<<k;

            b.data[1]=(c.data[1]<<k)|(c.data[0]>>k2);

            for(int i=2;i<15628;i+=2)

            {

                b.data[i]=(c.data[i]<<k)|(c.data[i-1]>>k2);

                b.data[i+1]=(c.data[i+1]<<k)|(c.data[i]>>k2);

            }

            return b;

        }

        int count()const

        {

            register int ans=0;

            for(int i=0;i<15628;i++)

            {

                unsigned long long tmp=data[i];

                while(tmp)

                {

                   if(tmp&1)ans++;

                   tmp>>=1;

                }

            }

            return ans;

        }

    private:

        unsigned long long data[15629];

    };

    bitset2 S[2];

    int main()

    {

        read(n);

        for(register unsigned int i=0;i<n;i++)

        {

            read(l[i]);

            read(r[i]);

        }

        register bool i2=1;

        //  vis[0]=1;

        S[0].setone();

        for(register unsigned int i=0;i<n;i++)

        {

            for(register unsigned int k=l[i];k<=r[i];k++)

            {

                S[i2]|=S[!i2]<<(k*k);

            }

            S[!i2].clear();

            i2^=1;

        }

        cout<<S[!i2].count();

        return 0;

    }

}

int main()

{

//  freopen("e100wt.in","r",stdin);

//  freopen("e100wt.out","w",stdout);

    return Solution::main();

}

/*

Process exited after 0.8867 seconds with return value 0

*/

点评

       不少题解的实现止步于本解题报告中的实现六，由于LOJ开启了O2优化，实现六不会超时，但NOIP赛事在测评时并不开启任何优化开关，本人在不开启任何优化的情况下用极限数据卡掉了所有题解以及结果为Accepted的代码。笔者希望读者不止步于OJ上的AC，尝试最优化自己的程序，以争取在NOIP的测评环境下不被“卡常”。其实，本人的实现七仍然有一定的优化空间，希望善于卡常的读者给出更加优的实现八，以在更差的CPU上不运行超时。