第十五届中北大学算法与程序设计竞赛（公开赛）题解

比赛链接

A.俄罗斯方块

题意：
10∗10的图
给四种俄罗斯的图形，给出位置横坐标，求下降完后的图形
题解：
图很小，直接从上向下模拟下降过程即可
AC代码

#include<bits/stdc++.h>
using namespace std;
int v[12][12];
void solve(){
    int n;cin>>n;
    for(int i=1;i<=11;i++)v[11][i]=1;
    while(n--){
        int x,y;cin>>x>>y;
        if(x==1){
            for(int i=2;i<=11;i++){
                if(!(!v[i][y]&&!v[i][y+1]&&!v[i-1][y]&&!v[i-1][y+1])){
                    i--;
                    v[i][y]=1,v[i][y+1]=1,v[i-1][y]=1,v[i-1][y+1]=1;
                    break;
                }
            }
        }
        if(x==2){
            for(int i=2;i<=11;i++){
                if(!(!v[i][y]&&!v[i][y+1]&&!v[i][y+2]&&!v[i-1][y])){
                    i--;
                    v[i][y]=1,v[i][y+1]=1,v[i][y+2]=1,v[i-1][y]=1;
                    break;
                }
            }
        }
        if(x==3){
            for(int i=1;i<=11;i++){
                if(!(!v[i][y]&&!v[i][y+1]&&!v[i][y+2]&&!v[i][y+3])){
                    i--;
                    v[i][y]=1,v[i][y+1]=1,v[i][y+2]=1,v[i][y+3]=1;
                    break;
                }
            }
        }
        if(x==4) {
            for(int i=2;i<=11;i++){
                if(!(!v[i][y]&&!v[i][y+1]&&!v[i][y+2]&&!v[i-1][y+1])){
                    i--;
                    v[i][y]=1,v[i][y+1]=1,v[i][y+2]=1,v[i-1][y+1]=1;
                    break;
                }
            }
        }
    }
    for(int i=1;i<=10;i++){
        for(int j=1;j<=10;j++)cout<<v[i][j]<<' ';
        cout<<endl;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}

B.真的是签到题

直接输出即可
AC代码

#include<bits/stdc++.h>
using namespace std;
void solve(){
    for(int i=0;i<3;i++)cout<<"NUC2020!!!"<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

C.港口

题意：
给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。问变相等的最少操作次数。
题解：
想要得到所有数都一样，也就是要使差分序列的 2~n 项全为 0。而第 1 项代表第一个数的大小，改变第1项只会让数列整体变大或变小，并不影响数列相同。计算差分序列，记录差分序列中正数和负数的个数，每次操作可以让差分序列中的两个数一个 +1 另一个 -1，因此，也就是差分后 Max( 正数和，负数和 ) 次。
AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define lowbit(x) x&(-x)
#define pb push_back
#define iter set<int>::iterator

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e6+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}
ll a[N],p,q;
void solve(){
    int n;cin>>n;
	for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=2;i<=n;i++){
        if(a[i]-a[i-1]>0)p+=a[i]-a[i -1];
        else q-=a[i]-a[i-1];
    }
    cout<<max(p,q);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}

D.构造数组

题意：
构造一个长度为n的数组A，构造方式如下：
依次进行n次操作，第i次操作在数组A的index[i]位置处插入整数number[i].
最后从左到右输出数组A的元素
题解：
这道题从前向后考虑是不行的，我们从后向前考虑，最后一个插入的数位置肯定是index[n]，然后倒二插入的位置可能是index[n-1]或index[n-1]+1,显然最后一个数的插入影响的倒二的数的位置，其实就是后面插入的数对前面插入的数的位置产生后移，所以每次只要找x-sum(x)=index[i]就行了，最终位置就是x,用树状数组维护前和就好了。
AC代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define lowbit(x) x&(-x)
#define pb push_back
#define iter set<int>::iterator

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e6+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}
ll a[N],b[N],ans[N],tree[N],n;
void add(int x,int y){
    while(x<=n){
        tree[x]+=y;
        x+=lowbit(x);
    }
}
ll sum(int x){
    ll sum=0;
    while(x>0){
        sum+=tree[x];
        x-=lowbit(x);
    }
    return sum;
}
int find(int x){
    int l=1,r=n;
    while(l<r){
        int mid=(l+r)>>1;
        if(mid-sum(mid)<x)l=mid+1;
        else r=mid;
    }
    return l;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
	for(int i=n;i>0;i--){
        int x=a[i];
        int k=find(x);
        add(k,1);
        ans[k]=b[i];
	}
	for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}

E.简单的线性代数*

题意：
已知A是一个n阶方阵，且Ak=0，E是一个n阶单位矩阵，求（E+A+……+A(k-1)）的逆
题解
我们用等比数列求和得到 E+A+……+A(k-1)=（E-Ak)/(E-A),
（E-Ak)/(E-A)*B=E，又Ak=0，则B=（E-A）
AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double esp=1e-8;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}
int a[1001][1001];
void solve(){
    ll n,k;cin>>n>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            if(i==j)a[i][j]=1-a[i][j];
            else a[i][j]*=-1;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cout<<a[i][j]<<' ';
        cout<<'\n';
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}

F.集合操作

题意
有一个集合S，刚开始是空集，现在有3种操作。
1.往集合中添加x,如果集合中已经存在x，则不添加。
2.从集合中删除x，如果集合中不存在x，则不删除。
3.查询大于等于x且不在集合S中的最小的正整数
题解
先离散化，然后用树状数组维护一下前缀，查询的时候我们二分找出一个数与x的实际差刚好等于与x间隔的数（集合中存在）的个数，也就是

sum(mid)-sum(k-1)==c[mid]-c[k]+1//k是离散化后x的下标，c是离散数组

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define lowbit(x) x&(-x)
#define pb push_back
#define iter set<int>::iterator

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e6+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}
ll a[N],b[N],c[N],tree[N],v[N],len;
void add(int x,int y){
    while(x<=len){
        tree[x]+=y;
        x+=lowbit(x);
    }
}
ll sum(int x){
    ll sum=0;
    while(x>0){
        sum+=tree[x];
        x-=lowbit(x);
    }
    return sum;
}
void solve(){
	int n;cin>>n;
	for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        c[i]=b[i];
	}
	sort(c+1,c+1+n);
	len=unique(c+1,c+1+n)-c-1;
	c[len+1]=INF;
	for(int i=1;i<=n;i++){
        int x=a[i],y=b[i];
        int k=lower_bound(c+1,c+1+len,y)-c;
        if(x==1&&!v[k])v[k]=1,add(k,1);
        if(x==2&&v[k])v[k]=0,add(k,-1);
        if(x==3){
            int l=k,r=len+1;
            while(l<r){
                int m=(r+l)>>1;
                if(sum(m)-sum(k-1)==c[m]-c[k]+1)l=m+1;
                else r=m;
            }
            if(l==k)cout<<c[k]<<'\n';
            else cout<<c[l-1]+1<<'\n';
        }
	}
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}

G.数位操作1

题意：
给你一个正整数 n ，找到最小的某个数据 ans (ans >9）
要求 ans 的每一数位(个位 十位 百位 千位…) 乘积与n相等， 不存在输出-1
题解：
按贪心思想，将原数按9~1分解即可，如果最后剩下的数大于9，则说明不存在，注意特判1.
AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double esp=1e-8;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}

void solve(){
    ll n;
    while(cin>>n){
        if(n==1){cout<<11<<endl;continue;}
        vector<int>v;
        for(ll i=9;n>1&&i>1;i--){
            while(n%i==0)n/=i,v.pb(i);
        }
        if(n>9){cout<<-1<<endl;continue;}
        else if(n>1)v.pb(n);
        if(v.size()==1)v.pb(1);
        sort(v.begin(),v.end());
        for(auto i:v)cout<<i;cout<<endl;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}

K.签个到

题意
给n个数，进行m次操作
每次操作可以使得任意一个数加或减他的下标，问m次操作后这个数列的极差最大是多少
题解
排一下序，然后对于任意一个数进行m次操作后最大极差为

max(abs(a[i]-b[1]),abs(a[i]-b[n]))+i*m

显然枚举一下a[n]，找对各个数的操作极差即可
AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
 
const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double esp=1e-8;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};
 
ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}
ll a[N],b[N];
void solve(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
    sort(b+1,b+1+n);
    ll ans=0;
    if(n==1){cout<<0;return;}
    for(ll i=1;i<=n;i++){
        ll k=max(abs(a[i]-b[1]),abs(a[i]-b[n]));
        ans=max(ans,k+i*m);
    }
    cout<<ans;
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}
全部评论

相关推荐

11-23 11:15
门头沟学院 Java
虎牙java后端开发日常一面凉经
8月投递java后端开发日常实习，base广州一面（挂）：（没有录屏，记不清了）1.自我介绍（以及为什么实习乱七八糟的.......）2.泛型上下限3.泛型的用法，项目中怎么用的？4.Mysql索引数据结构5.Hashmap相关？6.关键词全文检索怎么做的，怎么使用mysql实现（回答模糊查询，说太慢了，回去查了一下发现有个叫全文检索索引的）7.（场景题）如何本机访问服务器（改本机host，其他的方案全被否决）8.（场景提）开发中测试说你的接口有问题你会怎么做？如何排查？（说一堆全部反驳，还没实习怎么会和测试有合作）无手撕，没开摄像头，面完查看直接挂，难受了好久
查看8道真题和解析 软件开发笔面经 牛客创作赏金赛
点赞 评论 收藏
分享
11-24 14:20
北京大学 Java
秋招offer比较，头部大厂or明星初创
决赛圈了，希望各位前辈能帮忙斟酌一下，n∈[32k，35k]，m∈[10w，13w]&nbsp;字节：n×15&nbsp;+&nbsp;m期权&nbsp;+&nbsp;15w签字费&nbsp;初创：(n+7k)×16&nbsp;+&nbsp;2m期权&nbsp;+&nbsp;15w签字费&nbsp;1优点，字节算挺有诚意，本来确定要去了，但下面的初创给了个大的。毫无疑问title对未来跳槽帮助大&nbsp;1缺点，这个组的人才密度比较大，有一半多是top2的，晋升感觉无望，但跟着大佬多学点东西也还行。&nbsp;2优点:给的钱多，明星初创有一定前景?(几率很小)&nbsp;2缺点:加班比字节还严重。以及这类型公司跳槽，&nbsp;title的...
CoderEcho：虽然我没去大厂，但是待过俩家初创，我的感觉是厉害的初创很舍得给钱，也很看你的产出，产出不行直接把你开了。当然大厂也可能有这个问题。建议还是去大厂，如果被裁员了最起码还有大厂的title，这年头不确定的事儿太多了。
字节求职进展汇总 软开人，秋招你打算投哪些公司呢
点赞 评论 收藏
分享
10-30 17:07
University of California Riverside UE4
某些HR能不能有点职业素养
朋友圈挂人骂人巨婴😅😅
我已成为0offer的糕手：别惯着，胆子都是练出来的，这里认怂了，那以后被裁应届被拖工资还敢抗争？
点赞 评论 收藏
分享
10-21 11:09
北京邮电大学 C++
这公司也是神了
面试摇了我吧：啊哈哈面试提前五个小时发，点击不能参加就是放弃
点赞 评论 收藏
分享
11-26 14:40
辽宁工业大学 汽车电子工程师
比亚迪工作真实体验
加班文化在比亚迪是挺普遍的，不同部门不同岗位情况不一样。G级有加班工资，F级看情况，有的可以特批加班工资或者换调休。晋升方面，如果起点太低，机会不大，除非你有个好领导，个人能力强，还得有点机遇。比亚迪推崇智能化、信息化、自动化，老员工竞争力会越来越小，新来的本科生研究生专业知识强，学习能力也好，可能两三年就能达到老员工六七年的高度。内部换部门和事业部挺难的，没人能告诉你到底好不好，只有自己融入进去才知道。总的来说，比亚迪平台大，有好有坏，有机遇有前景，但能不能抓住得看运气。很多人想进来，也有很多人想出去，每个人的体验都不一样
比亚迪成长空间 168人发布
点赞 评论 收藏
分享
评论
2
收藏
分享

全站热榜

正在热议
# 25届秋招总结 #
381828次浏览 3798人参与
# ai智能作图 #
12490次浏览 196人参与
# 阿里云管培生offer #
52192次浏览 1501人参与
# 地方国企笔面经互助 #
6166次浏览 14人参与
# 我的实习求职记录 #
6109143次浏览 83853人参与
# 发工资后，你做的第一件事是什么 #
5156次浏览 20人参与
# 北方华创开奖 #
64965次浏览 519人参与
# 硬件兄弟们 甩出你的华为奖状 #
76315次浏览 617人参与
# 如果再来一次，你还会选择这个工作吗？ #
104065次浏览 1046人参与
# 哪些公司校招卡第一学历 #
31541次浏览 89人参与
# 如果有时光机，你最想去到哪个年纪？ #
27190次浏览 562人参与
# 华为工作体验 #
109587次浏览 853人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
9122次浏览 185人参与
# 还记得你第一次面试吗？ #
30193次浏览 425人参与
# 许愿池 #
216791次浏览 2543人参与
# 腾讯求职进展汇总 #
206057次浏览 1689人参与
# 你觉得第一学历对求职有影响吗？ #
15939次浏览 129人参与
# 产运销实习日记 #
27879次浏览 323人参与
# 阿里求职进展汇总 #
71920次浏览 785人参与
# 上班到公司第一件事做什么？ #
14632次浏览 165人参与
# 实习，投递多份简历没人回复怎么办 #
2429921次浏览 34650人参与
# 实习中的菜狗时刻 #
280162次浏览 2759人参与
牛客网
牛客企业服务