快速建设网站工具,四川成都广告公司,哈尔滨建站系统报价,查派网站建设#xff08;1#xff09;给出n,k#xff0c;n表示数组个数#xff0c;k表示要剔除的个数#xff0c;接下来n个数为数组元素#xff0c;求剔除k个数之后#xff0c;其他所有数互为倍数#xff0c;每个数最多剔除一次。
未检测代码#xff0c;超时。
#include ios…1给出n,kn表示数组个数k表示要剔除的个数接下来n个数为数组元素求剔除k个数之后其他所有数互为倍数每个数最多剔除一次。
未检测代码超时。
#include iostream
#include vector
#include set
#include string
#include algorithm
using namespace std;setstring strset;
int ans 0;
bool check(vectorint nums, vectorint path) {for (int i 0; i path.size(); i) {nums[path[i]] 0;}sort(nums.begin(), nums.end());bool flag true;for (int i path.size()1; i nums.size(); i) {if (nums[i] % nums[i-1]) {flag false;break;}}if (flag) {for (int i 0; i path.size(); i) {cout path[i] ;}cout endl;}return flag;
}void backtrace(vectorint nums, int start, vectorint path, vectorint vis, int k) {if (path.size() k) {if (check(nums, path)) {string ns ;sort(path.begin(), path.end());for (int ll 0; ll k; ll) {ns to_string(path[ll]);}strset.insert(ns);}return;}if (start nums.size()) return;for (int i start; i nums.size(); i) {// 这里不再需要vis数组因为每次是从i1往后选择不是从头开始选择// 如果每次for循环是从头开始的话需要vis数组进行标记// if (!vis[i]) {// vis[i] 1;path.push_back(i);backtrace(nums, i1, path, vis, k);path.pop_back();// vis[i] 0;// if (path.size() k)backtrace(nums, i1, path, vis, k);// }}
}int main() {int n, k;while (cin n k) { // 注意 while 处理多个 caseint t;vectorint nums(n);for (int i 0; i n; i) {cin t;nums[i] t;}vectorint vis(n);vectorint path;backtrace(nums, 0, path, vis, k);cout strset.size() endl;}return 0;
}
递归执行图如下
如果输入为4 2
1 2 4 6 粉红色表示path.size() k时返回蓝色表示startnums.size()时返回 2输入nmn表示接下来输入n个长度为m的字符串从每个字符串中选一个字符组合为一个字符串求是否存在一个字符串的子序列为“meituan”。
下面是超时的方法没有测试用例。
#include iostream
#include vector
#include string
using namespace std;bool flag false;
void backtrace(vectorstring strs, string s, int depth, int ind) {if (flag) return;if (depth s.size()) {// cout depth endl;flag true;return;}if (strs.size() - ind s.size() - depth) return;for (int i ind; i strs.size(); i) {if (strs[i].find(s[depth]) ! string::npos) {backtrace(strs, s, depth1, i1);}backtrace(strs, s, depth, i1);}
}int main() {int n, m;while (cin n m) { // 注意 while 处理多个 casestring t;vectorstring strs;for (int i 0; i n; i) {cin t;strs.push_back(t);} if (n 7) {cout NO endl;} else {for (int i 0; i n; i) {// 找到m的第一个位置以此位置为起点进行回溯if (strs[i].find(m) ! string::npos) {string s meituan;if (flag) break;backtrace(strs, s, 1, i1);}}if (flag) {cout YES endl;} else {cout NO endl;}}}return 0;
}
