第一题 P4702 取石子
题目描述
解题报告
原本以为会使很复杂的题目，比如去思考各自怎么取才能保证最优了，其实这些想法都是不必要的，因为题目已经说，两个人都很聪明，都是采用的最优取法，那么此时，题目的前提是Alice先手，而且最后一定会把石子拿完。
倘若Alice想赢，最后一次必须她来取，也就是石子的总数要是奇数；
因为Bob是第二个拿，倘若想要Bob赢，那么就石子的总数就必须是偶数，在偶数的情况下，Bob拿了石子之后，可以直接再让Alice拿不到石头。
这两个人太坏了
参考代码(C++版本)
#include <bits/stdc++.h> using namespace std; typedef long long LL; int main() { int n; cin >> n; int sum = 0; //统计每一堆石子的个数 for(int i = 0; i < n;i++) { int m; cin >> m; sum += m; } if(sum%2) puts("Alice"); else puts("Bob"); return 0; }
第二题 P5638 【CSGRound2】光骓者的荣耀
题目描述
解题报告
第一次读题可能会感觉像是图的题，但是看到下面的样例演示，应该可以感觉到，其实是让统计某个区间中花费的时间，数据范围是1 0 6 10^610 6，直接暴力是会超时的。求区间和？前缀和算法就可以拿出来了。
参考代码(C++版本)
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e6+10; LL sum[N]; int main() { //前缀和 int n , k; cin >> n >>k; //可以从1号点直达n号点，其间的半径为n-1 if(k >= n-1) cout << 0; //预处理前缀和 for(int i = 1; i < n;i++) { LL x = 0; cin >>x; sum[i] = sum[i-1] + x; } LL ans = sum[n-1];//这个ans记录的是当前最大的前缀和 //再使用传送机k来跳跃，找到最小的 for(int i = k; i < n;i++) ans = min(ans,sum[n-1]-(sum[i]-sum[i-k])); cout << ans; return 0; }
第三题 1441. 用栈操作构建数组
题目描述
解题报告
题目的背景蛮简单的，是相当于给咱一个序列，然后让咱们用栈的出栈和入栈的思想，去实现目标数组的状态。
因为序列和目标数组都是严格升序排列的，那么我们只需要从1开始，逐渐将1到n的数字转移Push进去，倘若在遍历的过程中，遇到目标数组不想要的，就使用Pop弹出。
参考代码(C++版本)
class Solution { public: vector<string> buildArray(vector<int>& target, int n) { //题目意思是给我们一个1~n的数组，然后嘞，咱们用栈的思想去构建模板数组 vector<string> ans; int len = target.size(); //扫一遍,根据情况push 和 pop for(int i = 1,j = 0;i <= n;i++) { //凑成目标数组了 if(j == len) return ans; //遇到数字直接先压进去 ans.push_back("Push"); //倘若不是模板数组中想要的了，再弹出来。 if(i != target[j]) ans.push_back("Pop"); else j++; } return ans; } };
第四题 1021. 删除最外层的括号
题目描述
解题报告
这个题目，难度可能不大，但是读题挺费解的，题目的意思其实是让我们拆出一对()中包含的括号。
倘若使用栈来维护，那么我们需要在统计的一对()之间的内容。
因此，我们在栈为空，并且当前的字符是(的时候，标记该字符的下一个位置，即l = i + 1。
当遇到的字符是)的时候，就以为着出现一对()括号了，此时就得开始清楚这个括号()里的内容了，假如经过pop之后，栈变成空的了，那么就是当前这个()区间的信息统计完成了，标记当前位置，即r = i。
最后使用substr截取出这个区间中字符串信息。
参考代码(C++版本)
class Solution { public: string removeOuterParentheses(string s) { //栈结合双指针来玩 int l = 0,r= 0;//代表截取区间的左指针和右指针 int n = s.size(); stack<char> stk; string ans = ""; for(int i = 0; i < n;i++) { //如果当前遇到的是左括号 if(s[i] == '(') { //而且当前这个栈是空的，标记截取区间的左端点 if(stk.empty()) l = i+1; //否则不标记，常规的入栈 stk.push(s[i]); } //如果当前的栈不是空的，而且当前遇到右括号了，弹出栈顶的东西 if(!stk.empty() && s[i] == ')') stk.pop(); //经过出栈操作之后，栈空 if(stk.empty()) { r = i; //s.substr(pos, n) 截取s中从pos开始（包括0）的n个字符的子串，并返回 ans += s.substr(l,r-l); } } return ans; } };
第五题 1700. 无法吃午餐的学生数量
题目描述
解题报告
本题的逻辑了，仍是常规的模拟吧。
因为三明治只有被取，那么相当于栈的出栈，所以就用栈来维护了。
学生排队取三明治了，有拿到满意的了，顺利出队不再回来，也有暂时拿不到满意的，出队之后又入队，所以可以使用一个队列来维护了。
题目给咱的是两个数组，这就需要咱们把数据取出来分别放到栈和队列中的。至于模拟取三明治的过程了，可以使用学生队列的长度用于循环，当有学生拿到自己满意的了，就将循环变量重置置为0，重新循环。
那么，倘若整个队列循环结束了，仍是匹配不到适合的三明治的时候，就结束循环，返回结果，确实是吃不到了。
参考代码(C++版本)
class Solution { public: int countStudents(vector<int>& students, vector<int>& sandwiches) { //用栈记录三明治，三明治只有出栈 //用队列记录学生，学生有出队和入队 stack<int> stk; queue<int> q; int sand_len = sandwiches.size(); int stu_len = students.size(); //把三明治的信息倒着存入栈中 for(int i = sand_len-1; i >= 0;i--) stk.push(sandwiches[i]); //把学生的信息顺着存到队列中 for(int i = 0; i < stu_len;i++) q.push(students[i]); //把学生作为循环 for(int i = 0; i < q.size();i++) { //如果栈顶和队列首相同，就是代表爱吃，那么就出栈，出队 if(stk.top() == q.front()) { stk.pop(); q.pop(); i = -1;//重置循环为i = 0,进行新的一轮（因为待会会有i++） }else { //如果不相同，就是出队，入队 int tmp = q.front(); q.pop(); q.push(tmp); } } //最后队列的长度，就是是在满足不了的。 return q.size(); } };
第六题 1381. 设计一个支持增量操作的栈
题目描述
解题报告
本质上是用咱们熟悉的数组，手动去模拟栈的实现，算是基础知识了吧，注意细节吧~
参考代码(C++版本)
class CustomStack { public: //这个题，其实就是让咱们数组模拟栈的功能了，基础的数据结构的知识了 vector<int> stk; int top; CustomStack(int maxSize) { //使用vecotr的resize方法改变Vector元素数量的大小 stk.resize(maxSize); top = -1; } void push(int x) { //先要判断当前的栈有没有满，不满才可以操作 if(top != stk.size()-1) { stk[++top] = x; } } int pop() { //还是判断可不可以出栈 if(top == -1) return -1; else return stk[top--]; } void increment(int k, int val) { //栈底的 k 个元素的值都增加 int n = min(k,top+1); for(int i = 0; i < n;i++) stk[i] += val; } }; /** * Your CustomStack object will be instantiated and called as such: * CustomStack* obj = new CustomStack(maxSize); * obj->push(x); * int param_2 = obj->pop(); * obj->increment(k,val); */
总结
① 无论是链表还是栈，其实都是可以使用数组模拟出来的，虽然有了STL大法，但是还是不能忘记可爱的数组
② 今天的简单博弈论了，先浅记录一下，不要去管它们怎么拿，只关心谁先手，谁想赢应该怎么办。
