企业官网建设流程全解析

一、小易的升级之路

题目解析

小易现在要打游戏，现在游戏角色的初始能力值为a，我们会遇到n个怪，这些怪物的防御值为b1、b2、b3...，如果我们的能力值要高于或者等于怪物的防御值，那我们的能力值就会加bi；如果不大于怪物的防御值，我们的能力值就加当前能力值和bi的最大公约数。

我们要求出来小易的最终能力值。

算法思路

这道题，也是一道很简单的模拟题目了，直接模拟整个过程即可。

当前能力值为c，如果c>=bi，那能力值就加上bi；

如果c<bi，那能力值就加上c和bi的最大公约数。

代码实现

这里要注意的是：题目是多组输入，我们这里要用while(cin>>n>>c)来进行多组输入

#include<iostream>usingnamespacestd;intmin_y(intx,inty){inttmp=x%y;while(tmp){x=y;y=tmp;tmp=x%y;}returny;}intmain(){intc,n;while(cin>>n>>c){for(inti=0;i<n;i++){intx;cin>>x;if(c>=x)c+=x;elsec+=min_y(x,c);}cout<<c<<endl;}return0;}

二、礼物的最大价值

题目解析

题目给了一个m*n的棋盘，每一个格子里面都放着一个礼物，每一个礼物都有一定价值；现在我们从左上角开始拿礼物，我们只能向右或者向下移动一格，直到棋盘的右下角；我们要计算最多可以拿到多少价值的礼物。

给定一个二维数组，每一个位置的值就表示该位置礼物的价值，我们从(1,1)位置开始，向右或者向下走，直到(m,n)位置，求最多可以拿到多少价值的礼物。

算法思路

这道题呢，算是一道路径问题，解法呢就是动态规划

题目中说，我们可以向右和向下走，也就是从[i,j]位置移动到[i][j+1]位置和[i+1][j]位置（我们反过来理解就是，要走到[i,j]位置，只能从[i][j-1]和[i-1][j]两个位置走过去，那走到[i,j]位置能拿到礼物的最大价值就等于，走到[i,j-1]和[i-1][j]位置能拿到礼物的最大价值的最大值再加上[i,j]位置礼物的价值。

动态规划思路：

状态表示：dp[i][j]表示走到[i,j]位置能拿到礼物的最大价值。

状态转移方程：dp[i][j] = max(dp[i][j-1] , dp[i-1][j]) + arr[i][j]。

代码实现

这里要注意

下标对应，题目给的数组grid下标是从(0,0)开始的，而我们的dp表为了方便初始化，下标是从(1,1)开始的。

所以对于(i,j)位置，该位置礼物的价值是存在(i-1,j-1)中的。

classSolution{public:intdp[201][201]={0};intmaxValue(vector<vector<int>>&grid){// write code hereintm=grid.size();intn=grid[0].size();for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){dp[i][j]=max(dp[i][j-1],dp[i-1][j])+grid[i-1][j-1];}}returndp[m][n];}};

三、对称之美

题目解析

这里，题目给出n个字符串，让第1个字符到第n个字符，每一个字符取出一个字符，这样组成一个新的字符串，让我们判断这个新的字符串是否可能是一个回文字符串；如果也可能输出Yes，否则就输出No。

题目有t组数据，对于每一组数据，我们都要进行判断并输出结果。

算法思路

这道题初看可能有一点思路，但不多；

对于n个字符串，每一个字符串取一个字符组成的新字符串，能否构成回文字符串；（对于回文字符串，我们知道，第1哥和第n个、第2个和第n-1个…这些字符都是相同的）

我们就非常好判断了，定义l和r分别从两边开始遍历字符数组，我们只需要判断l位置字符串和r位置字符串是否存在相同的字符就OK了。

思路：双指针 + 判断两个字符串是否存在相同的字符。

那么现在问题就变成了：如何判断两个字符串存在相同的字符？

那判断两个字符串中是否存在相同的字符，方法就很简单了：使用hash表计数。

首先遍历第一个字符串，将所有出现的字符放到hash表中，让遍历第二个字符串判断是否存在相同的字符即可。

代码实现

#include<iostream>#include<vector>#include<unordered_set>usingnamespacestd;boolfunc(string&str1,string&str2){unordered_set<char>hash;for(inti=0;i<str1.size();i++){hash.insert(str1[i]);}boolb=false;for(inti=0;i<str2.size();i++){if(hash.count(str2[i])){b=true;break;}}returnb;}intmain(){intn;cin>>n;while(n--){intk;cin>>k;vector<string>arr(k);for(inti=0;i<k;i++){cin>>arr[i];}intl=0,r=k-1;//判断两个字符串中是否存在相同的字符boolret=true;while(l<k){if(func(arr[l],arr[r])==false){ret=false;break;}l++;r--;}if(ret)cout<<"Yes"<<endl;elsecout<<"No"<<endl;}return0;}