SCIST S5 演算法季中賽公開題解

初階班

p_A 魔法咒語 (magic curse)

命題者：frostray

這題的目標是讀取 N 個字串，並將它們以 "字串1"+"字串2"+"字串3" 的格式輸出。

程式碼說明

if (i > 0) res += "+";

避免第一個字串前面有 +
- 若 i > 0（即非第一個字串），則這個字串的前面加上 +。

res += '\"' + s + '\"';

將字串用雙引號包起來
- s 是當前讀入的字串，而 '\"' 代表雙引號（因為 " 在 C++ 內部需要用 \ 轉義）。
- 例如當 s = "hamster"，這行程式會讓 res += "\"hamster\""，即字串 hamster 會被雙引號包圍。

code















#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    string res = "";
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (i > 0) res += '+';
        res += '\"' + s + '\"';
    }
    cout << res << '\n';
    return 0;
}

p_B 科摩多龍聯賽

命題者：BIR

~~先閱讀題序，然後小心實作即可。~~
掃過棋盤上三行，紀錄在那裏面的己方棋子數量還有總分，紀錄駒台上的總分，最後在紀錄整個棋盤上的己方棋子總分，然後檢查王將位置，小心判斷各種條件。

code
































































































































































#include<iostream>

int main() {
    

    char board[9][9];
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            cin>>board[i][j];
        }
    }
    int mygo[7];
    int urgo[7];
    for(int i=0;i<7;i++)
    {
        cin>>mygo[i];
    }
    for(int i=0;i<7;i++)
    {
        cin>>urgo[i];
    }
    
    int flag1=0;
    int flag2=0;
    int flag3=0;
    
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<9;j++)
        {
            if(board[i][j]=='K')
            {
                flag1=1;
                break;
            }
        }
    }
    
    int num=0;
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<9;j++)
        {
            if(board[i][j]=='R' ||board[i][j]=='B'||board[i][j]=='G'||board[i][j]=='S'||board[i][j]=='N'||board[i][j]=='L'||board[i][j]=='P')
            {
                num++;
            }
        }
    }
    if(num>=10)
    {
        flag2=1;
    }
    
    int score=0;
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<9;j++)
        {
            if(board[i][j]=='R')
            {
                score+=5;
            }
            if(board[i][j]=='B')
            {
                score+=5;
            }
            if(board[i][j]=='G')
            {
                score+=1;
            }
            if(board[i][j]=='S')
            {
                score+=1;
            }
            if(board[i][j]=='N')
            {
                score+=1;
            }
            if(board[i][j]=='L')
            {
                score+=1;
            }
            if(board[i][j]=='P')
            {
                score+=1;
            }
        }
    }
    score+=mygo[0]*5;
    score+=mygo[1]*5;
    score+=mygo[2]*1;
    score+=mygo[3]*1;
    score+=mygo[4]*1;
    score+=mygo[5]*1;
    score+=mygo[6]*1;
    if(score>=24)
    {
        flag3=1;
    }
    
    if(flag1==1 && flag2==1 && flag3==1)
    {
        for(int i=3;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]=='R')
                {
                    score+=5;
                }
                if(board[i][j]=='B')
                {
                    score+=5;
                }
                if(board[i][j]=='G')
                {
                    score+=1;
                }
                if(board[i][j]=='S')
                {
                    score+=1;
                }
                if(board[i][j]=='N')
                {
                    score+=1;
                }
                if(board[i][j]=='L')
                {
                    score+=1;
                }
                if(board[i][j]=='P')
                {
                    score+=1;
                }
            }
        }
        if(score>=31)
        {
            cout<<"WIN";
        }
        else
        {
            cout<<"DRAW";
        }
    }
    else
    {
        cout<<"LOSS";
    }
    
    
    
    
    
    return 0;
}

p_C 我一滴水都沒漏判我輸，有沒有邏輯啊!

命題者：a!!!

用陣列紀錄目前所有桶子的剩餘容量，每個詢問用迴圈從起點一直往右檢查當前水桶有沒有容量可以裝並更新水桶容量，直到水都被裝進水桶裡或是最後一個水桶被檢查完了就結束迴圈

code































#include<iostream>

using namespace std;

int c[200005], w[200005];
int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> c[i];
    int q;
    cin >> q;
    long long sum = 0;
    while(q--){
    	int cur, x;
    	cin >> cur >> x;
    	for(int i = cur; i <= n; i++){
    	    if(w[i] + x > c[i]){
    	        x -= c[i] - w[i];
    	        w[i] = c[i];
    	    }
    	    else{
    	        w[i] += x;
    	        x = 0;
    	        break;
    	    }
        }
        sum += x;
    }
    for(int i = 1; i <= n; i++) cout << w[i] << ' ';
    cout << '\n' << sum << '\n';
}

p_D 霸道乞丐

命題者：BIR

這題有兩種解法，一種是處理浮點數時使用double來保證足夠的精度，另一種是直接把浮點數當作字串處理，如果'.'之前是'1'的話就一定是1.0000，否則把'0.'去掉，題目中保證會把不足的位數補零，剩下的部分用int讀入很方便，然後就可以正常用整數比大小了。

code


































#include<iostream>

int main() {
    int n;
    cin>>n;
    double price;
    double rate;
    double ans;
    double flag=0;
    double min=1000000;
    for(int i=1;i<=n;i++)
    {
        cin>>price>>rate;
        if(min>price*rate)
        {
            ans=i;
            min=price*rate;
            flag=0;
        }
        else if(min == price*rate)
        {
            flag=1;
        }
    }
    if(flag==1)
    {
        cout<<"iwantshampoo";
    }
    else
    {
        cout<<ans;
    }
    return 0;
}

p_E problemlist

命題者：高睿（sakinu）

先用二維陣列與雙重迴圈將每個人做過哪些題目讀進來，再換個順序得出每道題被哪些人做過，並另外紀錄這道題是否有被做過，沒被做過的題目輸出

- 1

即可。

code
































#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 1e3+5;
string names[MAX_N];
int arr[MAX_N][MAX_N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i=0;i<n;i++ ) {
        cin >> names[i];
        for(int j=0;j<m;j++) {
            cin >> arr[i][j];
        }
    }
    for(int i=0;i<m;i++) {
        int cnt = 0;
        for(int j=0;j<n;j++) {
            if(arr[j][i] == 1) {
                if(cnt != 0) cout << " ";
                cout << names[j];
                cnt++;
            }
        }
        if(cnt == 0) {
            cout << "-1";
        }
        cout << "\n";
    }
}

進階班

p_A SCIentiST

命題者：高睿（sakinu）

先分成三種 case：

n < 5：
- 此時答案必然等於 0。
n == 5：
- 觀察到每個位置一定會對應到 "SCIST" 中的一個字母。
- 答案是每個位置能放上相應的大/小寫英文字母的數量的乘積。
n > 5：
- 枚舉五個字母選的所有可能位置組合，如果開五層迴圈複雜度會變
  $n^{5}$ ，所以小心的只枚舉前綴 / 後綴的位置避免 TLE。
- 對於那五個字母的位置，像 n == 5 時一樣算出乘積，並與所有未選中的位置，他們各自能選幾個大/小寫英文字母也做乘積，就會是最後的答案。

code









































































#include<bits/stdc++.h>
using namespace std;

#define int long long

const int MAX_N = 1e5+5, mod = 1e9+7;
int l[MAX_N];
int r[MAX_N];
int cnt[MAX_N];
int n;

int MUL(int x, int y) {
    return x*y%mod;
}

void add(int &x, int y) {
    x += y;
    if(x >= mod) x-=mod;
    if(x < 0) x+=mod;
}

int getlrNum(int pos) {     //得到 pos 這個位置共有幾種英文字母可選
    int ll = l[pos];
    int rr = r[pos];
    if('Z' < ll && rr < 'a') return 0;
    if('Z' < ll && ll < 'a') ll = 'a';
    if('Z' < rr && rr < 'a') rr = 'Z';
    if('a' <= ll) return rr-ll+1;
    if(rr <= 'Z') return rr-ll+1;
    return (rr-ll+1)-('a'-'Z'-1);
}

void solve() {
    string scist = "scist";
    string SCIST = "SCIST";
    cin >> n;
    if(n<5) {
        cout << 0 << "\n";
        return;
    }
    for(int i=0;i<n;i++) cin >> l[i];
    for(int i=0;i<n;i++) cin >> r[i];

    int ans = 0;
    
    for(int pre_len=0;pre_len<=5;pre_len++) {   //前綴的長度
        int nxt_len = 5-pre_len;                //後綴的長度
        vector<int> pos;                //五個字元的位置
        for(int j=0;j<pre_len;j++) pos.push_back(j);
        for(int j=0;j<nxt_len;j++) pos.push_back(n-(nxt_len)+j);
        int num = 1;
        for(int j=0;j<5;j++) {          //五個字元的選法乘積
            int cnt = 0;
            if(l[pos[j]] <= scist[j] && scist[j] <= r[pos[j]]) cnt++;
            if(l[pos[j]] <= SCIST[j] && SCIST[j] <= r[pos[j]]) cnt++;
            num = MUL(num, cnt);
        }
        int ll = pre_len;
        int rr = n-(nxt_len)-1;
        for(int j=ll;j<=rr;j++) {       //其他所有字元的選法乘積
            num = MUL(num, getlrNum(j));
        }
        add(ans, num);
        if(n == 5) break;
    }

    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
}

p_B hanoi

命題者：BIR

這題要注意各種細節~~卑鄙的小手段~~，首先雖然輸送帶轉一格看似需要移動所有輸送帶上的食材一格，但其實也可以想成是操作的人往反方向移動一格，只需要改動表示目前所在位置的一個整數就好了。接著如果使用和初始食材一樣大小的陣列，每次有食材被拿走就把那格改成-1之類的是不行的，因為如果在一連串空格左右被要求不斷來回走動的話，計算一下複雜度會發現超過1e9太多了，會得到TLE，這裡需要善用linked list來記錄目前的食物位置，直接移動指定方向上的下一個食物，接著看到題目直接叫hanoi，可能可以想到要使用stack來實作這些包著漢堡的皮的河內塔們，如果開了跟漢堡數量*食材數量的二維陣列，就會超過容量上限得到MLE，解決以上的所有考點並且小心實作語法即可AC，記得開個IO優化。

上面是出題者原話，這邊幫忙簡化一下：

如果開一個陣列，每次轉動都一直往左/右直到找到存在的食材會 TLE，可以用 linked list 紀錄食材的輸送帶，來達到每次操作都 O(1)
漢堡其實就是河內塔的塔，用 stack 維護即可
記得開 IO 優化

code































































































#include<bits/stdc++.h>

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

    int n; cin >> n;
    int pos=1;
    int linked_list[n+1];
    int left_linked[n+1];
    int right_linked[n+1];
    for(int i=1;i<=n;i++)
    {
        cin>>linked_list[i];
        left_linked[i]=i-1;
        right_linked[i]=i+1;
    }
    left_linked[1]=n;
    right_linked[n]=1;

    int m;cin>>m;
    vector<stack<int>> ham(m+1);

    int q;cin>>q;

    string opr;

    for(int i=0;i<q;i++)
    {
        cin>>opr;
        if(opr=="clockwise")
        {
            pos=left_linked[pos];
        }
        else if(opr=="counterclockwise")
        {
            pos=right_linked[pos];
        }
        else if(opr=="take")
        {
            int num;cin>>num;
            if(ham[num].empty()||linked_list[pos]<=ham[num].top())
            {
                ham[num].push(linked_list[pos]);
                right_linked[left_linked[pos]]=right_linked[pos];
                left_linked[right_linked[pos]]=left_linked[pos];
            }
            else
            {
                cout<<"Oops!";return 0;
            }
        }
        else if(opr=="move")
        {
            int start;cin>>start;
            int end;cin>>end;
            if(ham[start].empty())
            {
                cout<<"test";return 0;
            }
            else if(ham[end].empty())
            {
                ham[end].push(ham[start].top());
                ham[start].pop();

            }
            else if(ham[start].top()<=ham[end].top())
            {
                ham[end].push(ham[start].top());
                ham[start].pop();
            }
            else
            {
                cout<<"Oops!";return 0;
            }
        }
    }

    for(int i=1;i<=m;i++)
    {
        if(ham[i].empty())
        {
            cout<<"-1";
        }
        else
        {
            while(!ham[i].empty())
            {
                cout<<ham[i].top()<<" ";
                ham[i].pop();
            }
        }
        cout<<"\n";
    }
    return 0;
}

p_C 八方來踩

命題者：4yu

tag: 模擬、建表

這題也是純粹照著題目的規則來模擬即可，首先要依照格式讀入 N * M 的二維陣列，可以在過程中順便維護最大最小值以及它們的座標，具體做法跟當初培訓報名表單中的進階班小測驗找極值差不多，只是從一維變成二維而已，然後就是要開始從最高點走到最低點，需要枚舉八個方位，可以利用 2024/11/10 線上週所教的實作技巧：建表，將每個方位的 x、y 變化量先存在陣列裡，再用迴圈去跑，在判斷方位的部分，~~線上週沒來上課的可能會這樣寫~~：

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

子任務 1

輸出測資就能拿 10 分了














#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<vector<int>> grid;
    int m, n;
    cin >> m >> n;
    grid.resize(m, vector<int>(n));
    for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) cin >> grid[i][j];
    if(m == 4) cout << "YES\nDL+D+DL\n";
    else if(m == 5) cout << "NO\n";
    else if(m == 10) cout << "YES\nL+DL+L+DL+DR+D+D+D+DR+UR+R+DR+R+R+UR+U+UL+DL+UL+UL+L\n";
}

子任務 2

N = M = 3，自行寫判斷式枚舉即可

滿分解 AC Code

code























































































#include <bits/stdc++.h>
using namespace std;

// 建表 8 個移動方向
//        0  1   2  3   4  5   6  7
// 順時鐘：上 右上 右 右下 下 左下 左 左上 
const int dx[8] = {-1,-1,0,1,1,1,0,-1};
const int dy[8] = {0,1,1,1,0,-1,-1,-1};
const string ds[8] = {"U","UR","R","DR","D","DL","L","UL"};

vector<vector<int>> grid;
int m, n;
string path;

// 判斷是否在圖尺寸範圍中
bool in_range(int x, int y) { return (0 <= x && x < m && 0 <= y && y < n); }

// 從最高點走到最低點
bool GD(pair<int, int> max_pos, pair<int, int> min_pos)
{
    int x = max_pos.first, y = max_pos.second;

    while (make_pair(x, y) != min_pos) 
    {
        int best_d = -1;
        int min_height = grid[x][y];

        // 遍歷 8 個方向，找到最低的鄰居
        for (int i=0; i<8; ++i) 
        {
            int nx = x + dx[i]; 
            int ny = y + dy[i];
            if (in_range(nx,ny) && grid[nx][ny] < min_height) 
            {
                min_height = grid[nx][ny];
                best_d = i;
                
            }
        }

        // 如果八方都不能走就無法走到最低點
        if (best_d == -1) return false;
        
        path += ds[best_d] + "+";
        x += dx[best_d];
        y += dy[best_d];
    }

    return true;
}

int main()
{
    cin >> m >> n;
    grid.resize(m, vector<int>(n));

    int max_h = -1, min_h = 10001;
    pair<int, int> max_pos, min_pos;

    // 讀入二維圖並記錄最大最小值
    for (int i = 0; i < m; ++i) 
    {
        for (int j = 0; j < n; ++j) 
        {
            cin >> grid[i][j];
            if (grid[i][j] > max_h) 
            {
                max_h = grid[i][j];
                max_pos = {i, j};
            }
            if (grid[i][j] < min_h) 
            {
                min_h = grid[i][j];
                min_pos = {i, j};
            }
        }
    }
    
    bool ans = GD(max_pos, min_pos);
    
    if(ans)
    {
path.pop_back();
cout << "YES\n" << path << "\n";
    }
    else cout << "NO\n";
}

p_D literary-prison

命題者：hamster

觀察到7這個數字已經被刪掉
所以可以將原本數字的10進制變成9進制
然後注意轉成進制後每一位的 7 8 要改成 8 9 (對應7被刪除的情況)就可以了

code





























#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
void solve() {
    ll n;
    cin >> n;
 
    vector<ll> res;
    while (n) {
        res.push_back((n % 9 >= 7) ? (n % 9 + 1) : (n % 9));
        n /= 9;
    }
    for (int i = res.size() - 1; i >= 0; i--) {
        cout << res[i];
    }
    cout << '\n';
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while (t--) {
        solve();
    }    
}

p_E iwantshampoo

命題者：高睿（sakinu）

子題一 (

n, q \leq 1000

)：

可以每次詢問都暴力的枚舉答案，O(nq) 來完成。

子題二 (

n, q \leq 10^{5}

)：

觀察到對於任意詢問，答案都具有單調性（如果我用 x 塊錢買的套餐能滿足，則用 x+1 或更多錢一定也可以）
得出可以使用預處理先將前綴合做好，再使用二分搜得到答案的結論！

字串處理：

這一題的另一個難點，如何更簡單的實作出一些複雜的功能？
參考官解的寫法，例如將讀入的字串 s 自己加上 ','，來保證對於每種食物，他的結尾都會是 ','，來避免需要寫多餘的特判
善用內建的函數，例如 stoi、substr 來減少不必要的實作

code






































































#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5+5;
int arr[MAX_N][26];
int need[26];

void add(int pos) {
    string s;
    cin >> s;
    s = s + ',';
    int lit=0;
    for(int rit=0;rit<s.size();rit++) {
        if(s[rit] == ',') {          //lit~rit 是一種組合
            char type = s[lit++];
            arr[pos][type-'A'] += stoi(s.substr(lit, rit-lit));
            lit = rit+1;
        }
    }
    for(int j=0;j<26;j++)
        arr[pos][j] += arr[pos-1][j];
}

bool ok(int pos) {
    for(int i=0;i<26;i++)
        if(arr[pos][i] < need[i])
            return 0;
    return 1;
}

void query(int n) {
    for(int i=0;i<26;i++)
        need[i] = 0;
    string s;
    cin >> s;
    s = s + ',';
    int lit=0;
    for(int rit=0;rit<(int)s.size();rit++) {
        if(s[rit] == ',') {          //lit~rr 是一種組合
            char type = s[lit++];
            need[type-'A'] = stoi(s.substr(lit, rit-lit));
            lit = rit+1;
        }
    }
    int ll = 1, rr = n+1;
    while(ll!=rr) {
        int mid = (ll+rr)/2;
        if(ok(mid))
            rr = mid;
        else
            ll = mid + 1;
    }
    cout << (ll==n+1?-1:ll) << "\n";
}

void solve() {
    int n,q;
    cin >> n >> q;
    for(int i=1;i<=n;i++) {
        add(i);
    }
    while(q--) {
        query(n);
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
}

p_F problemlist

命題者：高睿（sakinu）

解法：同基礎班 pE

code


#include<基礎班 pE>

SCIST S5 演算法季中賽公開題解

初階班

p_A 魔法咒語 (magic curse)

p_B 科摩多龍聯賽

p_C 我一滴水都沒漏判我輸，有沒有邏輯啊!

p_D 霸道乞丐

p_E problemlist

進階班

p_A SCIentiST

p_B hanoi

p_C 八方來踩

子任務 1

子任務 2

滿分解 AC Code

p_D literary-prison

p_E iwantshampoo

p_F problemlist

Read more

SCIST 美食地圖

SCIST S5 培訓課程 113 學年度實體學員須知

【 SCIST S5 】113 學年度培訓課程資源大全

【 SCIST S5 】113 學年度培訓課程資源大全 封面

【 SCIST S5 】113 學年度培訓課程資源大全封面