大衞的筆記

題目大意

請你將題目給你的數列進行切斷，每一個切斷的數列裡不可以有某兩值相乘是完全平方數，求最小切斷的長度

題目連結

重點觀念

• 了解完全平方數的特性
• 進行優化，不可簡單思考就開始寫入

##　分析
這題很有趣，學了一課。

我們可以知道完全平方數的特性是，每一個質因數的次方都是偶數才有辦法組成完全平方數，那現在只剩下一個問題了，我們怎樣知道哪些數字相乘會等於完全平方數呢？

此時我們可以透過完全平方數反推，只要有一個質因數的次方不是偶數就不會是完全平方數，那麼只要有另外一個數字相乘可以讓所有的質因數次方都變成偶數。

舉例： 18 = 2 * 3 * 3，此時我們的 2 的次方是奇數，那我們只要再補給他 2 就會等於 36 是個完全平方數了！
在進一步想，如果讓 18 * 8 = 144，也是完全平方數， 8 = 2 * 2 * 2，2^3 也是奇數，因此我們只要讓兩個數字相乘後每一個質因數 都是偶數，遇到這樣的情況時就可以切斷。

而我們知道奇數 + 奇數 就是偶數，因此我們只要知道當前片段有幾個質因數是奇數在紀錄就好。

現在還有一個問題要稍微避險下，18 = 2 * 3 * 3, 6 = 2 * 3，這樣是沒有滿足所有的質因數的次方都是偶數，會變成 108 = 2 * 2 * 3 * 3 * 3，因此這樣不算。

如果要讓 6 乘以另一個數字相乘必須是滿足所有的質因數的次方都是偶數，因次需要另外一個 6 來補足就變成了 36 = 2 * 2 * 3 * 3。
這裡我們得知一件事，我們除了計算哪些質因數次方是奇數外，還要讓這些奇數質因數次方相乘。

得出結論

• 把所有數字拆解質因數
• 當數字的所有質因數為奇數次方時，相乘這些奇數次方的質因數(定義 p)
• 保存 p，只要後面的數字也有另外一個 p 時就切斷數列

參考連結

E1. Square-free division (easy version) (数论、思维) by tom_bbv

心得

題目考到我了QQ，不過我認為我學習了蠻多思維，希望這些思維我都能學會並且派上用場。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 200020
using namespace std;
int t, n, k, num[MAXN]; //num 輸入題目數列用
map<int,int> mp; //紀錄每個 p，前面定義過的

int divid(int x){
    int p = 1; //紀錄此數字所有奇數次方的質因數相乘
    for(int i = 2; i*i <= x; i++){ //質因數分解
        int cnt = 0;
        while(x % i == 0){ 
            cnt++; //紀錄總共有幾次的次方
            x /= i; //約分，加速迴圈效率
        }
        if(cnt % 2 != 0) p *= i; //奇數次方的質因數相乘
    }
    return p*x; //這邊還要再乘以 x，因為前面有約分，所以 x 會是最後一個沒有被加入迴圈的質因數，回傳 p
    //x 也可以等於 1，因為 1 是質因數
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        int ans = 0; //紀錄要切幾個線段
        mp.clear(); //先將前面紀錄有哪些 p 先清除，避免干擾
        cin >> n >> k;
        for(int i = 0; i < n; i++){ //輸入題目數列
            cin >> num[i];
            int p = divid(num[i]); //質因數分解，回傳此數字所有奇數次方的質因數相乘
            if(mp.count(p)){ //如果 p 有被記錄表示，這裡會被組成完全平方數
                ans++; //這邊切線段，然後清除之前紀錄的 p
                mp.clear();
            }
            mp[p] = 1; //這次的 p 要被記錄，因為是在另一個線段
        }
        cout << ans+1 << '\n'; //最後的線段不會再被我們切到，因此這邊要 +1，加入最後一個線段
    }


    return 0;
}

題目大意

有 Q 先生與 D 先生兩個人在玩遊戲，給你一組數列，Q 先生只能走遞減(可以向左或向右)、D 先生則是遞增(可以向左或向右)，Q 先走，D 後走，如果 Q 可以贏的話，輸出它有幾種贏法，第一個 x 的 index 算一種。
沒有就輸出零

題目連結

說明

我北科材資系的朋友 陳秉沅，最近剛獲得了一台雷霆 125，找我去跑山，雖然我很懶惰XD，但是我還是跟他一起去了XD。

說明

宣洩文，不懂老媽的心裏在想甚麼，整天只想帶給她自己覺得很棒的價值觀。

筆記說明

此筆記用途在於台北科技大學資訊與財金管理系大二下統計學重點整理
並非所有人都適用，部分對我而言稍加容易的內容並不會寫在此內。
這是觀看影片心得後的筆記，老師上課可能不太適用會忘記抄到

題目大意

這裡有 n 個水杯，每個水杯都有其最大容量與當前裝的水量，你可以透過將 A 杯的水全倒給 B 杯的方式來讓 A 杯水量增加，但過程中水會有 1/2 的輛被灑在地上，也就是說 A 杯只會增加 B 杯一半的水量，而 B 量則會變為零。

我們想知道如果我們只拿 n 杯且可以做倒水的動作時，那這 n 杯的總水量為多少。

題目大意

將給你一個字串 s，以及 k，請你找出一個字串比 s 下一個小的字串並且裡面的同個字母數量都能 mod k == 0 還有產生的字串長度必須等於 s

題目連結

題目大意

你現在在 pub 裡面，明天要程式設計競賽，朋友給你一個問題如果你沒有回答出來，就會要求你喝一杯酒，但你酒量不好，不可以讓自己失敗，幸好朋友給妳時間寫程式，朋友給你的題目如下：

會給你一個數列，之後會給你兩個命令

• C 改變數列中的某個數子
• P 請你查詢某個區間的所有數字相乘是正或負或零。

題目連結

題目大意

在一個海盜島上有許多的海盜，它們都有被編號(從 0 至 n)，且它們都有一個陣營，此海盜島上只有兩個陣營 Buccaneer、Barbary。

現在來了一個大魔法師，他可以將從 0 ~ n 的人變成 Buccaneer or Barbary 陣營的人或是把某區間的人陣營對調，原本是 Buccaneer 變為 Barbary，Barbary 變為 Buccaneer

神知道有這件事情後，非常生氣，他會問大魔法師一個區間內有幾個 Buccaneer 海盜，沒有就殺了他，所以請幫忙解決此問題吧！

題目連結

Segment Tree 線段樹 介紹

線段樹是一種二元樹型態的資料結構，通常用於需要大量查詢區間的問題，空間複雜度是 \(O(n)\)，查詢的時間複雜度則是 \(O(log \ n + k\)，k 為符合條件的區間數量

這種資料結構也能夠擴展到高維度

線段樹 - wiki