网易2022-8-20算法岗笔试AK代码

// A题
#include <bits/stdc++.h>

using namespace std;

const int N=1200;
int a[N],pos[N];
int main(){
    freopen("1.in","r",stdin);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        pos[a[i]]=i;
    }
    int ans=0;
    vector<pair<int,int> >res;
    for(int i=1;i<=n;i++){
        while(a[i]!=i){
            res.push_back(make_pair(i,pos[a[i]-1]));
            int tmp=pos[a[i]-1];
            pos[a[i]]=tmp;
            swap(a[i],a[pos[a[i]-1]]);
            pos[a[i]]=i;
            ans++;
        }
    }
    printf("%d\n",ans);
    for(auto&it:res){
        printf("%d %d\n",it.first, it.second);
    }
    return 0;
}
// B题
#include <bits/stdc++.h>


using namespace std;

char s[300005];
int num[30];
unordered_map<long long,int>mp;
long long change(int x,int y){
    return 1LL*(x+200006)*500000+(y+200006);
}
int main(){
    // freopen("1.in","r",stdin);
    scanf("%s",s+1);
    int n=strlen(s+1);
    long long res=0;
    mp[change(0,0)]++;
    for(int i=1;i<=n;i++){
        if(s[i]=='r') num[1]++;
        else if(s[i]=='e') num[2]++;
        else if(s[i]=='d') num[3]++;
        res+=1LL*mp[change(num[1]-num[2],num[2]-num[3])];
        mp[change(num[1]-num[2],num[2]-num[3])]++;
    }
    printf("%lld\n",res);
    return 0;
}

// C题
#include <bits/stdc++.h>


using namespace std;

const int N=1e5+7;
int pos[N][35];
bool vis[N];
int a[N];
int main(){
    // freopen("1.in","r",stdin);
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        int tmp=a[i];
        for(int j=33;j>=1;j--){
            if(tmp%2==1) pos[i][j]=1;
            else pos[i][j]=0;
            tmp/=2;
        }
    }
    int res=0;
    for(int j=1;j<=33;j++){
        int tmp=0;
        res*=2;
        for(int i=1;i<=n;i++){
            if(vis[i]) continue;
            if(pos[i][j]) tmp++;
        }
        if(tmp>=k){
            res++;
            for(int i=1;i<=n;i++){
                if(vis[i]) continue;
                if(pos[i][j]==0) vis[i]=true;
            }
        }
    }
    printf("%d\n",res);
    return 0;
}

//D 题
#include <bits/stdc++.h>


using namespace std;

long long a[4][4];
long long p[4][4];
long long res[4][4];
long long mod=1e9+6;
long long MOD=1e9+7;
void mul_1(){
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            res[i][j]=0;
            for(int k=1;k<=2;k++){
                res[i][j]=(res[i][j]+p[i][k]*p[k][j]%mod)%mod;
            }
        }
    }
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++) p[i][j]=res[i][j];
    }
}
void mul_2(){
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            res[i][j]=0;
            for(int k=1;k<=2;k++){
                res[i][j]=(res[i][j]+p[i][k]*a[k][j]%mod)%mod;
            }
        }
    }
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++) a[i][j]=res[i][j];
    }
}
void pow_(long long k){
    while(k){
        if(k%2==1){
            mul_2();
            k--;
        }
        else{
            mul_1();
            k/=2;
        }
    }
}
long long POW(long long x, long long y){
    long long res=1;
    x%=MOD;
    while(y){
        if(y%2==1){
            res=res*x%MOD;
            y--;
        }
        else{
            x=x*x%MOD;
            y/=2;
        }
    }
    return res;
}
int main(){
    // freopen("1.in","r",stdin);
    long long n,m,k;
    scanf("%lld%lld%lld",&n,&m,&k);
    if(k==1){
        printf("%lld\n",n%MOD);
        return 0;
    }
    else if(k==2){
        printf("%lld\n",m%MOD);
        return 0;
    }
    a[1][1]=0;
    a[2][1]=1;
    p[1][1]=p[1][2]=2;
    p[2][1]=1;
    p[2][2]=0;
    pow_(k-2);
    long long res1=a[1][1];
    a[1][1]=1;
    a[2][1]=0;
    a[1][2]=0;
    a[2][2]=0;
    p[1][1]=p[1][2]=2;
    p[2][1]=1;
    p[2][2]=0;
    pow_(k-2);
    long long res2=a[1][1];
    long long ans=POW(n,res1)*POW(m,res2)%MOD;
    printf("%lld\n",ans);
    // cout<<n<<' '<<m<<' '<<k<<endl;
    return 0;
}