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]; //1286583532342313400return 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。
对于一个排列, 有两种转移操作:
- 转移到其下一个排列。如果当前排列已经是最后一个排列, 那么下一个 排列就是第一个排列。
- 转移到其上一个排列。如果当前排列是第一个排列, 那么上一个排列就 是最后一个排列。
小蓝现在有两个排列, 分别为排列 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); //106148357572143return 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; //本就存在1return 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); //b2else if(s[0]=='w'&&s[1]=='o') q[2].push(i); //b1if(s[len-1]=='o') q[0].push(i); //a1else if(s[len-1]=='w'&&len>=2&&s[len-2]=='o') q[1].push(i); //a2}Deal();cout<<ans<<'\n';}return 0;
}
