计协考核5道题目的题解

01.寻宝图题目https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?page1problemSetProblemId1649748772841508875题解通过读题很容易看出来这是一道关于dfs的搜索题本题是有关连通块的知识并且这道题要我们输出非零连通块即陆地的数量和宝藏数即是大于1的点但是题目有一点陷阱它的输入是连在一起的所以不能用整型数组要用字符数组然后通过dfs可以找出所有的陆地先设置了fx和fy方向数组然后用f标记是否是宝藏c2统计宝藏的数目再分别计数即可。代码如下#includebits/stdc.h using namespace std; typedef long long ll; ll fx[4]{0,1,0,-1}; ll fy[4]{1,0,-1,0}; ll n,m; ll c2,f; void dfs(ll x,ll y,vectorvectorchara){ if(a[x][y]2a[x][y]9){ f1; } a[x][y]0; for(int i0;i4;i){ ll dxfx[i]x; ll dyfy[i]y; if(dx0dxndy0dyma[dx][dy]!0){ dfs(dx,dy,a); } } } int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cinnm; vectorvectorchara(n,vectorchar(m)); for(int i0;in;i){ for(int j0;jm;j){ cina[i][j]; } } int c10,c20; for(int i0;in;i){ for(int j0;jm;j){ f0; if(a[i][j]!0){ c1; dfs(i,j,a); if(f1)c2; } } } coutc1 c2; }02.谁管谁叫爹题目https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?page0problemSetProblemId1649748772841508871题解先读题很好理解就不解释了本题先将每个数以字符串的形式录入再通过将每项-0变成整数每个数分别相加算到了N的值再算原数字的值将字符串每项拆出来变成数字再通过公式 sumsum*10num 算原数字num即是每一项的数字再分别取模判断是否整除即可。代码如下#includebits/stdc.h using namespace std; typedef long long ll; ll n; char a[11],b[11]; ll a1[10010],b1[10010]; int main(){ cinn; for(int i0;in;i){ ll s10,s20,p10,p20; cinab; ll len1strlen(a); ll len2strlen(b); for(int i0;ilen1;i){ p1a[i]-0; } for(int i0;ilen2;i){ p2b[i]-0; } for(int i0;ilen1;i){ s1s1*10(a[i]-0); } for(int i0;ilen2;i){ s2s2*10(b[i]-0); } if(s1%p20s2%p1!0){ coutA\n; }else if(s1%p2!0s2%p10){ coutB\n; }else if((s1%p20s2%p10)||(s1%p2!0s2%p1!0)){ if(s1s2){ coutA\n; }else{ coutB\n; } } } }03.满树的遍历题目https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?page1problemSetProblemId1781658570803388426题解本题让我们找K阶满树即除了叶子节点外其他节点的度都相等的树所以我们要根据输入的值创建一个邻接表来存这个树又因为题目说要以先序遍历输出所以要对每个节点的子节点进行从小到大排序所以用来sort复杂度O(nlogn)然后我们来找最大的度的值只需要算子节点的数目即可然后只要有一个节点的子节点数和最大值不同则不是K阶满树最后来先序遍历该树通过dfs不断向下遍历直到叶子节点就回溯遍历上一个节点依次这样递归存储到b数组中最后遍历输出b数组即是先序遍历的序列。注意格式代码如下#includebits/stdc.h using namespace std; typedef long long ll; const ll N1e510; ll n,root; vectorvectorlla;//用来存树 vectorllb; int f1;//判断是否是k阶满树 void dfs(ll u,vectorvectorlla){ b.push_back(u); for(auto v:a[u]){ dfs(v,a); } } int main(){ cinn; a.resize(n1); for(int i1;in;i){ ll x; cinx; if(x0)rooti; else{ a[x].push_back(i); } } for(int i1;in;i){ sort(a[i].begin(),a[i].end()); } ll maxna[root].size(); for(int i1;in;i){ maxnmax((ll)a[i].size(),maxn); } for(int i1;in;i){ if((ll)a[i].size()0)continue; if((ll)a[i].size()!maxn){ f0; break; } } coutmaxn ; if(f0){ coutno\n; }else{ coutyes\n; } dfs(root,a); for(ll i0;ib.size();i){ if(i!b.size()-1){ coutb[i] ; } else{ coutb[i]; } } }04.大幂数题目https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?page1problemSetProblemId1913922872972247046题解​​​​​​​首先读题数据的范围最大是到2的31次方所以我们能知道最大的米次数肯定不会超过31次方并且要我们找到最大的幂次方数之和我们就可以让幂次方从大到小依次寻找所以设最大的幂次方为31足以然后内循环从1连续相加判断但不能直接用pow可能会导致精度的损失所以要用快速幂来计算次方的值然后用快速幂算次方的值如果值已经大于要求的值直接退出进行下一次循环直到sum等于n或循环完也不满足最终分别输出即可。代码如下#includebits/stdc.h using namespace std; typedef long long ll; ll n; ll ksm(ll a,ll b){ ll res1; while(b){ if(b1){ res*a; } a*a; b/2; } return res; } int main(){ cinn; for(int i31;i1;--i){ ll sum0; ll t0; for(int j1;j100000;j){ tksm(j,i); if(tn)break; sumt; if(sumn){ cout1^i; for(int k2;kj;k){ coutk^i; } return 0; } } } coutImpossible for n.; }05.影响力题目https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?page2problemSetProblemId1913922872972247053题解本题由于我的能力问题暂时只能想到最暴力的做法只能得一半的分如果有大佬有自己的想法可以在评论区讨论。我的代码如下#includebits/stdc.h using namespace std; typedef long long ll; ll n,m; int main(){ cinnm; vectorvectorlla(n1,vectorll(m1)); for(int i1;in;i){ for(int j1;jm;j){ cina[i][j]; } } for(int i1;in;i){ for(int j1;jm;j){ ll num0; for(int k1;kn;k){ for(int p1;pm;p){ if(kipj)continue; nummax(abs(k-i),abs(p-j)); } } if(jm)couta[i][j]*num\n; else{ couta[i][j]*num ; } } } }