T1 增援前线
实锤乱搞题，考试的时候写了一个错误的dp，只拿了一半的分。
实际上这一题应该属于贪心吧
我们用f[i]表示i号点能站多少人。
显然，前l个点的f[i]=a[i]；
对于其他情况，f[i]应由i-l到i-1这段区间内的点更新而来。
具体来说，就是“能跳则跳，满员为止”
我们优先选择距离当前点较远的点来更新，下面将证明这一结论。
我们每次只能在\(i-l\)到\(i-1\)这段区间内选择点来更新答案，每次我们可选的状态空间都会变动（整体右移），如果我们优先选择左边的点来更新的话，右边的点的可选方案数不会改变，而左边的点的可选方案显然是比右边的少的（因为左边的点会先退出可行方案），根据决策包容性我们可知该贪心方案正确。
代码中的3个if是优化枚举（可行性），否则时间复杂度将达到\(O((N-L)\times L)\) 然而数据太水不加也能过
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include<bits/stdc++.h> using namespace std; const int MAXN=100004; int f[MAXN],a[MAXN]; int n,l; int main(){ scanf("%d%d",&n,&l); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=0;i<=l;i++)f[i]=a[i]; a[n]=0x7fffffff; for(int i=l+1;i<=n;i++){ if(a[i]==0)continue; for(int j=i-l;j<i;j++){ if(f[j]==0)continue; if(a[i]==0)break; int tmp=min(a[i],f[j]); a[i]-=tmp;f[j]-=tmp;f[i]+=tmp; } } printf("%d",f[n]); return 0; } |
T2 进化序列
QAQ QAQ QAQ QAQ，就是这一题！！！！我可不是什么邪恶的史莱姆
考场上先写了一个暴力，然后写了线段树+二分（Binary Segment Tree简称BST），对拍发现答案不一样，最后发现是暴力写错了orz
然后自己造了好多大数据，都是暴力跑得快（但是暴力还是被卡了）
然后没开long long 或运算起来可能会爆int，见祖宗了
为什么用线段树？我们要查询的区间或值是满足区间可加性的。
为什么二分？可以发现越多的数或起来不会变小。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include<bits/stdc++.h> #define lt p<<1 #define rt p<<1|1 using namespace std; const int MAXN=100003; struct segTree{ long long data; int l,r; }t[MAXN<<2]; long long n,m; long long cnt=0; void build(int p,int l,int r){ t[p].l=l,t[p].r=r; if(r==l){ scanf("%lld",&t[p].data); return; } int mid=(l+r)>>1; build(lt,l,mid); build(rt,mid+1,r); t[p].data=t[lt].data|t[rt].data; } int ask(int p,int l,int r){ if(t[p].r<=r&&t[p].l>=l){ return t[p].data; } int mid=(t[p].l+t[p].r)>>1; int ans=0; if(l<=mid)ans|=ask(lt,l,r); if(r>mid)ans|=ask(rt,l,r); return ans; } int main(){ scanf("%lld%lld",&n,&m); build(1,1,n); for(int i=1;i<=n;i++){ int l=i,r=n;long long ans=0; while(l<=r){ int mid=(l+r)>>1; if(ask(1,i,mid)<m){ ans=mid-i;l=mid+1; } else r=mid-1; } cnt+=ans; } cout<<cnt<<endl; return 0; } |