9-11NOIP模拟赛总结

今天尽力了考了110，还算好吧，能拿的分都拿了。

T1

第一题是一道状压dp，可能是我状态没定好， 我的转移的复杂度有O(2n×n2×k)，明天去看看别人的状态怎么定的。其实发现离正解没差多少，只要记一个后缀就好了，学习了一个新的函数__builtin_ctz(x)数二进制后缀０的个数．clz相反．

T2

第二题没什么思路，打了个暴力。第二题就是个分治，问题是求∑i=1n∑j=inMax(i,j)∗Min(i,j)考虑分治，然后发现只需要统计l，r跨越mid的贡献，用两个指针扫，然后维护答案即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>

using namespace std;

typedef long long LL;
#define REP(i, a, b) for(register LL i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
#define DREP(i, a, b) for(register LL i = (a), i##_end_ = (b); i >= i##_end_; -- i)
#define mem(a, b) memset((a), b, sizeof(a))

LL read()
{
    register LL fg = 1,sum = 0;char c = getchar();
    while(!isdigit(c)) { if(c == '-')fg = -1; c = getchar(); }
    while(isdigit(c)) { sum = sum * 10 + c - '0'; c = getchar();    }
    return fg * sum;
}
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

const int maxn = 500000+10;
const LL mod = 1e9 + 7;
const LL INF = 1e14;
LL n;
LL a[maxn];
LL smx[maxn],smn[maxn],sm[maxn];
LL ans;

#define fl(a,n) fill(a+1,a+1+n,0);
void work(LL l,LL r)
{
    if(l == r)
    {
        (ans += (a[l] * a[l]) % mod) %= mod;
        return;
    }
    LL mid = (l + r) >> 1;
    work(l,mid); work(mid+1,r);

    LL x = -1e14,y = 1e14;
    REP(i,mid+1,r)
    {
        x = max(x,a[i]);y = min(y,a[i]);
        smx[i] = (smx[i-1] + x)%mod;
        smn[i] = (smn[i-1] + y)%mod;
        sm[i] = (sm[i-1] + (x * y)%mod)%mod;
    }
    LL j = mid + 1,k = mid+1;
    x = -1e14, y = 1e14;
    DREP(i,mid,l)
    {
        x = max(x, a[i]); y = min(y, a[i]);
        for(; j <= r && a[j] <= x; ++j);
        for(; k <= r && a[k] >= y; ++k);
        LL L = min(j, k), R = max(j, k);

        (ans += ((x * y) % mod * (L - mid - 1)) % mod) %= mod;
        (ans += (sm[r] - sm[R - 1] + mod) % mod) %= mod;
        if(j <= k) (ans += (y * (smx[R - 1] - smx[L - 1])) % mod) %= mod;
        else (ans += (x * (smn[R - 1] - smn[L - 1])) % mod) %= mod;
    }
}


int main()
{
#ifndef ONLINE_JUDGE
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
#endif
    n = read();
    REP(i,1,n) a[i] = read();
    work(1, n);
    printf("%lld\n", (ans + mod) % mod);
    return 0;
}

T3

同样暴力.60pt其实不难想，根据期望的一些线性，我们可以把期望分开来算，算这个位置的期望的位置，然后暴力统计就好了．

经验与不足

该拿的分都拿到，不能拿的尽量骗，先看题，打暴力，节奏要稳，不能因为题目难度乱了节奏，跟着今天这种节奏就很好的。