T1
模拟，80？
#include<iostream> #include<cstring> #include<queue> #include<algorithm> #include<cstdio> #include<cmath> #include<ctime> using namespace std; typedef long long LL; const int N=1e5+100; int a[N],n,len; char s[N]; int w[N],maxn; LL f[N],tot; int main() { freopen("maximum.in","r",stdin); freopen("maximum.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); cin>>(s+1); for(int i=1;i<=n;i++) { w[i]=s[i]-'0'; if(w[i]) maxn=i; } for(int i=1;i<=maxn;i++) { f[i]=f[i-1]; if(a[i]>0) f[i]+=a[i]; } w[0]=1;tot=0; while(maxn>=1) if(w[maxn]) { if(a[maxn]<=0) { cout<<(f[maxn-1]+tot)<<endl; return 0; } tot+=a[maxn]; while(!w[maxn-1]) maxn--; maxn--; } cout<<tot<<endl; return 0; }
#include<iostream> #include<cstring> #include<queue> #include<algorithm> #include<cstdio> #include<cmath> #include<ctime> using namespace std; typedef long long LL; const int N=1e5+100; int a[N],n,len; char s[N]; int w[N],maxn; LL f[N],tot=0,ans=0; int main() { freopen("maximum.in","r",stdin); freopen("maximum.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); cin>>(s+1); for(int i=1;i<=n;i++) { w[i]=s[i]-'0'; if(w[i]) maxn=i; } f[0]=0; for(int i=1;i<=maxn;i++) { f[i]=f[i-1]; if(a[i]>0) f[i]+=a[i]; } w[0]=1;tot=0; for(int i=maxn;i>=1;i--) if(w[i]) { // printf("%lld %lld ",i,tot+f[i-1]); ans=max(ans,tot+f[i-1]); tot+=a[i]; } cout<<ans<<endl; return 0; }
w[0]=1;tot=0;LL all=f[maxn]; while(maxn>=1) { if(a[maxn]<=0) { cout<<(f[maxn-1]+tot)<<endl; return 0; } tot+=a[maxn]; while(!w[maxn-1]) maxn--; maxn--; }
调了半天，我终于发现了错误所在。
说实话：我错的真不怨，我感觉很高兴，因为我找到了自己的思维误区。
怎么说呢：最大值可能出现在这些情况中的任意一个：
1除了最高位对应的数外，其他任意位上数的组合。（最高位是0）
2第二高的为0，其他的任意位上的数的组合。（最高位是1）
3第三高的为0，其他位上任意数的组合。（前两高的是1）
............ 这道题中的 最高位 是指 m的二进制位为1的。
做的时候还不如取个max那，我只是想当然的认为：
当最高位是是负数时，前面的一定比后面的要更优。（这是对的，但是）
我却认为这时，不加这个最高位的负数的结果是最优的。
其实不然，这时，对于不加这位的结果前面都算过，这一次却不一定是最优的！！！！！！
T2
二分+dp
奇怪的贪心。
#include<iostream> #include<cstring> #include<queue> #include<algorithm> #include<cstdio> #include<cmath> #include<ctime> using namespace std; const int N=1009; int a[N],b[N]; int n,k; int L,R,mid,ans; bool check(int x) { int sum=0,sum0=1e9+1; for(int i=1;i<=n;i++) a[i]=b[i]; a[n+1]=a[n]; for(int i=2;i<=n;i++) { if(abs(a[i]-a[i-1])>x) { if(a[i]>a[i-1]) { a[i]=a[i-1]+x; sum++; }else if(a[i-1]>a[i]) { a[i]=a[i-1]-x; sum++; } } } int i=1,j=n; for(int i=1;i<=n;i++,j--) a[i]=b[j]; a[n+1]=a[n]; for(int i=2;i<=n;i++) { if(abs(a[i]-a[i-1])>x) { if(a[i]>a[i-1]) { a[i]=a[i-1]+x; sum0++; }else if(a[i-1]>a[i]) { a[i]=a[i-1]-x; sum0++; } } } sum=min(sum,sum0); return sum<=k; } int main() { freopen("minimum.in","r",stdin); freopen("minimum.out","w",stdout); scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&b[i]); R=max(R,b[i]); } if(k>=n-1) { cout<<0<<' '; return 0; } L=0,R; while(L<=R) { mid=(L+R)/2; if(check(mid)) R=mid-1,ans=mid; else L=mid+1; } cout<<ans<<' '; return 0; }
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; int n,k; int a[2000],f[2000]; int L,R,mid; bool check(int x) { f[1]=0; int ans=n;//最大不超过n for(int i=2;i<=n;i++) { f[i]=i; for(int j=1;j<i;j++) if(abs(a[i]-a[j])<=(1LL*x*(i-j))) f[i]=min(f[i],f[j]+(i-j-1)); ans=min(ans,f[i]+n-i); } return ans<=k; } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); L=0,R=1e9+19; while(L<R-1) { mid=(L+R)>>1; if(check(mid)) R=mid; else L=mid; } if(check(L)) printf("%d ",L); else printf("%d ",R); return 0; }
T3
#include<iostream> #include<cstring> #include<queue> #include<algorithm> #include<cstdio> #include<cmath> #include<ctime> using namespace std; const int N=1e3+10; char s[N]; int n,x,y,len; int q,l,r; int A[N],B[N]; bool ok[N][N]; int main() { freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout); scanf("%d%d%d",&n,&x,&y); cin>>(s+1); for(int i=1;i<=n;i++) { A[i]=A[i-1];B[i]=B[i-1]; if(s[i]=='A') A[i]++; else B[i]++; } for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) { int Asum,Bsum; Asum=A[j]-A[i-1];Bsum=B[j]-B[i-1]; if(1LL*Asum*y==1LL*Bsum*x) ok[i][j]=1; } scanf("%d",&q); while(q--) { scanf("%d%d",&l,&r); int L=r-l+1; for(L;L>=1;L--) for(int i=l;i+L-1<=r;i++) if(ok[i][i+L-1]) { printf("%d ",L); L=0,i=r+3;break; } } return 0; }
待续。。。。。。
1用和为0，判断，链表查询，O（ n q）。
2分块。
3可持久线段树。。。难写。
最短 函数线段树