1.小易的升级之路
跟着题目一路模拟就行，注意longlong
代码：
#include <iostream> using namespace std; typedef long long LL; LL gcd(LL a,LL b){ return b==0?a:gcd(b,a%b); } int main() { int n; LL x; cin>>n>>x; LL a; for(int i=0;i<n;i++){ cin>>a; if(x>=a){ x+=a; }else{ x=x+gcd(x,a); } } cout<<x<<endl; }
2.礼物的最大价值
代码：
class Solution { public: int maxValue(vector<vector<int> >& grid) { int n=grid.size(); int m=grid[0].size(); vector<vector<int>> dp(n+1,vector<int>(m+1)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ dp[i][j]=max(dp[i-1][j]+grid[i-1][j-1],dp[i][j-1]+grid[i-1][j-1]); } } return dp[n][m]; } };
3.对称之美
想一下我们是怎么判断一个字符串是不是回文字符串的。从两边到中间不断的看是不是相同字符。
同样的，我们也可以从n个字符串中，从两边到中间看，有没有相同的字符。
用双指针l和r分别指向第一个字符串和最后一个字符串。只需要判断这俩字符串有没有相同的元素，如果没有，说明一定不能构成回文串。有则l++,r--继续找相同。直到l>=r结束。
快速判断俩字符串有没有相同元素，可以用位运算。或者用一个map遍历也可以。
代码：
#include <iostream> #include<cstring> using namespace std; const int N=110; int a[N]; int main() { int t; cin>>t; while(t--){ memset(a,0,sizeof a); int n; cin>>n; string str=""; for(int i=0;i<n;i++){ cin>>str; for(int j=0;j<str.size();j++){ int u=str[j]-'a'; a[i]|=(1<<u); } } int l=0,r=n-1; int f=0; while(l<r){ if((a[l]&a[r])!=0){ l++; r--; }else{ f=1; break; } } if(!f){ cout<<"Yes"<<endl; }else cout<<"No"<<endl; } }
