题解 | #糖糖别胡说,我真的不是签到题目#
糖糖别胡说,我真的不是签到题目
https://ac.nowcoder.com/acm/problem/14583
稍有常识的人都看得出,这里用的到前缀和差分,然后要倒着做,然后粗略的想到了要找前一个比后一个大的,但是因为时间问题,睡觉了,没有总结出上升序列,也没有看到分01两个序列,然后我就卡在倒着做那里了。 然后吐槽一下题目排版(排版全责,输入压成一行,针不戳)
和队友交流了以后,队友完全不能理解我犯得弱智错误,不知道我的问题在哪里(悲)
//我菜死了,浇浇我。
然后总结一下问题吧:
首先,长期缺乏有强度的训练和复习,前缀和差分忘了怎么做了。
其次,做题的时间再晚上,思维运转速度过慢,题目没有完全理解。
还是要多思考,不能养成看题解的坏习惯,这对思维的锻炼是有百害无一利的。
以下是ac代码:
#include <bits/stdc++.h> using namespace std; const int N = 5e4 + 5; long long a[N], b[N]; int main() { int t; cin >> t; while (t--) { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; } for (int i = n; i >= 1; i--) { b[i] -= b[i - 1]; } for (int i = 1; i <= m; i++) { int x; cin >> x; b[1]++; b[x + 1]--; } for (int i = 1; i <= n; i++) { b[i] += b[i - 1]; // cout << a[i] << " " << b[i] << "\n"; } //cout << "\n"; int m0 = 0, m1 = 0, ans = 0; for (int i = n; i >= 1; i--) { if (a[i] == 0) { if (b[i] >= m1) { ans++; } if (b[i] > m0) m0 = b[i]; } else { if (b[i] >= m0) { ans++; } if (b[i] > m1) m1 = b[i]; } } cout << ans << "\n"; } return 0; }