資訊之芽預試

前言

2/10、2/11就是資芽算法班考試了，好緊張><
希望不要燒雞=v=
最近應該會刷題勤勞一點。
講了那麼多廢話，上正題。

正題 — 2023 算法班歡樂報名預試

A. 99

題目

對，就是那個99 敘述太長我簡略w
注意事項：

1. 10 和 Q 只有減法，與原版本的規則不同。
2. 數值最小為 0 (打出 10 或 Q 不會讓數值變成負數)。
3. 每個玩家打出 5 時只會指定順序下一位玩家 (效果與 J 相同)。

給定一副 52 張撲克牌的順序，發牌/補牌按照撲克牌順序進行。
4 個人圍成一圈玩九九，一開始發牌一人發一張發五輪，從玩家 1 按照編號進行。
每個玩家會有自己的策略，對 52 張牌給定特定的優先值
每回合打牌時會出優先值最高且不會讓海的數值超過 99 的牌，並從牌庫頂端補牌（若牌庫還有牌）。
每個人按照固定的策略出牌，請輸出最後未被淘汰的玩家編號。

• 筆者亂講話時間
  恩對，這題我寫爛(0%)，但還是丟個code
  如果有大佬會歡迎指點一二 ORZ

code

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

struct Card {
  string name;
  int type;
  int value;
  int index;
};

queue<Card> cards;
int player[4][52];
vector<int> players = {0, 1, 2, 3};
int playerNum;

Card s2card(string s) {
  Card card;
  card.name = s;
  
  if (s[0] == 'S')
    card.type = 0;
  else if (s[0] == 'H')
    card.type = 1;
  else if (s[0] == 'D')
    card.type = 2;
  else if (s[0] == 'C')
    card.type = 3;

  stringstream ss;
  if (s[1] == 'A')
    card.value = 1;
  else if (s[1] == 'J')
    card.value = 11;
  else if (s[1] == 'Q')
    card.value = 12;
  else if (s[1] == 'K')
    card.value = 13;
  else if (s.size() == 3)
    card.value = 10;
  else {
    ss << s.substr(1, 1);
    ss >> card.value;
  }
  card.index = (card.value - 1) * 4 + card.type;
  return card;
}

void printCard(vector<Card> cards){
  cout << "===========\n";
  for(int i = 0; i < cards.size();i++){
    cout << cards[i].type << '/' << cards[i].value << '/' << player[players[playerNum]][cards[i].index] << '\n';
  }
  cout << "===========\n";
}

void printCard(Card card){
  cout << "[";
  cout << card.type << '/' << card.value << '/' << player[players[playerNum]][card.index];
  cout << "]\n";
}

bool cmp(Card c1, Card c2) {
  return player[players[playerNum]][c1.index] > player[players[playerNum]][c2.index];
}

int main() {
  // ios::sync_with_stdio(0);
  // cin.tie(0);
  int sea = 0;
  vector<Card> playerCard1;
  vector<Card> playerCard2;
  vector<Card> playerCard3;
  vector<Card> playerCard4;
  int _i = 0;
  string s;
  //發手牌
  for (int j = 0; j < 5; j++) {
    for (int k = 0; k < 4; k++) {
      cin >> s;
      if (k == 0) playerCard1.push_back(s2card(s));
      else if (k == 1) playerCard2.push_back(s2card(s));
      else if (k == 2) playerCard3.push_back(s2card(s));
      else if (k == 3) playerCard4.push_back(s2card(s));
      _i++;
    }
  }
  //其餘丟牌堆
  for (int i = _i; i < 52; i++) {
    cin >> s;
    cards.push(s2card(s));
  }
  //優先表
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 52; j++) {
      int num;
      cin >> num;
      player[i][j] = num;
    }
  }
  playerNum = 0;
  int nextplayer = 1;
  //開扁
  while (players.size() != 0) {
    //cout << "peopleNum: " << (int)players.size() << "(" << playerNum <<")"<< '\n';
    if (playerNum >= (int)players.size()) {
      playerNum = 0;
      //cout << "toobig!\n";
    }
    else if (playerNum < 0) {
      playerNum = players.size() - 1;
      //cout << "toosmall!\n";
    }
    
    
    vector<Card> playerCard;
    if (players[playerNum] == 0) playerCard = playerCard1;
    else if (players[playerNum] == 1) playerCard = playerCard2;
    else if (players[playerNum] == 2) playerCard = playerCard3;
    else if (players[playerNum] == 3) playerCard = playerCard4;
    
    cout << "player: " << players[playerNum]+1 << '\n';
    //cout << "(next: " << nextplayer << ")";
    if (playerCard.size() == 0) {
      //pcout << "沒卡了><\n";
      break;
    }
    //整理手牌(大->小)
    sort(playerCard.begin(),
         playerCard.end(), cmp);
    printCard(playerCard);
    int cardIndex = 0;
    int a = 0;
    bool bye = false;
    while (true) {
      if (cardIndex >= playerCard.size()) {
        cout << "bye" << '\n';
        bye = true;
        players.erase(players.begin() + playerNum);
        break;
      }
      Card nowCard = playerCard[cardIndex];
      cout << "num: " << cardIndex << "[" << nowCard.name << "]\n";
      //printCard(nowCard);
      //特殊牌
      if (nowCard.value == 1 && nowCard.type == 0) {
        sea = 0;
        break;
      }
      else if (nowCard.value == 4) {
        nextplayer *= -1;
        break;
      }
      else if (nowCard.value == 5 || nowCard.value == 11) {
        break;
      }
      else if (nowCard.value == 10) {
        sea -= 10;
        if (sea < 0) sea = 0;
        break;
      }
      else if (nowCard.value == 12) {
        sea -= 20;
        if (sea < 0) sea = 0;
        break;
      }
      else if (nowCard.value == 13) {
        sea = 99;
        break;
      }
      else if (sea + nowCard.value <= 99) {
        sea += nowCard.value;
        break;
      } 
      else cardIndex++;
    }
    //出牌
    if (bye) continue;
    playerCard.erase(playerCard.begin() + cardIndex);
    if (!cards.empty()){
      playerCard.push_back(cards.front());
      cards.pop();
    }
    
    if (players[playerNum] == 0) playerCard1 = playerCard;
    else if (players[playerNum] == 1) playerCard2 = playerCard;
    else if (players[playerNum] == 2) playerCard3 = playerCard;
    else if (players[playerNum] == 3) playerCard4 = playerCard;
    
    cout << "sea: " << sea << '\n' << "players: ";
    for (int i : players) {
      cout << i + 1 << " ";
    }
    cout << '\n' << '\n';
    //cout << "{" << playerNum << "}" << " -> ";
    playerNum += nextplayer;
    //cout << "{" << playerNum << "}" << '\n';
  }

  //倖存
  sort(players.begin(), players.end());
  for (int i : players) {
    cout << i + 1 << " ";
  }
  cout << '\n';
  return 0;
}

心得

這是預試我唯一寫爛的一題QQ
程式碼包含如何出牌的cout ，我到現在還是不知道自己的問題在哪…
然後…這題好像沒什麼好說的，就模擬 :)
寫完之後真心覺得自己模擬超爛，之前APCS也死在模擬 :(

B. 魔法字串

題目

code

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

int main(){
  int N, Q;
  string P, S;
  int appearTime[30];
  cin >> P >> N >> Q >> S;
  for(int i = 0;i < Q; i++){
    int t, x;
    cin >> t >> x;
    char s = S[x-1];
    int circle = 0;
    memset(appearTime, 0, sizeof(appearTime));
    while (t > 0){
      int index = s - '0';
      appearTime[index] += 1;
      s = P[index];
      t--;
      if (appearTime[index] == 2){
        circle += 1;
      }
      else if (appearTime[index] == 3){
        t %= circle;
      }
    }
    cout << s << '\n';
  }
  return 0;
}

心得

這題不能跟著他傻傻的跑，否則會TLE
我這邊用的方法是開一個陣列紀錄字母出現過幾次，若出現兩次則代表一個循環了
（現在才想到其實可以在第一圈就紀錄循環長度，上面為發現是一個循環後再繞一圈記長度w）
所以要操作的次數可以對循環長度取模（繞了一圈還是依樣嘛～）
就能得到實際上我們需要操作的次數了。

C. 簡單 V 硬

題目

code

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

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int N, Q;
  string text[105], f, word;
  int index, l, r, p;
  cin >> N >> Q;
  cin.get();
  for(int i = 0; i < N; i++){
    getline(cin, text[i]);
  }
  for(int i = 0 ;i < Q;i++){
    cin >> f >> index;
    if (f == "cut"){
      cin >> l >> r;
      int len = r - l + 1;
      word = text[index].substr(l, len);
      text[index].erase(l, len);
    }
    else if (f == "paste"){
      cin >> p;
      text[index].insert(p, word);
    }
  }
  for(int i = 0;i < N; i++){
    cout << text[i] << '\n';
  }
  return 0;
}

心得

如果你記的夠熟，這題用 c++ 字串的 function 就能解決啦～

D. 曹曹愛畫線

題目

code

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

int N, Q;
long long paper[2][5000];

void slove(){
  cin >> N >> Q;
  memset(paper, 0, sizeof(paper));
  for(int i = 0; i < Q; i++){
    long long op, n , k;
    cin >> op >> n >> k;
    op--; n--;
    paper[op][n] = max(k, paper[op][n]);
  }
}

int main(){
  ios::sync_with_stdio(0); cin.tie(0);
  slove();
  int op1 = N - 1, op2 = 0;
  int line1 = op1, line2 = op2;
  for(int i = 0; i < N; i++){
    line1 = op1; line2 = op2;
    for(int j = 0; j < N; j++){
      cout << max(paper[0][line1], paper[1][line2]) << ' ';
      line1--; line2++;
    }
    cout << '\n';
    op1++; op2++;
  }
}

心得

這題很有趣，主要想法是第幾條斜線用陣列的第n格去存，然後存兩個(左斜跟右斜)
再來是顏色比較生的會覆蓋，所以比個大小就結束啦！

E. ㄌㄌ

題目

code

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

int N, K;
int big(int n){
  if(K - n > n) n = K - n;
  return n;
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int max = -1, min = 1000000000;
  cin >> N >> K;
  for (int i = 0; i < N; i++){
    int LL;
    cin >> LL;
    if (max < big(LL)){
      max = big(LL);
    }
    if (min > big(LL)){
      min = big(LL);
    }
  }
  cout << max - min << '\n';
  return 0;
}

心得

哇～～差點就漏掉最精彩的一題了，原先沒找到竟是被我收藏起來了 (0v0)
我對這題的想法是: 雖說可以操作數次 K-Ai but K-(K-Ai) 又會是 Ai
因此會有一個大一個小，對每個Ai操作我們就可以得到大的組跟小的組
再來就只要在大組（或小組）之中找最大與最小的差就好啦～
太棒了，一天又平安的過去了，感謝ㄌㄌ大法師的努力！

結尾

呀～打完了，其實還滿有趣的
寫 code 累了就可以轉換一下心情
ㄌㄌ真的是神題目，我第一個就直接從ㄌㄌ下手
總之有一件事很重要……
開ｌｏｎｇｌｏｎｇ！！！


-2023/2/6 22:27更新了pE