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; }