文章目录

• 奇偶排序
• • 问题
  • 题解
• 小艺照镜子
• • 问题
  • 题解
  • 相关题目
  • • 题解
• 交换后的or
• • 问题
  • 题解
• 去除整数（不讲）
• • 题目
  • 题解
• 一些建议
• 参考

奇偶排序

问题

给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数

题解

毕竟简单的方法就是先把奇数输出完，最后把偶数输出完，而不用考虑在数组里进行重组。

#include 
using namespace std;
int main()
{int n;int a[1001];cin >> n;for (int i = 0; i <= n - 1; i++){cin >> a[i];if (a[i] % 2 != 0)cout << a[i] << " "; //先输出奇数}for (int i = 0; i <= n - 1; i++){if (a[i] % 2 == 0)cout << a[i] << " "; //再输出偶数}return 0;
}

小艺照镜子

问题

已知字符串str。 输出字符串str中最长回文串的长度。

相关最长回文子串题目

题解

通过二维数组进行动态规划，dp[i][j]表示从第i个位置到第j个位置的字符串是否回文，若dp[i][j]=1则表示回文，dp[i][j]=0则表示不回文。
而
dp[i][j]是否为1，则是通过dp[i+1][j-1]是否为1来确定的。
当i=j时，表示一个位置的字符，同一个字符当然是相等的，则dp[i][j]=1。
而当i和j相邻时，则判断str[i]是否等于str[j]即可判断dp[i][j]是否为1。

所以转移方程是：
dp[i][j]=dp[i+1][j−1]dp[i][j]=dp[i+1][j-1] dp[i][j]=dp[i+1][j−1]

核心代码：

class Solution {
public:string longestPalindrome(string s) {int n=s.size();vector>dp(n,vector(n,0));int maxx=0;for(int j=0;jfor(int i=0;i<=j;i++){if(s[i]==s[j]){if(j-i==1||i==j){dp[i][j]=1;}elsedp[i][j]=dp[i+1][j-1];}if(dp[i][j]==1&&j-i+1>maxx){maxx=j-i+1;}}}return maxx;}
};

相关题目

题解

class Solution {
public:string longestPalindrome(string s) {int n=s.size();string a(s);vector>dp(n,vector(n,0));int maxx=0;int begin=0;for(int j=0;jfor(int i=0;i<=j;i++){if(s[i]==s[j]){if(j-i==1||i==j){dp[i][j]=1;}elsedp[i][j]=dp[i+1][j-1];}if(dp[i][j]==1&&j-i+1>maxx){maxx=j-i+1;begin=i;}}}// return maxx;return a.substr(begin,maxx);}
};

交换后的or

问题

给定两组长度为n的二进制串，请问有多少种方法在第一个串中交换两个不同位置上的数字，使得这两个二进制串“或”的结果发生改变？

题解

由于交换导致的或关系改变只会涉及交换的4个数（即str1的左边，右边，str2的左边、右边），但str1的左边和str2的左边或关系是一个整体，所以也可以说只会涉及到两个整体。

我们使用二进制就可以表示位于同一个位置的不同串了，如第i个位置的10表示str1[i]=1,str2[i]=0，而一共有4种可能，故我们使用4个单位的数组存放。

具体细节和讲解在注释里讲了。

#include 
#include 
using namespace std;
typedef long long LL;
LL solution(int n, std::string str1, std::string str2){std::vector ctr(4);for(int i = 0; i < n; ++i) {                           //     2  2int msk = (str1[i] == '1') << 1 | (str2[i] == '1');//00  01 10 11  = 0 1 2 3 ++ctr[msk];}LL result = 0;for(int i = 0; i < 4; ++i)for(int j = i + 1; j < 4; ++j) {if((i >> 1) == (j >> 1))//若str1的前一个数(i)和后一个数(j)一样，则无论怎么换位置都不会改变值continue;//>>1表示提取str1的数，&1表示提取str2的数，其余同理(i表示前一个数，j表示后一个数)int d0 = ((i >> 1) | (i & 1)) ^ ((j >> 1) | (i & 1));//表示str1的后一个数(j)能否改变str2的前一个(i)数的或关系，若能改变即右边的数和下面左边的数或关系与改变位置之前的或关系不一样(d0=1)，则表示可以改变int d1 = ((j >> 1) | (j & 1)) ^ ((i >> 1) | (j & 1));//表示str1的前一个数(i)能否改变str2的后一个(j)数的或关系if(d0 || d1)result += (LL)ctr[i] * ctr[j];//ctr[]存放着有多少个类型不同的数，若有交换，则一共有str[i]*str[j]种}return result;
}
int main() {int n;std::string str1;std::string str2;std::cin>>n;std::cin>>str1;std::cin>>str2;LL result = solution(n, str1, str2);std::cout<

int solution(int n, int m, std::vector& vec){typedef long long LL;int result = 0;for(int i = 0; i < (1 << m); ++i) {//1<if((~i >> j) & 1)continue;sgn = -sgn;lcm = lcm / std::__gcd(lcm, (LL)vec[j]) * vec[j];}if(lcm <= n)result += sgn * (n / lcm);}return result;
}