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

1.数位染色01背包题目小红拿到了一个正整数 x 。她可以将其中一些数位染成红色。然后她想让所有染红的数位数字之和等于没染色的数位数字之和。她不知道能不能达成目标。你能告诉她吗输入描述一个正整数 x 1≤x≤1e18输出描述如果小红能按要求完成染色输出Yes。否则输出No示例输入 1234567 输出 Yes 说明 将3、4、7染成红色即可这样3471256分析这道题的题目可以翻译成 在一个数组中能否找到一些数的和为总和的一半每个数最多选择一次。由题意很容易想到是一个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 #includestring #includevector using namespace std; string s; int sum0; int n0; bool func() { //target必须是整数 if(sum%21) return false; int targetsum/2; vectorvectorbool dp(n1,vectorbool(target1)); dp[0][0]true; for(int i1;in;i) { for(int j0;jtarget;j) { //没选i dp[i][j]dp[i-1][j]; if(js[i-1]-0) dp[i][j]dp[i][j]||dp[i-1][j-(s[i-1]-0)]; } } return dp[n][target]; } int main() { cins; ns.size(); for(int i0;in;i) sums[i]-0; if(func()) coutYesendl; else coutNoendl; }2.素数回文模拟素数题目现在给出一个素数这个素数满足两点1、 只由1-9组成并且每个数只出现一次如13,23,1289。2、 位数从高到低为递减或递增如245987631。请你判断一下这个素数的回文数是否为素数13的回文数是131,127的回文数是12721。输入描述输入只有1行。第1行输入一个整数t保证t为素数。数据保证9t1e9输出描述输出一行字符串如果t的回文数仍是素数则输出“prime”否则输出noprime。示例输入 13 输出 prime 说明 13的回文数是131131是素数分析这道题就是一个模拟试除法判断素数的题。首先根据题意获得t的回文数具体代码实现过程就是把t当作一个字符串来读取然后从字符串的n-2位置遍历到0位置把遍历到的数字追加到字符串的末尾这样就能得到t的回文数了再把字符串用stol转换成long long类型的数字就可以拿去判断是否是素数了。注意t的最大值是1e9需要用long long来存回文并且要用stol 不要用stoi。代码#include iostream #includestring #includecmath using namespace std; string s; bool isprime(long long num) { if(num2) return false; for(long long i2;isqrt(num);i) if(num%i0) return false; return true; } int main() { cins; string tmp; int ns.size(); for(int in-2;i0;i--) { ss[i]; } long long numstol(s); if(isprime(num)) coutprimeendl; else coutnoprimeendl; }