#include <iostream>
using namespace std;
int n,m;
int a[500010];
struct Node
{
int l,r;
int maxx,lmax,rmax,sum;
}tr[2000010];
void pushup(Node &u,Node l,Node r)
{
u.sum=l.sum+r.sum;
u.lmax=max(l.lmax,l.sum+r.lmax);
u.rmax=max(r.rmax,r.sum+l.rmax);
u.maxx=max(l.maxx,max(r.maxx,l.rmax+r.lmax));
}
void build(int u,int l,int r)
{
if(l==r) tr[u]={l,r,a[l],a[l],a[l],a[l]};
else
{
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
}
void modify(int u,int x,int v)
{
if(tr[u].l==tr[u].r) tr[u]={x,x,v,v,v,v};
else
{
int mid=tr[u].l+tr[u].r>>1;
if(x<=mid) modify(u<<1,x,v);
else modify(u<<1|1,x,v);
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
}
Node query(int u,int l,int r)
{
if(tr[u].l>=l && tr[u].r<=r) return tr[u];
int mid=tr[u].l+tr[u].r>>1;
if(l>mid) return query(u<<1|1,l,r);
else if(r<=mid) return query(u<<1,l,r);
else
{
Node ansr=query(u<<1|1,l,r),ansl=query(u<<1,l,r);
Node ans;
pushup(ans,ansl,ansr);
return ans;
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
while(m--)
{
int k,x,y;
cin>>k>>x>>y;
if(k==1) cout<<query(1,min(x,y),max(x,y)).maxx<<endl;
else modify(1,x,y);
}
return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
活动打卡代码
AcWing 245. 你能回答这些问题吗
活动打卡代码
AcWing 1275. 最大数
#include <iostream>
using namespace std;
int m,p;
struct Node
{
int l,r,v;
}tr[800010];
void pushup(int u)
{
tr[u].v=max(tr[u*2].v,tr[u*2+1].v);
}
void build(int u,int l,int r)
{
tr[u].l=l,tr[u].r=r;
if(l==r) return;
int mid=l+r>>1;
build(u<<1,l,mid),build(u*2+1,mid+1,r);
}
int query(int u,int l,int r)
{
if(tr[u].l>=l && tr[u].r<=r) return tr[u].v;
int mid=tr[u].l+tr[u].r>>1;
int v=0;
if(l<=mid) v=query(u*2,l,r);
if(r>mid) v=max(v,query(u*2+1,l,r));
return v;
}
void modify(int u,int d,int x)
{
if(tr[u].l==tr[u].r) tr[u].v=x;
else
{
int mid=tr[u].l+tr[u].r>>1;
if(d<=mid) modify(u*2,d,x);
else modify(u*2+1,d,x);
pushup(u);
}
}
int main()
{
int last=0,n=0;
cin>>m>>p;
build(1,1,m);
while(m--)
{
char op;
int x;
cin>>op>>x;
if(op=='A') modify(1,++n,(last+x)%p);
else
{
int v=query(1,n-x+1,n);
cout<<v<<endl;
last=v;
}
}
return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
活动打卡代码
AcWing 312. 乌龟棋
#include <iostream>
#include <cstring>
using namespace std;
int n,m;
int score[360],s[5];
int f[40][40][40][40];
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>score[i];
while(m--)
{
int x;
cin>>x;
s[x]++;
}
for(int a=0;a<=s[1];a++)
for(int b=0;b<=s[2];b++)
for(int c=0;c<=s[3];c++)
for(int d=0;d<=s[4];d++)
{
int t=score[a+2*b+3*c+4*d];
f[a][b][c][d]=t;
if(a) f[a][b][c][d]=max(f[a][b][c][d],f[a-1][b][c][d]+t);
if(b) f[a][b][c][d]=max(f[a][b][c][d],f[a][b-1][c][d]+t);
if(c) f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c-1][d]+t);
if(d) f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c][d-1]+t);
}
cout<<f[s[1]][s[2]][s[3]][s[4]];
return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
活动打卡代码
AcWing 340. 通信线路
#include <iostream>
#include <deque>
#include <cstring>
using namespace std;
int n,m,k;
int h[1010],e[20010],ne[20010],w[20010],idx;
int dist[1010];
bool st[1010];
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool check(int x)
{
memset(dist,0x3f,sizeof(dist));
memset(st,false,sizeof(st));
deque<int> q;
dist[1]=0;
q.push_front(1);
while(q.size())
{
int t=q.front();
q.pop_front();
if(st[t]) continue;
st[t]=true;
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i],v=w[i]>x;
if(dist[j]>dist[t]+v)
{
dist[j]=dist[t]+v;
if(v) q.push_back(j);
else q.push_front(j);
}
}
}
return dist[n]<=k;
}
int main()
{
cin>>n>>m>>k;
memset(h,-1,sizeof(h));
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c),add(b,a,c);
}
int l=0,r=1e6+1;
while(l<r)
{
int mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
if(l==1e6+1) cout<<-1;
else cout<<l;
return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
活动打卡代码
AcWing 165. 小猫爬山
#include <iostream>
#include <algorithm>
using namespace std;
int n,w;
int a[20];
int sum[20],l=1;
int ans;
void dfs(int u)
{
if(l>=ans) return;
if(u==0)
{
ans=min(ans,l);
return;
}
for(int i=1;i<=l;i++)
if(sum[i]+a[u]<=w)
{
sum[i]+=a[u];
dfs(u-1);
sum[i]-=a[u];
}
sum[++l]=a[u];
dfs(u-1);
sum[l--]-=a[u];
}
int main()
{
cin>>n>>w;
for(int i=1;i<=n;i++) cin>>a[i];
ans=n;
sort(a+1,a+1+n);
dfs(n);
cout<<ans;
return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
活动打卡代码
AcWing 320. 能量项链
#include <iostream>
using namespace std;
int n;
int w[210];
int f[210][210];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>w[i];
w[i+n]=w[i];
}
for(int len=3;len<=n+1;len++)
for(int l=1;l+len-1<=n*2;l++)
{
int r=l+len-1;
for(int k=l+1;k<r;k++)
f[l][r]=max(f[l][r],f[l][k]+f[k][r]+w[k]*w[l]*w[r]);
}
int ans=0;
for(int i=1;i<=n;i++) ans=max(ans,f[i][i+n]);
cout<<ans;
return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
活动打卡代码
AcWing 1152. 格雷码
#include <iostream>
using namespace std;
int main()
{
unsigned long long n,k;
cin>>n>>k;
unsigned long long power2[64];
power2[0]=1;
for(int i=1;i<64;i++) power2[i]=power2[i-1]*2;
for(int i=0;i<64;i++) power2[i]-=1;
int a=1,b=0;
while(n)
{
if(k>power2[n-1])
{
k-=power2[n-1]+1;
cout<<a;
a=0,b=1;
}
else
{
cout<<b;
a=1,b=0;
}
n-=1;
}
return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
