NOIP常见模板集合

Preface

这篇博客记录的是我联赛前虽然只有两天了的打板子记录。

只求真的能给我起到些作用吧，一般按照难度排序。

而且从这篇博客开始我会用H3的标题代替H4

P1177 【模板】快速排序

快排模板？调用sort也太没技术含量了吧？

写一发松式基排，感觉速率还可以吧，一次过这个一次过不了退役算了

#include<cstdio>
#include<cctype>
#define RI register int
using namespace std;
typedef unsigned int u32;
const int N=100005,Radix=255;
int n; u32 a[N];
class FileInputOutput
{
    private:
        #define S 1<<21
        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
        #define pc(ch) (Ftop<S?Fout[Ftop++]=ch:(fwrite(Fout,1,S,stdout),Fout[(Ftop=0)++]=ch))
        char Fin[S],Fout[S],*A,*B; int pt[15],Ftop;
    public:
        FileInputOutput() { A=B=Fin; Ftop=0; }
        inline void read(int &x)
        {
            x=0; char ch; while (!isdigit(ch=tc()));
            while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
        }
        inline void read(u32 &x)
        {
            x=0; char ch; while (!isdigit(ch=tc()));
            while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
        }
        inline void write(int x,char ch)
        {
            if (!x) return (void)(pc('0'),pc(ch)); RI ptop=0;
            while (x) pt[++ptop]=x%10,x/=10; while (ptop) pc(pt[ptop--]+48); pc(ch);
        }
        inline void Fend(void)
        {
            fwrite(Fout,1,Ftop,stdout);
        }
        #undef S
        #undef tc
        #undef pc
}F;
class Radix_Sort
{
    private:
        int cnt1[Radix+1],cnt2[Radix+1],cnt3[Radix+1],cnt4[Radix+1]; u32 b[N];
    public:
        inline void sort(u32 *a,int n)
        {
            RI i; for (i=1;i<=n;++i)
            {
                ++cnt1[a[i]&Radix]; ++cnt2[a[i]>>8&Radix];
                ++cnt3[a[i]>>16&Radix]; ++cnt4[a[i]>>24&Radix];
            }
            for (i=1;i<=Radix;++i)
            {
                cnt1[i]+=cnt1[i-1]; cnt2[i]+=cnt2[i-1];
                cnt3[i]+=cnt3[i-1]; cnt4[i]+=cnt4[i-1];
            }
            for (i=n;i;--i) b[cnt1[a[i]&Radix]--]=a[i];
            for (i=n;i;--i) a[cnt2[b[i]>>8&Radix]--]=b[i];
            for (i=n;i;--i) b[cnt3[a[i]>>16&Radix]--]=a[i];
            for (i=n;i;--i) a[cnt4[b[i]>>24&Radix]--]=b[i];
        }
}R;
int main()
{
    freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
    RI i; for (F.read(n),i=1;i<=n;++i) F.read(a[i]);
    for (R.sort(a,n),i=1;i<=n;++i) F.write(a[i],i^n?' ':'\n');
    return F.Fend(),0;
}

NOIP常见模板集合

原文：https://www.cnblogs.com/cjjsb/p/9929887.html