H题题解简单题按照题目意思判断字符串末尾是否为isallyouneed是的话输出Yes并且打印前半部分不是输出No。代码#includeiostream using namespace std; int main() { string s; cin s; int n s.size(); string t isallyouneed; for (int i n - 12,cnt0; i n; i,cnt) { if (s[i] ! t[cnt]) { cout No; return 0; } } cout Yes\n; for (int i 0; i n - 12; i) { cout s[i]; } return 0; }K题题解根据题目意思n个人坐在一个牌桌上从一号玩家开始每个人依次出牌牌分为四种牌普通牌 没效果禁止牌跳过下家反转牌将出牌顺序进行反转罚抽两张牌下家牌数2并跳过。如果一位玩家手里的牌出完就算出局我们知道出牌的结果让求每个人最后剩下几张牌。思路按照题目意思进行模拟一开始想的是通过取模成环用一个数组记录每个人剩余的牌数用一个变量标记当前的出牌的顺序对于已经出局的人(牌数为0)我们会不断的移动但是由于出局人数始终重复被计算会导致超时。优化使用双向循环链表记录当前牌桌上的人对于当前牌数为0的玩家直接删除该节点不会重复的计算已经出局玩家。写法list自带的STL容器实现双向循环链表每个a[cur]--多需要判断是否为0如果该点为0执行删除节点逻辑保存该点it移动删除该点代码#include iostream #includevector #includelist using namespace std; #define cur *it int n, m; void move(listint::iterator it,listintmyList,int r) { if (r 1) { if (it myList.begin()) { it myList.end(); --it; } else { --it; } } else { if (it myList.end()) { it myList.begin(); } } } int main() { cin n m; vectorint a(n1, 0); for (int i 1; i n; i) cin a[i]; listintlst; for (int i 1; i n; i)lst.push_back(i); auto it lst.begin(); int r 0; listint::iterator tmp lst.begin(); for (int i 0; i m; i) { char op; cin op; if (op C) { if (--a[cur] 0) { tmp it; move(it, lst, r); lst.erase(tmp); } else { move(it, lst, r); } } else if (op S) { if (--a[cur] 0) { tmp it; move(it, lst, r); lst.erase(tmp); } else { move(it, lst, r); } move(it, lst, r); } else if (op R) { r ^ 1; if (--a[cur] 0) { tmp it; move(it, lst, r); lst.erase(tmp); } else { move(it, lst, r); } } else if (op D) { if (--a[cur] 0) { tmp it; move(it, lst, r); lst.erase(tmp); } else { move(it, lst, r); } a[cur] 2; move(it, lst, r); } } for (int i 1; i n; i) { cout a[i] \n; } return 0; }M题题解m个队伍做n道题之后给你一个二维矩阵表示做题情况a[i][j]表示第i个队伍是否通过第j道题0表示不通过1表示通过之后告诉你金银铜的最后一名又告诉你金银铜的最后一名的过题数目让你从这n道题中选出10-13道题让他满足给的排名还有过题数目。思路由于本题n和m的范围很小我选择回溯的方式暴力枚举所有情况对于每一道题就是选和不选最后检查是否方案是否合法状态枚举到第cur道题目已选题数num(辅助状态用于剪枝)状态转移第i道题选与不选终止状态num满足10-13满足check函数。剪枝当前选择题目数量未选数量10或者已选数量13进行剪枝check函数通过回溯我们得到了已选题目我们判断已选题目是否符合题目所说的我们统计每个队伍已选题目它通过的数量之后对其由大到小排序我们检查金银铜最后一名的过题数目是否等于他给的过题数目#includeiostream #includevector #includealgorithm using namespace std; const int N 210; int n, m; int rkg, rks, rkb; int pg, ps, pb; vectorstringscore(N); vectorintselected; bool check() { //统计每个队伍的过题数目并排序之后校验对应位值是否等于规定值 vectorintpassed; for (int i 1; i m; i) { int cnt 0; for (auto x : selected) { if (score[i][x - 1] 1) { cnt; } } passed.push_back(cnt); } sort(passed.begin(), passed.end(), greaterint()); if (pg passed[rkg - 1] ps passed[rks - 1] pb passed[rkb - 1]) { return true; } return false; } //cur:当前枚举的题目编号num已选题目数量 bool dfs(int cur, int num) { //目标状态选择的题目10~13,并且检查通过 if ( num 10 num 13 check()) { return true; } if (cur n) { return false; } //剪枝 if (num (n - cur 1) 10 || num 13)return false; //不选当前题目 if (dfs(cur 1, num)) return true; //选当前题目 selected.push_back(cur); if (dfs(cur 1, num 1))return true; selected.pop_back(); return false; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin n m; for (int i 1; i m; i) { cin score[i]; } cin rkg rks rkb; cin pg ps pb; if (dfs(1, 0)) { cout selected.size() \n; for (auto x : selected) { cout x ; } } else { cout -1; } return 0; }J题题解本题与括号匹配问题有异曲同工之妙初始有个标识符S可以进行两种操作 1 将第pos 个标识符S变成0S1S。 2 将第pos 个标识符S变成1S0S。 最终所有的标识符消失只保留字符串中的01字符。 现在给出01串T问能否生成。思路我们还是像括号匹配问题一样用栈去模拟只有01个数相等才能匹配成功所以我们可以先判断01个数是否相等之后0/1的个数就是操作数他和括号匹配问题不同的就是01能匹配10也能匹配从左向右遍历如果栈为空或者当前元素与栈顶元素相同那么他们都是匹配区间的左端点并且我们根据左端点是0就是1操作0S1S左端点是1就是2操作1S0S并且连续的左端点使用的都是同一个pos否则就是产生了一个01配对或者10配对那么就弹出栈顶元素此时pos需要1.代码#includebits/stdc.h using namespace std; int main() { stackintstk; string s; cin s; int num1 count(s.begin(), s.end(), 1); int num0 count(s.begin(), s.end(), 0); if (num1 ! num0) { cout -1 \n; return 0; } cout num0 \n; int pos 1; for (int i 0; i s.size(); i) { if (stk.empty() || stk.top() s[i]) { stk.push(s[i]); cout pos s[i] - 01 \n; } else { stk.pop(); pos; } } return 0; }D题题解一开始我就局限于数对个数与答案(差值的总和)之间的单调性关系实际上这道题的单调性关系是数对个数和差值之间的单调性关系即更大的差值允许出现更多的数对我们通过二分求得差值的最小值能够使数对个数满足k,一开始使用双指针就是漏求了一些实际上应该是先求所有小于ans的差值的总和(个数可能大于k个)之后再把多余的减去差值最大为ans说明前k个中一定有一个ans否则(反证如果前k个差值ans,那么差值的最小值能够使数对个数k就不是ans了)所以[k1,.....cnt]也就是多出来的一定是ans我们只需要用cnt-k*ans就是多出来的值再用总和一减就行,所有差值小于ans数对的差值的总和的求法还是再双指针过程求解对于当前的r来说a[r],能够与(a[l],a[l1],...a[r-1])构成的数对都满足条件所以就是(a[r]-a[l])(a[r]-a[l1])....(a[r]-a[r-1])也就是(r-1-l1)*a[r]-求和(l,....r-1),之后这个求和可以使用前缀和。代码#includeiostream #includevector #includealgorithm #define int long long using namespace std; int n, k; bool check(int mid, vectorint a) { int l 0, r 0; int cnt 0; for (; l n; l) { //右指针向右移动找到第一个不满足条件的 while (rna[r] - a[l] mid) { r; } //l1~r-1是满足条件的右端点 cnt (r - 1) - (l 1) 1; } return cnt k; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin n k; vectorinta(n); for (auto x : a)cin x; sort(a.begin(), a.end()); int l 0; int r a[n - 1] - a[0]; int ans 0; while (l r) { int mid (l r) / 2; if (check(mid,a)) { r mid - 1; ans mid; } else { l mid 1; } } vectorintpre(n 1, 0); for (int i 1; i n; i) { pre[i] pre[i - 1] a[i - 1]; } //现在已知最小的mid了我们只需要根据此求答案就行了 int l1 0, r1 0; int res 0; int sum 0; int cnt0; for (; l1 n; l1) { //右指针向右移动找到第一个不满足条件的 while (r1 n a[r1] - a[l1] ans) { if (r1 ! l1) { sum - pre[r1] - pre[l1]; sum (r1 - l1) * a[r1]; } r1; } //l1~r-1是满足条件的右端点 cnt (r1- 1) - (l1 1) 1; } res sum - (cnt - k) * ans; cout res; return 0; }