头像

Accepting

TYUT 太原理工大学


访客:15811

离线:4小时前


活动打卡代码 AcWing 1275. 最大数

Accepting
5小时前
#include<iostream>

using namespace std;

const int N=2e5+10;

struct Node
{
    int l,r;
    int v;
}tr[N*4];
int n,m,p;

int pushup(int u)
{
    tr[u].v=max(tr[u<<1].v,tr[u<<1|1].v);
}

void build(int u,int l,int r)
{
    tr[u]={l,r};
    if(l==r) return;
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}

int query(int u,int l,int r)
{
    if(l<=tr[u].l && r>=tr[u].r) return tr[u].v;
    int mid=tr[u].l+tr[u].r>>1;
    int val=0;
    if(l<=mid) val=max(val,query(u<<1,l,r));
    if(r>mid) val=max(val,query(u<<1|1,l,r));
    return val;
}

void modify(int u,int x,int v)
{
    if(tr[u].l==x && tr[u].r==x) tr[u].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(u);
    }
}

int main()
{
    cin>>m>>p;
    build(1,1,m);
    char op[2];
    int x,last=0;
    while(m--)
    {
        scanf("%s%d",op,&x);
        if(*op=='Q')
        {
            last=query(1,n-x+1,n);
            printf("%d\n",last);
        }
        else
        {
            modify(1,n+1,(last+x)%p);
            n++;
        }
    }
    return 0;
}


活动打卡代码 AcWing 244. 谜一样的牛

#include<iostream>

using namespace std;

const int N=1e5+10;

int t[N],a[N],n;

int lowbit(int x)
{
    return x & -x;
}

int ask(int x)
{
    int sum=0;
    for(int i=x;i;i-=lowbit(i))  sum+=t[i];
    return sum;
}

void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i)) t[i]+=c; 
}

int main()
{
    cin>>n;
    for(int i=2;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) t[i]=lowbit(i);
    for(int i=n;i;i--)
    {
        int k=a[i]+1;
        int l=1,r=n;
        while(l<r)
        {
            int mid=l+r>>1;
            if(ask(mid)>=k) r=mid;
            else l=mid+1;
        }
        a[i]=l;
        add(l,-1);
    }
    for(int i=1;i<=n;i++) printf("%d\n",a[i]);
    return 0;
}



#include<iostream>

using namespace std;

const int N=1e5+10;
typedef long long LL;

LL a[N],b[N],tr1[N],tr2[N];
int n,m;

int lowbit(int x)
{
    return x & -x;
}

LL ask(LL tr[],int x)
{
    LL sum=0;
    for(int i=x;i;i-=lowbit(i)) sum+=tr[i];
    return sum;
}

void add(LL tr[],int x,LL c)
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}

LL prefix(int x)
{
    return ask(tr1,x)*(x+1)-ask(tr2,x);
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)
    {
        int b=a[i]-a[i-1];
        tr1[i]=a[i]-a[i-lowbit(i)];
        add(tr2,i,(LL)i*b);
    }
    while(m--)
    {
        LL l,r,c;
        char op[2];
        scanf("%s%lld%lld",op,&l,&r);
        if(*op=='Q')
        {
            LL ans=prefix(r)-prefix(l-1);
            printf("%lld\n",ans);
        }
        else
        {
            scanf("%lld",&c);
            add(tr1,l,c),add(tr2,l,c*l);
            add(tr1,r+1,-c),add(tr2,r+1,(r+1)*(-c));
        }
    }
    return 0;
}



#include<iostream>

using namespace std;

const int N=100010;

typedef long long LL;

int n,m;
LL a[N],t[N];

int lowbit(int x)
{
    return x & -x;
}

LL ask(int x)
{
    LL sum=0; 
    for(int i=x;i;i-=lowbit(i))  sum+=t[i];
    return sum;
}

int add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i)) t[i]+=c;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++) t[i]=a[i]-a[i-lowbit(i)];
    while(m--)
    {
        char op[2];
        int l,r,c;
        scanf("%s%d",op,&l);
        if(*op=='Q')  printf("%lld\n",ask(l));
        else
        {
            scanf("%d%d",&r,&c);
            add(l,c),add(r+1,-c);
        }
    }
    return 0;
}


活动打卡代码 AcWing 241. 楼兰图腾

#include<iostream>

using namespace std;

const int N=2e5+10;
typedef long long LL;

int n,a[N],t[N],low[N],big[N];

int lowbit(int x)
{
    return x & -x;
}

int ask(int x)
{
    int sum=0;
    for(int i=x;i;i-=lowbit(i)) sum+=t[i];
    return sum;
}

void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i)) t[i]+=c;
}

int main()
{
    cin>>n;
    LL res1=0,res2=0;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        int y=a[i];
        low[i]=ask(y-1),big[i]=i-1-low[i];
        add(y,1);
        res1+=big[i]*(LL)(n-y-big[i]);
        res2+=low[i]*(LL)(y-1-low[i]);
    }
    cout<< res1 <<" "<< res2 <<endl;
    return 0;
}


活动打卡代码 AcWing 239. 奇偶游戏

带权偏移量

#include<iostream>
#include<unordered_map>

using namespace std;

const int N=20010;

unordered_map<int,int> S;
int p[N],d[N];
int k,n,m;

int get(int x)
{
    if(!S[x]) S[x]=++n;
    return S[x];
}

int find(int x)
{
    if(x!=p[x])
    {
        int root=find(p[x]);
        d[x]^=d[p[x]];
        p[x]=root;
    }
    return p[x];
}

int main()
{
    cin>>k>>m;
    for(int i=1;i<N;i++) p[i]=i;
    int res=m;
    for(int i=1;i<=m;i++)
    {
        int a,b,t=0;
        char op[5];
        scanf("%d%d%s",&a,&b,op);
        a=get(a-1),b=get(b);
        if(*op=='o') t=1;
        int pa=find(a),pb=find(b);
        if(pa==pb)
        {
            if((d[a]^d[b])!=t)
            {
                res=i-1;
                break;
            }
        }
        else
        {
            p[pb]=pa;
            d[pb]=d[a]^d[b]^t;
        }
    }
    cout<< res <<endl;
    return 0;
}

拓展域

#include<iostream>
#include<unordered_map>

using namespace std;

const int N=40010,B=20001;

unordered_map<int,int> S;
int p[N];
int k,n,m;

int get(int x)
{
    if(!S[x]) S[x]=++n;
    return S[x];
}

int find(int x)
{
    if(x!=p[x])  p[x]=find(p[x]);
    return p[x];
}

int main()
{
    cin>>k>>m;
    for(int i=1;i<N;i++) p[i]=i;
    int res=m;
    for(int i=1;i<=m;i++)
    {
        int a,b,t=0;
        char op[5];
        scanf("%d%d%s",&a,&b,op);
        a=get(a-1),b=get(b);
        if(*op=='e')
        {
            if(find(a+B)==find(b))
            {
                res=i-1;
                break;
            }
            p[find(a)]=find(b);
            p[find(a+B)]=find(B+b);
        }
        else
        {
            if(find(a)==find(b))
            {
                res=i-1;
                break;
            }
            p[find(a)]=find(B+b);
            p[find(a+B)]=find(b);
        }
    }
    cout<< res <<endl;
    return 0;
}


活动打卡代码 AcWing 238. 银河英雄传说

#include<iostream>
#include<cmath>

using namespace std;

const int N=30010;

int p[N],d[N],s[N];
int T;

int find(int x)
{
    if(x!=p[x])
    {
        int root=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=root;
    }
    return p[x];
}

int main()
{
    cin>>T;
    for(int i=1;i<N;i++) p[i]=i,s[i]=1;
    while(T--)
    {
        int a,b;
        char op[2];
        scanf("%s%d%d",op,&a,&b);
        int pa=find(a),pb=find(b);
        if(*op=='M')
        {
            if(pa!=pb)
            {
                d[pb]=s[pa];
                s[pa]+=s[pb];
                p[pb]=pa;
            }
        }
        else
        {
            if(pa!=pb) puts("-1");
            else printf("%d\n",max(0,abs(d[a]-d[b])-1));
        }
    }
    return 0;
}


活动打卡代码 AcWing 237. 程序自动分析

#include<iostream>
#include<algorithm>
#include<unordered_map>

using namespace std;

const int N=2e6+10,M=1e6+10;

unordered_map<int,int> S;
int id,p[N],m;
struct q
{
    int x,y,e;
}query[M];

int get(int x)
{
    if(!S.count(x)) S[x]=++id;
    return S[x];
}

int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        id=0;
        S.clear();
        cin>>m;
        bool flag=false;
        for(int i=0;i<m;i++)
        {
            int a,b,e;
            scanf("%d%d%d",&a,&b,&e);
            query[i]={get(a),get(b),e};
        }
        for(int i=1;i<=id;i++) p[i]=i;
        for(int i=0;i<m;i++)
            if(query[i].e==1)
            {
                int a=query[i].x,b=query[i].y;
                int pa=find(a),pb=find(b);
                if(pa!=pb) p[pb]=pa;
            }
        for(int i=0;i<m;i++)
            if(!query[i].e)
            {
                int a=query[i].x,b=query[i].y;
                int pa=find(a),pb=find(b);
                if(pa==pb)
                {
                    flag=true;
                    break;
                }
            }
        if(flag) puts("NO");
        else puts("YES");
    }
    return 0;
}


活动打卡代码 AcWing 1252. 搭配购买

#include<iostream>

using namespace std;

const int N=10010;

int f[N],v[N],w[N],p[N],pv[N],pw[N];
int nv[N],nw[N];
int n,m,k;

int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i],&w[i]);
        p[i]=i,pv[i]=v[i],pw[i]=w[i];
    }
    for(int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        int pa=p[a],pb=p[b];
        if(pa!=pb)
        {
            p[pb]=pa;
            pv[pa]+=pv[pb],pw[pa]+=pw[pb];
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++) if(p[i]==i) nv[++cnt]=pv[i],nw[cnt]=pw[i];
    for(int i=1;i<=cnt;i++)
        for(int j=k;j>=nv[i];j--)
        {
            f[j]=max(f[j],f[j-nv[i]]+nw[i]);
        }
    cout<< f[k] <<endl;
    return 0;
}


活动打卡代码 AcWing 181. 回转游戏

#include<iostream>

using namespace std;

const int N=24,M=100;

int path[M],q[N];
int op[8][7]={
    {0,2,6,11,15,20,22},
    {1,3,8,12,17,21,23},
    {10,9,8,7,6,5,4},
    {19,18,17,16,15,14,13},
    {23,21,17,12,8,3,1},
    {22,20,15,11,6,2,0},
    {13,14,15,16,17,18,19},
    {4,5,6,7,8,9,10},
};
int oppsite[8]={5,4,7,6,1,0,3,2};
int center[8]={6,7,8,12,17,16,15,11};

int f()
{
    int sum[4]={0},cnt=0;
    for(int i=0;i<8;i++) sum[q[center[i]]]++;
    for(int i=1;i<=3;i++) cnt=max(cnt,sum[i]);
    return 8-cnt;
}

void operate(int x)
{
    int t=q[op[x][0]];
    for(int i=1;i<7;i++) q[op[x][i-1]]=q[op[x][i]];
    q[op[x][6]]=t;
}

bool dfs(int u,int depth,int last)
{
    if(u+f()>depth) return false;
    if(!f()) return true;
    for(int i=0;i<8;i++)
        if(oppsite[i]!=last)
        {
            operate(i);
            path[u]=i;
            if(dfs(u+1,depth,i)) return true;
            operate(oppsite[i]);
        }
    return false;
}

int main()
{
    while(cin>>q[0],q[0])
    {
        for(int i=1;i<N;i++) scanf("%d",&q[i]);
        int depth=0;
        while(!dfs(0,depth,-1)) depth++;
        if(!depth) printf("No moves needed");
        else  for(int i=0;i<depth;i++) printf("%c",path[i]+'A');
        printf("\n%d\n",q[6]);
    }
    return 0;
}