模拟+辗转相除法
思路：
本题的能力值的累加分两种情况，一种是直接相加 bi, 一种是累加当前能力值于 bi 的最大公约数。最大公约数可以通过碾转相除法求得： a 与 b 的最大公约数相当于 b 与 a,b 余数的最大公约数。如果求余结果为 0 ， 则 b 为所 求结果
辗转相除法
int gcd(int a,int b) { int c; while(c=a%b){ a=b; b=c; } return b; }
#include <iostream> #include<vector> using namespace std; int gcd(int a,int b) { int c; while(c=a%b){ a=b; b=c; } return b; } int getpw(int n,int power) { vector<int> num(n); for(int i=0;i<n;i++) cin>>num[i]; for(int i=0;i<n;i++) { if(power>=num[i]) power+=num[i]; else power+=gcd(power,num[i]); } return power; } int main() { int n,a,power; while(cin>>n>>a) { power=getpw(n,a); cout<<power<<endl; } return 0; }
DP作图分析状态方程
思路：
传递公式：
lev[i][j]用来表示字符串a的[1...i]和字符串b[1...j]的levenshtein距离；
插入和删除操作互为逆过程：a删除指定字符变b等同于b插入指定字符变a；
如果a[i] == b[j]，则说明a[i]和b[j]分别加入a，b之后不会影响levenshtein距离，lev[i][j] = lev[i-1][j-1] + 0;
如果a[i] != b[j]，则需要考虑3种情况的可能：
a中插入字符，即lev[i][j] = lev[i-1][j] + 1;
b中插入字符，即lev[i][j] = lev[i][j-1] + 1;
a[i]替换成b[j]，lev[i][j] = lev[i-1][j-1] + 1;
取这4种情况的最小值。
若两个字符相等，即str1[i-1] == str2[j-1]，则在这一个位置的编辑距离和上一个字符相同，因此对应的数组dp[i][j]=dp[i-1][j-1]；
若两个字符不相等，可删除str1[i-1]这个字符，则dp[i][j] = 1 + dp[i-1][j]；删除str2[j-1]这个字符，则dp[i][j] = 1 + dp[i][j-1]；修改str1[i-1]使它与str2[i-1]相等，则dp[i][j] = 1 + dp[i-1][j-1]。
#include <iostream> #include<vector> using namespace std; int mind(const string &s1,const string &s2) { if(s1.empty()||s2.empty()) return max(s1.size(),s2.size()); int len1=s1.size(); int len2=s2.size(); vector<vector<int>> f(len1+1,vector<int>(len2+1,0)); for(int i=0;i<=len1;i++) f[i][0]=i;//初始化距离 for(int j=0;j<=len2;j++) f[0][j]=j;//表示当另一个字符串为空时，该串的距离 for(int i=1;i<=len1;i++) for(int j=1;j<=len2;j++) { // 判断word1的第i个字符是否与word2的第j个字符相等 if(s1[i-1]==s2[j-1]) { //相同，距离不需要增加 f[i][j]=f[i-1][j-1]; } else { int x=1+min(f[i-1][j],f[i][j-1]); //字符不同，需要增删替换，距离+1 f[i][j]=min(x,1+f[i-1][j-1]); } } return f[len1][len2]; } int main() { string s1,s2; while(cin>>s1>>s2) cout<<mind(s1,s2)<<endl; return 0; } // 64 位输出请用 printf("%lld")
找到只出现一次的字符：
时间复杂度O（n^2）
char getFirstOneChar_3(const string& str) { for (int i = 0; i < str.size(); ++i) { int index1 = str.find(str[i]); int index2 = str.rfind(str[i]); if (index1 == index2) return str[i]; } return -1; }
O（n）
//hash法 O(n) char getFirstOneChar_2(const string& str) { int hash[256] = {0}; for (int i = 0; i < str.size(); ++i) //统计字符的次数 hash[str[i]]++; for (int i = 0; i < str.size(); ++i) { if (hash[str[i]] == 1) return str[i]; } return -1; }
