DHU复试 Day16

DHU复试 Day16

Day16

今天学习的内容

一、基础题库

T71 发牌

#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;vector<vector<int>>a(4,vector<int>(13,0));//发牌for(inti=0;i<4;i++){for(intj=0;j<13;j++){a[i][j]=(i+4*j)%13;}}while(cin>>n){for(intj=0;j<13;j++){inti=n-1;intsum=i+4*j;if(j>0)cout<<" ";if(sum/13==0)cout<<"c"<<" "<<a[i][j];if(sum/13==1)cout<<"d"<<" "<<a[i][j];if(sum/13==2)cout<<"h"<<" "<<a[i][j];if(sum/13==3)cout<<"s"<<" "<<a[i][j];}cout<<endl;}return0;}

T72 数学金子塔----（动态规划）

#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;cin>>n;vector<vector<int>>a(n,vector<int>(n,0));for(inti=0;i<n;i++){for(intj=0;j<i+1;j++)cin>>a[i][j];}//用动态规划的思想进行求解vector<vector<int>>dp=a;//注意边界，直接从倒数第二行出发，因为倒数第一行无正下方或右下方//自下而上for(inti=n-2;i>=0;i--){for(intj=0;j<i+1;j++){//每一层的数据等于自身+两种选择的最大值dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);}}//顶部就是最大值cout<<dp[0][0]<<endl;return0;}

总结：对于动态规划问题，一般是要选择最优解，或者是最大解。那么就要涉及到选择问题，每一步都要选择符合题设要求，直至到最后。对于这道题而言，可以从上往下dp，也可以从下往上dp。但是从下往上涉及的边界条件比较少，容易理解。可以想象成金子塔倒着，则每次每行都要寻找到最大值，一直到最顶层。

T75 魔方阵

#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;while(cin>>n){vector<vector<int>>a(n+1,vector<int>(n+1,0));//放1a[1][(n+1)/2]=1;inti=1,j=(n+1)/2;intcnt=2;while(cnt<=n*n){//规则2intnew_i=i-1;intnew_j=j+1;//规则3 如果i为1 则newi为0if(new_i==0)new_i=n;//规则4 如果j为n则newi为n+1if(new_j==n+1)new_j=1;//规则5 由于上面已经判断了第一行 第n列if(a[new_i][new_j]==0){i=new_i;j=new_j;}else{i++;}a[i][j]=cnt;cnt++;}for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){if(j>1)cout<<" ";cout<<a[i][j];}cout<<endl;}cout<<endl;}return0;}

总结：按照题目的要求，来写条件，i，j表示的是原来的节点，而new_i、new_j是新的节点，从2开始，新节点都要按照规则2的要求处理，只是有一些特殊的点，需要按照规则3、4处理，规则5其实只有新节点已存在的时候，因为后续的一个条件，包括了规则3、4. 等把所有规则都过一遍后，在更新i 、j。同时更新数组的值。

T56 最少拦截系统—（）

#include<bits/stdc++.h>usingnamespacestd;intmain(){intt;cin>>t;while(t--){intn;cin>>n;vector<int>a(n,0);for(inti=0;i<n;i++)cin>>a[i];vector<vector<int>>d(n+1,vector<int>());//存放导弹系统 声明有多少行，每行为空intcnt=1;d[1].push_back(a[0]);for(inti=1;i<n;i++){inttemp=a[i];//遍历系统boolflag=false;for(intk=1;k<=cnt;k++){//如果小于第k套系统的末尾，就写入该系统if(temp<d[k].back()){d[k].push_back(temp);flag=true;break;}}//如果所有的系统都没有找到合适的，就重新开一个系统，并写入if(!flag){cnt++;d[cnt].push_back(temp);}}cout<<cnt<<endl;}return0;}

T45 回文数

#include<bits/stdc++.h>usingnamespacestd;//求逆序数intNixu(intn){intnum=0;while(n!=0){num=num*10+n%10;n/=10;}returnnum;}//判断是不是回文数boolIshuiwen(intn){inta=Nixu(n);returna==n;}intmain(){intn;while(cin>>n){if(n==0)break;inta=n,b=Nixu(a);while(1){intsum=a+b;cout<<a<<"+"<<b<<"="<<sum<<endl;//如果和是回文数，则退出if(Ishuiwen(sum))break;a=sum;b=Nixu(a);}}return0;}

T41 环—（对环的操作等效于循环左移操作）

#include<bits/stdc++.h>usingnamespacestd;//循环左移位voidremove(vector<int>&a){inttemp=a[0];for(inti=0;i<a.size()-1;i++){a[i]=a[i+1];}a[a.size()-1]=temp;}intmain(){intn;cin>>n;vector<int>a(9);while(n--){intcnt=0;//记录有多少种方法for(inti=0;i<9;i++)cin>>a[i];//开始剪for(intj=0;j<9;j++){vector<int>temp=a;//暂时代替a数组for(intk=0;k<j;k++)remove(temp);//顺时针形成的数intnum1=0;for(inti=0;i<9;i++){num1=num1*10+temp[i];}//逆时针形成的数intnum2=0;for(inti=8;i>=0;i--){num2=num2*10+temp[i];}if(abs(num1-num2)%396==0)cnt++;}cout<<cnt<<endl;}return0;}

T38 树-------（unorderd_set）

#include<bits/stdc++.h>usingnamespacestd;intmain(){intl,m;while(cin>>l>>m){inttotal=l+1;//总共的树vector<int>removes;//储存需要移出的树for(inti=0;i<m;i++){intstart,end;cin>>start>>end;//将要移出的区域输入到数组中for(intx=start;x<=end;x++){//标记看x是否已经存在数组中boolflag=false;for(inti=0;i<removes.size();i++){if(x==removes[i]){flag=true;break;}}if(!flag)removes.push_back(x);}}cout<<total-removes.size()<<endl;}return0;}//时间复杂度比较高，容易超时

//unordered_set 的插入时间复杂度能达到o（1）#include<bits/stdc++.h>usingnamespacestd;intmain(){intl,m;while(cin>>l>>m){inttotal=l+1;//总共的树unordered_set<int>removes;//储存需要移出的树for(inti=0;i<m;i++){intstart,end;cin>>start>>end;//将要移出的区域输入到数组中for(intx=start;x<=end;x++){removes.insert(x);}}cout<<total-removes.size()<<endl;}return0;}