2022年A组国赛

小蓝与钥匙

题目大意：

​​

题解：

显然，$ans=C_{28}^{14}\cdot f\left[ 14 \right]$

其中 f[i] 表示i个人都没拿到自己的钥匙的情况数

f[i] 的递推式见代码

Code：

#include <bits/stdc++.h>
using namespace std;
#define ioss ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
ll C[30][30],fact[15];
void init(){
    for(ll i=0;i<=28;++i){
        for(ll j=0;j<=i;++j){
            if(j==0||j==i)C[i][j]=1;
            else C[i][j]=C[i-1][j-1]+C[i-1][j];
        }
    }
    fact[1]=1;
    for(ll i=2;i<=14;++i){
        fact[i]=fact[i-1]*i;
    }
}
ll f[15]; // f[i]:i个人都没拿到自己的情况数
int main(){
    init();
    f[2]=1;
    for(ll i=3;i<=14;++i){
        f[i]=fact[i]-1;
        for(ll j=1;j<=i-2;++j){
            f[i]-=C[i][j]*f[i-j];
        }
    }
    cout<<C[28][14]*f[14]; //1286583532342313400
    return 0;
}

排列距离

题目大意：

小蓝最近迷上了全排列, 现在他有一个长度为 17 的排列, 里面包含的元素 有: abcdefghijklnopqr, 即 a 至 r 中除了 m 以外的所有小写字母, 这 17 个字母在任何一个排列中都恰好出现一次。前面几个排列依次是：

第 1 个排列为: abcdefghijklnopqr;

第 2 个排列为: abcdefghijklnoprq;

第 3 个排列为: abcdefghijklnoqpr;

第 4 个排列为: abcdefghijklnogrp;

第 5 个排列为: abcdefghijklnorpq;

第 6 个排列为: abcdefghijklnorqp;

第 7 个排列为: abcdefghijklnpoqr;

第 8 个排列为: abcdefghijklnporq;

第 9 个排列为: abcdefghijklnpqor;

第 10 个排列为: abcdefghijklnpqro。

对于一个排列, 有两种转移操作:

1. 转移到其下一个排列。如果当前排列已经是最后一个排列, 那么下一个 排列就是第一个排列。
2. 转移到其上一个排列。如果当前排列是第一个排列, 那么上一个排列就 是最后一个排列。

小蓝现在有两个排列, 分别为排列 A: aejcldbhpiogfqnkr, 以及排列 B : ncfjboqiealhkrpgd, 他现在想知道, 在只有上述两种转移操作的前提 下, 排列 A 最少转移多少次能得到排列 B 。

题解：

分别求出两个排列在全排列中的序号，然后往前跳和往后跳两种情况取最小值即可

求某个排列在全排列中的序号的方法是：

每个位置上的逆序对个数 * 这个位置的阶乘 （详情见代码）

逆序对用树状数组求比较方便简单

Code：

#include <bits/stdc++.h>
using namespace std;
#define ioss ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define lb(i) i&(-i)
typedef long long ll;
string xu=" abcdefghijklnopqr";
string a=" aejcldbhpiogfqnkr";
string b=" ncfjboqiealhkrpgd";
ll c[20],fact[20];
void add(ll x,ll d){
    for(ll i=x;i<=17;i+=lb(i)){
        c[i]+=d;
    }
}
ll sum(ll x){
    ll ret=0;
    for(ll i=x;i>=1;i-=lb(i)){
        ret+=c[i];
    }
    return ret;
}
ll calc(string &x){
    memset(c,0,sizeof c);
    ll ans=0;
    for(ll i=1;i<=17;++i){
        ll id=x.find(xu[i]);
        ll t=sum(id);
        ans+=t*fact[17-id];
        add(1,1);
        add(id+1,-1);
    }
    return ans;
}
void init(){
    fact[1]=1;
    for(ll i=2;i<=17;++i)fact[i]=fact[i-1]*i;
}
int main(){
    init();
    ll ida=calc(a);
    ll idb=calc(b);
    cout<<min(idb-ida,ida+fact[17]-idb); //106148357572143
    return 0;
}

内存空间

题目大意：

​​

样例输入

1
long[] nums=new long[131072];

样例输出

1MB

提示

样例 1，占用的空间为 131072 × 8 = 1048576 B，换算过后正好是 1MB，其它三个单位 GB、KB、B 前面的数字都为 0 ，所以不用输出。

样例 2，占用的空间为 4 × 2 + 8 × 2 + 10 + 8 × 100000 × 2 B，换算后是 1MB538KB546B。

对于所有评测用例，1 ≤ T ≤ 10，每条变量定义语句的长度不会超过 1000 。所有的变量名称长度不会超过 10，且都由小写字母和数字组成。对于整型变量，初始化的值均是在其表示范围内的十进制整数，初始化的值不会是变量。 对于 String 类型的变量，初始化的内容长度不会超过 50，且内容仅包含小写字母和数字，初始化的值不会是变量。对于数组类型变量，数组的长度为一个 整数，范围为：[0, 230]，数组的长度不会是变量。T 条语句定义的变量所占的内存空间总大小不会超过 1 GB，且大于 0 B。

题解：

挺简单的模拟题，注意细节就好了

Code：

#include <bits/stdc++.h>
using namespace std;
#define ioss ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
int T,ans;
string type,s;
string out[4]={"B","KB","MB","GB"};
void Deal(int x,int k){
    if(x/1024) Deal(x/1024,k+1);
    if(x%1024)cout<<x%1024<<out[k];
}
int main(){
    cin>>T;
    while(T--){
        cin>>type;
        if(type=="int"||type=="long"){
            int per,cnt=1;
            if(type=="int") per=4;
            else per=8;
            cin>>s;
            for(int i=0;s[i];++i){
                if(s[i]==',')cnt++;
            }
            ans+=cnt*per;
        }else if(type=="String"){
            int tmp=0;
            cin>>s;
            int bj=-1;
            for(int i=0;s[i];++i){
                if(s[i]=='"'){
                    if(!~bj){
                        bj=i;
                    }else{
                        tmp+=i-bj-1;
                        bj=-1;
                    }
                }
            }
            ans+=tmp;
        }else{ //数组
            int per;
            if(type[0]=='i')per=4;
            else per=8;
            cin>>s;
            do{
                cin>>s;
                int cnt=0;
                bool bj=0;
                for(int i=0;s[i];++i){
                    if(s[i]=='['){
                        bj=1;
                        continue;
                    }
                    if(s[i]==']') break;
                    if(bj){
                        cnt=cnt*10+s[i]-'0';
                        continue;
                    }
                }
                ans+=cnt*per;
            }while(s[s.size()-1]!=';');
        }
    }
    Deal(ans,0);
    return 0;
}

最大公约数

题目大意：

​​

题解：

手算几个样例，发现：如果数组中本就存在1，那么有多少不是1的就需要几步

如果不存在1，就看最近的一对互质数的距离 + n-1

如果不存在互质的数，那么就无法满足要求，输出-1

找最近的互质数的方法是：

ST表 + 二分法

ST表一般用于快速的区间查询，但是不支持修改，如果要修改的话，就考虑树状数组和线段树

Code：

#include <bits/stdc++.h>
using namespace std;
#define ioss ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
int n,a[100010];
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int f[100010][20];
void ST(){
    int upj=log2(n);
    for(int j=1;j<=upj;++j){
        for(int i=1;i+(1<<j)-1<=n;++i){
            f[i][j]=gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}
int Ask(int L,int R){
    int k=log2(R-L+1);
    return gcd(f[L][k],f[R-(1<<k)+1][k]);
}
int main(){
    cin>>n;
    int numone=0;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        f[i][0]=a[i];
        if(a[i]==1)++numone;
    }
    if(numone){
        cout<<n-numone; //本就存在1
        return 0;
    }
    ST();
    int mi=0x3f3f3f3f;
    for(int i=1;i<=n;++i){
        int L=i+1,R=n,mid,ans=-1;
        while(L<=R){
            mid=L+R>>1;
            if(Ask(i,mid)==1){
                ans=mid;
                R=mid-1;
            }else{
                L=mid+1;
            }
        }
        if(ans!=-1)mi=min(ans-i,mi); //注意这里是ans-i表示距离，不是ans
    }
    if(mi!=0x3f3f3f3f)cout<<mi+n-1;
    else cout<<-1; //不存在互质的数
    return 0;
}

owo

题目大意：

​​

题解：

写了一晚上，写不出来

用并查集，然后头尾分类建立队列，勉强通过了54.5%的数据

​​

实在不知道咋做了

Code：

#include <bits/stdc++.h>
using namespace std;
#define ioss ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
string s;
int n,ans;
queue<int> q[6];
int fa[1000010];
int get(int u){
    if(fa[u]==u)return u;
    return fa[u]=get(fa[u]);
}
int merge(int a,int b){
    int aa=get(a),bb=get(b);
    fa[aa]=bb;
    return bb;
}
void Deal(){
    while(!q[4].empty()){
        if(!q[0].empty()){
            int t=merge(q[4].front(),q[0].front());
            q[4].pop();q[0].pop();
            q[1].push(t);
        }else if(!q[3].empty()){
            int t=merge(q[4].front(),q[3].front());
            q[4].pop();q[3].pop();
            q[2].push(t);
        }else{
            break;
        }
    }
    while(!q[5].empty()){
        if(!q[1].empty()){
            int t=merge(q[5].front(),q[1].front());
            q[5].pop();q[1].pop();
            q[0].push(t);
            ans++;
        }else if(!q[2].empty()){
            int t=merge(q[5].front(),q[2].front());
            q[5].pop();q[2].pop();
            q[3].push(t);
            ans++;
        }else{
            break;
        }
    }
    while(!q[0].empty()&&!q[2].empty()){
        int ta=get(q[0].front()),tb=get(q[2].front());
        if(ta==tb){
            if(q[0].size()>1){
                int t=q[0].front();q[0].pop();q[0].push(t);
            }else if(q[2].size()>1){
                int t=q[2].front();q[2].pop();q[2].push(t);
            }else{
                break;
            }
        }
        merge(q[0].front(),q[2].front());
        q[0].pop();q[2].pop();
        ans++;
    }
    while(!q[1].empty()&&!q[3].empty()){
        int ta=get(q[1].front()),tb=get(q[3].front());
        if(ta==tb){
            if(q[1].size()>1){
                int t=q[1].front();q[1].pop();q[1].push(t);
            }else if(q[3].size()>1){
                int t=q[3].front();q[3].pop();q[3].push(t);
            }else{
                break;
            }
        }
        merge(q[1].front(),q[3].front());
        q[1].pop();q[3].pop();
        ans++;
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>s;
        fa[i]=i;
        int len=s.size();
        for(int j=0;s[j+2];++j){
            if(s[j]=='o'&&s[j+1]=='w'&&s[j+2]=='o'){
                ++ans;
                ++j;
            }
        }
        if(s=="w"){
            if(!q[0].empty()){
                int t=merge(i,q[0].front());
                q[0].pop();
                q[1].push(t);
            }else if(!q[3].empty()){
                int t=merge(i,q[3].front());
                q[3].pop();
                q[2].push(t);
            }else{
                q[4].push(i);
            }
        }else if(s=="o"){
            if(!q[1].empty()){
                int t=merge(i,q[1].front());
                q[1].pop();
                q[0].push(t);
                ans++;
            }else if(!q[2].empty()){
                int t=merge(i,q[2].front());
                q[2].pop();
                q[3].push(t);
                ans++;
            }else{
                q[5].push(i);
            }
        }else{
            if(s[0]=='o') q[3].push(i); //b2
            else if(s[0]=='w'&&s[1]=='o') q[2].push(i); //b1
            if(s[len-1]=='o') q[0].push(i); //a1
            else if(s[len-1]=='w'&&len>=2&&s[len-2]=='o') q[1].push(i); //a2
        }
        Deal();
        cout<<ans<<'\n';
    }
    return 0;
}