NPSC2020決賽

這次 $\text{NPSC}$ 我跟 089487 組隊，在初賽是第二名

初賽的題目不算太難，只是有兩題真的想不出來

A.方陣：把 $X$ 從 $1\sim 9$ 試試看，再看總和有沒有一樣

B.機器人障礙賽：這題真的不行，089487說可以一直繞圈圈，越繞越大，只是沒有成功

C. NPSC：恩

D.好朋友：我男女有幾筆可以，只是男男或女女就不會了

E.旅遊：我沒有看題目，089487說他會，然後就首殺了

F.方陣, Again：看看以對角線對稱的格子然後判斷，如果在對角線上要特別處理，然後要看格子是不是 $1\sim 9$，我們學校有一組沒看到 $1\sim 9$，最後還是有進決賽

決賽在台大比，我是第一個到的，在比賽前有點緊張，一開始先模擬 $30$ 分鐘，有三題，解了兩題，在計分板上是第一名，之後就要比決賽了

總共有 $7$ 題，我們解了四題，有一題首殺

A：NPSC, Again

大意：$\text{NPSC}$ 在 $12$ 月的第一或第二個禮拜六，給你 $12/1$ 是星期幾和在第幾個禮拜六，求日期

解法：

#include<bits/stdc++.h>
using namespace std;
int main() {
    string s[7] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
    string month;
    int n, now;
    cin >> month >> n;
    for (int i = 1; i <= 7; i++)
        if (month == s[i - 1])
            now = i;
    if (n == 1) {
        if (now == 7)
            cout << "7\n";
        else
            cout << 1 + (6 - now) << '\n';
    } else if (n == 2) {
        if (now == 7)
            cout << "14\n";
        else
            cout << 8 + (6 - now) << '\n';
    }
}

B：數迴

大意：有格子跟邊，格子上的數字代表周圍邊的數量，邊要呈一個封閉圈，可以的話輸出整個東西，不行的話輸出 $-1$

解法：我也不知道，出題者說可以從最上面的開始，然後...，反正沒有人解出來

C：最大公因數

大意：給一個正整數 $n$，想分成 $k$ 個正整數的和，問 $gcd$($k$個數字) 最大可以是多少

解法：先找出所有因數，再看小於等於 $n/k$ 且最接近它的數

#include <iostream>
#include <cmath>
#include <vector>
#define int long long
using namespace std;
signed main() {
    int t, n, k;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        int num = n / k;
        vector<int>vec, vec1;
        for (int i = 1, sq = sqrt (n); i <= sq; i++) {
            if (n % i == 0)
                vec.push_back (i), vec1.push_back (n / i);
        }
        for (int i = vec1.size() - 1; i >= 0; i--) {
            if (vec1[i] == vec[vec.size() - 1])
                continue;
            vec.push_back (vec1[i]);
        }
        for (int i = vec.size() - 1; i >= 0; i--) {
            if (vec[i] <= num) {
                cout << vec[i] << '\n';
                break;
            }
        }
    }
}

D：方陣, Again^2

大意：我也不知道，是089487解的

解法：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Size = 2001;
int l[Size][Size];
int sumx[Size];
int sumy[Size];
signed main() {
    int n;
    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> l[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            int k = 0, k2 = 0;
            for (int j = 0; j < n; j++) {
                k += l[i][j];
                k2 += l[j][i];
            }
            sumx[i] = k;
            sumy[i] = k2;
            if (i)
                sumx[i] += sumx[i - 1], sumy[i] += sumy[i - 1];
        }
        int ans = 0;
        for (int i = 1; i < n - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                int a1 = sumx[n - 1] - sumx[i];
                int a2 = sumy[n - 1] - sumy[j];
                if (i)
                    a1 -= sumx[i - 1];
                if (j)
                    a2 -= sumy[j - 1];
                if (a1 == 0 && a2 == 0) {
                    ans++;
                    //	cout<<i<<" "<<j<<"\n";
                }
            }
        }
        cout << ans << "\n";
    }
}

E：翻轉隊伍

大意：有 $k$ 次機會，可將隊伍從位置 $a\times b$ 翻轉，問最多有幾對相鄰且編號不同的人

解法：出題者說可以找規律，或是用數學解，只是我都不會

F：貓咪排隊買早餐

大意：有 $n$ 隻貓咪，分別有不同的編號，問在可以改其中一隻編號的狀況下，最長可以有幾隻連續編號相同

解法：唯一首殺題，我是先用 $\text{vector}$ 存編號跟數量，然後再判斷

#include <iostream>
#include <vector>
#define f first
#define s second
using namespace std;
int main() {
    ios::sync_with_stdio (false);
    cin.tie (0);
    int n, sum = 0, now = -1, in, ans = 0;
    vector<pair<int, int> >vec;
    cin >> n;
    while (n--) {
        cin >> in;
        if (now == -1)
            now = in, sum++;
        else if (in != now)
            vec.push_back ({now, sum}), sum = 1, now = in;
        else
            sum++;
    }
    vec.push_back ({now, sum});
    if (vec.size() == 1) {
        cout << vec[0].s << '\n';
        return 0;
    }
    for (int i = 0; i < vec.size(); i++) {
        if (i != vec.size() - 1) {
            int pp = 0;
            if (vec[i + 1].s > 1 || i == vec.size() - 2)
                pp = vec[i].s + 1;
            else if (vec.size() == 2)
                pp = vec[i].s + 1;
            else if (vec[i + 2].f == vec[i].f)
                pp = vec[i].s + 1 + vec[i + 2].s;
            else
                pp = vec[i].s + 1;
            if (pp > ans)
                ans = pp;
        }
        if (i != 0) {
            int pp = 0;
            if (vec[i - 1].s > 1 || i == 1)
                pp = vec[i].s + 1;
            else if (vec.size() == 2)
                pp = vec[i].s + 1;
            else if (vec[i - 2].f == vec[i].f)
                pp = vec[i].s + 1 + vec[i - 2].s;
            else
                pp = vec[i].s + 1;
            if (pp > ans)
                ans = pp;
        }
    }
    cout << ans << '\n';
}

G：布可的書架

大意：書房高度限制 $L$，書架高度不超過 $L$，有很多分層，假設書架寬度 $w$，每一層只能放 $w$ 本書(最後一層不須放滿)，且當層高度為 $max$(當層第一本書高度$\sim$ 最後一本高度(每本高度 $1\sim 10$))，求最少浪費空間

解法：一開始看不太懂題目，而且範例測資的提示好像有錯，089487原本想用線段樹還是什麼根號算法，後來我是用二分搜，只是都 $\text{TLE}$，出題者說可以用前綴和，原本 $O(n^2)$ 的時間被我們搞到 $O(n^2\times log(n))$。

心得：這次有五組都做四題(第一名太電了)，可謂非常驚險。今年因為疫情，沒有小點心，不過有晚餐餐盒，我吃了頭更痛:)，還是無法突破第二名，但是有一隻手機。升高中我可能連決賽都進不了，所以要好好珍惜現在。我一整年都沒什麼進步，$\text{Zerojudge}$ 還被一個學弟超過(以超驚人的速度)，所以我要有警覺心。恩，就這樣。

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！