Educational Codeforces Round 153 (Rated for Div. 2) C题题解

kurish / 2023-08-21 / 原文

CF Edu 153

C. Game on Permutation

设必胜态指从这一格开始开始行动的某人一定能获胜，必败态同理。

从左到右遍历序列，如果左方有比自己的值的必输态，那么这一格一定可以转移到此必输态，所以这一格一定是必胜态
如果没有比自己的值小的必输态，则
- 比自己值小的均为必胜态。此格必输（需要进行转移并且可转移的对象均能让对手获胜）
- 没有比自己小的值。无法转移，此格即为必胜态。

总结：从左到右遍历序列，不断更新必输态的最小值以及出现元素的最小值即可。O(n)。答案统计必输态的数量。

 1 #include<iostream>
 2 #include<string>
 3 #include<vector>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 
 8 typedef long long ll;
10 typedef pair<int, int> pii;
11 const int INF = 2e9;
14 
15 void solve() {
16     int n;
17     cin >> n;
18     vector<int> p(n);
19     for(int i = 0; i < n; i++){
20         cin >> p[i];
21     }
22 
23     int minv = 1e9;
24     int minlose = 1e9;
25     int ans = 0;
26     for(int i = 0; i < n; i++){
27         if(minlose < p[i] || minv > p[i]){ //必胜态
28         }
29         else{ //必输态
30             ans++;
31             minlose = min(minlose, p[i]);
32         }
33         minv = min(minv, p[i]);
34     }
35 
36     cout << ans << endl;
37 }
38 
39 int main() {
40     std::ios::sync_with_stdio(false);
41     std::cin.tie(0);
42     int t = 1;
43     cin >> t;
44     while (t--) {
45         solve();
46     }
47 
48     return 0;
49 }