DHU复试 Day16文章目录DHU复试 Day16Day16一、基础题库T71 发牌T72 数学金子塔----动态规划T75 魔方阵T56 最少拦截系统---T45 回文数T41 环---对环的操作等效于循环左移操作T38 树-------unorderd_setDay16今天学习的内容一、基础题库T71 发牌#includebits/stdc.husingnamespacestd;intmain(){intn;vectorvectorinta(4,vectorint(13,0));//发牌for(inti0;i4;i){for(intj0;j13;j){a[i][j](i4*j)%13;}}while(cinn){for(intj0;j13;j){intin-1;intsumi4*j;if(j0)cout ;if(sum/130)coutc a[i][j];if(sum/131)coutd a[i][j];if(sum/132)couth a[i][j];if(sum/133)couts a[i][j];}coutendl;}return0;}T72 数学金子塔----动态规划#includebits/stdc.husingnamespacestd;intmain(){intn;cinn;vectorvectorinta(n,vectorint(n,0));for(inti0;in;i){for(intj0;ji1;j)cina[i][j];}//用动态规划的思想进行求解vectorvectorintdpa;//注意边界直接从倒数第二行出发因为倒数第一行无正下方或右下方//自下而上for(intin-2;i0;i--){for(intj0;ji1;j){//每一层的数据等于自身两种选择的最大值dp[i][j]max(dp[i1][j],dp[i1][j1]);}}//顶部就是最大值coutdp[0][0]endl;return0;}总结对于动态规划问题一般是要选择最优解或者是最大解。那么就要涉及到选择问题每一步都要选择符合题设要求直至到最后。对于这道题而言可以从上往下dp也可以从下往上dp。但是从下往上涉及的边界条件比较少容易理解。可以想象成金子塔倒着则每次每行都要寻找到最大值一直到最顶层。T75 魔方阵#includebits/stdc.husingnamespacestd;intmain(){intn;while(cinn){vectorvectorinta(n1,vectorint(n1,0));//放1a[1][(n1)/2]1;inti1,j(n1)/2;intcnt2;while(cntn*n){//规则2intnew_ii-1;intnew_jj1;//规则3 如果i为1 则newi为0if(new_i0)new_in;//规则4 如果j为n则newi为n1if(new_jn1)new_j1;//规则5 由于上面已经判断了第一行 第n列if(a[new_i][new_j]0){inew_i;jnew_j;}else{i;}a[i][j]cnt;cnt;}for(inti1;in;i){for(intj1;jn;j){if(j1)cout ;couta[i][j];}coutendl;}coutendl;}return0;}总结按照题目的要求来写条件ij表示的是原来的节点而new_i、new_j是新的节点从2开始新节点都要按照规则2的要求处理只是有一些特殊的点需要按照规则3、4处理规则5其实只有新节点已存在的时候因为后续的一个条件包括了规则3、4. 等把所有规则都过一遍后在更新i 、j。同时更新数组的值。T56 最少拦截系统—#includebits/stdc.husingnamespacestd;intmain(){intt;cint;while(t--){intn;cinn;vectorinta(n,0);for(inti0;in;i)cina[i];vectorvectorintd(n1,vectorint());//存放导弹系统 声明有多少行每行为空intcnt1;d[1].push_back(a[0]);for(inti1;in;i){inttempa[i];//遍历系统boolflagfalse;for(intk1;kcnt;k){//如果小于第k套系统的末尾就写入该系统if(tempd[k].back()){d[k].push_back(temp);flagtrue;break;}}//如果所有的系统都没有找到合适的就重新开一个系统并写入if(!flag){cnt;d[cnt].push_back(temp);}}coutcntendl;}return0;}T45 回文数#includebits/stdc.husingnamespacestd;//求逆序数intNixu(intn){intnum0;while(n!0){numnum*10n%10;n/10;}returnnum;}//判断是不是回文数boolIshuiwen(intn){intaNixu(n);returnan;}intmain(){intn;while(cinn){if(n0)break;intan,bNixu(a);while(1){intsumab;coutabsumendl;//如果和是回文数则退出if(Ishuiwen(sum))break;asum;bNixu(a);}}return0;}T41 环—对环的操作等效于循环左移操作#includebits/stdc.husingnamespacestd;//循环左移位voidremove(vectorinta){inttempa[0];for(inti0;ia.size()-1;i){a[i]a[i1];}a[a.size()-1]temp;}intmain(){intn;cinn;vectorinta(9);while(n--){intcnt0;//记录有多少种方法for(inti0;i9;i)cina[i];//开始剪for(intj0;j9;j){vectorinttempa;//暂时代替a数组for(intk0;kj;k)remove(temp);//顺时针形成的数intnum10;for(inti0;i9;i){num1num1*10temp[i];}//逆时针形成的数intnum20;for(inti8;i0;i--){num2num2*10temp[i];}if(abs(num1-num2)%3960)cnt;}coutcntendl;}return0;}T38 树-------unorderd_set#includebits/stdc.husingnamespacestd;intmain(){intl,m;while(cinlm){inttotall1;//总共的树vectorintremoves;//储存需要移出的树for(inti0;im;i){intstart,end;cinstartend;//将要移出的区域输入到数组中for(intxstart;xend;x){//标记看x是否已经存在数组中boolflagfalse;for(inti0;iremoves.size();i){if(xremoves[i]){flagtrue;break;}}if(!flag)removes.push_back(x);}}couttotal-removes.size()endl;}return0;}//时间复杂度比较高容易超时//unordered_set 的插入时间复杂度能达到o1#includebits/stdc.husingnamespacestd;intmain(){intl,m;while(cinlm){inttotall1;//总共的树unordered_setintremoves;//储存需要移出的树for(inti0;im;i){intstart,end;cinstartend;//将要移出的区域输入到数组中for(intxstart;xend;x){removes.insert(x);}}couttotal-removes.size()endl;}return0;}