[ ]包围起来的是需要读取的字符集合
例如：%[abcd]表示只读取字符abcd，遇到其它的字符就读取结束（这句话是重点）\
不匹配某些字符只需要在[ ]内的最前面加一个^就可以了
scanf() 允许把读取到的数据直接丢弃，不往变量中存放，具体方法就是在 % 后面加一个*，例如：
scanf("%*[a-z]");
scanf("%*[a-z]")表示将读取到的小写字母丢弃scanf()的一些用法
“%ns”,n为整数,读入的字符串最长不超过n,然后在末尾补’\0’
%nf 读入的浮点数最多有n位整数,位数多于n,会截断。
“%n[a-z]” 读入最多n个字符,如果遇到非a-z的字符,停止
“%[^=]” 读入任意多的字符,直到遇到"="停止
“%n[^=]” 读入"="号前的至多n 个字符
"*"表示该输入项读入后不赋予任何变量，即跳过该输入值。
比如%[0-9]表示只读入’0’到’9’之间的字符，%[a-zA-Z]表示只读入字母，
'-'是范围连接符，也可以直接列出你需要读入的字符。1、 星球争霸篮球赛 MVP 和力扣 698很像
题解：
#includeusing namespace std;vector bucket;
bool backtrack(vector &nums, int index, int target);int main()
{int t;cin >> t;vector nums;int sum = 0;int tmp;while(cin >> tmp) {sum += tmp;nums.push_back(tmp);if(cin.get() == '\n') {break;}}cout << sum << ' ' << t << endl;//输入的时候计算和或者用函数求和// sum = accumulate(nums.begin(),nums.end());sort(nums.rbegin(), nums.rend());for(int k = t; k > 0; k--) {cout << k << endl;if(sum%k == 0) {bucket.resize(k);int target = sum/k;bool result = backtrack(nums, 0, target);if(result) {cout << target << endl;return 0;}}}return 0;
}bool backtrack(vector &nums, int index, int target) {if(index == nums.size()){return true;}for(int i = 0; i < bucket.size(); i++) {if(bucket[i] + nums[index] > target) {continue;}if(i > 0 && bucket[i] == bucket[i-1]) {continue;}bucket[i] += nums[index];if(backtrack(nums, index+1, target)) {return true;}bucket[i] -= nums[index];}return false;
}2、 开心消消乐 dfs深度搜索
题解：
#includeusing namespace std;int dir[8][2] = {-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1}; // 8个方向 8*vector
void dfs(vector> &nums, int i, int j);int main()
{int n,m;cin >> n >> m;vector> nums;for(int i = 0; i < n; i++) {vector tmp;int temp;for(int j = 0; j < m; j++) {cin >> temp;tmp.push_back(temp);}nums.push_back(tmp);}//vector> visit(n,vector(m,false));int count = 0;for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {if(nums[i][j]) {count++;dfs(nums, i, j);}}}cout << count << endl;return 0;
}void dfs(vector> &nums, int i, int j) {nums[i][j] = 0;for(int k = 0; k < 8; k++) {int nextx = i+dir[k][0];int nexty = j+dir[k][1];if(nextx < 0 || nextx >= nums.size()) {continue;}if(nexty < 0 || nexty >= nums[0].size()) {continue;}if(nums[nextx][nexty] == 0) {continue;}dfs(nums, nextx, nexty);}
}3、 特异性双端队列 、 最小调整顺序次数 、 最小的调整次数 栈、队列
题解：
#includeusing namespace std;int main() {string str;getline(cin, str);int N = stoi(str);int result = 0;bool inorder = true; // 有序int size = 0;for(int i = 0; i < N * 2; i++) {getline(cin, str);istringstream ss(str);ss >> str;if(str == "remove") {if(size == 0) {continue;} else {if(inorder == false) {result++;inorder = true;}size--;}} else {if(str == "head" && size != 0) {inorder = false;}size++;}}cout << result << endl;return 0;
}4、 微服务的集成测试 深度搜索
题解：
#include
#include using namespace std;int countTime(vector > use, int k) {int maxtime = 0;for (int i = 0; i < use.size(); ++i) {if (use[k][i] != 0 && i != k) {maxtime = max(maxtime, countTime(use, i));}}return maxtime + use[k][k];
}int main() {int n, k;cin >> n;vector > use(n, vector(n));for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {cin >> use[i][j];}}cin >> k;int time = countTime(use, k - 1);cout << time << endl;return 0;
}5、 优选核酸检测点 排序 逻辑 分别计算去每个点的花费和做完时间，然后按照要求排序
题解:
#include
#include
#include
using namespace std;struct Point {int id; // 监测点编号int dis; // 距离起点距离int que; // 排队人数int pay; // 支付金额int time; // 到达监测点的时间
};const int add8_10[] = {3, 480, 600}; // 8点到10点之间的监测点参数
const int add12_14[] = {10, 720, 840}; // 12点到14点之间的监测点参数int getTime(int start, Point& point) {int time = 0;// 累加路程时间time += point.dis * 10;// 去除路程中的排队人数 感觉这块有问题需要调整point.que = max(0, point.que - point.dis * 10);// 到监测点的时间int on = start + point.dis * 10;// 8点前到 非核酸时间没有人排队if (on <= add8_10[1]) {return add8_10[1] - start;}// 8点-10点到 8点-到达时间有新增 8点-到达时间有做完的if (on <= add8_10[2]) {point.que += (on - add8_10[1]) * add8_10[0] - (on - add8_10[1]);return time + point.que;}// 10-12点到if (on <= add12_14[1]) {return time + point.que;}// 12-14点到 12点-到达时间有新增 12点-到达时间有做完的if (on <= add12_14[2]) {point.que += (on - add12_14[1]) * add12_14[0] - (on - add12_14[1]);return time + point.que;}// 14点以后return time + point.que;
}void solution(int start, int end, vector& points) {vector res;for (auto& p : points) {if (start + p.time < end) {res.push_back(p);}}sort(res.begin(), res.end(), [](const Point& p1, const Point& p2) {if (p1.time != p2.time) { // 如果到达时间不同，按到达时间升序排列return p1.time < p2.time;} else { // 如果到达时间相同，按支付金额升序排列return p1.pay < p2.pay;}});cout << res.size() << endl; // 输出监测点数量for (auto& p : res) { // 输出每个监测点的编号、到达时间和支付金额cout << p.id << " " << p.time << " " << p.pay << endl;}
}int main() {int start_hour, start_minute, end_hour, end_minute, n;cin >> start_hour >> start_minute >> end_hour >> end_minute >> n;int start = start_hour * 60 + start_minute; // 起点时间int end = end_hour * 60 + end_minute; // 终点时间vector points(n); // 监测点数组for (int i = 0; i < n; i++) {Point point;cin >> point.id >> point.dis >> point.que;point.pay = point.dis * 10; // 支付金额point.time = getTime(start, point); // 到达监测点的时间points[i] = point;}solution(start, end, points); // 求解return 0;
}6、 核算采样的效率 动态规划 多重背包问题
题解：
dp[j]
#include
#include
#include
using namespace std;int main() {int num1,num2;cin >> num1 >> num2;vector v; //效率/10for (int i = 0; i < num1; i++) {int val;cin >> val;v.push_back(val/10);}// 志愿者多几个提升几倍效率，最多4M倍// dp[j]代表几个志愿者对应的提升效率vectordp(num2 + 1, 0);for (int i = 0; i < num1; i++) {for (int j = num2; j > 0; j--) {// 以上为01背包，然后加一个遍历个数for (int k = 1; k <= 4 && j - k >= 0; k++) { // 遍历个数dp[j] = max(dp[j], dp[j - k] + (k+1)* v[i]);}}}// 没有志愿者的时候 效率为80% 之和int sum = 0;for (int i = 0; i < num1; i++) {sum += 8*v[i];}cout << dp[num2] + sum;return 0;
}或者dp[i][j]
#include
#include
#include
using namespace std;int main() {int num1,num2;cin >> num1 >> num2;vector num1Vec;vector num2Vec; //效率/10for (int i = 0; i < num1; i++) {int val;cin >> val;num1Vec.push_back(val);num2Vec.push_back(val/10);}vector> dp(num1+1, vector(num2+1, 0));int count = 0;for(int i = 1; i < num1+1; i++) {for(int j = 1; j < num2+1; j++) {dp[i][j] = max( dp[i-1][j]+num1Vec[i-1]-2*num2Vec[i-1], dp[i-1][j-1]+num1Vec[i-1]); //志愿者大于等于1dp[i][j] = max( dp[i][j], j-2 >= 0 ? dp[i-1][j-2]+num1Vec[i-1]+num2Vec[i-1] : 0); //志愿者大于等于2dp[i][j] = max( dp[i][j], j-3 >= 0 ? dp[i-1][j-3]+num1Vec[i-1]+2*num2Vec[i-1] : 0); //志愿者大于等于3dp[i][j] = max( dp[i][j], j-4 >= 0 ? dp[i-1][j-4]+num1Vec[i-1]+3*num2Vec[i-1] : 0); //志愿者大于等于4（题目强调最多提示3M）}}cout << dp[num1][num2] << endl;return 0;
}7、 最大报酬 工作安排 动态规划
题解：
#include
#include
#include
using namespace std;int main() {int T, n;cin >> T >> n;vector> timePay(n, vector(2));int val1, val2;for(int i = 0; i < n; i++) {cin >> val1 >> val2;timePay[i][0] = val1;timePay[i][1] = val2;}vector dp(T+1,0);for(int i = 0; i < n; i++) {for(int j = T; j >= timePay[i][0]; j--) {dp[j] = max(dp[j], dp[j-timePay[i][0]]+timePay[i][1]);}}cout << dp[T] << endl;return 0;
}或者贪心：
#include using namespace std;int cmp(pair a, pair b) {if(a.second == b.second) {return a.first < b.first;} else {return a.second > b.second;}
}int main() {int T, n;cin >> T >> n;vector> nums(n);for(int i = 0; i < n; i++) {int t, w;cin >> t >> w;nums.push_back(pair{t, w});}sort(nums.begin(), nums.end(), cmp);int res = 0;int timesum = 0;for(int i = 0; i < n; i++) {timesum += nums[i].first;if(timesum <= T) {res += nums[i].second;} else {timesum -= nums[i].first;}}cout << res << endl;return 0;
}8、 预订酒店 abs(value-target)按照要求排序，之选择前k个再按照从小到大排序。
题解：
#include
#include
#include
#include
#include using namespace std;vector split(string str) {vector res;stringstream ss(str);while(getline(ss,str, ' ')) {res.push_back(stoi(str));}return res;
}int x;
bool cmp(int a, int b) {if(abs(a-x)==abs(b-x)) {return a vec=split(str);int n,k;n=vec[0],k=vec[1],x=vec[2];getline(cin,str);vector arr=split(str);sort(arr.begin(),arr.end(),cmp);vector res(arr.begin(),arr.begin()+k);sort(res.begin(),res.end());for(auto val : res) {cout << val << " ";}cout << endl;system("pause");return 0;
}9、 最接近最大输出功率的设备 /查找充电设备组合 寻找充电设备组合 回溯 或者 01背包动态规划
题解：
#include
#include
#include
#include
#include using namespace std;bool result;
void dfs(vector& value, int target, int index) {if(target == 0) {result = true;return;}for(int i = index; i < value.size(); i++) {if(target - value[i] >= 0) {dfs(value, target-value[i], i+1);}}
}int main() {int n, p_max;cin >> n;vector value;for(int i = 0; i < n; i++) {cin >> p_max;value.push_back(p_max);}cin >> p_max;result = false;dfs(value, p_max, 0);if(result) {cout << p_max << endl;} else {cout << '0' << endl;}system("pause");return 0;
}
或者：
#include
#include
#include
#include
#include using namespace std;int main() {int n, p_max;cin >> n;vector value;for(int i = 0; i < n; i++) {cin >> p_max;value.push_back(p_max);}cin >> p_max;vector dp(p_max+1,0);for(int i = 0; i < value.size(); i++) {for(int j = p_max; j >= value[i]; j--) {dp[j] = max(dp[j], dp[j-value[i]] + value[i]);}}if(dp[p_max] == p_max) {cout << p_max << endl;} else {cout << "0" << endl;}system("pause");return 0;
}10、 单词接龙 回溯 广搜
题解： 输入不对
#include
#include
#include
#include
#include
#include
#include
#include using namespace std;int ladderLength(string beginWord, string endWord, vector& wordList) {// 将vector转成unordered_set，提高查询速度unordered_set wordSet(wordList.begin(), wordList.end());// 如果endWord没有在wordSet出现，直接返回0if (wordSet.find(endWord) == wordSet.end()) return 0;// 记录word是否访问过unordered_map visitMap; // // 初始化队列queue que;que.push(beginWord);// 初始化visitMapvisitMap.insert(pair(beginWord, 1));while(!que.empty()) {string word = que.front();que.pop();int path = visitMap[word]; // 这个word的路径长度for (int i = 0; i < word.size(); i++) {string newWord = word; // 用一个新单词替换word，因为每次置换一个字母for (int j = 0 ; j < 26; j++) {newWord[i] = j + 'a';if (newWord == endWord) return path + 1; // 找到了end，返回path+1// wordSet出现了newWord，并且newWord没有被访问过if (wordSet.find(newWord) != wordSet.end()&& visitMap.find(newWord) == visitMap.end()) {// 添加访问信息visitMap.insert(pair(newWord, path + 1));que.push(newWord);}}}}return 0;
}int main() {string beginWord, endWord;getline(cin, beginWord);getline(cin, endWord);string str;vector wordList;while(getline(cin, str)) {wordList.push_back(str);}int result = ladderLength(beginWord, endWord, wordList);cout << result << endl;system("pause");return 0;
}11、 发现新词的数量 /新词挖掘/ 知识图谱 图谱新词挖掘1 滑动窗口
题解：
第一种方法 滑动窗口
#include
using namespace std;
int main() {string c,w;cin >> c >> w;int clen = c.size();int wlen = w.size();int res=0;map mp2;for(int i=0;i mp1;for(int i=0;i
#include using namespace std;int findNewword(string&c, string& w) {int count = 0;for(int i = 0; i <= c.size()-w.size(); i++) {string str = c.substr(i, w.size());sort(str.begin(), str.end());if(str == w)) {count++;}}return count;
}int main() {string c, w;cin >> c >> w;if(c.size() < w.size()) {cout << '0' << endl;return 0;}sort(w.begin(), w.end());int res = findNewword(c,w);cout << res << endl;system("pause");return 0;
}12、 AI 处理器 逻辑处理
题解：
#include using namespace std;vector split(string str) {vector res;stringstream ss(str);while(getline(ss, str, ',')) {res.push_back(stoi(str));}return res;
}int main(){string str;getline(cin, str);int val;cin >> val;vector vec = split(str.substr(1,str.size()-2));int v1 = 0;int v2 = 0;vector vis(8);for(int i = 0; i < vec.size(); i++) {if(vec[i]<4) {v1++;}else{v2++;}vis[vec[i]] = 1;}vector> ans;if (val == 1) {//申请1个处理器int state = 0;//亲和度判断if (v1 == 1 || v2 == 1) state = 1;else if (v1 == 3 || v2 == 3) state = 3;else if (v1 == 2 || v2 == 2) state = 2;else if (v1 == 4 || v2 == 4) state = 4;if (v1 == state) {for (int i = 0; i < 4; i++) {if (vis[i] == 1) {vector tmp;tmp.push_back(i);ans.push_back(tmp);}}}if (v2 == state) {for (int i = 4; i < 8; i++) {if (vis[i] == 1) {vector tmp;tmp.push_back(i);ans.push_back(tmp);}}}} else if (val == 2) {//申请2个处理器int state = 0;if (v1 == 2 || v2 == 2) state = 2;else if (v1 == 4 || v2 == 4) state = 4;else if (v1 == 3 || v2 == 3) state = 3;if (v1 == state) {for (int i = 0; i < 4; i++) {for (int j = i + 1; j < 4; j++) {if (i != j && vis[i] == 1 && vis[j] == 1) {vector tmp;tmp.push_back(i);tmp.push_back(j);ans.push_back(tmp);}}}}if (v2 == state) {for (int i = 4; i < 8; i++) {for (int j = i + 1; j < 8; j++) {if (i != j && vis[i] == 1 && vis[j] == 1) {vector tmp;tmp.push_back(i);tmp.push_back(j);ans.push_back(tmp);}}}}} else if (val == 4) {cout<<"[";//申请4个处理器if (v1 == 4) {cout<<"[0,1,2,3]";}if (v2 == 4) {if(v1 == 4) cout<<",";cout<<"[4,5,6,7]";}cout << "]";} else if (val == 8) {if(vec.size()==8) {cout<<"[0,1,2,3,4,5,6,7]";}else{cout<<"[]";}}cout<<"[";int i=0;for(auto se:ans) {i++;cout<<"[";for(int i=0;i
#include
#include