Max Coding blog

APCS實作題

2021/08/27

APCS實作

Default code v1

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define out cout << '\n';
#define int long long
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
signed main(){
IOS

return 0;
}

My default code

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int main(){
IOS

return 0;
}

About pragma

1
2
3
4
5
6
#pragma GCC optimize("O0")//不優化(預設)
#pragma GCC optimize("O1")//優化一些
#pragma GCC optimize("O2")//優化更多
#pragma GCC optimize("O3")//O2優化再加上inline函式優化
#pragma GCC optimize("Os")//針對程式大小進行優化(程式最小)
#pragma GCC optimize("Ofast")//O3加上一些快速但不安全的數學運算

More about pragma

1
2
3
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
  1. Ofast優化,加上迴圈展開、忽略堆疊溢出攻擊。
  2. 針對CPU的指令集擴充,只有一些intel支援,有些AMD也有。
  3. 加開堆疊,可以讓遞迴函式跑多一點。 $$$$

111/01

第一題:程式交易

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define out cout<<'\n';
#pragma GCC optimize("Ofast")
using namespace std;
int main(){
IOS
long long n, d, arr[105];
cin >> n >> d;
for(int i = 0;i < n;i++) cin >> arr[i];
int cost = arr[0], profit = 0, pre = 0;
bool judge = true;
for(int i = 1;i < n;i++){
if(judge){
if(arr[i] - cost >= d){
judge = false;
profit = profit + abs(arr[i] - cost);
cost = arr[i];
}
}
else{
if(cost - d >= arr[i]){
cost = arr[i];
judge = true;
}
}
}
cout << profit;

return 0;
}

第二題:贏家預測

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
int main(){
IOS
// freopen("sample1.in", "r", stdin);
int n, m, m_cnt[1005];
ll s[1005], t[1005];
vector<int> idx, win, lose;
cin >> n >> m;
for(int i = 1;i <= n;i++) cin >> s[i];
for(int i = 1;i <= n;i++) cin >> t[i];
for(int i = 0;i < n;i++){
int tmp;
cin >> tmp;
idx.push_back(tmp);
}
for(int i = 1;i <= n;i++) m_cnt[i] = m;
while(idx.size() > 1){
for(int i = 0;i + 1 < (int)idx.size();i += 2){
int a = idx[i], b = idx[i + 1];
if(s[a] * t[a] < s[b] * t[b]) swap(a, b);

ll new_sa = s[a] + (s[b] * t[b]) / (2 * t[a]), new_ta = t[a] + (s[b] * t[b]) / (2 * s[a]);
s[a] = new_sa; t[a] = new_ta;
s[b] += s[b] / 2; t[b] += t[b] / 2;

m_cnt[b]--;
win.push_back(a);
if(m_cnt[b] > 0){
lose.push_back(b);
}
}
if((int)idx.size() % 2 == 1) win.push_back(idx.back());
idx = win;
for(int i : lose) idx.push_back(i);
win.clear();
lose.clear();
}
cout << idx[0] << '\n';

return 0;
}

第四題:牆上海報

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
vector<ll> board(200005), post(5005);
int n, k;
int main(){
IOS
cin >> n >> k;
for(int i = 1;i <= n;i++) cin >> board[i];
for(int i = 1;i <= k;i++) cin >> post[i];
int l = 1, r = 1000000001;
while(l < r - 1){
int mid = (l + r) >> 1;
int cnt = 0, cur = 1;
bool judge = false;
for(int i = 1;i <= n;i++){
if(board[i] >= mid){
cnt++;
if(cnt == post[cur]){
cnt = 0;
if(cur == k){
judge = true;
break;
}
cur++;
}
}
else cnt = 0;
}
if(judge) l = mid;
else r = mid;
}
cout << l << '\n';

return 0;
}

110/9

第三題:幸運數字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
ll n, pre[300005] = {0}, arr[300005];
bool cmp(int a, int b){
return arr[a] > arr[b];
}
vector<ll> vec;
int main(){
IOS
cin >> n;
for(int i = 1;i <= n;i++){
cin >> arr[i];
vec.push_back(i);
pre[i] = pre[i - 1] + arr[i];
}
sort(vec.begin(), vec.end(), cmp);
int l = 1, r = n;
while(l != r){
while(vec.back() < l || vec.back() > r) vec.pop_back();
int m = vec.back();
vec.pop_back();
ll t1 = pre[m - 1] - pre[l - 1], t2 = pre[r] - pre[m];
if(t1 > t2) r = m - 1;
else l = m + 1;
}
cout << arr[l] << '\n';

return 0;
}

109/10

第一題:人力分配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
int main(){
int a,b,c,d,e,f,n;
cin >> a >> b >> c;//y = ax^2 + bx + c
cin >> d >> e >> f;//y = dx^2 + ex + f
cin >> n;
long long int max_num = -2147483647,y1,y2;
for(int i = 0;i <= n;i++){
y1 = a*i*i + b*i + c;
y2 = d*(n-i)*(n-i) + e*(n-i) + f;
max_num = (y1+y2) > max_num ? (y1+y2) : max_num;
}
cout << max_num;

return 0;
}

第二題:人口遷移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int r,c,k,m,max_ = -1,min_ = 2147483647;
cin >> r >> c >> k >> m;
int arr[r+3][c+3],temp[r+3][c+3];
for(int i = 1;i <= r;i++){
for(int j = 1;j <= c;j++){
cin >> arr[i][j];
temp[i][j] = arr[i][j];
}
}
while(m > 0){
for(int i = 1;i <= r;i++){
for(int j = 1;j <= c;j++){
int tmp = arr[i][j]/k;
if(arr[i][j] == -1) continue;
if(i != 1 && arr[i-1][j] != -1){
temp[i-1][j] += tmp;
temp[i][j] -= tmp;
}
if(i != r && arr[i+1][j] != -1){
temp[i+1][j] += tmp;
temp[i][j] -= tmp;
}
if(j != 1 && arr[i][j-1] != -1){
temp[i][j-1] += tmp;
temp[i][j] -= tmp;
}
if(j != c && arr[i][j+1] != -1){
temp[i][j+1] += tmp;
temp[i][j] -= tmp;
}
}
}
for(int i = 1;i <= r;i++){
for(int j = 1;j <= c;j++){
arr[i][j] = temp[i][j];
}
}
m--;
}
for(int i = 1;i <= r;i++){
for(int j = 1;j <= c;j++){
if(arr[i][j] == -1) continue;
if(arr[i][j] >= max_) max_ = arr[i][j];
if(arr[i][j] <= min_) min_ = arr[i][j];
}
}
cout << min_ << '\n' << max_;

return 0;
}

108/7

第一題:購物車

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int main(){
IOS
int a, b, n;
cin >> a >> b >> n;
int ans = 0;
while(n--){
int a_judge = 0, b_judge = 0;
int arr[100], tmp, q = 0;
while(true){
cin >> tmp;
if(tmp == 0) break;
if(tmp == a) a_judge++;
else if(tmp == b) b_judge++;
else if(tmp == a*(-1)) a_judge--;
else if(tmp == b*(-1)) b_judge--;
else continue;
}
if(a_judge > 0 && b_judge > 0) ans++;
}
cout << ans;

return 0;
}

第二題:骰子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
struct dice{
int up = 1;
int down = 6;
int left = 5;
int right = 2;
int forw = 4;
int bacw = 3;
};
int main(){
IOS
// dice arr[10];
// arr[1].bacw = 100;
// arr[1].down = 49;
// cout << arr[0].bacw << " " << arr[0].down << '\n';
// arr[0] = arr[1];
// cout << arr[0].bacw << " " << arr[0].down;
int n, m, tmp;
dice arr[50];
cin >> n >> m;
while(m--){
int a, b;
cin >> a >> b;
a--;
if(b == -1){
int ba = arr[a].bacw;
int fo = arr[a].forw;
int u = arr[a].up;
int d = arr[a].down;
arr[a].bacw = d;
arr[a].forw = u;
arr[a].up = ba;
arr[a].down = fo;
}
else if(b == -2){
int r = arr[a].right;
int l = arr[a].left;
int u = arr[a].up;
int d = arr[a].down;
arr[a].right = u;
arr[a].left = d;
arr[a].up = l;
arr[a].down = r;
}
else{
b--;
arr[40] = arr[a];
arr[a] = arr[b];
arr[b] = arr[40];
}
}
for(int i = 0;i < n;i++) cout << arr[i].up << " ";

return 0;
}

108/6

第一題:籃球比賽

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
using namespace std;
struct bask{
int first,second;
};
int main(){
bask a[5],b[5],sum1,sum2;
sum1.first = 0;
sum1.second = 0;
sum2.first = 0;
sum2.second = 0;
for(int i = 0;i < 4;i++){
cin >> a[i].first;
sum1.first += a[i].first;
}
for(int i = 0;i < 4;i++){
cin >> b[i].first;
sum2.first += b[i].first;
}
int one = 0,two = 0;
if(sum1.first > sum2.first) one++;
else if(sum1.first < sum2.first) two++;
for(int i = 0;i < 4;i++){
cin >> a[i].second;
sum1.second += a[i].second;
}
for(int i = 0;i < 4;i++){
cin >> b[i].second;
sum2.second += b[i].second;
}
if(sum1.second > sum2.second) one++;
else if(sum1.second < sum2.second) two++;
cout << sum1.first << ":" << sum2.first << endl;
cout << sum1.second << ":" << sum2.second << endl;
if(one > two) cout << "Win";
else if(one < two) cout << "Lose";
else if(one == two) cout << "Tie";

return 0;
}

108/2

第一題:合成函數

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <sstream>
using namespace std;
int cacu(){
string str;
cin >> str;
if(str == "f"){
int x = cacu();
return (2 * x) - 3;
}
else if(str == "g"){
int a = cacu();
int b = cacu();
return (2 * a) + b - 7;
}
else if(str == "h"){
int q = cacu();
int w = cacu();
int e = cacu();
return (3 * q) - (2 * w) + e;
}
else{
stringstream ss;
int num = 0;
ss << str;
ss >> num;
return num;
}
}
int main(){
int a = cacu();
cout << a ;

return 0;
}

107/10

第二題:子集合的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <algorithm>
#include <climits>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
int n, p, arr[30], close = 2e10, ans = 0, cnt = 0;
void rec(int i, int num){
if(i >= n){
if(p - num > 0 && (p-num) < close){
close = p-num;
ans = num;
cnt++;
}
return;
}
rec(i + 1, num + arr[i]);
rec(i + 1, num);
return;
}
signed main(){
IOS
cin >> n >> p;
for(int i = 0;i < n;i++) cin >> arr[i];
rec(0, 0);
cout << ans;

return 0;
}

第三題:二維黑白影像編碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <algorithm>
#include <cstring>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define out cout<<'\n';
#define int long long
#pragma GCC optimize("Ofast")
using namespace std;
string str;
int num, idx = -1;
int matrix(int n){
idx++;
if(str[idx] == '0') return 0;
else if(str[idx] == '1') return n * n;
else if(str[idx] == '2'){
int cnt = 0;
for(int i = 0;i < 4;i++){
cnt += matrix(n/2);
}
return cnt;
}
}
signed main(){
cin >> str;
cin >> num;
int output = matrix(num);
cout << output;

return 0;
}

107/02

第三題:支點切割

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
int arr[50001];
long long prefix[50005], suffix[50005];
int reg(int k, int l, int r){
if(k < 1) return 0;
if(r - l <= 1) return 0;

prefix[l] = 0;
long long delta1 = 0;
for(int i = l + 1;i <= r;i++){
delta1 += arr[i - 1];
prefix[i] = prefix[i - 1] + delta1;
}
// for(int i = 0;i <= 7;i++) cout << prefix[i] << ' ';
// cout << endl;
suffix[r] = 0;
long long delta2 = 0;
for(int i = r - 1;i >= l;i--){
delta2 += arr[i + 1];
suffix[i] = suffix[i + 1] + delta2;
}
// for(int i = 0;i <= 7;i++) cout << suffix[i] << ' ';
// cout << endl;
long long min_j = 2e18;
int idx = 0;
for(int i = l + 1;i < r;i++){
long long cost = abs(prefix[i] - suffix[i]);
if(cost < min_j){
min_j = cost;
idx = i;
}
}
// cout << idx << '\n';
k--;
return arr[idx] + reg(k, l, idx-1) + reg(k, idx+1, r);
}
int main(){
int n, k;
cin >> n >> k;
for(int i = 1;i <= n;i++) cin >> arr[i];
cout << reg(k, 1, n);

return 0;
}

106/10

第一題:邏輯運算子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
using namespace std;
int main(){
int a,b,c;
cin >> a >> b >> c;
if(a > 0) a = 1;
else a = 0;
if(b > 0) b = 1;
else b = 0;
bool judge = true;
if((a == b && a == 1 && c == 1) || (a != b && c == 0) || (a == b && a == 0 && c == 0)){
cout << "AND" << endl;
judge = false;
}
if(((a == 1 || b == 1) && c == 1) || (a == 0 && b == 0 && c == 0)){
cout << "OR" << endl;
judge = false;
}
if((a == b && c == 0) || (a != b && c == 1)){
cout << "XOR" << endl;
judge = false;
}
if(judge) cout << "IMPOSSIBLE";

return 0;
}

第二題:交錯字串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cctype>
using namespace std;
int main(){
int k;
string str;
cin >> k >> str;
int count_max = 0;
for(int j = 0;j < str.size();j++){
bool judge = true;
bool out = false;
if(isupper(str[j])) judge = false;
else judge = true;
int counts = 0,index = 0,before = 0;
for(int i = j;i < str.size();i++){
if(judge){
if(islower(str[i])) index++;
else out = true;
}
else{
if(isupper(str[i])) index++;
else out = true;
}
if(index == k && out == false){
counts += k;
judge = !judge;
index = 0;
}
if(out){
count_max = counts > count_max ? counts : count_max;
break;
}
}
}
if(str.size() == 1 && k == 1) count_max = 1;
cout << count_max;
return 0;
}

第三題:樹的高度與根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
long long parent[100005] = {0}, h[100005] = {0}, total = 0, child[100005];
int root;
queue<int> Q;
int main(){
IOS
int n;
cin >> n;
for(int i = 1;i <= n;i++){
cin >> child[i];
if(child[i] == 0) Q.emplace(i);
for(int j = 0;j < child[i];j++){
int foo;
cin >> foo;
parent[foo] = i;
}
}
while(true){
int data = Q.front();
Q.pop();
total += h[data];
if(parent[data] == 0){
root = data;
break;
}
h[parent[data]] = max(h[parent[data]], h[data]+1);
child[parent[data]]--;
if(child[parent[data]] == 0) Q.emplace(parent[data]);
}
cout << root << ' ' << total;

return 0;
}

106/3

第一題:秘密差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
using namespace std;
int main(){
int suma = 0,sumb = 0;
string num;
cin >> num;
vector<int> a,b;
for(int i = 0;i < num.length();i++){
if(i%2 == 0) a.push_back(num[i]-48);
else b.push_back(num[i]-48);
}
for(int i = 0;i < a.size();i++){
suma += a[i];
}
for(int i = 0;i < b.size();i++){
sumb += b[i];
}
cout << abs(suma-sumb);

return 0;
}

第二題:小群體

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n;
cin >> n;
int id[50001];
for(int i = 0;i < n;i++)
cin >> id[i];
int num = 0;
bool boolean[50001];
fill(boolean,boolean+50001,1);
for(int i = 0;i < n;i++){
if(boolean[i]){
if(i == id[id[i]]){
num++;
boolean[i] = false;
boolean[id[i]] = false;
}
else if(id[i] != id[id[i]]){
int temp = i,j = id[i];
boolean[i] = false;
while(id[j] != temp){
boolean[j] = false;
j = id[j];
}
boolean[j] = false;
num++;
}
}
}
cout << num << endl;

return 0;
}

第三題:數字龍捲風

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define out cout << '\n';
#pragma GCC optimize("Ofast")
using namespace std;
int n, dir, arr[55][55];
void left(int *i,int *j){
*j = *j-1;
cout << arr[*i][*j];
}
void up(int * i,int * j){
*i = *i - 1;
cout << arr[*i][*j];
}
void right(int *i,int *j){
*j = *j+1;
cout << arr[*i][*j];

}
void down(int *i,int *j){
*i = *i+1;
cout << arr[*i][*j];
}
int main(){
IOS
cin >> n;
cin >> dir; // 0-left // 1-up // 2-right // 3-down
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
cin >> arr[i][j];
}
}
int cnt = 0, step = 0, idx = 0, a = n/2, b = n/2;
int n1, n2, n3, n4;
switch(dir){
case 0:
n1 = 1; n2 = 2; n3 = 3; n4 = 0;
break;
case 1:
n1 = 0; n2 = 1; n3 = 2; n4 = 3;
break;
case 2:
n1 = 3; n2 = 0; n3 = 1; n4 = 2;
break;
case 3:
n1 = 2; n2 = 3; n3 = 0; n4 = 1;
break;
}
cout << arr[a][b];
for(int i = 0;i < (n * n)-1;){
if(step % 2 == 0) cnt++;
if(idx == n1){
for(int j = 0;j < cnt;j++){
if(i >= (n * n)-1) break;
up(&a, &b);
i++;
}
}
if(idx == n2){
for(int j = 0;j < cnt;j++){
if(i >= (n * n)-1) break;
right(&a, &b);
i++;
}
}
if(idx == n3){
for(int j = 0;j < cnt;j++){
if(i >= (n * n)-1) break;
down(&a, &b);
i++;
}
}
if(idx == n4){
for(int j = 0;j < cnt;j++){
if(i >= (n * n)-1) break;
left(&a, &b);
i++;
}
}
step++;
if(idx == 3) idx = -1;
idx++;
}
out
return 0;
}

第四題:基地台

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
int n, k, arr[50005];
bool valid(int num){
int cover = arr[0] + num, cnt = 1;
for(int i = 1;i < n;i++){
if(cover < arr[i]){
cover = arr[i] + num;
cnt++;
}
}
return (cnt <= k);
}
int main(){
IOS
cin >> n >> k;
for(int i = 0;i < n;i++) cin >> arr[i];
sort(arr, arr + n);
int l = 0, r = (arr[n - 1] - arr[0]) / k + 1, ans;
while(l < r){
int mid = (l + r) >> 1;
if(valid(mid)) ans = mid, r = mid;
else l = mid + 1;
}
cout << ans << '\n';

return 0;
}

105/10

第一題:三角形辨別

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int arr[4];
cin >> arr[0] >> arr[1] >> arr[2];
sort(arr,arr+3);
cout << arr[0] << " " << arr[1] << " " << arr[2] << endl;
if((arr[0] + arr[1]) <= arr[2]) cout << "No";
else if(((arr[0] * arr[0]) + (arr[1] * arr[1]) < (arr[2] * arr[2]))) cout << "Obtuse";
else if(((arr[0] * arr[0]) + (arr[1] * arr[1]) == (arr[2] * arr[2]))) cout << "Right";
else if(((arr[0] * arr[0]) + (arr[1] * arr[1]) > (arr[2] * arr[2]))) cout << "Acute";

return 0;
}

第二題:最大和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n,m,sum = 0,k = 0;
int s[21][21],msum[21];
cin >> n >> m;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
cin >> s[i][j];
}
}
for(int i = 0;i < n;i++){
int temp = 0;
for(int j = 0;j < m;j++){
if(s[i][j] > temp) temp=s[i][j];
}
msum[i] = temp;
}
for(int i= 0;i < n;i++){
sum+=msum[i];
}
cout << sum << endl;
for(int i = 0;i < n;i++){
if(sum%msum[i] == 0) continue;
else msum[i] = 300;
}
for(int i = 0;i < n;i++){
if(msum[i] != 300){
cout << msum[i];
if(i != n-1) cout << " ";
k = 1;
}
}
if(k == 0) cout << "-1";

return 0;
}

第三題:定時K彈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
using namespace std;

int main() {
int n, m, k;
cin >> n >> m >> k;
vector<int> vec;
for(int i = 0;i < n;i++)
vec.push_back(i);
int index = 0;
for(int i = 0;i < k;i++){
index = (index+m-1) % vec.size();
vec.erase(vec.begin() + index);
index %= vec.size();
}
cout << vec[index] + 1 << endl;

return 0;
}

105/3

第一題:成績指標

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> vec,pass,fail;
int num,temp,minelement,maxelement,length;
cin >> num;
for(int i = 0;i < num;i++){
cin >> temp;
vec.push_back(temp);
}
sort(vec.begin(),vec.end());
for(int i = 0;i < num;i++){
cout << vec[i] << " ";
}
for(int i = num-1;i >= 0;i--){
if(vec[i] >= 60) pass.push_back(vec[i]);
if(vec[i] < 60) fail.push_back(vec[i]);
}
cout << endl;
if(pass.empty()){
maxelement = *max_element(fail.begin(),fail.end());
cout << maxelement << endl;
cout << "worst case" << endl;
return 0;
}
if(fail.empty()){
minelement = *min_element(pass.begin(),pass.end());
cout << "best case" << endl;
cout << minelement << endl;
return 0;
}
minelement = *min_element(pass.begin(),pass.end());
maxelement = *max_element(fail.begin(),fail.end());
if(fail.empty() == false && pass.empty() == false)
cout << maxelement << '\n' << minelement << endl;
return 0;
}

第二題:矩陣轉換

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <stack>
using namespace std;
void flip(int arr[100][100],int &r,int &c);
void change(int arr[100][100],int r,int c);//up and down
int main(){
int r,c,m;
while(cin >> r >> c >> m){
int arr[100][100];
for(int i = 0;i < r;i++){
for(int j = 0;j < c;j++){
cin >> arr[i][j];
}
}
stack<int> s;
for(int i = 0;i < m;i++){
int tmp;
cin >> tmp;
s.push(tmp);
}
int l = s.size();
for(int i = 0;i < l;i++){
if(s.top() == 0) flip(arr,r,c);
else change(arr,r,c);
s.pop();
}
cout << r << " " << c << endl;
for(int i = 0;i < r;i++){
for(int j = 0;j < c;j++){
cout << arr[i][j];
if(j != c-1) cout << " ";
}
cout << endl;
}
}
return 0;
}
void flip(int arr[100][100],int &r,int &c){//旋轉
int temp[100][100];
for(int i = 0;i < r;i++){
for(int j = 0;j < c;j++){
temp[c-j-1][i] = arr[i][j];
}
}
for(int i = 0;i < c;i++){
for(int j = 0;j < r;j++){
arr[i][j] = temp[i][j];
}
}
int t = c;
c = r;
r = t;
}
void change(int arr[100][100],int r,int c){
int temp[100][100];
for(int i = 0;i<r;i++){
for(int j = 0;j < c;j++){
temp[r-i-1][j] = arr[i][j];
}
}
for(int i = 0;i < r;i++){
for(int j = 0;j < c;j++){
arr[i][j] = temp[i][j];
}
}
}

第三題:線段覆蓋長度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <algorithm>
using namespace std;
struct node{
int a;
int b;
};
bool cmp(node x,node y){
if(x.a == y.a) return x.b < y.b;
else return x.a < y.a;
}
node c[10001];
int main(){
int n,big,small,ans = 0;
cin >> n;
for(int i = 0;i < n;i++)
cin >> c[i].a >> c[i].b;
sort(c,c+n,cmp);
for(int i = 0;i < n;i++){
small = c[i].a;
big = c[i].b;
while((i+1 < n) && c[i+1].a < big){
if(c[i+1].b <= big){
i++;
}
else{
big = c[i+1].b;
i++;
}
}
ans = ans + big - small;
}
cout << ans;

return 0;
}
CATALOG
  1. 1. APCS實作
    1. 1.1. Default code v1
    2. 1.2. My default code
      1. 1.2.1. About pragma
      2. 1.2.2. More about pragma
    3. 1.3. 111/01
      1. 1.3.1. 第一題:程式交易
      2. 1.3.2. 第二題:贏家預測
      3. 1.3.3. 第四題:牆上海報
    4. 1.4. 110/9
      1. 1.4.1. 第三題:幸運數字
    5. 1.5. 109/10
      1. 1.5.1. 第一題:人力分配
      2. 1.5.2. 第二題:人口遷移
    6. 1.6. 108/7
      1. 1.6.1. 第一題:購物車
      2. 1.6.2. 第二題:骰子
    7. 1.7. 108/6
      1. 1.7.1. 第一題:籃球比賽
    8. 1.8. 108/2
      1. 1.8.1. 第一題:合成函數
    9. 1.9. 107/10
      1. 1.9.1. 第二題:子集合的和
      2. 1.9.2. 第三題:二維黑白影像編碼
    10. 1.10. 107/02
      1. 1.10.1. 第三題:支點切割
    11. 1.11. 106/10
      1. 1.11.1. 第一題:邏輯運算子
      2. 1.11.2. 第二題:交錯字串
      3. 1.11.3. 第三題:樹的高度與根
    12. 1.12. 106/3
      1. 1.12.1. 第一題:秘密差
      2. 1.12.2. 第二題:小群體
      3. 1.12.3. 第三題:數字龍捲風
      4. 1.12.4. 第四題:基地台
    13. 1.13. 105/10
      1. 1.13.1. 第一題:三角形辨別
      2. 1.13.2. 第二題:最大和
      3. 1.13.3. 第三題:定時K彈
    14. 1.14. 105/3
      1. 1.14.1. 第一題:成績指標
      2. 1.14.2. 第二題:矩陣轉換
      3. 1.14.3. 第三題:線段覆蓋長度