前言

高一選修程式設計期末考

Scoreboard

scoreboard

考試過程

???

早上下雨 穿拖鞋來的，所以光著腳考試哈哈

解題順序(min : sec)

$01:58$

$pA$

$AC$

$06:28$

$pB$

$AC$

$08:51$

$pC$

$AC$

$13:17$

$pD$

$WA$

$18:48$

$pD$

$AC(secondsubmission)$

總計 :

$19$

$mins$

$$

$4$

$AC$

$$

$1$

$WA$

題目

題目總覽

Sa 中譯
pA - AtCoder cf_2015_morning_easy_b - ヘイホー君と置き換え
pB - AtCoder abc341_c - Takahashi Gets Lost
pC - AtCoder abc226_b - Counting Arrays
pD - AtCoder abc264_d - "redocta".swap(i,i+1)

pA - AtCoder cf_2015_morning_easy_b - ヘイホー君と置き換え

題意 :
給一數

$N$ 與 一長度為

$N$ 的字串

$S$
假如

$S$ 為兩個相同的子字串所串接而成
稱為平方字串
今要把

$S$ 變為平方字串能使用以下操作

• 選擇一個整數
  $P$ 滿足
  $1\le P\le N$ ，再選擇一個英文小寫字母
  $C$ ，之後將
  $S$ 的第
  $P$ 個字替換為
  $C$。

求最小操作輛量，假如

$S$ 無法變為平方字串則輸出-1

範例輸入1 :

8
abacbabc

範例輸出1 :

3

範例輸入2 :

5
abcde

範例輸出2 :

-1

想法 :
假如

$S$ 的字串長度

$|S|$ 為奇數
則不可能成為平方字串
而最小操作數量可以得知，只要將前後子字串同步即可

---

code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	
	int n; cin >> n;
	string s; cin >> s;
	if(n%2) {cout << "-1\n"; return 0;}
	int ans = 0;
	for(int i = 0; i < s.size()/2; i++) {
		if(s[i] != s[i+s.size()/2]) {
			ans++;
		}
	}
	cout << ans << '\n';
}

---

解題心得 :
大概是水題ㄅ
一分鐘就解掉了

pB - AtCoder abc341_c - Takahashi Gets Lost

題意 :
給三數

$H$

$W$

$N$ 分別代表地圖的列數與行數 及 接下來的指示自串

$S$ 的長度
接著輸入一字串

$S$ 代表著指示字串，L代表左，R代表右，U代表上，D代表下
接著輸入

$N$ 列 每列

$M$ 個字元 代表著地圖的東西

$A_{ij}$ ，

$(1\le i\le N，1\le j\le M)$
#代表障礙物，.代表空格

輸出有多少點能夠符合指示之行為模式

範例輸入1 :

6 7 5
LULDR
#######
#...#.#
##...##
#.#...#
#...#.#
#######

範例輸出1 :

2

範例輸入2 :

13 16 9
ULURDLURD
################
##..##.#..####.#
###.#..#.....#.#
#..##..#####.###
#...#..#......##
###.##.#..#....#
##.#####....##.#
###.###.#.#.#..#
######.....##..#
#...#.#.######.#
##..###..#..#.##
#...#.#.#...#..#
################

範例輸出2 :

6

想法 :
建表比較好做，存LRDU可以用map也可以用字串來儲存
考試的時候我是用字串儲存

---

code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
string m = "LRUD";
int h, w, n;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0 ,0};
bool chk(int i, int j, vector<string> &v, string &s) {
	for(char &c : s) {
		int id = 0;
		while(m[id] != c) {id++;}
		i += dx[id];
		j += dy[id];
		if(i < 0 || i >= h || j < 0 || j >= w) {return false;}
		if(v[i][j] != '.') {return false;}
	}
	return true;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	
	cin >> h >> w >> n;
	string s; cin >> s;
	vector<string> v(h); for(string &d : v) {cin >> d;}
	int ans = 0;
	for(int i = 0; i < h; i++) {
		for(int j = 0; j < w; j++) {
			if(v[i][j] == '.') {
				ans += chk(i, j, v, s);
			}
		}
	}
	cout << ans << '\n';
}

---

Abc 341 這場比賽我剛好有打過
所以就直接做出來了:D

pC - AtCoder abc226_b - Counting Arrays

題意 :
給一數

$N$
接下來有

$N$ 行輸入
每一行開頭會有一整數

$L_i$ 代表此數列之長度

$(1\le i\le N)$

輸出有多少種不同的數列

範例輸入1 :

4
2 1 2
2 1 1
2 2 1
2 1 2

範例輸出1 :

3

想法 :
有看到有人直接getline當作一行數列
也有人用STL解 (我是用map)
但一般陣列其實也能解
就大概sort後再找也是可以的

---

code

1. 比賽時

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	
	map<vector<int>, int> mp;
	int n; cin >> n;
	for(int i = 0; i < n; i++) {
		int l; cin >> l;
		vector<int> tmp(l);
		for(int j = 0; j < l; j++) {
			cin >> tmp[j];
		}
		mp[tmp]++;
	}
	cout << mp.size() << '\n';
}

2. 賽後想出來的

#include <bits/stdc++.h>
using namespace std;
#define ll long long
string v[200005];
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n; cin >> n;
	cin.ignore();
	for(int i = 0; i < n; i++) {
		getline(cin, v[i]);
	}
	sort(v, v+n);
	int ans = 1;
	for(int i = 0; i < n-1; i++) {
		if(v[i] != v[i+1]) {ans++;}
	}
	cout << ans << '\n';
	
}

---

有學過STL回來解的很方便ㄏㄏ

pD - AtCoder abc264_d - "redocta".swap(i,i+1)

題意 :
給一字串

$S$ 由 atcoder所組成
只能對換左右邊相鄰的兩數
求最小操作數

範例輸入1 :

redocta

範例輸出1 :

21

想法 :
看每個字元，假如不是的話從後面交換過來
一遍遍搜就過了

---

code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
string g = "atcoder";
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	
	string s; cin >> s;
	ll ans = 0;
	int id = 0;
	while(s != g) {
		if(s[id] != g[id]) {
			int i;
			for(i = id+1; i < s.size(); i++) {
				if(s[i] == g[id]) {
					break;
				}
			}
			for(int j = i; j >= id+1; j--) {
				swap(s[j], s[j-1]);
				ans++;
			}
			// cout << tmp << '\n';
		}
		id++;
	}
	cout << ans << '\n';
}

---

一開始沒看到只能交換相鄰的數
耗了很多時間QQ

總結

高一選修就這樣結束了…
自從上學期根本不知道C++怎麼寫程式的小高一
如今已經要成為高二生&資訊社社長的我
有太多太多成長發生在我的身上
這一年來刷的題目真的好多
加起來大概超過1000多題
也很佩服自己的毅力以及對資訊的熱愛
希望明年的我能更加強大，且

不忘初心!

2023/11/17 選修期中考

2023/12/29 選修期末考

2024/05/03 選修期中考

2024/06/14 選修期末考