DAY1
T1 区间开方线段树
这题我以前好像做过。好像除了用线段树还可以用分块来写。
考试时花30分钟,过了样例就轻松切了。
T2 能量收集
刚开始打了个暴力,把样例调了出来。
把他和他能到达的点连一条边,发现好像是道分层图最长路的问题。
于是打了一个小时的最长路,把样例调了出来就去看下一道了。
考完试才发现这是道 DP + 单调队列优化的题。
现在也不会,先把坑占上吧。
T3 奶牛的反抗
想了半天发现自己不会写。
自己只会打个暴力加特判。
最后只能拿了 40pts 的分就灰溜溜的走人了。
正解: 树状数组优化DP
我们考虑维护一个前缀和,方便我们来进行区间求和。
但我们发现前缀和可能有负数,所以我们还要离散化。
我们设 \(f[i]\) 表示 到i的方案数。
那么当他能和前面的区间合并时有这样一个条件
sum[i] - sum[l-1] > 0
即 sum[i] > sum[l-1]
因此我们得到了一个转移方程
f[i] = \(\sum_{l=1}^{i} f[l]\) \((sum[i] > sum[l-1])\)
可这是O(n^2)的,所以我们要考虑优化。
我们可以 以\(sum[i]\) 为下标开一个树状数组。树状数组的权值为f[i]
这样我们就可以O(logn)的求出每个\(f[i]\)
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int p = 1e9+9;
int n,m,cnt,a[100010];
int sum[100010],f[100010],t[100010],tr[100010];
inline int read()
{
int s = 0 , w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10+ch -'0'; ch = getchar();}
return s * w;
}
int lowbit(int x){ return x & -x;}
void chenge(int x,int val)
{
for(; x <= n; x += lowbit(x))
{
tr[x] = (tr[x] + val) % p;
}
}
int ask(int x)
{
int ans = 0;
for(; x; x -= lowbit(x))
{
ans = (ans + tr[x]) % p;
}
return ans;
}
int main()
{
n = read();
for(int i = 1; i <= n; i++)
{
a[i] = read();
sum[i] = sum[i-1] + a[i];
t[i] = sum[i];
}
sort(t,t+n+1);//离散化
cnt = unique(t,t+n+1)-t-1;
for(int i = 0; i <= n; i++)
{
sum[i] = lower_bound(t,t+cnt+1,sum[i])-t+1;
}
chenge(sum[0],1);//把0这个节点单独放进去
for(int i = 1; i <= n; i++)
{
f[i] = ask(sum[i]);//用树状数组维护f[i]
chenge(sum[i],f[i]);//修改操作
}
printf("%d\n",f[n]);
}
考完
MD 毒瘤出题人,第一题卡快读,硬生生我的正解卡成70分。
第二题以为想出了正解,结果只对了几个点,后面全炸了。
果然 DP是我永远过不去的坎啊!!!。