前言

身為一個垃圾，當然要打的像垃圾一樣 先是校內爆掉，現在換 div.3 爆掉 。。。pC 沒開 long long 溢位被 hack 成智障的就是我 坐等晚上 rating change 沒意外應該會噴掉啦

先放上所有題目的連結

problem A

題目

大意就是，假設在奇數回合往右走 $a$ 步，偶數回合往左走 $b$ 步 然後請問第 $K$ 回合現在位置在哪（假設起始位置為 $0$ 且向右為正）

解法

阿不就直接暴力就好 算一下會往左次往右幾次，算一下就好

code

// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int main(){
    ios::sync_with_stdio ( false );
    cin.tie ( 0 );
    #define int LL

    int t, k, a, b, swp, ans;
    cin >> t;
    while ( t-- ){
        cin >> a >> b >> k;
        swp = a - b;
        ans = swp * ( LL ) ( k / 2 );
        if ( k & 1 )
            ans += a;
        cout << ans << '\n';
    }
}

problem B

題目

給定一排房屋現在是否有開燈 通常關燈了就是在睡覺了

題目定義會被干擾就是有戶人家已經在睡覺了，但是隔壁兩間房子的人都有開著燈 那麼那戶人家就會被干擾 但是請注意，只有一邊的鄰居開燈並不會被干擾

現在想要讓所有在睡覺的人都不會被干擾 求達成此目標所需要的最小關燈（把原先亮著的燈關掉）數

解法

因為只有一邊有開燈並不會被干擾 也就是說，針對每一個會被干擾的人，把一邊的燈關掉就好了

那麽，我先找出有哪幾戶人家會被干擾，然後把其中一邊的燈關掉 順便特判一下有沒有關一戶燈，兩邊就都不會被打擾的狀況，避免重複計算

code

// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio ( false );
    cin.tie ( 0 );
    cout.tie ( 0 );

    int n, ans = 0, m;
    cin >> n;
    vector < int > data ( n ), lib;
    for ( auto &i: data )
        cin >> i;
    for ( int i = 1 ; i < n - 1 ; i++ ){
        if ( !data[i] && data[i - 1] && data[i + 1] )
            lib.push_back ( i );
    }

    m = lib.size();
    while ( lib.size() > 1 ){
        if ( lib[1] - lib[0] == 2 ){
            ans++;
            lib.erase ( lib.begin() );
            lib.erase ( lib.begin() );
        }
        else{
            ans++;
            lib.erase ( lib.begin() );
        }
    }

    if ( !lib.empty() )
        ans++;
    cout << ans << '\n';
}

problem C

就是這題，我沒有開 long long 然後就被 hack 了 名次噴掉 1500 多名

題目

給定一條長度為 $N$ 的序列 我們假設一個序列是「好的」為以下情況：這個序列的其中一個數字，剛好等於此序列其他元素的和 也就是說，$[ 1, 3, 3, 7 ]$ 這個序列是好的，因為 $7 = 1 + 3 + 3$ 求一共有幾種可能，在移除掉一個元素的情況下，這個序列會是好的 請列出數量，以及些解的位置

因為題目有點難懂，我放上其中一個例子好了 那現在看另外一個序列 $[ 8, 3, 5, 2 ]$

1. 移除掉第一個元素（也就是 $8$ ），這個序列會是好的，因為 $[ 3, 5, 2 ] \to 5 = 3 + 2$
2. 移除掉第四個元素（也就是 $2$ ），這個序列也會是好的，因為 $[ 8, 3, 5 ] \to 8 = 3 + 5$

解法

1. 計算原先序列的總和
2. 每舉所有元素 ( $a[i]$ )，把他從 $sum$ 減掉
3. 把 $sum$ 為奇數則返回步驟2
4. 尋找 $\frac{sum}{2}$ 是否出現於原序列中
5. 檢查 $\frac{sum}{2}$ 是否與 $a[i]$ 相等，如果相等，那麼 $a[i]$ 是否出現於原序列中兩次
6. 如果有出現過兩次，那麼 i 就是其中一個答案
7. 返回步驟 2

有一點可能會覺得有點奇怪，為什麼 $sum - a[i]$ 一定要是偶數 假設 $sum' = sum - a[i]，sum'$ 代表除了 $a[i]$ 以外的元素和 既然一個序列為好的序列，代表說這個序列會被切成兩部分 而這兩部分的和會一樣 既然都會被切成兩個一樣的東西了，為什麼 $sum'$ 會是奇數 這就矛盾了，所以 $sum'$ 一定為偶數

code

// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define int LL

map < int, int > lib;

#undef int

int main(){
    ios::sync_with_stdio ( false );
    cin.tie ( 0 );
    #define int LL

    int n, sum = 0;
    cin >> n;
    vector < int > data ( n ), ans;
    for ( auto &i: data ){
        cin >> i;
        sum += i;
        lib[i]++;
    }
    for ( int i = 0 ; i < n ; i++ ){
        sum -= data[i];
        if ( sum & 1 ){
            sum += data[i];
            continue;
        }
        sum >>= 1;
        if ( ( lib[sum] == 1 && sum != data[i] ) || lib[sum] > 1 ){
            ans.push_back ( i + 1 );
        }
        sum <<= 1;
        sum += data[i];
    }

    cout << ans.size() << '\n';
    for ( auto i: data )
        cout << i << ' ';
    cout << '\n';
}

problem D

題目

給定一大小為 $N$ 的可重複集合 $S$ 求找出一大小為 $K$ 的可重複集合 $S' ( S'\subseteq S )$ 且 $S'$ 在 $S$ 中出現次數最多

元素可重複，這件事情非常重要

解法

我先做離散化，反正數字跟解法沒有關係 接著紀錄每個數字出現幾次 我先二分搜最多那個集合最多可以出現幾次 然後按照次數輸出，反正只要符合要求的都行

code

// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
#define maxN 200005

int cnt[maxN], m, k, ma;
vector < int > lib;
map < int, vector < int > > table;

inline bool check ( int tms ){
    int res = 0;
    for ( int i = tms ; i < ma ; i++ )
        for ( auto j: table[i] )
            res += cnt[j] / tms;

    return res >= k;
}

int main(){
    ios::sync_with_stdio ( false );
    cin.tie ( 0 );

    int n, l = 0, r = -1, mid;
    cin >> n >> k;
    vector < int > data ( n );
    for ( auto &i: data )
        cin >> i;
    if ( n == k ){
        for ( auto i: data )
            cout << i << ' ';
        cout << '\n';
        return 0;
    }
    lib = data;
    sort ( lib.begin(), lib.end() );
    lib.erase ( unique ( lib.begin(), lib.end() ), lib.end() );
    m = lib.size();
    for ( auto i: data ){
        cnt[lower_bound ( lib.begin(), lib.end(), i ) - lib.end()]++;
    }
    for ( int i = 0 ; i < m ; i++ ){
        r = max ( r, cnt[i] );
        table[cnt[i]].push_back ( i );
    }
    ma = ++r;
    mid = ( l + r ) >> 1;
    while ( r - l > 1 ){
        if ( check ( mid ) )
            l = mid;
        else
            r = mid;
        mid = ( l + r ) >> 1;
    }

    l = k;
    for ( int i = 0 ; i < m ; i++ ){
        for ( int j = 0 ; j < min ( cnt[i] / mid, l ) ; j++ )
            cout << lib[i] << ' ';
        l -= min ( cnt[i] / mid, l );
        if ( !l )
            break;
    }
    cout << '\n';
}

problem E

這題我賽中只有想到喇賽解法，賽後才想到正解

題目

給定一些題目，$a_i$ 即代表第 $i$ 題的種類為 $a_i$ 要求每場比賽的的題目種類都要一樣，用過的種類不能再次使用 且每一場需要的題目數量是前一場的兩倍（第一天的題目數量可以任意） 求最多可以使用多少題目 注意！你應該要最大會題目數量，而非天數

解法

每舉第一天的題數，然後暴力往後找 用 lower_bound 去尋找是個不錯的選擇

code

// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
#define maxN 200005

LL cnt[maxN];

int main(){
    ios::sync_with_stdio ( false );
    cin.tie ( 0 );

    int n, m, ma, ans = -1, swp, idx, id;
    cin >> n;
    vector < int > data ( n ), lib;
    for ( auto &i: data )
        cin >> i;
    lib = data;
    sort ( lib.begin(), lib.end() );
    lib.erase ( unique ( lib.begin(), lib.end() ), lib.end() );
    m = lib.size();
    for ( auto i: data )
        cnt[lower_bound ( lib.begin(), lib.end(), i ) - lib.begin()]++;

    data.clear();
    for ( int i = 0 ; i < m ; i++ ){
        data.push_back ( cnt[i] );
    }
    sort ( data.begin(), data.end() );
    ma = data.back() + 1;

    for ( int i = 0 ; i < ma ; i++ ){
        swp = idx = 0;
        for ( int j = i ; j < ma && idx < m ; j <<= 1 ){
            id = lower_bound ( data.begin() + idx, data.end(), j ) - data.begin();
            if ( id < data.size() )
                swp += j;
            idx = id + 1;
        }

        ans = max ( ans, swp );
    }

    cout << ans << '\n';
}

後記

老實說我這場有點慘 pC 被 Hack，pE 賽中沒寫出來 以我的實力來說不應該這樣子的 因為沒開 long long 而炸掉，我現在已經在我的 default code 裡加上 #define int long long 了@@

希望下一場可以好好發揮