比赛情况
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 摆动数列
首先我通过观察发现 xy 的可以分开讨论。
再接着设计一个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;
}T3 星球大战
不会。等我变强了再把这题补起来。