周赛188
Rank：2546 / 3981 AC：1/4

5404. 用栈操作构建数组

先拿个表标记一下，然后再去遍历这个表，有的话就是Push，没有就算Push Pop

  1. class Solution {
  2. public:
  3.     vector<string> buildArray(vector<int>& target, int n) {
  4.         vector<string> res;
  5.         int pos = 0,f[105],m=0;
  6.         fill(f,f+105,0);
  7.         for(int i=0;i<target.size()&&i<=n;i++){
  8.             f[target[i]]++;
  9.             m = max(m,target[i]);
  10.         }
  11.         for(int i=1;i<=m;i++){
  12.             if(f[i]){
  13.                 res.push_back("Push");
  14.             }
  15.             else {
  16.                 res.push_back("Push");
  17.                 res.push_back("Pop");
  18.             }
  19.         }
  20.         return res;
  21.     }
  22. };

5405. 形成两个异或相等数组的三元组数目

0 <= i < j <= k < arr.length, a==b就意味着a^b==0，所以arr[i]^arr[i+1]^….^a[k]==0,只要两个端点锁定，j就有k-i种可能。一个很简便的思路。

  1. class Solution {
  2. public:
  3.     int countTriplets(vector<int>& arr) {
  4.         int n = arr.size(),res = 0;
  5.         for(int i=0;i<n;i++){
  6.             int t = arr[i];
  7.             for(int j=i+1;j<n;j++){
  8.                 t ^= arr[j];
  9.                 if(t==0){
  10.                     res+= j-i;
  11.                 }
  12.             }
  13.         }
  14.         return res;
  15.     }
  16. };

5406. 收集树上所有苹果的最少时间

BFS思路，如果一条路径上有苹果，那这条路径一定会走过两遍，无论中间节点是否有苹果，只要将中间结点也标记上有苹果，然后利用BFS思路求得的路径一定是最短的，从上到下广度优先搜索，只要结点标记有苹果，就加2。

  1. class Solution {
  2. public:
  3.     int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
  4.         vector<vector<int>> adj(n);
  5.         for(auto& e: edges){
  6.             adj[e[0]].push_back(e[1]);
  7.         }
  8.         while(true){
  9.             int num = 0;
  10.             for(int i=0;i<n;i++){
  11.                 num += hasApple[i]==true;
  12.             }
  13.             for(auto &e:edges){
  14.                 if(hasApple[e[1]]) hasApple[e[0]] = true; 
  15.             }
  16.             for(int i=0;i<n;i++){
  17.                 num -= hasApple[i]==true;
  18.             }
  19.             if(num==0) break;
  20.         }
  21.         queue<int> qu;
  22.         int res = 0;
  23.         qu.push(0);
  24.         while(qu.size()){
  25.             int top = qu.front(); qu.pop();
  26.             for(int i=0;i<adj[top].size();i++){
  27.                 if(hasApple[adj[top][i]]) {
  28.                     res++; qu.push(adj[top][i]);
  29.                 }
  30.             }
  31.         }
  32.         return res*2;
  33.     }
  34. };

5407. 切披萨的方案数

待补…