創作內容

5 GP

7/4 APCS

作者:路過的一隻山姆│2020-07-04 19:15:22│巴幣:1,008│人氣:943
更 觀念5 實作4 ==
===================================================================
今天是我第一次考APCS
難度感覺還好
觀念很簡單 實作也不難
我在這裡打我實作的解法(不一定正確 我也不太記得題目了)

pA 給a,b兩個數字 和一個m
     執行m次 每次會有100個以內的數字
     數字是正的->拿物品
     數字是負的->放回去
     問同時拿到a,b有幾次
     這題就紀錄每次拿了a,b幾次就解決了
程式碼
#include <bits/stdc++.h>

#define ll long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

int main(){
fastio
int a,b,m, ans = 0;
cin >> a >> b >> m;
while(m--){
int tmp, cnt1 = 0, cnt2 = 0;
cin >> tmp;
while(cin >> tmp){
if(tmp==0) break;
if(tmp > 0){
if(tmp == a) cnt1++;
if(tmp == b) cnt2++;
}
else{
if(tmp == -a) cnt1–;
else if(tmp ==-b) cnt2–;
}
}
if(cnt1&&cnt2) ans++;
}
cout << ans << "\n";
}
pB 給n個骰子 進行m次操作
     骰子一開始都是由1朝上 由4朝前
     每次操作有a,b兩個數字
     當b是正的時候 把a,b兩骰子調換
     如果b是-1把骰子往前轉
            b是-2把骰子往右轉
     問進行操作之後每個骰子上方的數字
     用一個三項的陣列存每個骰子的上前右
程式碼
#include <bits/stdc++.h>

#define ll long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

int main(){
fastio
int n,m;
cin >> n >> m;
array<int,3> arr[n];
for(int i = 0;i < n;i++) arr[i] = {1,4,2};
while(m--){
int a,b;
cin >> a >> b;
a--;
if(b > 0){
b--;
array<int,3> tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}else{
if(b == -1){
int tmp = arr[a][1];
arr[a][1] = arr[a][0];
arr[a][0] = 7 - tmp;
}else{
int tmp = arr[a][2];
arr[a][2] = arr[a][0];
arr[a][0] = 7 - tmp;
}
}
}
for(int i = 0;i < n;i++) cout << arr[i][0] << " ";
}
pC 給n個房間連成一環跟m把鑰匙 離開每個房間有各自的點數
     要照順序(0->1->2->...->n-1->0->1->...)走
     達到一定的點數就能得到鑰匙 但是點數會歸零
     問最後停留的房間
     我自己是用前綴和加二分搜去解
程式碼
#include <bits/stdc++.h>

#define ll long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

int n,m;
int binary_search(int arr[], int l, int r, int target){
while(l < r){
int mid = (l+r)/2;
int tmp = arr[mid%n] + (mid >= n ? arr[n-1] : 0);
if(tmp < target){
l = mid+1;
}else if(tmp > target){
r = mid-1;
}else{
return mid;
}
}
return l;
}

int main(){
fastio
cin >> n >> m;
int pref[n];
for(int i = 0;i < n;i++){
cin >> pref[i];
if(i!=0) pref[i] += pref[i-1];
}
int room = 0;
for(int t = 0, point;t < m;t++){
cin >> point;
room = (binary_search(pref,room,room+n, point + (room==0 ? 0 : pref[room-1])))%n+1;
}
cout << room << "\n";
}
pD 這題大概是這次最難的一題了
      有關DNA 給予n個樣本 DNA長度為m
      樣本一為根節點
      每個DNA當中會有@為未知的字元
      問最少變異次數
      
      這題是有關樹的題目 一般就是DFS或是BFS
      我自己用了兩次DFS
      先從葉節點開始填@
      第二次DFS再去算變異次數和把剩下的@填滿
      不確定是不是對的 不過測資不大 應該不會TLE
程式碼
#include <bits/stdc++.h>

#define ll long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e3+5;
vector<pair<int,string>> adj[N];

int diff(string &s1, string &s2){
int cnt = 0;
for(int i = 0;i < s1.size();i++){
if(s1[i]=='@'&&s2[i]!='@') s1[i] = s2[i];
else if(s1[i]!='@'&&s2[i]=='@') s2[i] = s1[i];
else if(s1[i]!=s2[i]) cnt++;
}
return cnt;
}

int ans = 0;
void dfs(int u, string &s){
for(auto &x : adj[u]){
dfs(x.first, x.second);
}
unordered_map<char,int> m;
for(int i = 0;i < s.size();i++){
if(s[i]!='@') continue;
m.clear();
for(auto &x : adj[u]){
if(x.second[i]!='@') m[x.second[i]]++;
}
if(!m.empty()) s[i] = max_element(m.begin(), m.end(), [&](pair<char,int> a, pair<char,int> b){return a.second < b.second;})->first;
}
for(auto &x : adj[u]){
for(int i = 0;i < s.size();i++)
if(x.second[i]=='@') x.second[i] = s[i];
}
}

void dfs2(int u, string &s){
//cout << u << " " << s << "\n";
for(auto &x : adj[u]){
ans += diff(s,x.second);
dfs2(x.first,x.second);
}
}

int main(){
fastio
int n,m;
cin >> n >> m;
string root;
while(n--){
int u,v;
string s;
cin >> u >> v >> s;
if(u==v){
root = s;
continue;
}
adj[v].push_back({u,s});
}
dfs(1,root);
dfs2(1,root);
cout << ans << "\n";
}
第一次考APCS 希望能拿4分以上 最好能有5分

引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4838151
All rights reserved. 版權所有,保留一切權利

相關創作

留言共 14 篇留言

美好的過去漸行漸遠
原來第三題真的要用2分搜= =

07-04 19:19

路過的一隻山姆
我記得我寫了二分搜 但我忘記我考APCS時有沒有把線性搜尋改成二分搜了 如果沒有的話可能就沒機會5了07-04 19:21
ʕ •ᴥ•ʔ
怕是大佬ʕ; •`ᴥ•´ʔ 不過我第三題不是用二分搜 是直接用加的 這樣會不會tle

07-04 20:20

路過的一隻山姆
測資是10^5還10^6 如果是二分搜 時間是O(logn*m) 但是如果線性搜會是O(n*m) 可能只會對部分測資07-04 20:23
超稀有S級食材魩仔魚
我就不會

07-04 22:33

路過的一隻山姆
加油 練習一下 下次就會了07-04 22:41
超稀有S級食材魩仔魚
可是我沒有要讀理工科系

07-04 22:42

路過的一隻山姆
當興趣也不錯啊07-04 22:43
超稀有S級食材魩仔魚
難的要死 大概只會淺淺的學一點

07-04 22:44

積極努力認真向上
#include <iostream>
using namespace std;
我都這樣打就開始
你打的有些看不懂,疴啊啊學得好不扎實

07-05 00:21

路過的一隻山姆
沒 我的開頭比較偏競賽會用到的

07-05 00:57
積極努力認真向上
問ㄍ你有習慣的學習資源嗎?

07-05 01:27

專業邊緣人
山姆佬看到CF的成績CSY教徒準備要抓你進去ㄌㄏㄏ

07-05 01:27

路過的一隻山姆

07-05 01:28
專業邊緣人
可能之後你就知道ㄌ

07-05 01:30

南國蛋蛋香噴噴
第三題直接按照順序跑了,一定TLE已經TLE,第四題沒時間寫,搶了30分,就看有沒有機會可以4級別了(btw觀念好難OAO)

07-05 16:02

路過的一隻山姆
希望能有吧 只要兩題半就有4了07-05 16:16
蘇小小(*¯︶¯*)
只會做1,3 QQ

07-05 16:26

路過的一隻山姆
也不錯啦 三級分07-05 19:29
ʕ •ᴥ•ʔ
我之前聽說bit比較慢,如果有辦法就盡量不要用耶

07-05 19:26

路過的一隻山姆
也不會慢多少 有沒有cin.tie 那個差比較多07-05 19:29
ㄅㄅ(可憐麻糬 mode
唉 巴哈不能排版,看了眼睛好痛
@_@

這C++?

07-10 22:40

路過的一隻山姆
07-10 22:49
美好的過去漸行漸遠
是說標頭檔APCS的編譯器可以用?

10-06 00:33

路過的一隻山姆
可以10-06 00:35
路過的一隻山姆
那個我記得只有太舊的cpp不能用而已10-06 00:36
我要留言提醒:您尚未登入,請先登入再留言

5喜歡★sam571128 可決定是否刪除您的留言,請勿發表違反站規文字。

後一篇:決定開始紀錄每天的競程訓...

追蹤私訊切換新版閱覽

作品資料夾

happy1111222挖坑一堆
待看清單真的是一年比一年長哇...:3看更多我要大聲說昨天20:43


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】