头像

Get_Update


访客:1044

离线:14小时前



题目描述

树状数组求逆序对的数量:

给定一个长度为n的整数数列,请你计算数列中的逆序对的数量。
逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满足 i < j 且 a[i] > a[j],则其为一个逆序对;否则不是。

输入样例

6
2 3 4 5 6 1

输出样例

5

算法

树状数组

const int N = 1060000
因为这个树状数组的下标是数的范围,不是题中的n,数的个数的范围。
然后利用树状数组的区间查询,去算有多少个数的位置在这个数之前,并且大于他的。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1060000;

int n,m;
int w[N],tr[N];

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

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

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

int main(){
    scanf("%d",&n);

    for(int i=0;i<n;i++) scanf("%d",&w[i]);

    LL sum=0;
    for(int i=0;i<n;i++){
        sum+=(query(N)-query(w[i]));
        add(w[i],1);
    }

    printf("%lld",sum);

    return 0;
}


活动打卡代码 AcWing 901. 滑雪

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 310;

int n,m;
int g[N][N];
int f[N][N];//以i,j为出发点的最大滑行距离为f[i][j]


int dfs(int x,int y){
    if(f[x][y]!=0) return f[x][y];

    int dx[4]={-1,0,+1,0};
    int dy[4]={0,+1,0,-1};
    f[x][y]=1;
    for(int i=0;i<4;i++){
        int nx=x+dx[i], ny=y+dy[i];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&g[nx][ny]<g[x][y]){
            f[x][y]=max(f[x][y],dfs(nx,ny)+1);
        }
    }
    return f[x][y];
}
int main(){
    cin>>n>>m;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>g[i][j];
        }
    }

    int res=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            res=max(res,dfs(i,j));
        }
    }

    cout<<res<<endl;

    return 0;
}



#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 6600;

int happy[N];
int e[N],h[N],ne[N],idx;
bool st[N];
int f[N][3];

void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int u){
    f[u][0]=0;
    f[u][1]=happy[u];

    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs(j);
        f[u][1]+=f[j][0];
        f[u][0]+=max(f[j][0],f[j][1]);
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>happy[i];

    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        add(b,a);
        st[a]=true;
    }

    int root=1;
    while(st[root]) root++;

    dfs(root);

    printf("%d",max(f[root][0],f[root][1]));

    return 0;
}


活动打卡代码 AcWing 2065. 整除序列

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main(){
    long long n;
    scanf("%lld",&n);

    while(n>0){
        printf("%lld ",n);
        n/=2;
    }

    return 0;
}


活动打卡代码 AcWing 91. 最短Hamilton路径

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 21, M = 1<<N;

int n;
int f[M][N];
int w[N][N];

int main(){
    ios::sync_with_stdio(false);//加快cin的读入速度,但是scanf将会不能用。
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>w[i][j];
        }
    }

    memset(f,0x3f,sizeof f);
    f[1][0]=0;
    for(int i=0;i< 1<<n;i++){
        for(int j=0;j<n;j++){
            if(i>>j&1){
                int past=i-(1<<j);
                for(int k=0;k<n;k++){
                    if(past>>k&1){
                        f[i][j]=min(f[i][j],f[past][k]+w[k][j]);
                    }
                }
            }
        }
    }

    cout<<f[(1<<n)-1][n-1]<<endl;

    return 0;
}



#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 12, M = 1<<N;

int n,m;
vector<int> state[M];//用于记录合法的状态
bool st[M];//用于判别
LL f[N][M];//f[i][j]表示前i-1列已经摆好,同时从第i-1列,伸到第i列的状态为j的方案数

int main(){
    while(cin>>n>>m,n||m){
        for(int i=0;i< 1<<n;i++){//枚举在n行的情况下,假设可以合法摆放的状态为i
            int cnt=0;//数连续的竖着的小方格个数是不是偶数
            bool is_valid=true;
            for(int j=0;j<n;j++){
                if(i>>j&1){//如果i状态下,第j行选择从上一行伸向这一行
                    if(cnt&1){
                        is_valid=false;//如果之前连续0的个数是奇数,竖的方块插不进来,这种状态不行
                        break;
                    }
                }
                else cnt++;//如果
            }
            if(cnt&1) is_valid=false;//到末尾再判断一下前面0的个数是否为奇数,同前
            st[i]=is_valid;//断定此状态是否合法
        }

        for(int i=0;i< 1<<n;i++){//枚举在n行的情况下,假设可以合法摆放的状态为i
            state[i].clear();
            for(int j=0;j< 1<<n;j++){//枚举在i的状态下,下一列可以的状态假设为j
                if((i&j)==0&&st[i|j]){//如果j状态,它们没有冲突,i这一列被占位的情况也是合法的话
                    state[i].push_back(j);//将j状态存入能和i匹配的状态中
                }
            }
        }

        memset(f,0,sizeof f);//一定要记得初始化成0,对于每一轮新的输入要重新计算f[N][M]
        f[0][0]=1;
        for(int i=1;i<=m;i++){
            for(int j=0;j< 1<<n;j++){
                for(int k=0;k<state[j].size();k++){
                    f[i][j]+=f[i-1][state[j][k]];//那么这种状态下它的方案数等于之前每种state[j][k]状态数目的和
                }
            }
        }

        cout<<f[m][0]<<endl;//求的是第m行排满,并且第m行不向外伸出块的情况
    }
    return 0;
}


活动打卡代码 AcWing 900. 整数划分

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1600, mod = 1e9 + 7;

int f[N];

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

    f[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            f[j]=(f[j]+f[j-i])%mod;
        }
    }

    cout<<f[n]<<endl;

    return 0;
}


活动打卡代码 AcWing 282. 石子合并

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 360;

int s[N];
int f[N][N];

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

    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int l=i,r=l+len-1;
            f[l][r]=1e8;
            for(int k=l;k<r;k++){
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
            }
        }
    }

    cout<<f[1][n]<<endl;

    return 0;
}


活动打卡代码 AcWing 899. 编辑距离

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 15, M = 1010;

int n, m;
int f[N][N];
char str[M][N];

int edit_distance(char a[], char b[])
{
    int la = strlen(a + 1), lb = strlen(b + 1);

    for (int i = 0; i <= lb; i ++ ) f[0][i] = i;
    for (int i = 0; i <= la; i ++ ) f[i][0] = i;

    for (int i = 1; i <= la; i ++ )
        for (int j = 1; j <= lb; j ++ )
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }

    return f[la][lb];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%s", str[i] + 1);

    while (m -- )
    {
        char s[N];
        int limit;
        scanf("%s%d", s + 1, &limit);

        int res = 0;
        for (int i = 0; i < n; i ++ )
            if (edit_distance(str[i], s) <= limit)
                res ++ ;

        printf("%d\n", res);
    }

    return 0;
}

// 作者:yxc
// 链接:https://www.acwing.com/activity/content/code/content/62479/
// 来源:AcWing
// 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


活动打卡代码 AcWing 902. 最短编辑距离

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1600;

int f[N][N];
char a[N],b[N];
int main(){
    int n,m;
    cin>>n>>a+1>>m>>b+1;

    for(int i=0;i<=n;i++) f[i][0]=i;
    for(int i=0;i<=m;i++) f[0][i]=i;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
            if(a[i]==b[j])
                f[i][j]=min(f[i][j],f[i-1][j-1]);
            else 
                f[i][j]=min(f[i][j],f[i-1][j-1]+1);
        }
    }

    cout<<f[n][m]<<endl;

    return 0;
}