牛客OI周赛13-提高组比赛总结

比赛情况

1h才写出T1 100pts + T2 50pts（都是简单dp可还行）。~~然后就去颓废了~~。颓废完来康康T3的暴力，wow，T3咋这么难呢！？期望概率好像不太会了，退了吧qwq。

所以最后 100+50+0=150pts, rank 22。

比赛总结

说实话比赛前还有些紧张呢，但是我这次吸取了经验，牢记dalao之前对我讲的，“花2h肝T1，T2是值得的。”(CSP-S就是因为花2h+肝T3暴力，让我留下了终身的遗憾)，于是安心写T1，T2，稳扎稳打拿下150pts
在这次比赛学到了一个简单的树状数组优化dp。

T1 0还是1

定义 f[i,0/1] 表示使用完前 i 个运算符后结果为 0/1 的方案总数，分当前位是 0还是1 讨论。

入门级别的dp题放在tgT1合不合适呢，我想放在 CSP-S D1T1 可能还合适吧qwq

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 1e7, MOD = 1e9+7;
int n;
int f[N][2];
char s[N];
signed main()
{
    //freopen("a.in","r",stdin);
    n = read();
    scanf("%s",s+1);
    f[0][0] = f[0][1] = 1;
    for(int i=1;i<=n;++i) {
        if(s[i] == '&') {
            f[i][0] = (((2*f[i-1][0])%MOD) + f[i-1][1])%MOD;
            f[i][1] = (f[i-1][1])%MOD;
        } else if(s[i] == '|') {
            f[i][0] = (f[i-1][0])%MOD;
            f[i][1] = (((2*f[i-1][1])%MOD) + f[i-1][0])%MOD;
        } else if(s[i]=='^') {
            f[i][0] = (f[i-1][1] + f[i-1][0])%MOD;
            f[i][1] = (f[i-1][0] + f[i-1][1])%MOD;
        }
    }
    printf("%lld\n",f[n][1]%MOD);
    return 0;
}

T2 摆动数列

首先我通过观察发现 x<y 的和 x>y 的可以分开讨论。

再接着设计一个dp，有点像最长上升子序列有木有？

考虑可以用树状数组维护一个高度的前缀最大值，累加上去。这样就达到了优化dp的效果。

时间复杂度 $O(nlogn)$

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 4e5+7;
int n,m,cnt;
int X[N],Y[N],b[N];
struct Tree_Data {
    int d[N];
    inline void Add(int x,int y) {
        while(x <= m) {
            d[x] = max(d[x],y); x += x&-x;
        }
    }
    inline int Qmax(int x) {
        int res = 0;
        while(x > 0) {
            res = max(res,d[x]); x -= x&-x;
        }
        return res;
    }
}Tu,Td;
signed main()
{
    //freopen("b.in","r",stdin);
    n = read();
    for(int i=1;i<=n;++i) {
        X[i] = read(), Y[i] = read();
        b[++cnt] = X[i], b[++cnt] = Y[i];
    }
    sort(b+1, b+1+cnt);
    m = unique(b+1, b+1+cnt) - b - 1;
    //printf("must test 'm' = %d\n",m);
    for(int i=1;i<=n;++i) {
        X[i] = lower_bound(b+1, b+1+m, X[i]) - b; Y[i] = lower_bound(b+1, b+1+m, Y[i]) - b;
        //printf("for.%d ,X[i]=%d, Y[i]=%d\n",i,X[i],Y[i]);
        if(X[i] < Y[i]) {
            int now = Tu.Qmax(m-X[i]) + 1; Tu.Add(m-Y[i]+1,now);
        } else {
            int now = Td.Qmax(X[i]-1) + 1; Td.Add(Y[i],now);
        }
    }
    printf("%lld\n",max(Tu.Qmax(m+1),Td.Qmax(m+1)));
    return 0;
}