第十五届中北大学算法与程序设计比赛部分题解
A题：俄罗斯方块
思路：模拟题，只要模拟出4个图形落下后的矩阵的01情况，同时，每步之后不断更新10列的所能下落到的最小值h[11](从1-10）因为这是从下往上的，所以只要不断更新h的各元素的值即可。下落一个图形的时候，找到该图形所覆盖的区域的（也就是所覆盖的相关的列）高度的最小值，图形就是在该值-1，也就是在该值的上面。
出题人还是减低了难度，如果四个图形的底不是平行的话，那就要考虑比较多的了。
代码：
#include<bits/stdc++.h>
using namespace std;
int a[12][12];
int h[12];
int main(){
int n;
cin>>n;
memset(a,0,sizeof(a));
for(int i=1;i<11;i++) h[i]=10;
while(n--){
int id,x;
cin>>id>>x;
if(id==1){
int mi=12;
for(int i=x;i<=x+1;i++){
mi=min(h[i],mi);
}
a[mi][x]=a[mi][x+1]=a[mi-1][x]=a[mi-1][x+1]=1;
h[x]=h[x+1]=mi-2;
}
if(id==2){
int mi=12;
for(int i=x;i<=x+2;i++){
mi=min(h[i],mi);
}
a[mi][x]=a[mi][x+1]=a[mi][x+2]=a[mi-1][x]=1;
h[x]=mi-2,h[x+1]=h[x+2]=mi-1;
}
if(id==4){
int mi=12;
for(int i=x;i<=x+2;i++){
mi=min(h[i],mi);
}
//cout<<mi<<endl;
a[mi][x]=a[mi][x+1]=a[mi][x+2]=a[mi-1][x+1]=1;
h[x]=mi-1,h[x+1]=mi-2,h[x+2]=mi-1;
}
if(id==3){
int mi=12;
for(int i=x;i<x+4;i++){
mi=min(mi,h[i]);
}
a[mi][x]=a[mi][x+1]=a[mi][x+2]=a[mi][x+3]=1;
h[x]=h[x+1]=h[x+2]=h[x+3]=mi-1;
}
// for(int i=1;i<=10;i++){
// for(int j=1;j<=10;j++){
// cout<<a[i][j];
// if(j<10) cout<<" ";
// }
// cout<<endl;
// }
}
for(int i=1;i<=10;i++){
for(int j=1;j<=10;j++){
cout<<a[i][j];
if(j<10) cout<<" ";
}
cout<<endl;
}
return 0;
}B题：真的是签到题
这个应该没话说吧
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
for(int i=0;i<3;i++){
cout<<"NUC2020!!!"<<endl;
}
return 0;
}E题：简单的线性代数
思路：这个主要是考线性代数，其实没有算法难度的，只要知道这个特殊的就可以了。(E+A+A^2+……A^k-1)的逆=（E-A），然后就只要输出即可了。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[1002][1002];
int main(){
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(j==i) a[i][j]=1-a[i][j];
else a[i][j]=0-a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<a[i][j];
if(j<n) cout<<" ";
}
cout<<endl;
}
return 0;
}G题：数位操作1
思路：这题，一开始想的是对n进行质因数分解，然后对所有的质因数进行组合，找到最大的那个值输出即可。但是，不知道为什么只过了百分之三十的数据，理解不了，ORZ，后来，看了他们的代码后，才发现自己原来还是想复杂了，其实可以通过i直接从9-2，一直找可以整除i的值，然后保存，可以重复。但是，这里还要特判一下1-9的时候，由于ans>9,所以如果在1-9，则n+10输出即可。
通过这个题目，感觉自己还是需要磨练一下做题的心态，要学会转换角度思考问题。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
void solve(){
if(n<10){ //10以内的数字
cout<<n+10<<endl;
return;
}
vector<int> v;
for(int i=9;i>=2;i--){
while(n%i==0){
v.push_back(i);
n/=i;
}
if(n==1) break;
// cout<<n<<endl;
}
if(n!=1) cout<<"-1"<<endl;
else{
for(int i=v.size()-1;i>=0;i--){
cout<<v[i];
}
cout<<endl;
}
}
int main(){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
while(scanf("%ld",&n)!=EOF){
solve();
}
return 0;
}K题：签个到
思路：我们通过观察可以发现，我们将所有的m次操作都作用于数组中的一个元素是最优的，然后，我们只要输出这个过程中，出现的最大的ans即可。然后，对于每个数组中的元素，我们可以这样做：先找出原始数组中的最大值mx，最小值mi，然后，对每个元素单独处理，我们先计算这个元素离mx，mi的最大的距离为tmp，然后对该元素进行m次操作，此时tmp=tmp+i*m,然后不断更新ans即可，最后输出。
特判：当n=1的时候，直接输出0即可。
代码：
using namespace std;
typedef long long ll;
ll a[100010];
int main(){
int n,m;
cin>>n>>m;
ll mx=-1e9,mi=1e9;
for(int i=1;i<=n;i++){
cin>>a[i];
mx=max(mx,a[i]);
mi=min(mi,a[i]);
}
if(n==1){
cout<<"0"<<endl;
return 0;
}
ll ans=-1e9;
for(int i=1;i<=n;i++){
ll tmp=max(a[i]-mi,mx-a[i]);
ans=max(ans,tmp+m*i);
}
cout<<ans<<endl;
return 0;
}
查看5道真题和解析