03

#include <algorithm> //还看到了dp的做法，dp做法主要是要想出来如何将大问题分解小问题，这道题就是一个二维dp。 //用dp[i][j]表示以i开始，以j结束的字符串是否是回文串。 //当i=j时，dp[i][j] = (s[i] == s[i]) = true; //当j = i +　1 时，dp[i][j] = (s[i] == s[i+1])； //其他，dp[i][j] = (dp[i-1][j+1] && s[i]==s[j]) //动态规划 class Solution { public:     string longestPalindrome(string s) {         int len = s.size();         vector<vector<int> > dp(len+1,vector<int>(len+1,0));         //dp[i][j]代表从i到j-1中是否是回文串，1代表是，0代表不是         //循环的时候i从大到小循环，j从小到大循环         int maxLen = 0;         int start = 0;         int end = 0;         for(int i=len-1;i>=0;i--)         {             for(int j=1;j<=len;j++)             {                 if(i==j-1)                     dp[i][j]=1;                 else if((i+1==j-1)&&(s[i]==s[j-1]))                     dp[i][j]=1;                 else                     dp[i][j]=((dp[i+1][j-1])&&(s[i]==s[j-1]));                   if(dp[i][j]==1)                 {                     if(j-i>maxLen)                     {                         start = i;                         end = j-1;                         maxLen = j-i;                     }                                     }             }         }         return s.substr(start,end-start+1);     } };

#include <string> #include <iostream> using namespace std; //给一个字符串，都是十六进制表示的 //都是十六进制表示的，其中有两个需要转码 //A->12 34 //B->AB CD //7 1 2 3 4 5 A B //9 1 2 3 4 5 12 34 AB CD //第一个数字记录个数，也为十六进制 //十六进制转换函数 string toHex(int num) { //知道商为0为止 string result = ""; while(num) { int temp = num % 16; num = num / 16; string temp_s; if (temp < 10) { temp_s = to_string(temp); } else  { temp_s = (temp - 10) + 'A'; } result = temp_s + result; } return result; } int main() { string num; cin >> num; string str; string result = ""; int number = stoi(num); while (cin >> str) { if (str == "A") { str = "12 34"; number++; } if (str == "B") { str = "AB CD"; number++; } //如果是其他的字符则维持原状 result = result+" "+str; } //接下来要把number这个数字转换为十六进制 string s = toHex(number); result = s + result; cout << result << endl; system("pause"); return 0; }//报文转发啊

//求输入的范围中的质数的个位数相加的和与十位数相加的较小值 #include <iostream> #include <algorithm> using namespace std; //用空间换时间，用一个数组存放一个范围内的质数和合数的情况 int isPrime[1000] = {0}; //prime表示质数 //0表示质数，1表示合数 int main() { //初始化数组 for (int i = 2; i <= 1000; i++) { //从i开始能整除i的都是合数 if (isPrime[i] == 0) { for (int j = i + i; j <= 1000; j += i) { isPrime[j] = 1; } } } int low; int high; int sum1 = 0; int sum2 = 0; //求[low,high]范围内质数和合数的情况 cin >> low >> high; for (int i = low; i <= high; i++) { if (isPrime[i] == 0) { //为质数 sum1 += (i%10); sum2 += (i/10)%10; } } cout << min(sum1,sum2)<<endl; system("pause"); return 0; }

#include <iostream> #include <cmath> #include <algorithm> using namespace std; bool isPrime(int n); int main() { //输入区间 int low; int high; cin >> low >> high; int sum1 = 0; int sum2 = 0; for (int i = low; i <= high; i++) { if (isPrime(i)) { sum1 += i % 10; sum2 += (i / 10) % 10; } } cout<<min(sum1,sum2); system("pause"); } bool isPrime(int n) { if (n == 1) return true; //此函数用来判断n是否是素数 for (int i = 2; i <=sqrt(n); i++) { //如果这个数有公约数，那么一定是一个数小于等于sqrt(i),一个数大于等于sqrt(i); if (n%i == 0) return false; } return true; }

//用数组实现一个栈 #include <vector> #include <iostream> using namespace std; template<typename T> class stacks  { public: stacks();//构造函数 ~stacks();//析构函数 T getTop();//获取栈顶元素 bool pop();//删除栈顶元素 bool push(T number);//添加栈顶元素 bool empty(); int getSize(); private: int size = 0;//栈中元素的个数 int top = -1;//栈顶指针//栈顶下标 vector<T> v; }; //写成员函数的定义 template<typename T>  stacks<T>::stacks() {} template<typename T> stacks<T>::~stacks() {} template<typename T> bool stacks<T>::push(T number) { v.push_back(number); size++; top++; return true; } template<typename T> bool stacks<T>::pop() { if (empty()) { cout << "栈为空，弹出失败" << endl; return false; } v.pop_back(); size--; top--; return true; } template<typename T> T stacks<T>::getTop() { return v[top]; } template<typename T> bool stacks<T>::empty() { if (size == 0) return true; return false; } template<typename T> int stacks<T>::getSize() { return size; } int main() { stacks<int> s; s.push(4); s.push(6); s.push(8); int n = s.getSize(); for (int i = 0; i < n; i++) { cout << s.getTop() << endl; s.pop(); } system("pause"); return 0; }

//实现一个栈 //用数组 #include <iostream> #include <vector> using namespace std; template<typename type> class stack1 { private: vector<type> v;//数组实现栈 int size = 0;//栈的大小 int top = -1; public: stack1(); ~stack1(); bool empty(); type gettop(); void push(type t); bool pop(); int getsize(); }; template<typename type>  stack1<type>::stack1(){} template<typename type> stack1<type>::~stack1(){} template<typename type> type stack1<type>::gettop() { return v[top]; } template<typename type> void stack1<type>::push(type t) { v.push_back(t); size++; top++; } template<typename type> bool stack1<type>::pop() { if (empty()) { cout << "栈为空" << endl; return false; } v.pop_back(); size--; top--; return true; } template <typename type> bool stack1<type>::empty() { if (size == 0) return true; return false; } template<typename type> int stack1<type>::getsize() { return size; } int main() { stack1<int> s; s.push(3); s.push(4); s.push(5); int n = s.getsize(); for (int i = 0; i < n; i++) { int result = s.gettop(); s.pop(); cout << result << " "; } system("pause"); return 0; }

#include <iostream> using namespace std; void BubbleSort(char num[]); int main() { char s[] = "wsnqdhoihohkjbsad"; BubbleSort(s); cout << s << endl; system("pause"); } void BubbleSort(char num[]) { int len = strlen(num); bool NeedSort = true; for (int i = 0; (i < len - 1) && NeedSort; i++) { NeedSort = false; for (int j = len - 1; j > i; j--) { if (num[j] < num[j - 1]) { char temp = num[j]; num[j] = num[j - 1]; num[j - 1] = temp; NeedSort = true; } } } }

#include <iostream> #include <cmath> using namespace std; int main() { //输出100-200之间的素数 //素数只能1和自己整除 //开始考虑优化：减少循环次数 //中间两边不需要重复验证 //偶数不是素数，不需要验证 for (int i = 101; i <= 200; i+=2) { bool flag = true; for (int j = 2; j <= sqrt(i); j++) { if (i%j == 0) { flag = false; break; } } if (flag) cout << i << " "; } system("pause"); return 0; }

//输入5 //输入1 4 3 2 5 //输出6 //把数组通过增加数字变成先递增后递减或者递增或者递减 #include <iostream> #include <algorithm> #include <vector> using namespace std;  int main(){     int n;     cin >> n; vector<int> arr(n); vector<int> dp(n, 0); for(int i=0; i<n; i++) cin >> arr[i]; int pre = arr[0]; for(int i=1; i<n; i++) {        // 把数组从 0 到 i  加成递增需要的数量    dp[i] = dp[i-1] + max(0, pre - arr[i] + 1);  pre = max(pre + 1, arr[i]);   }     int res = dp.back(), cur = 0;     pre = arr.back();    for(int i=n-2; i>=0; i--){   // 重复加 的部分    //比较变成递增和变成递减需要增加的数字哪个小 int repeat = min(dp[i] - (i==0 ? 0 : dp[i-1]) , max(0, pre - arr[i] + 1));   // 把数组从 i 到 n-1 加成递减需要的数量     cur += max(0, pre - arr[i] + 1);   pre = max(pre + 1, arr[i]);        // dp[i] + cur - repeat  这个值为把第 i 个元素变成最大的元素，往左递减，往右递减，需要花费的最小代价     // 算出每一个情况，取最小  res = min(dp[i] + cur - repeat, res);  }   cout << res << endl;    system("pause"); return 0; }

//比赛 //大赛开始了，要求双方较小体重大于或者等于较大的90% //N个人最多进行多少场比赛 //5 //1 1 1 1 1 //输出10 #include <iostream> #include <vector> #include <algorithm> using namespace std; //binary_search(begin,end,val)二分查找搜索val //lower_vound() //upper_bound() //equal_range() //includes() int main() { int number; cin >> number; vector<int> v(number,0); vector<int> v1(number, 0); int j = 0; for (auto i : v) { cin >> i; v1[j++] = i*0.9; } int count = 0; for (int k = 0; k < number; k++) { //当前下标为0，找到的下标为index int index = upper_bound(v1.begin(),v1.end(),v[k])-v1.begin(); if (index - k - 1 > 0) count += index - k - 1; } cout << count << endl; system("pause"); return 0; }

//int转换成char*的函数 #include <iostream> #include <string.h> using namespace std; void intToS(int num, char* str) { char temp[100]; bool isNegative = false; if (num < 0) { isNegative = true; num = -num; } int i = 0; do { temp[i++] = (num % 10)+'0'; num = num / 10; } while (num); //这样能保证至少执行一次 //这样的话0执行一次后变为0 if (isNegative) { temp[i++] = '-'; } temp[i] = '\0'; //将其复制到str字符串中 int j = 0; for (int i = strlen(temp)-1; i >= 0; i--) { str[j++] = temp[i]; } str[j] = '\0'; } int main() { char s[100]; intToS(0,s); cout << s << endl; system("pause"); return 0; }

#include <iostream> #include <vector> #include <limits.h> using namespace std; void f(vector<int>& dp,int n,vector<int> a); int i = 0; int main(){  cin >> i; int num = 0; vector<int> a(i,0); while (num<i) { cin >> a[num]; num++; } vector<int> dp(i,0); vector<int> dp1(i,0); f(dp,i,a); reverse(a.begin(),a.end()); f(dp1,i,a); reverse(dp1.begin(), dp1.end()); reverse(a.begin(), a.end()); int mm = 0; for (int m = 0; m < i; m++) { if (dp[m]+dp1[m]-a[m] > mm) mm = dp[m] + dp1[m] - a[m]; } cout << mm << endl; system("pause");   return 0; } void f(vector<int>& dpp, int n,vector<int> a) { dpp[0] = a[0]; for (int j = 1; j < i; j++) { int max = 0; for (int k = 0; k <j; k++) { if (a[k] < a[j] && dpp[k] > max) { max = dpp[k]; } } dpp[j] = max + a[j]; } }

#include <iostream> #include <limits.h> using namespace std; int dp[100] = {0}; int a[100] = {0}; int main(){     int i = 0;     while ((cin >> a[i++]));       dp[0] = 1;  for (int j = 1; j < i; j++)   {        int max = dp[j];   for (int k = 0; k <j ; k++)     {            if (a[k] < a[j] && dp[k] > max) {         max = dp[k]; }       }   dp[j] = max + 1; }       int mm = 0; for (int m = 0; m < i; m++)  {     if (dp[m] > mm)           mm = dp[m];   }     cout << mm << endl;   system("pause");   return 0; }

#include <iostream> #include <cmath> using namespace std; int main() { int number; cin >> number; if (number < 2) return 0; int front; cin >> front; int after; cin >> after; int temp = after; int min = abs(front-after); //cout << min << endl; number = number - 2; while (number--) { int temp2; cin >> temp2; if (abs(temp2 - temp)< min) { //cout << abs(temp2 - temp) << endl; min = abs(temp2 - temp); front = temp; after = temp2; } temp = temp2; } cout << front <<" "<< after << endl; system("pause"); return 0; }

//旋转字符串，将"I am a student."转换为"student. a am I" #include <string> #include <iostream> using namespace std; string rotateString(string str) { string result = ""; string temp = ""; int len = str.size(); for (int i = 0; i < len; i++) { if (str[i] != ' ') temp += str[i]; else { if (result.size()) { result = temp + " " + result; } else result = temp + result; temp = ""; } } result = temp +" "+result; return result; } int main() { string str = "I am a student."; cout<<rotateString(str); system("pause"); return 0; }

//进行字符串替换 //给定一个字符串，一个替换前的字符串，一个替换后的字符串 //string& replace(size_t pos,size_t len,const string& str); //string& replace(const_iterator it1,const_iterator i2,const string& str); //size_type find(const string& str, size_type index); //strstr(str1,str2); //strstr(str1,str2)用来判断str2是否是str1的子串，如果是，则返回str2在str1中的子串,否则返null //使用c语言，实现字符串子串替换接口 #define _CRT_SECURE_NO_WARNINGS #include <stdlib.h> #include <string.h> #include <stdio.h> #include <cctype> #include <iostream> using namespace std; char* replaceSubstr(const char* str,const char* srcSubstr,const char* dstSubstr,char* out) //实现字符串替换 { //str,srcsubstr,dstsubstr const char* p; int len = 0; char* _out = out; const char* _str = str; const char* _src = srcSubstr; const char* _dst = dstSubstr; int src_size = strlen(_src); int dst_size = strlen(_dst); //strstr用来在字符串中搜索指定的子字符串     //_out用来指向新生成的字符串目前//的位置// //_str用来指向源字符串目前的位置// //_src和_dst用来表示源子串和目标子串// do{ p = strstr(_str, _src); if (p == 0) { strcpy(_out, _str); return out; } len = p - _str; memcpy(_out, _str, len); memcpy(_out + len, _dst, dst_size); _str = p + src_size; _out = _out + len + dst_size; } while (p); return out; } int main() { char str[1024];  char srcSubStr[1024];  char dstSubStr[1024];  char out[1024];   cin.getline(str,1024);   //其次是多个字符/字符串的输入/输出函数对应的声明： //char *fgets(char *s, int size, FILE *stream); char *gets(char *s); //读入字符串，fgets适合取代gets，因为gets无法限制读取字符的个数。gets是直接从标准输入读取。 cin.getline(srcSubStr,1024);  cin.getline(dstSubStr,1024);   replaceSubstr(str, srcSubStr, dstSubStr, out);    printf("%s\n", out);  system("pause"); return 0; }

#include <iostream> #include <limits.h> using namespace std; int dp[100] = {0}; int a[100] = {0}; int main() { int i = 0; while ((cin >> a[i++])); //dp[i]用来存储到i为止的升序序列的最大元素和 //i代表元素个数 dp[0] = a[0]; for (int j = 1; j < i; j++) { //求dp[j]的值 //int max = 0; int max = INT_MIN; for (int k = 0; k < j; k++) { if (a[k] < a[j]) { if (dp[k]>max) max = dp[k]; } } if (max == INT_MIN) dp[j] = a[j]; else dp[j] = max + a[j];  } int mm = dp[0]; for (int m = 1; m < i; m++) { if (dp[m] > mm) mm = dp[m]; } cout << mm << endl; system("pause"); return 0; }

#include <iostream> #include <iomanip> using namespace std; int main() { int n, m; int count = 0; cin >> n >> m; int l = n; while (l--) { int temp; cin >> temp; count += temp; } cout <<fixed<<setprecision(2)<< (double)count / (double)(n - m); system("pause"); return 0; }

//一个等式满足a+b=a|b //给出a,求满足要求的第k个b //创建两个数组，一个把x的各个字符存成数组， //一个把k的各个字符存成数组 //当x的某位置上的数字为0时，y可为0，可为1 //当x=的某位置上的数字为1时，y必须为0 #include <iostream> using namespace std; //创建一个数组posX用来存放x的各个字符 //创建一个数组posK用来存放k的各个字符 int x,k,t; int posX[32], posK[32], posA[32]; int main() { cin >> t;//输入数据的组合数目 while (t--) { //循环输入检测 cin >> x >> k; //将x存入数组 for (int i = 31; i >= 0; i--) { posX[i] = x & 1;  x = x >> 1; } //将k存入数组 for (int i = 31; i >= 0; i--) { posK[i] = k & 1; k = k >> 1; } //生成第k个y int mm = 31; for (int i = 31; i >= 0; i--) { if (posX[i] == 1) posA[i] == 0; else posA[i] = posK[mm--]; } //化成整数 int result = 0; for (int i = 0; i < 32; i++) { result = result << 1; result = posA[i] | result; } cout << result << endl; } system("pause"); return 0; }

//把数字拆开 //一个数字若能被3整出，则它的各个位上的数字相加可以被3整出 //所以题目其实是求，数字的组合，使子串的各位相加可以被3整出 //一个数字，除以3，余数为0，1，2 //所以，可以把字符串直接当作它的余数串 //892213467 //202210101 //1.把0单独领出来，认为可以被3整出 //2.尽量每次分的越少越好 //3.现在只考虑1和2的情况 //111 //222 //1和2交替，一旦出现了既有1又有2，那么可以被3整出 #include <iostream> #include <string> //现在开始循环遍历 using namespace std; int main() { string str; cin >> str; int leng = str.size(); int count = 0;//count用来统计可以整除3的个数 int num = 0;//用来统计当前数字的总和 int c1 = 0; int c2 = 0; //c1和c2分别统计当前余数为1和余数 for(int i=0;i<leng;i++) { //str[i]为字符，str[i]-'0'为数字 int now = str[i] - '0'; if (now % 3 == 0) { count++; c1 = 0; c2 = 0; num = 0; } else if (now % 3 == 1) { num+=str[i]; c1++; } else { num+=str[i]; c2++; } //再次判断能否组合成一个字符串 if ((num > 0 && num % 3 == 0) || (c1&&c2)) { count++; c1 = 0;c2 = 0;num = 0; } } cout << count << endl; system("pause"); return 0; }