【Luogu】【关卡2-13】线性数据结构（2017年10月）【还差一道题】

任务说明：数组，链表，队列，栈，都是线性结构。巧用这些结构可以做出不少方便的事情。

P1996 约瑟夫问题

n个人，排成环形，喊到m的人出列，输出出列顺序。

咳咳，这个题目不好写，尽管简单就是模拟题...但是orz 乱七八糟加上debug的时间一共花了四十多分钟....

 #include <iostream>

 #include <cstdio>

 #include <vector>

 #include <climits>

 #include <stack>

 #include <string>

 using namespace std;

 const int INF = ;

 int main () {

     int n, m;

     cin >> n >> m;

     vector<int> vec(n+, );

     vec[] = INF;

     int out = , ptr = , number = ;

     while(out < n) {

         if (ptr > n) { ptr = ptr % n; }

         if (number == m) {

             /*

             if (vec[ptr] == INF) {

                 cout << "\nexception \n";

                 printf("ptr[%d]\n", ptr);

                 for (int ele = 0; ele <= n; ++ele) {

                     printf("%5-d", ele);

                 }

                 printf("\n");

                 for (auto ele : vec) {

                     printf("%5-d", ele);

                 }

                 cout << endl;

                 return 0;

             }

             */

             cout << ptr << " " ;

             number = ;

             vec[ptr] = INF;

             ++out;

         } else {

             //printf("=======debug========number[%d], ptr[%d]\n", number, ptr);

             ++ptr;

             if (ptr > n) { ptr = ptr % n; }

             while(vec[ptr] == INF) {

                 ++ptr;

                 if (ptr > n) { ptr = ptr % n; }

             }

             ++number;

         }

     }

     if (out) {

         cout << endl;

     }

     return ;

 }

有空看看题解优化下代码..

P1115 最大子段和

做了这个题才颠覆了我对最大字段和的认识。

以前默认的解法就是用dp[i] 表示 a[0..i] 的和，然后用二重循环相减，求出最大子段和。

提交了发现才过了两个点，剩下的三个点TLE。

然后看了题解才发现原来可以这么做：就是用一个变量来记录读进来数字的当前子段和，如果发现这个变量(当前子段和)比零小，那么就把它置0。因为后面那一坨不论是啥，前面加个负数都不划算，所以这么解最优。

时间复杂度O(N), 空间复杂度O(1)

 #include <iostream>

 #include <cstdio>

 #include <vector>

 #include <climits>

 using namespace std;

 int main () {

     int n;

     cin >> n;

     int ans = INT_MIN, dp = ;

     for (int i = ; i <= n; ++i) {

         int x;

         cin >> x;

         if (i == ) {

             dp = ans = x;

         } else {

             dp = dp + x >  ? dp + x : x;

         }

         ans = max(ans, dp);

     }

     cout << ans << endl;

     return ;

 }

P1739 表达式括号匹配

简单题，不用复习，就是给个字符串，判断左右括号是否匹配。字符串没有空格隔开，直接cin就好。

提交一次AC了。

 #include <iostream>

 #include <cstdio>

 #include <vector>

 #include <climits>

 #include <stack>

 #include <string>

 using namespace std;

 int main () {

     stack<char> stk;

     string str;

     cin >> str;

     for (auto ele : str) {

         if (ele == '@') {

             if (stk.empty()) {

                 cout << "YES" << endl;

             } else {

                 cout << "NO" << endl;

             }

             return ;

         }

         if (ele == '(') {

             stk.push(ele);

         }

         if (ele == ')') {

             if (stk.empty()) {

                 cout << "NO" << endl;

                 return ;

             }

             stk.pop();

         }

     }

     return ;

 }

队列安排

P1449 后缀表达式

后缀表达式求值，用栈做。注意- 和/的时候top出来的两个变量顺序。要是考到，直接用个减法当例子。

提交一次AC了。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <vector>

 #include <climits>

 #include <stack>

 #include <string>

 #include <sstream>

 using namespace std;

 int getNextOper(string& str, int& idx) {

     string strOper;

     for (int i = idx; i < str.size(); ++i) {

         if (str[i] == '.') {

             idx = i + ;

             break;

         }

         if (!isdigit(str[i])) {

             printf("exception\n\n");

             exit(-);

         }

         strOper += str[i];

     }

     stringstream ss(strOper);

     int ans;

     ss >> ans;

     return ans;

 }

 int main () {

     stack<int> stk;

     string str;

     cin >> str;

     int startIdx = ;

     int iOper = getNextOper(str, startIdx);

     stk.push(iOper);

     int answer = ;

     while (str[startIdx] != '@') {

         if (isdigit(str[startIdx])) {

             int iOper = getNextOper(str, startIdx);

             stk.push(iOper);

         } else {

             if (stk.size() < ) {

                 printf("exception \n\n");

             }

             int a = stk.top(); stk.pop();

             int b = stk.top(); stk.pop();

             if (str[startIdx] == '+') {

                 answer = a + b;

             }

             if (str[startIdx] == '-') {

                 answer = b - a;

             }

             if (str[startIdx] == '*') {

                 answer = a * b;

             }

             if (str[startIdx] == '/') {

                 answer = b / a;

             }

             startIdx++;

             stk.push(answer);

         }

     }

     cout << stk.top() << endl;

     return ;

 }

巴特西

【Luogu】【关卡2-13】线性数据结构（2017年10月）【还差一道题】

最新文章

热门文章