APCS 20231022 題解

前言

我不會指標

機械鼠

想法

先排序，然後看往左走往右走哪邊比較好。

時間複雜度

$O(NlgN)$

code

#include <bits/stdc++.h>
using namespace std;
array<int, 24> F;
signed main(){
    int n, pos, l = 0, r = 0;
    cin >> pos >> n;
    for(int i = 0; i < n; i++){
        cin >> F[i];
    }
    sort(F.begin(), F.begin() + n);
    for(int i = 0; i < n; i++){
        if(F[i] <= pos) l++;
        if(F[i] >= pos) r++;
    }
    if(l > r) cout << l << " " << F[0];
    else cout << r << " " << F[n - 1];
    return 0;
}

卡牌遊戲

想法

對每個牌找他的另一半是不是在隔壁，然後一直消直到沒東西消。
用 linked list 實做就不用管

$NM$ 多大了。

時間複雜度

$O(C^2)$

code

#include <bits/stdc++.h>
using namespace std;
struct linki{
    int v;
    linki *pre, *nex;
    linki(){
        v = -1;
        pre = nex = nullptr;
    }
    linki(int x){
        v = x;
        pre = nex = nullptr;
    }
    linki* push(int x){
        nex = new linki(x), nex->pre = this;
        return nex;
    }
};
array<linki*, 44> I, J;
array<array<linki*, 2>, 1004> H, V;
array<int, 1004> vis;
void del(linki *l){
    l->pre->nex = l->nex;
    if(l->nex) l->nex->pre = l->pre;
    delete l;
}
int match(){
    int p = -1;
    for(int i = 0; i <= 1000; i++){
        if(vis[i]) continue;
        if(H[i][0]->pre == H[i][1] || V[i][0]->pre == V[i][1]){
            del(H[i][0]), del(H[i][1]), del(V[i][0]), del(V[i][1]);
            p = max(p + i, i);
            vis[i] = 1;
        }
    }
    return p;
}
signed main(){
    int n, m, sum = 0, p;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) I[i] = new linki;
    for(int j = 1; j <= m; j++) J[j] = new linki;
    for(int i = 0; i <= 1000; i++) vis[i] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> p;
            H[p][vis[p]] = I[i] = I[i]->push(p);
            V[p][vis[p]] = J[j] = J[j]->push(p);
            vis[p] = 0;
        }
    }
    while(1){
        if((p = match()) < 0) break;
        sum += p;
    }
    cout << sum;
    return 0;
}

搬家

想法

把全部字母都換成對應的形狀建圖，再砸 D/BFS 跑連通塊大小。

時間複雜度

$O(NM)$

聽說 DFS 會被 zerojudge 卡 stack limit

code

#include <bits/stdc++.h>
using namespace std;
array<int, 4> dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
array<array<int, 1504>, 1504> G, vis;
array<array<char, 504>, 504> O;
int a(int x){return 3 * x + 1;}
int b(int x){return 3 * x + 2;}
int c(int x){return 3 * x + 3;}
void build(int x, int y, char p){
    if(p == '0') return;
    G[b(x)][b(y)] = 1;
    if(p == 'X') G[a(x)][b(y)] = G[b(x)][a(y)] = G[b(x)][c(y)] = G[c(x)][b(y)] = 1;
    else if(p == 'I') G[a(x)][b(y)] = G[c(x)][b(y)] = 1;
    else if(p == 'H') G[b(x)][a(y)] = G[b(x)][c(y)] = 1;
    else if(p == 'L') G[a(x)][b(y)] = G[b(x)][c(y)] = 1;
    else if(p == 'F') G[c(x)][b(y)] = G[b(x)][c(y)] = 1;
    else if(p == '7') G[b(x)][a(y)] = G[c(x)][b(y)] = 1;
    else G[b(x)][a(y)] = G[a(x)][b(y)] = 1;
}
int DFS(int x, int y){
    if(vis[x][y] || !G[x][y]) return 0;
    vis[x][y] = 1;
    int sum = 1;
    for(int i = 0; i < 4; i++){
        sum += DFS(x + dx[i], y + dy[i]);
    }
    if(x % 3 == 2 && y % 3 == 2) sum -= O[x / 3][y / 3] == 'X'? 4 : 2;
    return sum;
}
int BFS(int x, int y){
    int sum = 0;
    queue<pair<int, int>> Q;
    Q.push({x, y});
    while(!Q.empty()){
        auto [i, j] = Q.front();
        Q.pop();
        if(vis[i][j] || !G[i][j]) continue;
        vis[i][j] = 1;
        sum++;
        if(i % 3 == 2 && j % 3 == 2) sum -= O[i / 3][j / 3] == 'X'? 4 : 2;
        for(int k = 0; k < 4; k++){
            Q.push({i + dx[k], j + dy[k]});
        }
    }
    return sum;
}
signed main(){
    int n, m, com = 0;
    cin >> n >> m;
    getchar();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            O[i][j] = getchar();
            build(i, j, O[i][j]);
        }
        getchar();
    }
    for(int i = 1; i <= 3 * n; i++){
        for(int j = 1; j <= 3 * m; j++){
            com = max(com, BFS(i, j));
        }
    }
    cout << com;
    return 0;
}

投資遊戲

想法

正常人看到一個 DP 題，有

$N$ 有

$K$ 都會想要砸 aliens。

砸不了 aliens 我破防了

$D{P}_{i,j}=$ 第

$i$ 天，用過

$j$ 張金牌。

$D{P}_{i,0}$ 就最大連續和

$D{P}_{i,j}=max(D{P}_{i-1,j}+P_i,D{P}_{i-1,j-1})$

時間複雜度

$O(NK)$

code

#include <bits/stdc++.h>
#define int long long
using namespace std;
array<int, 150004> P;
array<array<int, 24>, 150004> dp;
int DP(int n, int k){
    int ans = 0;
    for(int i = 1; i <= n; i++){
        dp[i][0] = max(dp[i - 1][0], 0ll) + P[i];
        ans = max(ans, dp[i][0]);
    }
    for(int j = 1; j <= k; j++){
        for(int i = 1; i <= n; i++){
            dp[i][j] = max(dp[i - 1][j] + P[i], dp[i - 1][j - 1]);
            ans = max(ans, dp[i][j]);
        }
    }
    return ans;
}
signed main(){
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> P[i];
    cout << DP(n, k);
    return 0;
}