头像

Stack_Overflow




在线 


最近来访(44)
用户头像
zwling
用户头像
acwing_9052
用户头像
someone
用户头像
hby
用户头像
山海皆可平
用户头像
余睿
用户头像
NikolaTesla
用户头像
乐天知命故不忧
用户头像
Arthur_5
用户头像
Nan97
用户头像
今晚打老虎_7
用户头像
neepoo
用户头像
qiao
用户头像
Lxc_pyrola
用户头像
wangdong
用户头像
ijkstar
用户头像
用户头像
填海难....填心更难
用户头像
DaHUA
用户头像
zombotany


构造成差分后,每个项的值都由前往后累加得到

#include <iostream>
using namespace std;

const int N=1e5+10;
int n, m;
int a[N], tr[N];

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

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

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

int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i];

    for(int i=1; i<=n; i++) add(i, a[i]-a[i-1]);    // 构造差分数组

    char op[2];
    int l, r, d;
    while(m--)
    {
        cin>>op>>l;

        if(*op=='C')
        {
            cin>>r>>d;
            add(l, d), add(r+1, -d);
        }
        else cout<<sum(l)<<endl;
    }
    return 0;
}


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

乘法原理

左边比a[i]大的$\times$右边比a[i]大的$=$所有以a[i]为最大值的三元组个数

如何求比 $a[i]$ 大的数的个数?

  1. add(y, 1):加1代表这个数出现过;
  2. sum[a[i]]:代表所有<=a[i]的个数;

由于$y_1\sim y_n$是$1\sim n$的排列
所以sum[n]-sum[a[i]-1]即为比a[i]大的个数

树状数组下标不能从0开始

因为 $lowbit(0)$ 还是0,再怎么加都是0;

先计算后add的原因?

无所谓,也可以先add;
屏幕截图 2021-12-05 142311.png

#include <iostream>
#include <cstring>
using namespace std;

typedef long long ll;
const int N=2e5+10;
int n;
int a[N], tr[N];
int big[N], low[N];

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

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

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

int main()
{
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];

    for(int i=1; i<=n; i++)
    {
        int y=a[i];
        big[i]=sum(n)-sum(y);
        low[i]=sum(y-1);
        add(y, 1);
    }

    memset(tr, 0, sizeof tr);

    ll res1=0, res2=0;
    for(int i=n; i; i--)
    {
        int y=a[i];
        res1 += big[i]*(ll)(sum(n)-sum(y));
        res2 += low[i]*((ll)sum(y-1));
        add(y, 1);
    }

    cout<<res1<<' '<<res2;

    return 0;
}


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

1.怎么保持顺序接到第j列尾部?

让排头当根节点

2.i,j如果处于同一列,如何求它们之间的战舰数量?

统一维护当前战舰到排头的距离

屏幕截图 2021-12-04 163753.png
屏幕截图 2021-12-04 175905.png

#include <iostream>
#include <cmath>
using namespace std;

const int N=3e4+10;
int T;
int p[N], len[N], d[N];         // 队列长度;到队头的距离

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

int main()
{
    cin>>T;
    int x, y;
    char op[2];

    for(int i=1; i<=N; i++)
    {
        p[i]=i;
        len[i]=1;
    }

    while(T--)
    {
        cin>>op>>x>>y;
        int pa=find(x), pb=find(y);
        if(op[0]=='M')
        {
            p[pa]=pb;               // 加到队尾
            d[pa]+=len[pb];         // 计算距离
            len[pb]+=len[pa];       // 计算总长
        }
        else
        {
            if(pa!=pb) puts("-1");
            else cout<<max(0, abs(d[x]-d[y])-1)<<endl;
        }
    }
    return 0;
}


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

  • =的时候就合并到一个连通块;
    不相等时就判断是否在一个连通块,如果在就记为false;

屏幕截图 2021-12-02 182045.png

非保序性离散化

int get(int x)
{
    if(!S.count(x)) S[x] = ++n;
    return S[x];
}
#include <iostream>
#include <unordered_map>
using namespace std;

const int N=2e5+10;
int T, n, m;
int p[N];
unordered_map<int,int> S;
struct node{
    int x, y, e;
}querry[N];

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

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

int main()
{
    cin>>T;
    while(T--)
    {
        n=0;        
        S.clear();  // 每个问题要重新离散化

        cin>>m;
        int x, y, e;
        for(int i=0; i<m; i++)
        {
            cin>>x>>y>>e;
            querry[i]={get(x), get(y), e};
        }

        for(int i=1; i<=n; i++) p[i]=i;

        for(int i=0; i<m; i++)
            if(querry[i].e)
            {
                int pa=find(querry[i].x), pb=find(querry[i].y);
                p[pa]=pb;
            }

        int flag=1;
        for(int i=0; i<m; i++)
            if(!querry[i].e)
            {
                int pa=find(querry[i].x), pb=find(querry[i].y);
                if(pa==pb)
                {
                    flag=0;
                    break;
                }
            }

        if(flag) puts("YES");
        else puts("NO");
    }
    return 0;
}


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

价钱看成是体积Joe的钱看成背包容量,价值还是价值;
怎么找每一个合并后的集合?if(p[i]==i)即可;

#include <iostream>
using namespace std;

const int N=10010;

int n, m, vol;
int v[N], w[N];
int p[N], f[N];

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

int main()
{
    cin>>n>>m>>vol;

    for(int i=1; i<=n; i++) p[i]=i;
    for(int i=1; i<=n; i++) cin>>v[i]>>w[i];

    int a, b, pa, pb;
    while(m--)
    {
        cin>>a>>b;
        pa=find(a), pb=find(b);
        if(pa!=pb)      // 必须在不等时合并,否则会多加一遍v和w
        {
            p[pa]=pb;
            v[pb]+=v[pa];
            w[pb]+=w[pa];
        }
    }

    for(int i=1; i<=n; i++)
        if(p[i]==i)         // 只找祖宗结点
            for(int j=vol; j>=v[i]; j--)
                f[j]=max(f[j], f[j-v[i]]+w[i]);

    cout<<f[vol];
    return 0;
}


活动打卡代码 AcWing 1250. 格子游戏

先检查再连线
因为一旦连上自然就是一个父节点了;

这个$\alpha (n)$听不清是啥函数
屏幕截图 2021-11-29 222620.png

#include <iostream>
using namespace std;

const int N=40010;          // 点是200个
int n,m;
int p[N];

int get(int x,int y)
{
    return x*n+y;
}

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

int main()
{
    cin>>n>>m;
    for(int i=1; i<=n*n; i++) p[i]=i;       // n*n

    int x, y, res=0;
    char c;
    for(int i=1; i<=m; i++)
    {
        cin>>x>>y>>c;
        x--, y--;                   // 投影到(0,0)的坐标
        int a=get(x, y);
        int b;
        if(c=='D') b=get(x+1, y);
        else b=get(x, y+1);

        int pa=find(a), pb=find(b);
        if(pa==pb)
        {
            cout<<i;
            return 0;
        }
        p[pa]=pb;
    }
    puts("draw");

    return 0;
}


新鲜事 原文

什么时候能出个移除粉丝的功能, 挑战关注全部人真的很无聊
图片


活动打卡代码 AcWing 98. 分形之城

思路很难想
屏幕截图 2021-11-16 181612.png
屏幕截图 2021-11-16 182330.png
屏幕截图 2021-11-16 182417.png

为什么再减一
因为坐标从0开始

#include <iostream>
#include <cmath>
using namespace std;

typedef long long LL;
struct Point{
    int x, y;
};

Point get(LL n,LL a)            // Point
{
    if(n==0) return {0, 0};
    LL len=1ll<<n-1, block=len*len;
    auto p=get(n-1, a%block);
    LL x=p.x, y=p.y;
    LL z=a/block;

    if(z==0) return {y, x};
    else if(z==1) return {x, y+len};
    else if(z==2) return {x+len, y+len};
    else return {len-y-1+len, len-x-1};         // 
}

int main()
{
    int T;
    cin>>T;

    LL n, a, b;
    while(T--)
    {
        cin>>n>>a>>b;
        auto pa=get(n, a-1), pb=get(n, b-1);        // 这的-1也是
        double dx=pa.x-pb.x, dy=pa.y-pb.y;
        printf("%.0lf\n", 10*sqrt(dx*dx+dy*dy));    // .f就是四舍五入了
    }

    return 0;
}


活动打卡代码 AcWing 97. 约数之和

屏幕截图 2021-11-13 171952.png
屏幕截图 2021-11-13 171302.png
屏幕截图 2021-11-13 171655.png

#include <iostream>
using namespace std;

const int mod=9901;
int a, b;

int qmi(int a,int b)
{
    int res=1;
    a%=mod;                 // 
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

int sum(int p,int k)
{
    if(k==1) return 1;
    if(k%2==0) return (1+qmi(p, k/2))*sum(p, k/2)%mod;
    return (sum(p, k-1)+qmi(p, k-1))%mod;
}

int main()
{
    cin>>a>>b;

    int res=1;
    for(int i=2; i*i<=a; i++)
    {
        int s=0;
        if(a%i==0)
        {
            while(a%i==0) a/=i, s++;
            res=res*sum(i, s*b+1)%mod;      // p^α ---> p^(α*b)
        }
    }

    if(a>1) res=res*sum(a, b+1)%mod;        //   p ---> p^b
    if(!a) res=0;

    cout<<res;
    return 0;
}


活动打卡代码 AcWing 90. 64位整数乘法

龟速乘:顾名思义,就是将乘法通过加法来实现,虽然速度十分慢,但是却解决了两个大数相乘爆LL的问题

$a\times b=a+a+…+a;(b个a)$

屏幕截图 2021-10-31 195344.png
屏幕截图 2021-11-13 161557.png

#include <iostream>
using namespace std;

typedef long long LL;

LL qadd(LL a,LL b,LL p)
{
    LL res=0;
    while(b)
    {
        if(b&1) res=(res+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return res;
}

int main()
{
    LL a, b, p;
    cin>>a>>b>>p;
    cout<<qadd(a, b, p);

    return 0;
}