# 2023_NCUMA_CPE_course_midterm

### [考試題目連結](https://ncuma-oj.math.ncu.edu.tw/contest/2/problems)
contest password ： 123
之後會放進一般題目，讓大家補題

## 獎品


## 成績

[2023_NCUMA_CPE_course_midterm ranking](https://hackmd.io/@HIPP0/r1RnGuEM2)

## 出題心得

### 出題
很想要讓題目出得很漂亮，有挑戰性，又不至於解不出來，所以其實耗費了不少功夫，最喜歡的是最後一題，因為最後一題是之前在比賽途中想到的題目XD，覺得很適合二分搜的精神，就拿來出題了。而原本是想要出7題的，但是考慮到只有兩小時，還是索性把最後一題困難拿掉了，並且我是估計大家平均應該是3題左右。

出題總共耗時了兩個禮拜，應該有20小時左右，想題目是只要有時間就會想一下，所以前幾題幾乎在連假前就想好了，出測資才是最麻煩的，可以看到題目裡面有些數量都是五次方六次方再跑，所以需要寫一個程式去出測資，每一題光出測資就花了2個多小時了，題目的敘述也是想的蠻久的XD，想要像ICPC題目一樣，都有個小故事起頭，來襯托出整個題目，雖然大部分看example就可以知道在問什麼。

<!-- 然後沒什麼人來考-.- 我好難過，芋頭也沒考 -->

### 題目考什麼

PA(簡單)，水題，如果不會的話，那...完蛋了

PB(簡單)，為陣列配合迴圈的應用。

PC(簡單)，簡單數學在程式中的應用，能不能把自己想法寫進程式碼中，並且不能用笨方法。

PD(簡單)，把題目用前綴的方式解決問題。

PE(中間)，想辦法把絕對值拿掉(用排序)，並且減少重複運算，從$O(n^2)$優化到$O(n)$

PF(中間)，想到使用二分搜解決問題，並且這題的二分搜不明顯，另外就是要告訴大家之前提到的內建二分搜其實很多時候要自己刻。

CPE難度前3~4題差不多就這幾題的難度，我們的目標就是3題，所以大家如果有想進步的話把這幾題不會的也在看一下。

# 題解

## PA Easy Plus Minus Multiplication

### 題目
給定三個整數，判斷 A 加或減或乘 B = C，輸出 + 或 - 或 *

### 思路
太簡單 所以...略

## PB Alternating Binary String

### 題目
給一由小寫組成的字串，把相同字母變成0 或 1，詢問是否能夠形成010101交錯字串

### 思路
因為不論第一個是0或是1，只要能形成交錯字串兩者都行，所以就從第1個字元，判斷到第n個字元。
第一個字元設為0，然後把後面相同的字元也設成0，並儲存前一個字元

判斷兩件事情：
- 如果當下的字元已經有賦予0 or 1了，判斷跟前一個字元是否一樣，一樣則輸出NO
- 如果當下的字元沒有賦予，則賦予和前一個字元不同的(0/1)，並把後面跟當前字元一樣的也賦予一樣的0/1

:::spoiler <a style = "color:pink"> 程式碼 </a>

void solve() {
    int n;
    cin >> n;
    string a;
    cin >> a;
    
    bool check[2005] = {0};
    bool color[n+1] = {0};
    bool last = -1;
    for (int i = 0 ; i < n ; i++) {
        if (check[a[i]] && last == color[i]) {
            cout << "NO" << '\n';
            return ;
        }
        if (i == 0) {
            check[a[i]] = 1;
            color[i] = 1;
            for (int j = i + 1 ; j < n ; j++) {
                if (a[j] == a[i]) color[j] = color[i] = 1;
            }
        }else{
            check[a[i]] = 1;
            color[i] = !last;
            for (int j = i + 1 ; j < n ; j++) {
                if (a[j] == a[i]) color[j] = color[i];
            }
        }
        last = color[i];
    }
    cout << "YES" << '\n';
    return ;
}

:::

## PC Prime Factors

### 題目

質因數分解，輸出格式：假設 為 $2^3$ * $5^3$ 輸出 2 3 5 3

### 思路

可以注意到題目的大小有到$10^{12}$，記得開long long. 並且不能用O(n)的方式。

一個數字要怎麼質因數分解，就是從2判斷到n-1，除除看可不可以整除n，如果可以就記錄下來，並且把n處以該數字，繼續判斷該數字可不可以除。 要注意，只要判斷到i*i > n的話就不用了，因為該數字必定為質數。同時也可以證明從2~n-1只要可以整除的話，當前的那個數一定是質數。

:::spoiler <a style = "color:pink"> 程式碼(一般判斷) </a>

void solve() {
    long long n;
    cin >> n;
    long long now, times = 0;
    while (n > 1) { // 先判斷2的 因為468這些都不是質數，方便後續從3開始一次加2
        if (n%2==0) {
            n/=2;
            times++;
        }else{
            break;
        }
    }
    
    if (times > 0) { //如果可以整除2，那就輸出到底是 2的幾次方
        cout << 2 << ' ' << times << ' ';
    }
    
    times = 0, now = 3; //記得times歸零
    while (n > 1) { // n=1的話就不用判斷了
        if (now * now > n) { //如果大於的話，代表n是質數
            cout << n << ' ' << 1 << ' ';
            break;
        }
        
        while (n % now == 0) {
            n/=now;
            times++;
        }
        
        if (times > 0) { //如果可以整除now，那就輸出到底是 now的幾次方
            cout << now << ' ' << times << ' ';
            times = 0; //記得times歸零
        }
        now += 2;
    }
    cout << '\n';
    return ;
}

:::

:::spoiler <a style = "color:pink">程式碼(用map存結果)</a>

void solve(){
    map<long long, long long> mp;
    long long n;
    cin >> n;
    while (n > 1) {
        if (n%2 == 0) {
            n/=2;
            mp[2]++;
            continue;
        }
        bool check = true;
        for (int i = 3 ;  i*i <= n ; i+=2) {
            if (n % i == 0) {
                n/=i;
                mp[i]++;
                check = false;
                break;
            }
        }
        if (check) {
            mp[n]++;
            break;
        }
    }
    for (auto it : mp) {
        cout << it.first << " " << it.second <<' ';
    }
    cout << '\n';
}

:::
## PD interval change sum

給一組數據，並且把區間a~b改成k，問總和是否為奇數

### 思路

假設數據為a[n], 令$S_i = a_1 + a_2 + \space ... + a_i$，所以區間a~b的和 = $S_b - S_{a-1}$，去判斷改之前這個區間，跟改之後是否都同為奇偶數，在判斷全部一開始是否為奇數

如果全部和是奇數，那個區間改之前跟改之後，同為(奇)偶數，則改後還是奇數，反之偶數
如果全部和是偶數，那個區間改之前跟改之後，同為(奇)偶數，則改後還是偶數，反之奇數

並且可以不用真的紀錄數據，可以讓數據壓縮，直接看他是奇數還偶數(1 or 0)就好

:::spoiler <a style = "color:pink">程式碼(數據沒有壓縮)</a>

void solve(){
    int n, q;
    cin >> n >> q;
    vector<long long> arr(n+1);
    arr[0] = 0;
    
    long long sum = 0;
    for (int i = 1 ; i <= n ; i++) {
        long long x;
        cin >> x;
        arr[i] = arr[i-1] + x;
        sum += x;
    }
    
    while (q--) {
        long long L, R, K;
        cin >> L >> R >> K;
        if ((long long)(R-L+1)*K % 2 == (arr[R] - arr[L-1]) % 2){
            if (sum % 2 == 1) {
                cout << "YES" << '\n';
            }else{
                cout << "NO" << '\n';
            }
        }else{
            if (sum % 2 == 0) {
                cout << "YES" << '\n';
            }else{
                cout << "NO" << '\n';
            }
        }
    }
}

:::

:::spoiler <a style = "color:pink">程式碼(數據有壓縮版本)</a>

void solve(){
    int n, q;
    cin >> n >> q;
    vector<bool> arr(n+1,0);
    
    bool sum = 0;
    for (int i = 1 ; i <= n ; i++) {
        int x;
        cin >> x;
        arr[i] = (arr[i-1] ^ (x & 1));
        sum ^= (x & 1);
    }
    
    while (q--) {
        int L, R, K;
        cin >> L >> R >> K;
        K = (k&1);
        if ((((R-L+1)&1)&K) == (arr[R] ^ arr[L-1])){
            if (sum) {
                cout << "YES" << '\n';
            }else{
                cout << "NO" << '\n';
            }
        }else{
            if (!sum) {
                cout << "YES" << '\n';
            }else{
                cout << "NO" << '\n';
            }
        }
    }
}

:::

## PE New Card Game

### 題目
給定n組牌，每個牌有m個 $a_1$~$a_m$, $b_1$~$b_m$ 以此類推 n個

求所有兩兩相減(序號要一樣)的絕對值總和
也就是|$a_1$ - $b_1$| + |$a_2 - b_2$| + .... +|$a_m - b_m$|+ |$a_1-c_1$| + ...的值

### 思路

### 序號互調
因為所有序號一樣才能做相減，所以n組牌其實相同序號可以互調，例如
1 5 7
4 2 6
跟
1 2 7
4 5 6
跟
1 2 6
4 5 7
是一樣的意思的

所以我們可以對每個序號做排序(由小到大)

1 2 6
4 5 7

### 每組牌相加
然後可以知道前面一定比較小，所以絕對值拿掉後，假設$S_i$ 為第i組牌之和
總和可以變成$S_2 - S_1$ + $S_3 - S_1$ + ... + $S_3 - S_2$ + $S_4 - S_2$ ...

假設有三組牌，已經對每個序號由小排到大

1 2 3
4 5 6
7 8 9

把每組牌加起來可以換成

6
15
24

總和就是 (24 - 15) + (24 - 6) + (15 - 6)

### 優化算法

我們可以把 $S_{i+1} - S_i$ 記錄下來，也就是紅色的部分


可以知道每段紅色的線的總共會有，後面的個數 * 前面的個數。
這樣算法就會優化到$O(n)$，如果是一個一個算的話，需要$O(n^2)$
注意計算乘的時候，有可能會超過int，所以記得要long long

:::spoiler <a style = "color:pink">程式碼</a>

void solve() {
    long long n, m;
    cin >> n >> m;
    //這邊用二維　int[][]也可以，sort那邊要注意要用 sort(arr[i],arr[i]+n);
    
    vector<vector<long long>> arr(m,vector<long long>(n)); 
    for (int i = 0 ; i < n ; i++) {
         for (int j = 0 ; j < m ; j++){
              cin >> arr[j][i];
         } 
    }
    
    if (n == 1) {
        cout << 0 << '\n';
        return ;
    }
    
    for (int i = 0 ; i < m ; i++) {
        sort(arr[i].begin(),arr[i].end());
    }
    vector<long long> sum(n,0);
    for (int i = 0 ; i < n ; i++) {
        for (int j = 0 ; j < m ; j++) {
            sum[i] += arr[j][i];
        }
    }
    
    long long ans = 0;
    for (long long i = 1; i < n ; i++) {
        ans += (sum[i] - sum[i-1]) * i * (n-i);
    }
    
    cout << ans << '\n';
    return ;
}

:::

## PF Prevent Growth King

### 題目
給你一組數據 a[n] ， 每天所有人會+1，直到有人變成target，就停下來，但是巫師可以阻止其中一個人當天的成長，求幾天後(不含一開始跟最後一天)會有人抵達target

所以假設 初始 -> 第一天 -> 第二天 -> 第三天(有人成為國王) 要輸出2天

### 思路

如果直接暴力的話，肯定會TLE，因為他數字達到$10^{15}$，每天又只加1，所以就算是O(n)也會爆，很明顯要用O(logN)的解法。

轉個念頭，每天巫師只能阻止一個人成長，所以第K天總共可以減少K的量。
所以我們可以假設過了X天，則所有人正常的值應該會是 $a_i$ + X
再來看有多少值超過了target，如果超過的量<K，因為巫師可以減少K的量，所以一定不會有人可以當上國王。


如此一來，我們只要針對X做二分搜，就可以知道X要到多少才會有人當上國王，記得答案要-1，不含最後一天

因為課程需求 暫時先拿掉答案

<!-- :::spoiler <a style = "color:pink">程式碼</a>

bool SUM (long long n, long long tar, long long X, vector<long long> &vec) {
    long long sum = 0;
    for (auto it : vec) {
        if (tar < it + X) sum += it + X - tar;
        if (sum >= X) return 0;
    }
    return 1;
}
 
void solve(){
    long long n, tar;
    cin >> n;
    cin >> tar;
    vector<long long> vec(n);
    int times = 0;
    for (int i = 0 ; i < n; i++) cin >> vec[i];
    long long l = 1, r = 1e16;
    
    while (l < r) {  
        long long mid = (l + r + 1)/2;
        if (SUM(n,tar,mid,vec)) l = mid;
        else r = mid - 1;
    }
    
    long long mid = (l + r)/2;
    cout << mid - 1 << '\n';
    return ;
}

::: -->

###### tags: `演算法`
{%hackmd /@hipp0/Hippotumuxthem %}