2022年A组国赛
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。
对于一个排列, 有两种转移操作:
- 转移到其下一个排列。如果当前排列已经是最后一个排列, 那么下一个 排列就是第一个排列。
- 转移到其上一个排列。如果当前排列是第一个排列, 那么上一个排列就 是最后一个排列。
小蓝现在有两个排列, 分别为排列 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;
}