# APCS 衝刺班
## 筆記
* 萬用表頭: `#include <bits/stdc++.h>`
* 加速運行:
```
ios::sync_with_stdio(0);
cin.tie(0);
```
* `cin` 和 `scanf` / `sscanf` 混用時不可寫上述兩行
* int to string: `to_string()`
* string to int: `stoi()`
* 類似py的`map()`的功能: `sscanf(str, "%d:%d:%d", &var1, &var2, &var3)`
* 相關概念用法
| 輸入用符號 | 含意 |
| -------- | -------- |
| `%d` |十進位制有符號整數|
| `%u` |進位制無符號整數|
| `%f` |浮點數|
| `%s` |字串|
| `%c` |單個字元|
| `%p` |指標的值|
| `%e` |指數形式的浮點數|
| `%x`,` %X` |無符號以十六進位制表示的整數 |
| `%0` |無符號以八進位制表示的整數|
| `%g` |自動選擇合適的表示法|
| `%ld` |表示輸出long int|
| `%ld` |表示輸出double|
* 取得整行
```
string s;
getline (cin, s);
// type of s is string
```
或
```
char cs[256];
cin.getline (cs, sizeof(cs));
// type of cs is char[]
```
* 字串相關
```cpp=
s.size()和s.length() 會傳回字串的長度
s[0]指的是字串的第一個字元，s[s.size()-1]指的是字串的最後一個字元
isalpha(字元x); //判斷是不是a~z，A~Z，傳回true或false
isdigit(字元x); //判斷是不是0~9，傳回true或false
isupper(字元x); //判斷是不是大寫字母，傳回true或false
islower(字元x); //判斷是不是小寫字母，傳回true或false
toupper(字元x); //轉成大寫字母
tolower(字元x); //轉成小寫字母
reverse(s.begin(), s.end()); //將字串s反轉
s.find('a'); //傳回字元a在字串s中第1次被發現的位置(引索值從0開始)
" "雙引號，括起來的是字串，可以是很多個字元，例如："abc123"
' ' 單引號，括起來的是字元，只能放1個，例如：'a'或'1'
```
## a096: 時間差計算
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
char str[10];
int h, m, s;
while( cin.getline(str,10) ){
sscanf(str, "%d:%d:%d", &h, &m, &s);
int t1 = h*3600 + m*60 + s;
cin.getline(str,10);
sscanf(str, "%d:%d:%d", &h, &m, &s);
int t2 = h*3600 + m*60 + s;
int dif = (86400 + t2 - t1) % 86400;
string h = to_string(dif/3600);
string m = to_string( (dif%3600)/60 );
string s = to_string( (dif%3600)%60 );
if( h.length() == 1 ){
h = '0' + h;
}
if( m.length() == 1 ){
m = '0' + m;
}
if( s.length() == 1 ){
s = '0' + s;
}
cout<< h << ':' << m << ':' << s;
}
return 0;
}
```
## a064: 成績指標
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int times;
cin>>times;
int arr[times];
for(int i=0; i<times; i++){
cin>>arr[i];
}
sort(arr, arr+times);
if(arr[0] >= 60){ //best
for(int i=0; i<times; i++){
cout<<arr[i]<<" ";
}
cout<<endl;
cout<<"best case"<<endl;
cout<<arr[0]<<endl;
}else if(arr[times-1] < 60){ //worst
for(int i=0; i<times; i++){
cout<<arr[i]<<" ";
}
cout<<endl;
cout<<arr[times-1]<<endl;
cout<<"worst case"<<endl;
}else{
for(int i=0; i<times; i++){
cout<<arr[i]<<" ";
}
cout<<endl;
for(int i=0; i<times; i++){
if(arr[i] < 60 && arr[i+1] >= 60){
cout<<arr[i]<<endl;
cout<<arr[i+1]<<endl;
}
}
}
}
```
## a104: 雪花片片
聽不懂 還沒寫
## a144: 找出最小的完全平方
```cpp=
#include <bits/stdc++.h>
using namespace std;
bool even( long long a ) {
while( a > 0 ) {
if( ( a % 10 ) % 2 == 1 ) return false;
else a /= 10;
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n , k;
cin >> n;
while( n-- ) {
cin >> k;
int s = (int)sqrt( pow( 10 , k - 1 ) );
int e = (int)sqrt( pow( 10 , k ) );
for( int i = s ; i <= e ; i++ ) {
long long a = i * i;
if( even(a) ) {
cout << a << endl;
break;
}
}
}
}
```
## a116: 一起回家的日子
```cpp=
#include <bits/stdc++.h>
using namespace std;
bool check_year(int year){
if ( (year % 4 == 0) && (year % 100 != 0) || (year % 400 == 0) ) return true;
return false;
}
int main() {
int n, a;
cin>>n;
cin>>a;
n--;
while(n){
int x; cin>>x;
a = a * x / __gcd(a, x);
n--; // originally didn't write this line, resulting in CE
}
char date[12];
int month_days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
scanf("%s", date);
int y, m ,d;
sscanf(date, "%d/%d/%d", &y, &m, &d);
d += a;
while( d > month_days[m] ){
d -= month_days[m];
if( m==12 ){
y++; m=1;
}else if( m<12 && m>0 ){
if( check_year(y) && m==2 ) d--;
m++;
}
}
cout<<y <<"/";
if( m<10 ) cout<<0;
cout<<m <<"/";
if(d<10) cout<<0;
cout<<d;
}
```
## a157: 費波那契數列
```cpp=
#include <bits/stdc++.h>
using namespace std;
int fib( int d ) {
if ( d == 0 ) return 0;
if ( d == 1 ) return 1;
return fib(d - 1) + fib(d - 2);
}
int main() {
ios::sync_with_stdio(false);
int n;
while( cin >> n ) cout << fib(n) << endl;
}
```
## a117: 三色河內塔
WRONG 沒考慮三色
```cpp=
#include <bits/stdc++.h>
using namespace std;
int cnt = 0;
void move_all(int n, char from, char to, char by){
if(n <= 0) return;
move_all(n-1, from, by, to);
cout<< "ring " << n << " : " << from << " => " << to << '\n';
cnt++;
move_all(n-1, by, to, from);
}
void move(int n, char from, char to, char by){
if(n <= 0) return;
move_all(n-1, from, by, to);
cout << "ring " << n << " : " << to << " => " << by << '\n';
cnt++;
move(n-2, by, from, to);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n; cin>>n;
move(n, 'A', 'C', 'B');
cout<< "共需" << cnt << "個移動";
return 0;
}
```
## a118: 指數2^k的四個自然數平方和之所有表示法
```cpp=
#include <bits/stdc++.h>
using namespace std;
int sq[65536] = {};
int solutions, num[4];
void solve(int remain, int id){
if( id == 3 ){
int n = sqrt(remain);
if( sq[n] == remain ){
solutions++;
num[3] = n;
cout<<num[0]<<' '<<num[1]<<' '<<num[2]<<' '<<num[3]<<"\n";
}
return;
}
int lbound;
if( id > 0 ) lbound = num[id - 1];
else lbound = 1;
int ubound = sqrt( remain / ( 4 - id ) );
for( int i = lbound ; i <= ubound ; i++ ) {
num[id] = i;
solve( remain - sq[i] , id + 1 );
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int k;
for( int i = 1 ; i < 65536 ; i++ ) sq[i] = i * i;
cin >> k;
solutions = 0;
solve( 1 << k , 0 );
if( solutions == 0 ) cout << 0;
}
```
## a147: 促銷活動
NA (97%)
```cpp=
#include <iostream>
using namespace std;
void discount(int p1, int p2){
if( p1 == p2 ){
p2 = p1 / 2;
}
cout << "Price after discount:" << endl;
cout << p1 << " " << p2 << endl;
return;
}
int main(){
double p1, p2;
cout << "Original price:" << endl;
cin >> p1 >> p2;
discount(p1, p2);
return 0;
}
```
## a159: 錯誤更正
```cpp=
#include <bits/stdc++.h>
using namespace std;
int a[100][100];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
while( cin >> n ) {
if( n == 0 ) return 0;
int rsum[100] = {0} , csum[100] = {0};
for( int i = 0 ; i < n ; i++ ) {
for( int j = 0 ; j < n ; j++ ) {
cin >> a[i][j];
rsum[i] += a[i][j];
csum[j] += a[i][j];
}
}
int rcnt = 0 , ccnt = 0;
int ci = -1 , cj = -1;
for( int i = 0 ; i < n ; i++ ) {
if( rsum[i] % 2 ) {
rcnt++;
ci = i;
}
if( csum[i] % 2 ) {
ccnt++;
cj = i;
}
}
if( ( rcnt == 0 ) && ( ccnt == 0 ) ) cout << "OK\n";
else if( ( rcnt == 1 ) && ( ccnt == 1 ) ) cout << "Change bit (" << ci + 1 << ',' << cj + 1 << ')' << endl;
else cout << "Corrupt" << endl;
}
}
```
## a105: 爺爺種樹
```cpp=
#include <bits/stdc++.h>
using namespace std;
int t[501][501];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n , m , row;
cin >> n >> m >> row;
int r1 , c1 , r2 , c2;
memset( t , 0 , sizeof(t) );
for( int i = 0 ; i < row ; i++ ) {
cin >> c1 >> r1 >> c2 >> r2;
int dr = r2 - r1 , dc = c2 - c1;
if( dr > 0 ) dr = 1;
else if( dr < 0 ) dr = -1;
if( dc > 0 ) dc = 1;
else if( dc < 0 ) dc = -1;
t[r2][c2] = 1;
if( r1 == r2 ) {
for( int c = c1 ; c != c2 ; c += dc ) t[r1][c] = 1;
} else {
for( int r = r1 , c = c1 ; r != r2 ; r += dr , c += dc ) {
t[r][c] = 1;
}
}
}
int tsum = 0;
for( int r = 1 ; r <= m ; r++ ) {
for( int c = 1 ; c <= n ; c++ ) tsum += t[r][c];
}
cout << tsum;
}
```
## a106: 冰果遊戲
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n;
char name[100] = {0} , line[100][10] = {0};
pair<int , int> mp[100][16];
bool check( int i , int p ) {
int r = mp[i][p].first;
int c = mp[i][p].second;
line[i][r]++;
if( line[i][r] == 4 ) return true;
line[i][c + 4]++;
if( line[i][c + 4] == 4 ) return true;
if( ( r + c ) == 3 ) {
line[i][8]++;
if( line[i][8] == 4 ) return true;
}
if( r == c ) {
line[i][9]++;
if( line[i][9] == 4 ) return true;
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
char ch;
int v;
cin >> ch >> n;
for( int i = 0 ; i < n ; i++ ) {
cin >> name[i];
for( int j = 0 ; j < 16 ; j++ ) {
cin >> v;
mp[i][v].first = j / 4;
mp[i][v].second = j % 4;
}
}
char cp;
int p , cnt = 16;
bool stop = false;
cin >> cp;
while( cnt-- ) {
cin >> p;
cout << p << " ";
for( int i = 0 ; i < n ; i++ ) {
if( check( i , p ) ) {
cout << name[i] << " ";
stop = true;
}
}
if( stop ) return 0;
}
}
```
## a107: 加密解密
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;
string a = "abcdefghijklmnoprstuvwxyz";
string b = "EXAMPLBCDFGHIJKNORSTUVWYZ";
int main(){
int n;
string s;
cin>>n;
getline(cin, s); // read enter
getline(cin, s);
reverse(s.begin(), s.end());
for(int i=0; i<s.size(); i+=2){
string f, t;
if( s[0]>='a' && s[0]<='z' ){
f = a; t = b;
}else{
f = b; t = a;
}
int p1 = f.find(s[i]);
int p2 = f.find(s[i+1]);
int i1 = p1 / 5;
int j1 = p1 % 5;
int i2 = p2 / 5;
int j2 = p2 % 5;
cout<<t[i1*5 + j2]<<t[i2*5 + j1];
}
}
```
## a065: 秘密差
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
string x;
while(cin>>x){
int ans = 0, sign = 1;
for(int i=0; i<x.size(); i++){
ans += (x[i] - '0') * sign;
sign *= -1;
}
cout<<abs(ans)<<'\n';
}
}
```
## a067: ROT13
```cpp=
#include <iostream>
using namespace std;
int main(){
string s;
while(getline(cin, s)){
for(auto c: s){ // get each char c from s
if( isupper(c) ){
cout<<(char)( (c-'A'+13) % 26 + 'A');
}else if( islower(c) ){
cout<<(char)( (c-'a'+13) % 26 + 'a');
}else cout<<c;
}
}
}
```
## a109: 跑長編碼與資料壓縮
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
string s , binary[8] = { "000" , "001" , "010" , "011" , "100" , "101" , "110" , "111" };
cin >> n;
cin.ignore();
while( n-- ) {
getline( cin , s );
string t = "";
int ori = s.length();
int after = 0;
int times = 1;
char ch = s[0];
if( ch != '0' && ch != '1' ) {
cout << "-1" << endl;
continue;
}
for( int i = 1 ; i <= s.length() ; i++ ) {
if( i != s.length() && s[i] != '0' && s[i] != '1' ) {
after = -1;
break;
}
if( s[i] != ch ) {
t += ch;
t += binary[times];
t += " ";
times = 1;
ch = s[i];
after += 4;
} else {
times++;
if( times == 7 ) {
t += ch;
t += binary[times];
t += " ";
times = 1;
after += 4;
ch = s[i + 1];
i++;
}
}
}
if( after == -1 ) cout << "-1" << endl;
else cout << t << setprecision(0) << fixed << (double)after * 100 / ori << "%" << endl;
}
}
```
## a105 計算字串間隔距離
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
string s;
char ch;
cin >> s >> ch;
int a1;
ch = toupper(ch);
for( int i = 0 ; i < s.length() ; i++ ) {
if( toupper(s[i]) == ch ) {
a1 = i;
break;
}
}
int a2;
for( int i = a1 + 1 ; i < s.length() ; i++ ) {
if( toupper(s[i]) == ch ) {
a2 = i;
cout << a2 - a1 << ' ';
a1 = a2;
}
}
}
```
## a110: 棒球遊戲
```cpp=
#include <bits/stdc++.h>
using namespace std;
map < int , queue<string> > mp;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int a , b;
for( int i = 0 ; i < 9 ; i++ ) {
cin >> a;
string s;
while( a-- ) {
cin >> s;
mp[i].push(s);
}
}
cin >> b;
int out = 0;
int b1 = 0 , b2 = 0 , b3 = 0 , b4 = 0;
int score = 0;
int n = -1;
while(1) {
int t = 0;
n = ( n + 1 ) % 9;
string hit = mp[n].front();
mp[n].pop();
if( hit == "SO" || hit == "GO" || hit == "FO" ) {
out++;
if( out == b ) break;
if( out % 3 == 0 ) {
b1 = b2 = b3 = b4 = 0;
continue;
}
} else if( hit == "HR" ) t = 4;
else t = hit[0] - '0';
for( int i = 1 ; i <= t ; i++ ) {
b4 = b3;
b3 = b2;
b2 = b1;
if( i == 1 ) b1 = 1;
else b1 = 0;
if( b4 == 1 ) score++;
}
}
cout << score;
}
```
## a180: 多邊形面積
```cpp=
#include <bits/stdc++.h>
using namespace std;
struct Coor{
double x;
double y;
};
int main(){
int n;
Coor coor[100];
cin>>n;
for(int i=0; i<n; i++){
cin >> coor[i].x >> coor[i].y;
}
double area;
for(int i=0; i<n; i++){
if( i== n-1 ){
area += (coor[i].x) * (coor[0].y) - (coor[0].x) * (coor[i].y);
}else{
area += (coor[i].x) * (coor[i+1].y) - (coor[i+1].x) * (coor[i].y);
}
}
area = abs(0.5 * area);
cout<< setprecision(2) << fixed << area;
}
```
## a113: 99遊戲
```cpp=
#include <bits/stdc++.h>
using namespace std;
map < int , queue<string> > mp;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
for( int i = 0 ; i < 4 ; i++ ) {
char x;
cin >> x;
for( int j = 0 ; j < 13 ; j++ ) {
string s;
cin >> s;
mp[x - 'A'].push(s);
}
}
int id = 0;
int dir = 1;
int sum = 0;
while( sum <= 99 ) {
string card = mp[id].front();
if( card == "A" ) sum = 0;
else if( card == "4" ) dir *= -1;
else if( card == "5" ) ;
else if( card == "10" ) {
sum += 10;
if( sum > 99 ) sum -= 20;
} else if( card == "J" ) ;
else if( card == "Q" ) {
sum += 20;
if( sum > 99 ) sum -= 40;
}
else if( card == "K" ) sum = 99;
else {
sum += card[0] - '0';
if( sum > 99 ) {
cout << char( 'A' + id ) << endl << mp[id].size() - 1 << endl;
break;
}
}
mp[id].pop();
if( mp[id].empty() ) {
cout << char( 'A' + id ) << endl << sum << endl;
break;
}
id = ( id + dir + 4 ) % 4;
}
}
```
## a111: 排隊
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
int t[1000][3];
int lineup = 0;
int ans = 0;
int now_service = 0;
cin >> n >> t[0][0] >> t[0][1];
t[0][2] = t[0][0] + t[0][1];
for( int i = 1 ; i < n ; i++ ) {
cin >> t[i][0] >> t[i][1];
if( t[i][0] < t[i - 1][2] ) {
t[i][2] = t[i - 1][2] + t[i][1];
} else {
t[i][2] = t[i][0] + t[i][1];
}
if( t[i][0] >= t[now_service][2] ) {
ans = max( ans , lineup );
while( t[i][0] >= t[now_service][2] ) {
if( now_service == i ) break;
lineup--;
now_service++;
}
}
if( t[i][0] < t[now_service][2] ) {
lineup++;
}
}
ans = max( ans , lineup );
cout << ans;
}
```
## a112: 動物數量統計
```cpp=
#include <bits/stdc++.h>
using namespace std;
map < string , queue< pair< string , int > > > mp;
int main() {
int n;
vector <string> pcmp;
cin >> n;
while( n-- ) {
string an , p;
int qu , idx;
cin >> an >> qu >> p;
idx = find( pcmp.begin() , pcmp.end() , p ) - pcmp.begin();
if( idx == pcmp.size() ) pcmp.push_back(p);
mp[p].push( {an , qu} );
}
for( auto i : pcmp ) {
cout << i << ":";
map < string , int > sta;
vector <string> almp;
while( !mp[i].empty() ) {
string an = mp[i].front().first;
int qu = mp[i].front().second;
mp[i].pop();
int idx = find( almp.begin() , almp.end() , an ) - almp.begin();
if( idx == almp.size() ) almp.push_back(an);
if( sta.count(an) == 0 ) sta[an] = qu;
else sta[an] += qu;
}
bool comma = false;
for( auto j : almp ) {
if( comma ) cout << ",";
cout << j << " " << sta[j];
comma = true;
}
cout << endl;
}
}
```
## a151: 後序式求值
```cpp=
#include <bits/stdc++.h>
using namespace std;
map < string , queue< pair< string , int > > > mp;
int main() {
string s;
while( getline(cin, s) ){
stack<int> st;
int ans = 0;
for(int i=0; i<s.size(); i++){
if( isdigit(s[i]) ){
st.push( s[i] - '0' );
}else {
int a = st.top();
st.pop();
int b = st.top();
st.pop();
if( s[i] == '+' ) st.push( b + a );
else if( s[i] == '-' ) st.push( b - a );
else if( s[i] == '*' ) st.push( b * a );
else if( s[i] == '/' ) st.push( b / a );
else if( s[i] == '%' ) st.push( b % a );
}
}
cout << st.top() << endl;
}
}
```
## a120: 中置式轉後置式
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
map < char , int > mp = { {'+' , 1} , { '+' , 1 } };
mp['+'] = 1;
mp['-'] = 1;
mp['*'] = 2;
mp['/'] = 2;
string s;
cin >> s;
stack <char> st;
for( int i = 0 ; i < s.size() ; i++ ) {
if( s[i] == '(' ) st.push( '(' );
else if( s[i] == ')' ) {
while( st.top() != '(' ) {
cout << st.top();
st.pop();
}
st.pop();
} else if( s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
while( !st.empty() && mp[st.top()] >= mp[s[i]] ) {
cout << st.top();
st.pop();
}
st.push(s[i]);
} else {
cout << s[i];
}
}
while(!st.empty()) {
cout << st.top();
st.pop();
}
}
```
## a164: 團體佇列
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int t , c = 0;
while( cin >> t ) {
if( t == 0 ) break;
map < int , int > mp;
for( int i = 0 , n , x ; i < t ; i++ ) {
cin >> n;
while( n-- ) {
cin >> x;
mp[x] = i;
}
}
queue <int> Q;
queue <int> t[1000];
int in[1000] = {0};
string cmd;
cout << "Scenario #" << ++c << endl;
while( cin >> cmd ) {
int x;
if( cmd[0] == 'E' ) {
cin >> x;
if( in[mp[x]] == 0 ) Q.push( mp[x] );
t[mp[x]].push(x);
in[mp[x]]++;
} else if( cmd[0] == 'D' ) {
int team = Q.front();
cout << t[team].front() << endl;
t[team].pop();
in[team]--;
if( in[team] == 0 ) Q.pop();
} else if( cmd[0] == 'S' ) {
cout << endl;
break;
}
}
}
}
```
## a076: 二元搜尋樹高度
```cpp=
#include <bits/stdc++.h>
using namespace std;
bool tree[2049];
int D;
int drop( int v ) {
if( v >= 1 << ( D - 1 ) ) return v;
tree[v] = !tree[v];
if( tree[v] ) return drop( 2 * v );
else return drop( 2 * v + 1 );
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t , I;
cin >> t;
while( t-- ) {
memset( tree , 0 , sizeof(tree) );
cin >> D >> I;
int ans;
for( int i = 0 ; i < I ; i++ ) ans = drop(1);
cout << ans << endl;
}
}
```
## a122: 血緣關係
solution 1
```cpp=
#include <bits/stdc++.h>
using namespace std;
map <int , vector<int>> G;
int d[100005];
void dfs( int x , int fa ) {
for( auto i : G[x] ) {
if( i != fa ) {
d[i] = d[x] + 1;
dfs( i , x );
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int a , b;
for( int i = 1 ; i <= n - 1 ; i++ ) {
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
d[0] = 0;
dfs( 0 , 0 );
int u = 0;
for( int i = 1 ; i < n ; i++ ) u = ( d[i] > d[u] ) ? i : u;
d[u] = 0;
dfs( u , u );
int v = u;
for( int i = 0 ; i < n ; i++ ) v = ( d[i] > d[v] ) ? i : v;
cout << d[v];
}
```
solution 2
```cpp=
#include <bits/stdc++.h>
using namespace std;
map <int , vector<int>> T;
int ans = 0;
int dfs( int x , int px ) {
int h1 = 0 , h2 = 0;
for( auto i : T[x] ) {
int h = dfs( i , x ) + 1;
if( h > h1 ) {
h2 = h1;
h1 = h;
} else if( h > h2 ) h2 = h;
}
ans = max( ans , h1 + h2 );
return h1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n , a , b;
cin >> n;
vector <int> fa( n , -1 );
for( int i = 1 ; i <= n - 1 ; i++ ) {
cin >> a >> b;
T[a].push_back(b);
fa[b] = a;
}
int root = 0;
while(fa[root] != -1 ) root++;
dfs( root , root );
cout << ans;
}
```
## a123 樹狀圖分析
```cpp=
#include <bits/stdc++.h>
using namespace std;
map <int , vector<int>> T;
vector <int> fa( 100005 , -1 );
int h[100005];
void dfs( int x ) {
int mx = 0;
for( auto p : T[x] ) {
dfs(p);
mx = max( mx , h[p] + 1 );
}
h[x] = mx;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n , k , v;
cin >> n;
for( int i = 1 ; i <= n ; i++ ) {
cin >> k;
for( int j = 0 ; j < k ; j++ ) {
cin >> v;
T[i].push_back(v);
fa[v] = i;
}
}
int root = 1;
while( fa[root] != -1 ) root++;
dfs(root);
int ans = 0;
for( int i = 1 ; i <= n ; i++ ) ans += h[i];
cout << root << endl << ans;
}
```
## a051: 城市旅遊
```cpp=
#include <bits/stdc++.h>
using namespace std;
char G[801][10001];
int n;
bool dfs( int from , int to ) {
if( G[from][to] == '1' ) return true;
for( int i = 1 ; i <= n ; i++ ) {
if( G[from][i] == '1' ) {
G[from][i] = -1;
return dfs( i , to );
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int m , x , y , a , b;
cin >> n >> m;
memset( G , 0 , sizeof(G) );
for( int i = 0 ; i < m ; i++ ) {
cin >> x >> y;
G[x][y] = '1';
}
cin >> a >> b;
if( dfs( a , b ) ) cout << "Yes";
else cout << "No";
}
```
## a103: 小群體
```cpp=
#include <bits/stdc++.h>
using namespace std;
int a[50001] = {0};
bool visited[50001] = {0};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for( int i = 0 ; i < n ; i++ ) cin >> a[i];
int next , ans = 0;
for( int i = 0 ; i < n ; i++ ) {
if( !visited[i] ) ans++;
while( !visited[i] ) {
next = a[i];
visited[i] = true;
i = next;
}
}
cout << ans;
}
```
## a124: 二分圖
```cpp=
#include <bits/stdc++.h>
using namespace std;
vector <int> G[100001];
int color[100001] , cnt[2];
bool dfs( int x , int c ) {
color[x] = c;
cnt[c]++;
bool result = true;
for( int i : G[x] ) {
if( color[i] == color[x] ) return false;
else if( color[i] == -1 ) result &= dfs( i , !c );
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n , m , ans = 0;
cin >> n >> m;
memset( color , -1 , sizeof(color) );
for( int i = 0 , a , b ; i < m ; i++ ) {
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
for( int i = 0 ; i < n ; i++ ) {
if( color[i] == -1 ) {
cnt[0] = cnt[1] = 0;
if( !dfs( i , 0 ) ) {
cout << 0;
return 0;
}
ans += min( cnt[0] , cnt[1] );
}
}
cout << ans;
}
```
## a126: 馬步問題
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n;
bool visit[3][10] , found;
int answer[30];
int temp[30];
bool smaller() {
for( int i = 0 ; i < 3 * n ; i++ ) {
if( temp[i] < answer[i] ) return true;
else if( temp[i] > answer[i] ) return false;
}
return false;
}
bool inrange( int x , int y ) {
return x >= 0 && x < 3 && y >= 0 && y < n;
}
void dfs( int row , int col , int step ) {
int dir[8][2] = { {-2 , 1} , {-2 , -1} , {2 , 1} , {2 , -1} , {1 , 2} , {1 , -2} , {-1 , 2} , {-1 , -2} };
temp[row * n + col] = step;
visit[row][col] = true;
if( step == 3 * n ) {
if( !found || smaller() ) {
for( int i = 0 ; i < 3 * n ; i++ ) answer[i] = temp[i];
}
found = true;
return;
}
for( int i = 0 ; i < 8 ; i++ ) {
int x = row + dir[i][0];
int y = col + dir[i][1];
if( inrange( x , y ) && !visit[x][y] ) {
dfs( x , y , step + 1 );
visit[x][y] = false;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
found = false;
dfs( 0 , 0 , 1 );
if( !found ) cout << 0;
else {
for( int i = 0 ; i < 3 * n ; i++ ) cout << answer[i] << ' ';
}
}
```
## a127: 連號或不連號
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
while( cin>>n ){
set <int> st;
for( int i=0, x; i<n; i++ ){
cin>>x;
st.insert(x);
}
int mn = *st.begin();
int mx = *(--st.end()); //st.end()是st結束的位置 所以最大值是st.end()的前一個位置
if( st.size() == mx - mn + 1) cout<<mn<<' '<<mx<<' '<<"yes";
else cout<< mn<<' '<<mx<<' '<<"no";
}
}
```
## 字元頻率
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
bool cmp( pair<int , int> x , pair<int , int> y ) {
if( x.second == y.second ) return ( x.first > y.first );
else return ( x.second < y.second );
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
string s;
while( getline( cin , s ) ) {
map <int , int> mp;
vector <pair <int , int>> vec;
for( auto c : s ) mp[c]++;
for( auto x : mp ) vec.push_back(x);
sort( vec.begin() , vec.end() , cmp );
for( auto v : vec ) cout << v.first << ' ' << v.second << endl;
}
}
```cpp=
#include <bits/stdc++.h>
using namespace std;
int f[10001];
map <int , set<int>> mp;
void eat( int win , int lose ) {
for( auto i : mp[lose] ) mp[win].insert(i);
mp[lose].clear();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n , m;
cin >> n >> m;
fill( f , f + n + 1 , 10 );
for( int i = 1 ; i <= n ; i++ ) mp[i].insert(i);
int x = 0;
while(m--) {
int a , b , win , lose;
cin >> a >> b;
win = ( f[a] >= f[b] ) ? a : b;
lose = ( f[a] >= f[b] ) ? b : a;
f[win] += f[lose];
f[lose] = 0;
if( f[win] > f[x] ) x = win;
eat( win , lose );
}
cout << x << endl;
for( auto i : mp[x] ) cout << i << ' ';
}
```
## a129: 飛天桑妮
```cpp=
#include <bits/stdc++.h>
using namespace std;
vector <pair<int , int>> tree;
bool cmp( pair<int , int> a , pair<int , int> b ) {
if( a.first == b.first ) return ( a.second > b.second );
else return ( a.first < b.first );
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n , x , y , h;
cin >> n;
for( int i = 0 ; i < n ; i++ ) {
cin >> x >> y >> h;
tree.push_back({ x * x + y * y , h });
}
sort( tree.begin() , tree.end() , cmp );
int ans = 0 , maxh = 0;
for( int i = 0 ; i < n ; i++ ) {
maxh = max( maxh , tree[i].second );
ans = max( ans , maxh - tree[i].second );
}
cout << ans;
}
```
Sign in with Wallet
Connect another wallet