每日两道算法题（第四天）（01背包，模拟+素数）

1.数位染色（01背包）

题目：

小红拿到了一个正整数 x 。她可以将其中一些数位染成红色。然后她想让所有染红的数位数字之和等于没染色的数位数字之和。
她不知道能不能达成目标。你能告诉她吗？

输入描述：

一个正整数 x ，1≤x≤1e18

输出描述：

如果小红能按要求完成染色，输出"Yes"。否则输出"No"

示例：

输入： 1234567 输出： Yes 说明： 将3、4、7染成红色即可，这样3+4+7=1+2+5+6

分析：

这道题的题目可以翻译成 在一个数组中能否找到一些数的和为总和的一半（每个数最多选择一次）。

由题意很容易想到是一个01背包的问题，接下来就是分析01背包的五步。

1.状态表示

dp[i][j]：从前i个数中选，能否挑选出一些数的总和为j。

2.状态转移方程

dp[i][j]有两种情况，第一种情况就是不选i位置的数dp[i][j]=dp[i-1][j]（不选i位置的数，如果从前i-1个数中能凑成，那么从前i个数中就也能凑成），第二种情况就是选择i位置的数，此时dp[i][j]=dp[i-1][j-nums[i]]（选i位置的数，如果从前i-1个数中能凑成要凑成的数（j）减去i位置选择的数，那么从前i个数种就也能凑成），两种情况有一种成立即可，所以dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]]，要注意的是j-nums[i]一定要大于等于0。

3.初始化

初始化就是多加一行多加一列，并要把dp[0][0]初始化为true（代表从前0个种凑总和为0，所以是true）。

4.填表顺序

从上往下，从左到右

5.返回值

dp[n][sum/2]

代码：

#include <iostream> #include<string> #include<vector> using namespace std; string s; int sum=0; int n=0; bool func() { //target必须是整数 if(sum%2==1) return false; int target=sum/2; vector<vector<bool>> dp(n+1,vector<bool>(target+1)); dp[0][0]=true; for(int i=1;i<=n;i++) { for(int j=0;j<=target;j++) { //没选i dp[i][j]=dp[i-1][j]; if(j>=s[i-1]-'0') dp[i][j]=dp[i][j]||dp[i-1][j-(s[i-1]-'0')]; } } return dp[n][target]; } int main() { cin>>s; n=s.size(); for(int i=0;i<n;i++) sum+=s[i]-'0'; if(func()) cout<<"Yes"<<endl; else cout<<"No"<<endl; }

2.素数回文（模拟+素数）

题目：

现在给出一个素数，这个素数满足两点：

1、 只由1-9组成，并且每个数只出现一次，如13,23,1289。

2、 位数从高到低为递减或递增，如2459，87631。

请你判断一下，这个素数的回文数是否为素数（13的回文数是131,127的回文数是12721）。

输入描述：

输入只有1行。

第1行输入一个整数t，保证t为素数。

数据保证：9<t<1e9

输出描述：

输出一行字符串，如果t的回文数仍是素数，则输出“prime”，否则输出"noprime"。

示例：

输入： 13 输出： prime 说明： 13的回文数是131，131是素数

分析：

这道题就是一个模拟+试除法判断素数的题。

首先根据题意获得t的回文数，具体代码实现过程就是，把t当作一个字符串来读取，然后从字符串的n-2位置遍历到0位置，把遍历到的数字追加到字符串的末尾，这样就能得到t的回文数了，再把字符串用stol转换成long long类型的数字就可以拿去判断是否是素数了。

注意：t的最大值是1e9，需要用long long来存回文，并且要用stol 不要用stoi。

代码：

#include <iostream> #include<string> #include<cmath> using namespace std; string s; bool isprime(long long num) { if(num<2) return false; for(long long i=2;i<=sqrt(num);i++) if(num%i==0) return false; return true; } int main() { cin>>s; string tmp; int n=s.size(); for(int i=n-2;i>=0;i--) { s+=s[i]; } long long num=stol(s); if(isprime(num)) cout<<"prime"<<endl; else cout<<"noprime"<<endl; }