真开心，挂没了。。

考完："你们怎么第二题打了这么点分，明明一个爆搜就有65pts！！！怎么跟别人打？！"

然后我看了看我的爆搜，30pts。

然后认为自己打爆了。。。

我又想为什么会有这么多分，还是在大一点的测试点上：

然后我知道了。。

打表

一个看不懂题目的题。。。。

然而是一个结论题。。

答案就是：

\[\huge{\frac{\sum_{i=0}^{2^k-1}|A_i-A_{ans}|}{2^k}}
\]

就这？？？

就这。

#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define asm(i,x) for(register signed i=head[x];i;i=edge[i].next)
namespace xin_io
{
    #define sb(x) cout<<#x" = "<<x<<' '
    #define jb(x) cout<<#x" = "<<x<<endl
    #define debug cout<<"debug"<<endl
    #define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
    char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull;
    class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &s)
    {
        register int f = 0;s = 0; register char ch = gc();
        while(!isdigit(ch)) {f |= ch == '-'; ch = gc();}
        while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch  xor 48),ch = gc(); return s = f ? -s : s,*this;
    }}io;
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+7; const ll llinf = 1e18+7;
#define int long long
namespace xin
{
    const int mod = inf;
    inline int ksm(int x,int y)
    {
        int ret = 1;
        while(y)
        {
            if(y & 1) ret = ret * x % mod;
            x = x * x % mod; y >>= 1;
        }
        return ret;
    }
    int ans = 0;
    int k,pos;
    int a[maxn];
    inline short main()
    {
        io >> k >> pos; int er = ksm(2,k); er = ksm(er,mod-2);
        try(i,0,(1 << k) - 1) io >> a[i];
        try(i,0,(1 << k) - 1) (ans += abs(a[i] - a[pos])% mod) %= mod;
        cout<<ans * er % mod<<endl;
        return 0;
    }
}
signed main() {return xin::main();}

蛇

这个题目爆搜很多分，就是数组。。。。。

不说了。。。

然后贴一个 \(60pts\) 的爆搜吧。。。

因为正解还没改出来。。。

#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define asm(i,x) for(register signed i=head[x];i;i=edge[i].next)
namespace xin_io
{
    #define sb(x) cout<<#x" = "<<x<<' '
    #define jb(x) cout<<#x" = "<<x<<endl
    #define debug cout<<"debug"<<endl
    #define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
    #define scanf ak = scanf
    int ak; typedef long long ll; typedef unsigned long long ull;
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+7; const ll llinf = 1e18+7;
namespace xin
{
    #define mp std::make_pair
    const int dx[] = {0,1,-1,0,0},dy[] = {0,0,0,1,-1};
    char s[3][maxn];
    char ake[maxn];
    int l,ans = 0,m;
    bool vis[5001][5001];
    std::vector<std::pair<int,int> >vec;
    std::map<std::vector<std::pair<int,int> >,int>ji;
    void dfs(int now,int x,int y)
    {
        try(i,1,4)
        {
            register int nx = x + dx[i],ny = y + dy[i];
            if(nx >= 1 and nx <= 2 and ny >= 1 and ny <= m and !vis[nx][ny] and s[nx][ny] == ake[now+1])
            {
                if(now == l-1)
                {
                    vec.push_back(mp(nx,ny));
                    if(!ji[vec])
                        ji[vec] = 1,ans++;
                    vec.pop_back();
                }
                else
                {
                    vec.push_back(mp(nx,ny));
                    vis[nx][ny] = 1,dfs(now+1,nx,ny),vis[nx][ny] = 0;
                    vec.pop_back();

                }
            }
        }
    }
    inline short main()
    {
        scanf("%s%s%s",s[1]+1,s[2]+1,ake+1);
        m = strlen(s[1]+1);
        l = strlen(ake+1);
        if(l == 1)
        {
            try(i,1,2) try(j,1,m) if(s[i][j] == ake[1])
                ans++;
            cout<<ans<<endl;
            return 0;
        }
        try(i,1,2) try(j,1,m) if(s[i][j] == ake[1]) vis[i][j] = 1,vec.push_back(mp(i,j)),dfs(1,i,j),vec.pop_back(),vis[i][j] = 0;
        cout<<ans<<endl;
        return 0;
    }
}
signed main() {return xin::main();}

购物

有个结论。。。

然而不太能推出来。。

题解多好。。

然而我不是这么做的。。。

嘿嘿嘿。。。

将权值放入桶中，然后排序，之后进行二分查找。。

正确性显然

#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define asm(i,x) for(register signed i=head[x];i;i=edge[i].next)
namespace xin_io
{
    #define sb(x) cout<<#x" = "<<x<<' '
    #define jb(x) cout<<#x" = "<<x<<endl
    #define debug cout<<"debug"<<endl
    #define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
    char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull;
    class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &s)
    {
        register int f = 0;s = 0; register char ch = gc();
        while(!isdigit(ch)) {f |= ch == '-'; ch = gc();}
        while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch  xor 48),ch = gc(); return s = f ? -s : s,*this;
    }}io;
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+7; const ll llinf = 1e18+7;
#define int long long
namespace xin
{
    int w[maxn];
    int n;
    inline short main()
    {
        io >> n;
        try(i,1,n) io >> w[i]; int pre  = 0 ,temp = n;
        std::sort(w+1,w+n+1);
        try(i,1,temp) pre = pre + w[i],w[++n] = pre;
        std::sort(w+1,w+n+1);
        //n = std::unique(w+1,w+n+1) - (w + 1);
        int now = w[n],vis = 0,ans = 0;
        while(now)
        {
            register int mid = (now + 1) >> 1; ans += now - mid + 1 - vis;
            temp = std::lower_bound(w+1,w+n+1,mid) - w;
            if(now == w[temp]) now = w[temp - 1],vis = 0;
            else now = w[temp],vis = now - mid + 1;
        }
        cout<<ans<<endl;
        return 0;
    }
}
signed main() {return xin::main();}

ants

这个题目是我一生的耻辱！！！！！！

在这场考试的前一天，我做到了莫队算法专题的倒数第二题。。

然后太虚真人告诉我最后一个题目是一个回滚莫队，然后我就想明天再学。

然后就放下了一个题目。。

结果。。。。

这个题目就是那个最后一个题目的原题！！！！

连TM样例都一样！！！！

淦

自己在考场上看出来是莫对算法的题目，然后只会写 \(add\) 函数但是并不会写\(del\)，然后手玩了两个小时，之后放弃。。。

然后此题抱零。。

气展了！！！！！！！

这到题目就是一个回滚莫队的板子题目，自己看看网上回滚莫队算法的讲解就行了。

#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define asm(i,x) for(register signed i=head[x];i;i=edge[i].next)
namespace xin_io
{
    #define debug cout<<"debug"<<endl
    #define sb(x) cout<<#x" = "<<x<<' '
    #define jb(x) cout<<#x" = "<<x<<endl
    #define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
    char buf[1<<20],*p1 = buf,*p2 = buf; typedef long long ll; typedef unsigned long long ull;
    class xin_stream{public:template<typename type>xin_stream &operator >> (type &s)
    {
        register bool f = 0; s = 0; register char ch = gc();
        while(!isdigit(ch)) f |= ch == '-',ch = gc();
        while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
    }}io;
}
using namespace xin_io; static const int maxn = 1e6+10;
namespace xin
{
    int ans1 = 0,ans2 = 0,top = 0,s1[maxn],s2[maxn],up[maxn],down[maxn],ans[maxn];
    class xin_query
    {
        private:
            friend bool operator < (xin_query x,xin_query y)
            {return x.bel == y.bel ? x.r < y.r : x.bel < y.bel;}
        public:
            int l,r,id,bel;
    }d[maxn];
    int n,m,a[maxn];
    inline void add(int x)
    {
        up[x] = up[x + 1] + 1; down[x] = down[x - 1] + 1;
        int temp = up[x] + down[x] - 1;
        s1[++top] = x + up[x] - 1;  s2[top] = down[s1[top]];
        s1[++top] = x - down[x] + 1;s2[top] = up[s1[top]];
        down[s1[top-1]] = up[s1[top]] = temp;
        ans1 = std::max(ans1,temp);
    }
    inline short main()
    {
        io >> n >> m; int kuai = (int)(1.0 * n / std::sqrt(m));
        try(i,1,n) io >> a[i];
        try(i,1,m) io >> d[i].l >> d[i].r,d[i].id = i,d[i].bel = (d[i].l - 1) / kuai + 1;
//        try(i,1,m) sb(d[i].l),sb(d[i].r),jb(d[i].bel);
        std::sort(d+1,d+m+1);
        int r_pre = 0,ret = 0;
        try(i,1,m)
        {
            if(d[i].bel xor d[i-1].bel)
            {
                memset(up,0,sizeof(int) * (n + 1)); memset(down,0,sizeof(int) * (n + 1));
                ret = r_pre = d[i].bel * kuai; ans2 = 0;
            }
            top = ans1 = 0;
            while(r_pre < d[i].r) add(a[++r_pre]);
            top = 0;
            ans1 = ans2 = std::max(ans1,ans2);
            try(j,d[i].l,std::min(ret,d[i].r)) add(a[j]);
            ans[d[i].id] = ans1;
            throw(j,top,1)
            if(j & 1) down[s1[j]] = s2[j];
            else up[s1[j]] = s2[j];
            try(j,d[i].l,std::min(ret,d[i].r)) up[a[j]] = down[a[j]] = 0;
        }
        try(i,1,m) printf("%d\n",ans[i]);
        return 0;
    }
}
signed main() {return xin::main();}