8-3作业/重写ren_gao_zu

· · 个人记录

作业

P5149 会议座位

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=5e5+5;
int n;
string s[N];
unordered_map<string,int>mp;
int ans,tot;
int sum[N];
int lowbit(int x){
    return x & -x;
}
void modify(int x,int val){
    while(x<=n){
        sum[x]+=val;
        x+=lowbit(x);
    }
}
int get_sum(int x){
    int res=0;
    while(x){
        res+=sum[x];
        x-=lowbit(x);
    }
    return res;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        mp[s[i]]=++tot;
    }
    for(int i=1;i<=n;i++)cin>>s[i];
    for(int i=n;i>=1;i--){
        //cin>>s[i];
        ans+=get_sum(mp[s[i]]-1);
        modify(mp[s[i]],1);
    }cout<<ans;
    return 0;
}

P1774 最接近神的人

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
int n,num[N],sum[N],tot,b[N];
map<int,int>mp;
int lowbit(int x){return x & -x;}
int get_sum(int x){
    int res=0;
    while(x){
        res+=sum[x];
        x-=lowbit(x);
    }
    return res;
}
void modify(int x,int val){
    while(x<=n){
        sum[x]+=val;
        x+=lowbit(x);
    }
}
int ans;
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    //tot++;
    for(int i=1;i<=n;i++){
        cin>>num[i];
        b[i]=num[i];
    }
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++){
        if(b[i]!=b[i-1]){
            tot++;
            mp[b[i]]=tot;
        }
    }
    //for(int i=1;i<=n;i++)
    for(int i=n;i>=1;i--){
        ans+=get_sum(mp[num[i]]-1);
        modify(mp[num[i]],1);
    }cout<<ans;
    return 0;
}

P10454 奇数码问题

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=3e5+5;
int n,suma[N],a[N],b[N],to,ot,sumb[N];
int lowbit(int x){return x & -x;}
void modifya(int x,int val){
    while(x<=to)suma[x]+=val,x+=lowbit(x);
}
int get_suma(int x){
    int res=0;
    while(x)res+=suma[x],x-=lowbit(x);
    return res;
}
void modifyb(int x,int val){
    while(x<=ot)sumb[x]+=val,x+=lowbit(x);
}
int get_sumb(int x){
    int res=0;
    while(x)res+=sumb[x],x-=lowbit(x);
    return res;
}
void solve(){
    memset(suma,0,sizeof suma);
    memset(sumb,0,sizeof sumb);
    if(n==1){
        cout<<"TAK\n";
        return;
    }
    int ans=0,cnt=0;
    for(int i=to;i>=1;i--){
        ans+=get_suma(a[i]-1);
        modifya(a[i],1);
    }
    for(int i=ot;i>=1;i--){
        cnt+=get_sumb(b[i]-1);
        modifyb(b[i],1);
    }
    if((ans%2==0&&cnt%2==0)||(ans%2==1&&cnt%2==1))cout<<"TAK\n";
    else cout<<"NIE\n";
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(cin>>n){
        to=0;
        ot=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                int num;
                cin>>num;
                if(num!=0)a[++to]=num;
            }   
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                int num;
                cin>>num;
                if(num!=0)b[++ot]=num;
            }
        }
        solve();
    }
    return 0;
}

重写

无