歷屆第2題

2016年3月

矩陣轉換

提示
二維陣列
反向操作

題解
反向操作
翻轉直接做
旋轉時開另一個陣列來存，處理好之後交換

C++範例代碼：

 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int r,c,m;
    while (cin >> r >> c >> m){
        int n = max(r,c);
        vector<vector<int>> arr(n);
        for (int i = 0;i<n;i++)arr[i].resize(n);
        vector<vector<int>> arr2(n);
        for (int i = 0;i<n;i++)arr2[i].resize(n);
        for (int i = 0;i<r;i++){
            for (int j = 0;j<c;j++){
                cin >> arr[i][j];
            }
        }
        vector<int> action(m);
        for (int i = 0;i<m;i++)cin>>action[i];
        reverse(action.begin(),action.end());
        int x = 0;
        for (int a : action){
            if (a){
                for (int i = 0;i<r/2;i++){
                    for (int j = 0;j<c;j++){
                        swap(arr[i][j],arr[r-i-1][j]);
                    }
                }
            }else{
                for (int i = 0;i<r;i++){
                    for (int j = 0;j<c;j++){
                        arr2[c-j-1][i] = arr[i][j];
                    }
                }
                arr.swap(arr2);// 交換陣列
                swap(r,c);// 交換長寬
            }
        }
        cout << r << " " << c << "\n";
        for (int i = 0;i<r;i++){
            for (int j = 0;j<c;j++){
                cout << arr[i][j] << " \n"[j+1==c];
            }
        }
    }
}


Python範例代碼：

2016年10月

最大和

提示

題解
每一群之中最大以外的不重要
在輸入的時候可以直接只保留最大值

C++範例代碼：

 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin >> n >> m;
    vector<int> out;
    int ans = 0;
    while (n--){
        int x = 0;
        for (int z = 0;z<m;z++){
            int i;
            cin >> i;
            x = max(x,i);
        }
        ans += x;
        out.push_back(x);
    }
    vector<int> aaa;
    for (int x : out) if(ans%x==0) aaa.push_back(x);
    cout << ans << "\n";
    if (aaa.empty()){
        cout << "-1\n";
    }else{
        for (int i = 0;i<aaa.size();i++) cout << aaa[i] << " \n"[i+1==aaa.size()];
    }
}


Python範例代碼：

2017年3月

小群體

提示

題解
對每個人判斷有哪些朋友
過程中紀錄有誰被數過

C++範例代碼：

 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0;i<n;i++) cin >> a[i];
    vector<bool> counted(n,false);
    int ans = 0;
    for (int i = 0;i<n;i++){
        if (!counted[i]){
            int j = i;
            while (!counted[j]){
                counted[j] = true;
                j = a[j];
            }
            ans++;
        }
    }
    cout << ans << "\n";
}


Python範例代碼：

2017年10月

交錯字串

提示

題解
數每個連續相同大小寫的子字串有多長，再做處裡

C++範例代碼：

 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int k;
    cin >> k;
    string s;
    cin >> s;
    vector<int> ls;
    int l = 0;
    int cur = -1;
    for (int i = 0;i<s.size();i++){
        int cs = s[i]>='a';
        if (cs == cur){
            l++;
        }else{
            if(l) ls.push_back(l);
            cur = cs;
            l = 1;
        }
    }
    if(l) ls.push_back(l);
    int ans = 0;
    int len = 0;
    for (int l : ls){
        if (l==k || (l>k && len==0)){
            len += k;
            ans = max(len,ans);
        }else if (l>k){
            len += k;
            ans = max(len,ans);
            len = k;
        }else{
            len = 0;
        }
    }
    cout << ans << "\n";
}


Python範例代碼：

2019年6月

機器人的路徑

提示

題解
直接模擬機器人的行動

C++範例代碼：

 
#include <bits/stdc++.h>
using namespace std;
struct pos{
    int x;
    int y;
    pos(){}
    pos(int X, int Y):x(X),y(Y){}
};
pos add(const pos &a, const pos &b){
    return pos(a.x+b.x,a.y+b.y);
}
int n,m;
bool valid(const pos &p){
    return p.x>=0&&p.y>=0&&p.x<n&&p.y<m;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> m;
    pos fs[4] = {pos(0,1),pos(0,-1),pos(1,0),pos(-1,0)};
    vector<vector<int>> arr(n);
    vector<vector<bool>> used(n);
    int sm = 1e8;
    pos cur = pos(0,0);
    for (int i = 0;i<n;i++){
        arr[i].resize(m);
        used[i].assign(m,false);
        for (int j = 0;j<m;j++){
            cin >> arr[i][j];
            if (arr[i][j]<sm){
                sm = arr[i][j];
                cur = pos(i,j);
            }
        }
    }
    int ans = 0;
    while(valid(cur)){
        used[cur.x][cur.y] = true;
        ans += arr[cur.x][cur.y];
        pos to = pos(-1,-1);
        int sm = 1e8;
        for(pos &f : fs){
            pos ed = add(cur,f);
            if (valid(ed) && !used[ed.x][ed.y] && arr[ed.x][ed.y]<sm){
                sm = arr[ed.x][ed.y];
                to = ed;
            }
        }
        cur = to;
    }
    cout << ans << "\n";
}


Python範例代碼：

2020年1月

矩陣總和

提示

題解
窮舉每一個的子矩陣

C++範例代碼：

 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int s,t,n,m,r;
    cin >> s >> t >> n >> m >> r;
    vector<vector<int> > a(s);
    for (int i = 0 ;i<s;i++){
        a[i].resize(t);
        for (int j = 0 ;j<t;j++){
            cin >> a[i][j];
        }
    }
    vector<vector<int> > b(n);
    for (int i = 0 ;i<n;i++){
        b[i].resize(m);
        for (int j = 0 ;j<m;j++){
            cin >> b[i][j];
        }
    }
    int c = 0;
    int ans = -1;
    for (int x = 0 ;x<=n-s;x++){
        for (int y = 0 ;y<=m-t;y++){
            int dif = 0;
            int dlt = 0;
            for (int i = 0 ;i<s;i++){
                for (int j = 0 ;j<t;j++){
                    if (a[i][j]!=b[i+x][j+y]){
                        dif++;
                        dlt+=a[i][j]-b[i+x][j+y];
                    }
                }
            }
            dlt = dlt>0?dlt:-dlt;
            if (dif<=r){
                c++;
                ans = ans<dlt&&ans>=0?ans:dlt;
            }
        }
    }
    cout << c << "\n" << ans << "\n";
}


Python範例代碼：

2020年7月

骰子

提示

題解
紀錄每個骰子面的值
再模擬操作

C++範例代碼：

 
#include<bits/stdc++.h>
using namespace std;
struct dice{
    int u,r,f,l,b,d;// 上右前左後下
    dice():u(1),r(2),f(4),l(5),b(3),d(6){}
    void fo(){
        int t = u;
        u = b;
        b = d;
        d = f;
        f = t;
    }
    void ri(){
        int t = u;
        u = l;
        l = d;
        d = r;
        r = t;
    }
};
int main(){
    int n,m;
    cin >> n >> m;
    vector<dice> di(n);
    while (m--){
        int a,b;
        cin >> a >> b;
        a--;
        if (b==-1){
            di[a].fo();
        }else if(b==-2){
            di[a].ri();
        }else{
            b--;
            dice t = di[a];
            di[a] = di[b];
            di[b] = t;
        }
    }
    for (int i = 0;i<n;i++){
        cout << di[i].u << " \n"[i+1==n];
    }
}


Python範例代碼：

2020年10月

人口遷移

提示

題解
依題敘模擬

C++範例代碼：

 
#include <bits/stdc++.h>
using namespace std;
int r,c,k,m;
vector<vector<int>> a,b;
bool valid(int i,int j){
    if (i<0||j<0||i>=r||j>=c) return false;
    return a[i][j]>=0;
}
int main(){
    cin >> r >> c >> k >> m;
    a.resize(r);
    b.resize(r);
    for (int i = 0;i<r;i++){
        a[i].resize(c);
        b[i].resize(c,0LL);
        for (int j = 0;j<c;j++){
            cin >> a[i][j];
        }
    }
    while (m--){
        for (int i = 0;i<r;i++){
            for (int j = 0;j<c;j++){
                int d = a[i][j]/k;
                if (valid(i+1,j)){
                    b[i][j]-=d;
                    b[i+1][j]+=d;
                }
                if (valid(i-1,j)){
                    b[i][j]-=d;
                    b[i-1][j]+=d;
                }
                if (valid(i,j+1)){
                    b[i][j]-=d;
                    b[i][j+1]+=d;
                }
                if (valid(i,j-1)){
                    b[i][j]-=d;
                    b[i][j-1]+=d;
                }
            }
        }
        for (int i = 0;i<r;i++){
            for (int j = 0;j<c;j++){
                a[i][j]+=b[i][j];
                b[i][j] = 0;
            }
        }
    }
    int bi = 0;
    int s = 1e9;
    for (int i = 0;i<r;i++){
        for (int j = 0;j<c;j++){
            if (valid(i,j)){
                bi = max(a[i][j],bi);
                s = min(s,a[i][j]);
            }
        }
    }
    cout << s << "\n" << bi << "\n";
}


Python範例代碼：

2021年1月

流量

提示

題解
窮舉每一個方案
先求出每對城市之間要傳輸的量
再計價
求出最好的

C++範例代碼：

 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m,k;
    cin >> n >> m >> k;
    vector<vector<int>> q(n);
    for (int i = 0;i<n;i++){
        q[i].resize(m);
        for (int j = 0;j<m;j++){
            cin >> q[i][j];
        }
    }
    int ans = 1e9;
    while (k--){
        int cost = 0;
        vector<vector<int>> f(m);
        for (int j = 0;j<m;j++) f[j].resize(m,0);
        for (int i = 0;i<n;i++){
            int c;
            cin >> c;
            for (int j = 0;j<m;j++) f[c][j]+=q[i][j];
        }
        for (int i = 0;i<m;i++){
            for (int j = 0;j<m;j++){
                if (i==j) cost+=f[i][j];
                else cost+=f[i][j]*3-max(f[i][j]-1000,0);
            }
        }
        ans = min(ans,cost);
    }
    cout << ans << "\n";
}


Python範例代碼：

2021年9月

魔王迷宮

提示

題解
依題敘模擬
注意每一回合的操作順序

  1. 魔王放炸彈
  2. 魔王移動
  3. 確認魔王是否活著(檢查出界、炸彈)
  4. 消除被踩到的炸彈


C++範例代碼：

 
#include <bits/stdc++.h>
using namespace std;
int n,m,k;
bool inside(int px, int py){
    return px>=0 && py >= 0 && px < n && py < m;
}
int main(){
    cin >> n >> m >> k;
    vector<int> x(k);
    vector<int> y(k);
    vector<int> s(k);
    vector<int> t(k);
    vector<bool> alive(k);
    vector<vector<int>> bomb(k);
    for(int i = 0; i<n;i++){
        vector<int> line(m);
        for(int j = 0; j<m;j++){
            line[j] = 0;
        }
        bomb[i] = line;
    }
    for(int i = 0; i<k;i++){
        cin >> x[i] >> y[i] >> s[i] >> t[i];
        alive[i] = true;
    }
    int alivecount = k;
    vector<pair<int,int>> exp;
    while (alivecount>0){
        for(int i = 0; i<k;i++){
            if (alive[i]){
                bomb[x[i]][y[i]]++;
            }
        }
        for(int i = 0; i<k;i++){
            if (alive[i]){
                x[i] += s[i];
                y[i] += t[i];
            }
        }
        for(int i = 0; i<k;i++){
            if (alive[i]){
                if (inside(x[i],y[i])){
                    if (bomb[x[i]][y[i]]>0){
                        alivecount--;
                        alive[i] = false;
                        exp.push_back(make_pair(x[i],y[i]));
                    }
                }else{
                    alivecount--;
                    alive[i] = false;
                }
            }
        }
        for (int i = 0;i<exp.size();i++){
            auto pos = exp[i];
            int a = pos.first;
            int b = pos.second;
            bomb[a][b] = 0;
        }
        exp.clear();
    }
    int ans = 0;
    for(int i = 0; i<n;i++){
        for(int j = 0; j<m;j++){
            if (bomb[i][j]>0) ans++;
        }
    }
    cout << ans << "\n";
}


Python範例代碼：

2021年11月

動線安排

提示
二維陣列

題解
用二維陣列記錄每一格的狀態
直接暴力算每一次放置的變化
有5種狀態

  1. 空
  2. 橫線
  3. 直線
  4. 十字線
  5. 木樁

雖然2和3可以合併，但那樣不好寫，不建議合併
要注意細節

放置的時候要由
該方向是否有木樁 & 該方向是否有對應方向的線
判斷是否需要拉線
拆除的時候由
該方向是否有對應方向的線
判斷是否需要拆線


C++範例代碼：

 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int m,n,h;
    cin >> m >> n >> h;
    vector<vector<int>> stat(m);
    for (int i = 0; i <m;i++) stat[i].resize(n,0);
    int ans = 0, cur = 0;
    for (int z = 0;z<h;z++){
        int r,c,t;
        cin >> r >> c >> t;
        if (t==0){
            if (stat[r][c]==0)cur++;
            stat[r][c] = 4;
            int x,y;
            bool ok;
            ok = false;
            x = r;y = c;
            for (x = r+1;x<m;x++){
                if (stat[x][y]==4)ok = true;
            }
            if (ok&&((stat[r+1][c]&1)==0)){
                for (x = r+1;x<m;x++){
                    if (stat[x][y]==4)break;
                    if (stat[x][y]==0)cur++;
                    stat[x][y]|=1;
                }
            }
            ok = false;
            x = r;y = c;
            for (x = r-1;x>=0;x--){
                if (stat[x][y]==4)ok = true;
            }
            if (ok&&((stat[r-1][c]&1)==0)){
                for (x = r-1;x>=0;x--){
                    if (stat[x][y]==4)break;
                    if (stat[x][y]==0)cur++;
                    stat[x][y]|=1;
                }
            }
            ok = false;
            x = r;y = c;
            for (y = c+1;y<n;y++){
                if (stat[x][y]==4)ok = true;
            }
            if (ok&&((stat[r][c+1]&2)==0)){
                for (y = c+1;y<n;y++){
                    if (stat[x][y]==4)break;
                    if (stat[x][y]==0)cur++;
                    stat[x][y]|=2;
                }
            }
            ok = false;
            x = r;y = c;
            for (y = c-1;y>=0;y--){
                if (stat[x][y]==4)ok = true;
            }
            if (ok&&((stat[r][c-1]&2)==0)){
                for (y = c-1;y>=0;y--){
                    if (stat[x][y]==4)break;
                    if (stat[x][y]==0)cur++;
                    stat[x][y]|=2;
                }
            }
        }else{
            stat[r][c] = 0;
            cur--;
            int x = r, y = c;
            if (r+1<m&&(stat[r+1][c]&1)){
                for (x = r+1;x<m;x++){
                    if (stat[x][y]==4)break;
                    stat[x][y]^=1;
                    if (stat[x][y]==0)cur--;
                }
            }
            x = r; y = c;
            if (r-1>=0&&(stat[r-1][c]&1)){
                for (x = r-1;x>=0;x--){
                    if (stat[x][y]==4)break;
                    stat[x][y]^=1;
                    if (stat[x][y]==0)cur--;
                }
            }
            x = r; y = c;
            if (c+1<n&&(stat[r][c+1]&2)){
                for (y = c+1;y<n;y++){
                    if (stat[x][y]==4)break;
                    stat[x][y]^=2;
                    if (stat[x][y]==0)cur--;
                }
            }
            x = r; y = c;
            if (c-1>=0&&(stat[r][c-1]&2)){
                for (y = c-1;y>=0;y--){
                    if (stat[x][y]==4)break;
                    stat[x][y]^=2;
                    if (stat[x][y]==0)cur--;
                }
            }
        }
        ans = max(ans,cur);
    }
    cout << ans << "\n" << cur << "\n";
}


Python範例代碼：

2022年1月

贏家預測

提示

題解
照題敘算

C++範例代碼：

 
#include <bits/stdc++.h>
using namespace std;
int main(){

}


Python範例代碼：

 
n,m = map(int,input().split())
s = [int(text) for text in input().split()]
t = [int(text) for text in input().split()]
health = [m]*n
o = [int(text)-1 for text in input().split()]
while len(o)>1:
    win=[True]*n
    for i in range(len(o)//2):
        p1=o[i*2]
        p2=o[i*2+1]
        p1,p2=(p1,p2) if s[p1]*t[p1]>=s[p2]*t[p2] else (p2,p1)
        d=s[p2]*t[p2]//2
        s[p1],t[p1]=s[p1]+d//(t[p1]),t[p1]+d//(s[p1])
        s[p2]+=s[p2]//2
        t[p2]+=t[p2]//2
        health[p2]-=1
        win[p2]=False
    o = [i for i in o if win[i]]+[i for i in o if not win[i] and health[i]]
print(o[0]+1)

2022年6月

字串解碼

提示

題解
在計算每一步的時候
用deque，由右往左掃描
遇到0則放前面，遇到1放後面

C++範例代碼：

 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int m,n;
    cin >> m >> n;
    vector<string> e(m);
    string s;
    for (string &o : e) cin >> o;
    cin >> s;
    deque<char> dat(s.begin(),s.end());
    for (int i = m-1;i>=0;i--){
        int r = 0;
        deque<char> nw;
        for (int j = n-1;j>=0;j--){
            r^=e[i][j]-'0';
            if (e[i][j]-'0') nw.push_back(dat[j]);
            else  nw.push_front(dat[j]);
        }
        if (r) for (int j = 0;j<(n>>1);j++) swap(nw[j],nw[n-(n>>1)+j]);
        dat = nw;
    }
    for(char c : dat) cout << c;
    cout << "\n";
}


Python範例代碼：