首页 / 更多教程 / 1.27 动归赛II总结
1.27 动归赛II总结
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了1.27 动归赛II总结,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3883字,纯文字阅读大概需要6分钟。
内容图文
t1mzoj 1354: 最大子序列的和
得分:10pts,本题我打了一个半小时,1.单调队列不熟悉,2.数据范围看错了,空间爆掉,死死翘翘!
思路:
看到区间的问题首先肯定是想到求前缀和,
我们把[1,k]的和记为sum[k],可以得到sum[i] = sum[i - 1] + a[i],[l,r]的和即为sum[r] - sum[l - 1](这里视sum[0] = 0)。(减法原理)
我们假设选择的区间为[l,r]且r固定,可知r?B+1≤l≤r?A+1若要使[l,r]区间的值最大,则sum[l - 1]需最小,才可使得sum[r] - sum[l - 1]最小。当i右移一位到i+1,因为p,q为给定不变的值,对应寻找最小sum[l-1]的区间也右移一位。
#include<bits/stdc++.h>
#define ll long long
#define N 1000010
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
ll sum[N],q[N];
ll n,ans=-2147483647,A,B;
int main()
{
//freopen("input.txt","r",stdin);
n=read(),A=read(),B=read();
rep(i,1,n)
sum[i]=sum[i-1]+read();
int head=0,tail=1;
rep(i,A,n)
{
while(head<=tail && q[head]<i-B)//不处于维护范围内的,出队
head++;
while(head<=tail && sum[i-A]<=sum[q[tail]])//更优的sum[l - 1]予以插队
tail--;
q[++tail]=i-A;
ans=max(ans,sum[i]-sum[q[head]]);//更新答案
}
printf("%lld\n",ans);
return 0;
}
插播一条线段树做法
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+5;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ll long long
ll s[maxn];
int n,a,b;
ll mi[maxn<<2];
void pushup(int rt)
{
mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);
}
void buildtree(int l,int r,int rt)
{
if(l==r)
{
mi[rt]=s[l];
return;
}
int m=(l+r)>>1;
buildtree(lson);
buildtree(rson);
pushup(rt);
}
ll query(int L,int R,int l,int r,int rt)
{
//printf("%d %d,%d %d %d\n",L,R,l,r,rt);
if(R<=0)return 0;
if(R<l||L>r) return 1e15;
if (L<=l&& R>=r)
{
return mi[rt];
}
int m=(l+r)>>1;
ll ans=1e15;
if(L<=m)ans=min(ans,query(L,R,lson));
if(R>m)ans=min(ans,query(L,R,rson));
return ans;
}
ll read()
{
ll x=0,f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
return x*f;
}
void init()
{
freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
}
void readdata()
{
n=read();a=read();b=read();
s[0]=0;
for(int i=1;i<=n;i++)
{
s[i]=read()+s[i-1];
}
buildtree(0,n,1);
}
void work()
{
ll ans=-1e15;
for (int i=a;i<=n;i++)
{
ans=max(ans,s[i]-query(max(0,i-b),max(0,i-a),0,n,1));
}
printf("%lld",ans);
}
int main()
{
//init();
readdata();
work();
return 0;
}
t3 数的划分加强版
得分:10pts 1.因为第一题想写正解,调了太久,没时间啦,想了个玄学暴力只得了10pts………2.前几天才做了一道数的划分,以为是原题,结果!并不是……ouyang skr(是个) 狠人!
/*
1.random_shuffle 随机大法好!
2.状压基本都可以靠随机和模拟退火水过去……还是100分的那种……
*/
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,m,ans,cnt,sum;
int w[20];
int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int main()
{
n=read(),m=read();
ans=n;//最坏情况
rep(i,1,n)
w[i]=read();
rep(times,1,1000000)
{
random_shuffle(w+1,w+n+1);
sum=0,cnt=0;
rep(i,1,n)
{
sum+=w[i];
if(sum>m)
{
++cnt;
sum=w[i];
}
}
if(sum)++cnt;
ans=min(ans,cnt);
}
printf("%d",ans);
return 0;
}
还有一种贪心思想:即小的数字更加灵活,先从大的数字枚举
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dwn(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int n,m,ans;
long long w[20],sum[20];
bool vis[20];
int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int main()
{
//freopen("input.txt","r",stdin);
n=read(),m=read();
rep(i,1,n)
w[i]=read();
sort(w+1,w+n+1);
dwn(i,n,1)//精髓
{
if(!vis[i])
{
sum[i]=w[i];
dwn(j,i-1,1)//精髓
{
if(!vis[j]&&sum[i]+w[j]<=m)
{
vis[j]=1;
sum[i]+=w[j];
}
}
}
}
rep(i,1,n)
if(sum[i])
ans++;
printf("%d",ans);
return 0;
}
原文:https://www.cnblogs.com/sjsjsj-minus-Si/p/11635638.html
内容总结
以上是互联网集市为您收集整理的1.27 动归赛II总结全部内容,希望文章能够帮你解决1.27 动归赛II总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。