🌍 集合地點 台中火車站樓梯上去之後的大貧台 🚎
🕐 集合時間 早上 8：20🕒
✔ 攜帶錢錢 建議 1000 快以上(方便的話先給念誠車錢750 💲)
💦 攜帶物品 悠遊卡 💳
學生證 🎴(或健保卡、身分證)
口罩幾個 😷
💄 歷屆試題 據說近年網路上可以找到的不多，不過TIOJ 有 2018 的 ，根據中一中有經驗的學長現身說法，快速冪(矩陣)、區間問題(線段樹)是相對常出現的問題 💢 念誠因為實力不足、缺乏實作經驗、欠缺熱情，所以只有練習三題歷屆試題。個人認為背一下 4 行的 Floyd-Warshall 多源最短路徑演算法，縮不定可以快速撈到一些分 💔
😴 念誠有寫過的 1. 🎨 矩陣快速冪 可以先看吳教授的講義(P65) ，不懂可以問兆新學長，不過他最近很忙，可能不方便 🤗
練習題：TIOJ 2053 . 費氏數列（Fibonacci）[2018-TOI-pre]
糟糕的參考乘勢 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 <bits/stdc++.h>
using namespace std ;
#define ull unsigned long long int
#define ivec vector<ull>
const int p = 1e9 + 7 ;
/* template <typename T>
using ivec = vector<T>;
*/
ivec matrixchen ( ivec a , ivec b ) {
ivec tmp ({(( a [ 0 ] * b [ 0 ]) % p + ( a [ 1 ] * b [ 2 ]) % p ) % p ,
(( a [ 0 ] * b [ 1 ]) % p + ( a [ 1 ] * b [ 3 ]) % p ) % p ,
(( a [ 2 ] * b [ 0 ]) % p + ( a [ 3 ] * b [ 2 ]) % p ) % p ,
(( a [ 2 ] * b [ 1 ]) % p + ( a [ 3 ] * b [ 3 ]) % p ) % p });
return tmp ;
}
int main () {
ios_base :: sync_with_stdio ( 0 );
cin . tie ( 0 );
ull x1 , x2 , a , b , n ;
cin >> x1 >> x2 >> a >> b >> n ;
ivec tmat ({ 1 , 0 , 0 , 1 });
ivec ans ({ x2 , 0 , x1 , 0 });
n -= 2 ;
for ( ivec opMat ({ b , a , 1 , 0 }); n > 0 ; opMat = matrixchen ( opMat , opMat ), n >>= 1 )
if ( n & 1 ) tmat = matrixchen ( tmat , opMat );
auto tmp = matrixchen ( tmat , ans );
cout << tmp [ 0 ] << endl ;
}
2. 🎄線段樹 區間問題，我一律建議線段樹，單點修改囚區間和是可以考慮BIT喇😲，不過我不會🥰
可以先看wiwiho寫的這個 和這個東西 ，不懂可以問兆新學長，不過他最近很忙，可能不方便🤗
練習題：TIOJ 2055 . 直升機（Helicopter）[2018-TOI-pre]
糟糕的參考乘勢 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
#include <bits/stdc++.h>
#define int long long
#define maxn 1e6
#define lc(v) ((2 * v) + 1)
#define rc(v) ((2 * v) + 2)
#define onedieonedie \
ios_base::sync_with_stdio(0); \
cin.tie(0)
using namespace std ;
int st [ signed ( maxn ) * 4 ] = {};
int a [ signed ( maxn )] = {};
int ql , qr , n , minv ;
void build ( int l , int r , int v ) {
if ( l == r ) {
st [ v ] = a [ l ];
return ;
}
int m = ( l + r ) / 2 ;
build ( l , m , lc ( v ));
build ( m + 1 , r , rc ( v ));
st [ v ] = min ( st [ lc ( v )], st [ rc ( v )]);
}
void query ( int l , int r , int v ) {
if ( ql <= l && r <= qr ) {
minv = min ( st [ v ], minv );
return ;
}
int m = ( l + r ) / 2 ;
if ( ql <= m ) query ( l , m , lc ( v ));
if ( qr > m ) query ( m + 1 , r , rc ( v ));
}
signed main () {
onedieonedie ;
cin >> n ;
for ( int i = 0 ; i < n ; i ++ )
cin >> a [ i ];
build ( 0 , n - 1 , 0 );
for ( int i = 0 ; i < n ; i ++ ) {
cin >> ql >> qr ;
ql -- ;
qr -- ;
minv = INT_MAX ;
query ( 0 , n - 1 , 0 );
cout << minv + 1 << '\n' ;
}
}
3. 💥 怪怪化學蹄 可以先看高中化學課本，複習怎麼看化學式，計算一下原子小精鋼有幾個，這個部分念誠很不在行，不懂可以問兆新學長，不過他最近很忙，可能不方便 🤗
練習題：TIOJ 2051 . 化學元素分析（Chemical Analysis）[2018-TOI-pre]
糟糕的參考乘勢 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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std ;
struct Atom {
string name ;
int amount ;
} atoms [ 256 ];
struct tag {
int si ;
int ei ;
int cm ; //change amount
} tags [ 256 ];
string cf ; //chemical formula 打扣也能學英文
int ca ( int & i ) {
int amount = 0 ;
while ( isdigit ( cf [ i + 1 ])) {
amount = ( cf [ i + 1 ] - '0' ) + amount * 10 ;
i ++ ;
}
return amount ;
} //count atoms
int main () {
ios_base :: sync_with_stdio ( 0 );
while ( cin >> cf ) {
int i = 0 , b = 0 , aatmp ; //brackets, atomsAmountTmp
string antmp ; //atomsNameTmp
stack < struct tag > tagSt ;
for ( int k = 0 ; k < 256 ; k ++ ) {
atoms [ k ]. name = "NULL" ;
atoms [ k ]. amount = 0 ;
tags [ k ]. si = 0 ;
tags [ k ]. ei = 0 ;
tags [ k ]. cm = 0 ;
}
while ( i < cf . length ()) {
if ( isalpha ( cf [ i ])) {
antmp = cf [ i ];
if ( isalpha ( cf [ i + 1 ]) && islower ( cf [ i + 1 ])) {
antmp += cf [ i + 1 ];
i ++ ;
}
if (( isalpha ( cf [ i + 1 ]) && isupper ( cf [ i + 1 ])) || cf [ i + 1 ] == '(' || cf [ i + 1 ] == ')' || i + 1 == cf . length ())
aatmp = 1 ;
if ( isdigit ( cf [ i + 1 ]))
aatmp = ca ( i );
atoms [ i ]. name = antmp ;
atoms [ i ]. amount = aatmp ;
} else if ( cf [ i ] == '(' ) {
struct tag tmptag ;
tmptag . si = i ;
tagSt . push ( tmptag );
} else if ( cf [ i ] == ')' ) {
tagSt . top (). ei = i ;
tagSt . top (). cm = ca ( i );
tags [ b ] = tagSt . top ();
tagSt . pop ();
b ++ ;
}
i ++ ;
}
for ( int i = 0 ; i < b ; i ++ ) {
if ( tags [ i ]. cm == 0 ) continue ;
for ( int j = tags [ i ]. si ; j < tags [ i ]. ei ; j ++ ) {
if ( atoms [ j ]. name != "NULL" )
atoms [ j ]. amount *= tags [ i ]. cm ;
}
}
map < string , int > ansA ;
map < string , int >:: iterator iter ;
for ( int i = 0 ; i < cf . length (); i ++ ) {
if ( atoms [ i ]. name != "NULL" ) {
if ( ansA . find ( atoms [ i ]. name ) != ansA . end ())
ansA [ atoms [ i ]. name ] += atoms [ i ]. amount ;
else
ansA [ atoms [ i ]. name ] = atoms [ i ]. amount ;
}
}
cout << cf << endl ;
for ( iter = ansA . begin (); iter != ansA . end (); iter ++ ) {
cout << iter -> first << ":" << iter -> second << endl ;
}
}
}
😩 趕快學啟來可能有用ㄉ東西 1. 🦕Floyd-Warshall 演算法 可以先看一些網路文章，如果不懂得話，建議去看 YT 上面ㄉ教學影片，像念誠是看一個印度人學的 🦧 TOI 線上練習那邊也有簡報 😋
練習題：e792: a3.旅行(Trip) [2019-TOI-線上練習賽]
糟糕的參考乘勢 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
#include <bits/stdc++.h>
using namespace std ;
int main () {
bool c [ 201 ][ 201 ] = { 0 }; //Connected
int n , m , q ;
for ( int i = 0 ; i < n ; i ++ ) {
c [ i ][ i ] = 1 ;
}
cin >> n >> m >> q ;
while ( m -- ) {
int a , b ;
cin >> a >> b ;
c [ a ][ b ] = 1 ;
}
for ( int k = 0 ; k < n ; k ++ ) {
for ( int i = 0 ; i < n ; i ++ ) {
for ( int j = 0 ; j < n ; j ++ ) {
c [ i ][ j ] = c [ i ][ j ] || ( c [ i ][ k ] && c [ k ][ j ]);
}
}
}
while ( q -- ) {
int a , b ;
cin >> a >> b ;
cout << ( c [ a ][ b ] ? "YES" : "NO" ) << endl ;
}
}
