###### tags: `BiWeekly Contest`
# BiWeekly Contest 104

## [2678. Number of Senior Citizens](https://leetcode.com/problems/number-of-senior-citizens/)(<font color=#00B8A3>Easy</font>)

限制 :

<ul>
<li><code>1 &lt;= details.length &lt;= 100</code></li>
<li><code>details[i].length == 15</code></li>
<li><code>details[i] consists of digits from '0' to '9'.</code></li>
<li><code>details[i][10] is either 'M' or 'F' or 'O'.</code></li>
<li>The phone numbers and seat numbers of the passengers are distinct.</li>
</ul>

### Solution
就看清楚給的字串分別代表什麼，再把要的抓出來判斷
s[11]跟s[12]分別代表年齡的十位數跟個位數
判有沒有大於60就好

#### 時間複雜度: $O(n)$

#### 空間複雜度: $O(1)$

程式碼:

class Solution {
public:
    int countSeniors(vector<string>& details) {
        int ans = 0;
        for(int i = 0; i < details.size(); ++i){
            if(details[i][11] >= '7') ++ans;
            if(details[i][11] == '6' && details[i][12] > '0')   ++ans;
        }
        return ans;
    }
};

## [2679. Sum in a Matrix](https://leetcode.com/problems/sum-in-a-matrix/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 &lt;= nums.length &lt;= 300</code></li>
<li><code>1 &lt;= nums[i].length &lt;= 500</code></li>
<li><code>0 &lt;= nums[i][j] &lt;= 10³</code></li>
</ul>

### Solution
先找出所有row中排序第幾大的值
再從上面的值中找到最大值
加入最後的答案

#### 時間複雜度: $O(n^2 * log(n))$

#### 空間複雜度: $O(1)$

程式碼:

class Solution {
public:
    int matrixSum(vector<vector<int>>& nums) {
        int ans = 0;
        int temp = 0;
        for(auto& i : nums){
            sort(i.begin(), i.end(), greater<int>());
        }
        for(int i = 0; i < nums[0].size(); ++i){
            temp = 0;
            for(int j = 0; j < nums.size(); ++j){
                temp = max(temp, nums[j][i]);
            }
            ans += temp;
        }
        return ans;
    }
};

## [2680. Maximum OR](https://leetcode.com/problems/maximum-or/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 &lt;= nums.length &lt;= 10⁵</code></li>
<li><code>1 &lt;= nums[i] &lt;= 10⁹</code></li>
<li><code>1 &lt;= k &lt;= 15</code></li>
</ul>

### Solution
用陣列來存每個bit總共有多少個1

針對每個數做以下操作 :
1. 從上述陣列中減去現在的這個數
2. 做k次操作後再加回原本的陣列
3. 算出現在的數值是多少並跟現在最大值比較
4. 比完之後再回復到原本的狀態
5. 繼續做下一個數

#### 時間複雜度: $O(n)$

#### 空間複雜度: $O(1)$

程式碼:

class Solution {
public:
    void to_binary_minus(long long n, vector<int>& v){
        int idx = 49;
        while(n){
            if(n % 2) --v[idx];
            n /= 2;
            --idx;
        }
    }
    void to_binary_add(long long n, vector<int>& v){
        int idx = 49;
        while(n){
            if(n % 2) ++v[idx];
            n /= 2;
            --idx;
        }
    }
    long long to_ll(vector<int>& v){
        long long sum = 0;
        for(int i = 0; i < v.size(); ++i){
            sum *= 2;
            if(v[i]) ++sum;
            
        }
        return sum;
    }
    long long maximumOr(vector<int>& nums, int k) {
        vector<int> v(50);
        long long ans = 0;
        long long temp;
        long long res;
        for(int& i : nums){
            to_binary_add(i, v);
        }
            // for(int j = 40; j < v.size(); ++j){
            //     cout << v[j] << " ";
            // }
            // cout << endl;
        for(int& i : nums){
            temp = i;
            to_binary_minus(temp, v);
            temp <<= k;
            to_binary_add(temp, v);
            res = to_ll(v);
            ans = max(res, ans);
            to_binary_minus(temp, v);
            temp >>= k;
            to_binary_add(temp, v);
        }
        return ans;
    }
};

### 補充
bit operation可以**用陣列**來存每個bit的狀況

如果是要and全部的數
就是紀錄每個bit有幾個0
要拿掉一個數就看那個數有哪幾個bit是0
從陣列中減掉
如果陣列中的值是0就代表全部其他值and的值的**那個bit是1**
存0有幾個是因為**只要有一個0，結果就會是0**

反之or則是儲存有幾個1
因為or**只要有一個1，結果就會是1**

## [2681. Power of Heroes](https://leetcode.com/problems/power-of-heroes/)(<font color=#FF375F>Hard</font>)

限制 :

<ul>
<li><code>1 &lt;= nums.length &lt;= 10⁵</code></li>
<li><code>1 &lt;= nums[i] &lt;= 10⁹</code></li>
</ul>

### Solution
參考[這篇](https://leetcode.com/problems/power-of-heroes/solutions/3520215/greedy-cpp-easy-greedy-solution-with-detailed-explanation-o-n-log-n/)
先排序，因為他要的是陣列中的最大值跟最小值，排序完計算最大值與最小值中間有幾種排列組合比較方便

之後再計算陣列中每個**包含此數且最大值為此數**的排列組合有幾個
計算排列組合有幾種可以從前一項來推導

就可以計算出題目要的score

#### 時間複雜度: $O(nlog(n))$

#### 空間複雜度: $O(1)$

程式碼:

class Solution {
public:
    typedef long long ll;
    const int mod = 1e9 + 7;
    int sumOfPower(vector<int>& nums) {
        int n = nums.size();
        ll last2 = 0;
        ll last = 0;
        ll output = 0;
        sort(nums.begin(), nums.end());
        for(int i = 0 ; i < n; i++) {
            ll val = nums[i];
            ll v1 = (val * val) % mod;
            ll v2 = (last + last2 + val) % mod;
            output = (output + ((v1 * v2) % mod)) % mod;
        
            last2 = (((last2 + last) % mod) * 2) % mod;
            last = nums[i];
        }
        return output;
    }
};