头像

wx090708




离线:1天前


新鲜事 原文

~~acwing的视频防盗我发现只要把网页源代码删了就得了~~



#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 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;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



为什么线段树的数组都要开4倍大?



活动打卡代码 AcWing 312. 乌龟棋

wx090708
15天前
#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;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


新鲜事 原文

wx090708
17天前
为什么我换了一个屏幕大一点的台式电脑,代码就显示不全了,吞关键字啊


活动打卡代码 AcWing 340. 通信线路

wx090708
19天前
#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. 小猫爬山

wx090708
19天前
#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. 能量项链

wx090708
20天前
#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. 格雷码

wx090708
20天前
#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;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~