owned this note
owned this note
Published
Linked with GitHub
# 學測後復建 練題
學測後太久沒寫題目，開個筆記紀錄一下復健過程。順便寫寫看沒寫過的AP325，後面AP325沒東西寫就隨便寫了
這份筆記是復健用，而且題目也沒很難，所以我就不像以前一樣打想法了，實作code也打得比較隨興，沒有整理。
本次練習用彰化精誠中學的judge。但這個網站題目沒有很完整，後面有些東西會去其他解題網站練習，例如TIOJ、UVA、Sprout OJ(neoj)之類的
目前累積44題
# 可以複習的題目
P-6-8 : local alignment
TIOJ 1092 : topological sort
TIOJ 1290 : dijkstra
UVa 10986 : dijkstra
UVA 11015 : Floyd-Warshall
UVa 558 : SPFA負環判斷
# P-1-1
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a135
```cpp=
#include<bits/stdc++.h>
using namespace std;
int f();
int g();
int main(){
char c;
cin >> c;
if(c == 'f'){
cout << f() <<'\n';
}
else{
cout << g() << '\n';
}
}
int f(){
int x;
string s;
cin >> s;
if(s== "f"){
x = f();
}
else if(s == "g"){
x = g();
}
else{
x = stoi(s);
}
return 2* x-1;
}
int g(){
int x, y;
string s;
cin >> s;
if(s== "f"){
x = f();
}
else if(s == "g"){
x = g();
}
else{
x = stoi(s);
}
cin >> s;
if(s== "f"){
y = f();
}
else if(s == "g"){
y = g();
}
else{
y = stoi(s);
}
return x + 2 * y - 3;
}
```
# P-1-3
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a133
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
int p[50005];
int cost = 0;
int search(int l, int r, int x){
int k = l;
for(int i = (r - l) / 2; i > 0; i /= 2){
while(k + i < r and p[k+i] <= x){
k += i;
}
}
if(p[k] - p[l] < p[r] - p[k+1]){
k ++;
}
return k;
}
void f(int l, int r){
if(r -l <= 1){
return;
}
int pp = search(l, r, (p[r] + p[l]) / 2);
if(pp == l | pp == r){
return;
}
cost += (p[r] - p[l]);
f(l, pp);
f(pp,r);
}
signed main(){
int n, L;
cin >> n >> L;
p[0] = 0;
for(int i = 1; i <= n; i++){
cin >> p[i];
}
p[n+1]=L;
f(0, n+1);
cout << cost << '\n';
}
```
# P-1-7
https://zerojudge.cchs.chc.edu.tw/Submissions
```cpp=
#include<bits/stdc++.h>
using namespace std;
int c;
int n;
int arr[30];
void f(int x, int i){
if(i >= n){
if(x % 10009 == 1){
//cout << x <<'\n';
c++;
}
return;
}
f((x * arr[i])%10009, i+1);
f(x,i+1);
}
int main(){
cin >> n;
for(int i = 0; i < n; i++){
cin >> arr[i];
}
f(1, 0);
cout << c - 1<< '\n';
}
```
# P-2-2
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a140
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
cin >> n;
int arr[n];
int sarr[n];
for(int i = 0; i < n; i++){
cin >> arr[i];
sarr[i] = arr[i];
}
sort(sarr, sarr+n);
int change[n];
change[0] = sarr[0];
int num = 1;
for(int i = 1; i < n; i++){
if(sarr[i] != sarr[i-1]){
change[num++] = sarr[i];
}
}
for(int i = 0; i < n; i++){
arr[i] = lower_bound(change, change+num, arr[i]) - change;
}
for(int i = 0 ;i < n; i++){
cout << arr[i] << ' ';
}cout << '\n';
}
```
# P-2-3
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a141
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
int p;
int pow_(int x, int y){
int r = 1;
if(y == 0)return 1;
int a = x;
while(y > 0){
if(y & 1){
r = (r * a) % p;
}
a = (a * a) % p;
y >>= 1;
}
return r;
}
signed main(){
int x, y;
cin >> x >> y >> p;
cout << pow_(x,y) << '\n';
}
```
# P-2-6
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a155
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int m ,n , k;
while(cin >> m >> n >> k){
int A[m];
set<int> st;
for(int i = 0; i < m; i++){
cin >> A[i];
}
for(int i = 0; i < n; i++){
int tmp;
cin >> tmp;
st.insert(tmp);
}
int count_ = 0;
for(int i = 0; i < m; i++){
auto b = st.find(k - A[i]);
if(b != st.end()){
count_++;
}
}
cout << count_ << '\n';
}
}
```
# P-2-11
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a162
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n, k;
cin >> n >> k;
int A[n];
for(int i = 0; i < n; i++){
cin >> A[i];
}
set<int> pre;
pre.insert(0);
int pre_sum = 0;
int closest_sum = INT_MIN;
for(int i = 0; i < n; i++){
pre_sum += A[i];
//k >= pre_sum - x -> x >= pre_sum - k
auto it = pre.lower_bound(pre_sum - k);
if(it != pre.end()){
closest_sum = max(closest_sum , pre_sum - *it);
}
pre.insert(pre_sum);
}
cout << closest_sum << '\n';
}
```
# P-3-2
https://zerojudge.cchs.chc.edu.tw/Submissions
```cpp=
#include <bits/stdc++.h>
using namespace std;
bool f(char a, char b){
if(a == '(' and b == ')'){
return 1;
}
else if(a == '[' and b == ']'){
return 1;
}
else if(a == '{' and b == '}'){
return 1;
}
else{
return 0;
}
}
void check(stack<char> &st){
if(st.size() < 2){
return;
}
char b = st.top();
st.pop();
char a = st.top();
st.pop();
// cout << a << ' '<< b << '\n';
bool flag = f(a, b);
// cout << flag << '\n';
if(flag){
check(st);
}
else{
st.push(a);
st.push(b);
return;
}
}
int main(){
string s;
while(cin >> s){
stack<char> st;
st.push(s[0]);
for(int i = 1; i < s.size(); i++){
st.push(s[i]);
check(st);
}
if(st.size() == 0){
cout << "yes" << '\n';
}
else{
cout << "no" << '\n';
}
}
}
```
# P-3-4
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a167
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
int update(vector<pair<int,int> > &st, int h){
while(h >= st[st.size()-1].first){
auto it = st.end();
it = prev(it);
st.erase(it);
}
return st[st.size()-1].second;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
int n;
cin >> n;
vector<pair<int,int> > st;
st.push_back(make_pair(INT_MAX, 0));
int ans = 0;
for(int i = 1 ; i <= n; i++){
int h;
cin >> h;
ans += i - update(st,h);
st.push_back(make_pair(h,i));
}
cout << ans << '\n';
}
```
# P-3-6
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a173
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, l;
cin >> n >> l;
map<int,int> mp;
int c[n];
int h[n];
for(int i = 0; i <n; i++){
cin >> c[i];
}
for(int i = 0; i < n; i++){
cin >> h[i];
}
mp[0] = INT_MAX;
mp[l] = INT_MAX;
for(int i = 0; i < n; i++){
mp[c[i]] = h[i];
}
int count_ = 0;
int highest = 0;
for(auto it = next(mp.begin()); it != prev(mp.end());){
// cout << it -> first << ' ' << it->second << '\n';
if(it -> first - it -> second >= prev(it) -> first or it -> first + it -> second <= next(it) -> first){
// cout <<"::"<< it -> first << ' ' << it->second << '\n';
count_++;
highest = max(highest, it -> second);
auto tmp = prev(it);
mp.erase(it);
it = tmp;
}
else{
it++;
}
}
cout << count_ << '\n' << highest << '\n';
}
```
# P-3-7
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a174
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n, k;
cin >> n >> k;
deque<int> dq;
int arr[n];
for(int i = 0; i < n; i++){
cin >> arr[i];
}
int sum = 0;
int count_ = 0;
int max_sum = 0;
for(int i = 0; i < n; i++){
dq.push_front(arr[i]);
sum += arr[i];
// cout << sum << '\n';
while(sum > k){
sum -= dq.back();
dq.pop_back();
// cout << sum << '\n';
}
if(sum == max_sum){
count_++;
}
else if(sum > max_sum){
count_ = 1;
max_sum = sum;
}
}
cout << max_sum << '\n';
cout << count_ << '\n';
}
```
# P-3-8
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a175
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
int n, k;
cin >> n >> k;
deque<int> dq;
int arr[n];
for(int i = 0; i < n; i++){
cin >> arr[i];
}
int max_gap = 0;
int maxx = INT_MIN;
int minn = INT_MAX;
map<int,int> mp;
for(int i = 0; i < n; i++){
dq.push_front(arr[i]);
maxx = max(maxx, arr[i]);
minn = min(minn, arr[i]);
mp[arr[i]] += 1;
if(i >= k){
int tmp = dq.back();
dq.pop_back();
if(mp[tmp] == 1){
mp.erase(tmp);
}
else{
mp[tmp] -= 1;
}
}
int minp = mp.begin() -> first;
int maxp = next(mp.end()) -> first;
max_gap = max(max_gap, maxp - minp);
}
cout << max_gap << '\n';
}
```
# P-3-9
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a176
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
map<int,int> mp;
deque<int> dq;
int n, l;
cin >> n >> l;
int maxx = INT_MIN;
for(int i = 0; i < n ;i++){
int a;
cin >> a;
dq.push_front(a);
mp[a] += 1;
if(i >= l){
int tmp = dq.back();
dq.pop_back();
if(mp[tmp] > 1){
mp[tmp] -= 1;
}
else{
mp.erase(tmp);
}
}
int s = mp.size();
maxx = max(maxx, s );
}
cout << maxx << '\n';
}
```
# P-3-10
https://zerojudge.cchs.chc.edu.tw/Submissions
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
deque<int> dq;
map<int,int> mp;
int n;
cin >> n;
int arr[n];
map<int,int> count_;
for(int i = 0; i < n; i++){
cin >> arr[i];
count_[arr[i]] += 1;
}
int total_color = count_.size();
int minn = INT_MAX;
for(int i = 0; i < n; i++){
dq.push_front(arr[i]);
mp[arr[i]] += 1;
while(mp[dq.back()] > 1){
mp[dq.back()] -= 1;
dq.pop_back();
}
if(mp.size() == total_color){
int s = dq.size();
minn = min(minn, s);
}
}
cout << minn << '\n';
}
```
# P-4-1
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a310
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int m;
cin >> m;
while(m--){
int a;cin >> a;
int count_ = 0;
count_ += a / 50;
a = a % 50;
count_ += a / 10;
a = a % 10;
count_ += a / 5;
a = a % 5;
count_ += a;
cout << count_ << '\n';
}
}
```
# P-4-2
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a312
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n; cin >> n;
vector<int> enemy(n);
int ally[n];
for(int i = 0; i < n;i ++){
cin >> enemy[i];
}
for(int i = 0; i < n; i++){
cin >> ally[i];
}
sort(enemy.begin(), enemy.end());
sort(ally , ally +n);
int ans = 0;
for(int i = n-1; i >= 0 ;i--){
auto it = lower_bound(enemy.begin(),enemy.end(),ally[i]);
if(it != enemy.begin()){
it = prev(it);
ans += 1;
enemy.erase(it);
}
}
cout << ans << '\n';
}
```
# P-4-3
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a313
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n; cin >> n;
int arr[n];
for(int i = 0; i < n; i++){
cin >> arr[i];
}
sort(arr,arr+n);
int ans = 0;
int sum = 0;
for(int i = 0; i < n; i++){
sum += arr[i];
ans += sum;
}
cout << ans << '\n';
}
```
# P-4-4
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a314
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n; cin >> n;
vector<pair<int,int> > vc(n);
for(int i = 0; i < n; i++){
cin >> vc[i].second; // start
cin >> vc[i].first; // end
}
sort(vc.begin(),vc.end());
int ans = 1;
int back_p = vc[0].first;
for(int i = 1; i < n; i++){
if(vc[i].second <= back_p){
}
else{
ans ++;
back_p = vc[i].first;
}
}
cout << ans << '\n';
}
```
# P-4-5
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a315
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct cmp{
bool operator()(pair<int,int> a, pair<int,int> b){
double aa = (double)a.second / (double)a.first;
double bb = (double)b.second / (double)b.first;
// cout << "cmp "<< aa << ' ' << bb << '\n';
return aa > bb;
}
};
signed main(){
int n; cin >> n;
vector<pair<int, int> > vc(n);
for(int i = 0; i < n; i++){
cin >> vc[i].first;//time
}
for(int i = 0; i < n; i++){
cin >> vc[i].second;//weight
}
sort(vc.begin(),vc.end(),cmp());
int sum = 0;
int ans = 0;
for(int i = 0 ;i < n ;i++){
// cout << vc[i].first << ' ' << vc[i].second << '\n';
sum += vc[i].first;
ans += sum * vc[i].second;
}
cout << ans << '\n';
}
```
# P-4-7
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a324
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct cmp{
int num;
bool operator<(const cmp &a)const{
return a.num < this->num;
}
};
signed main(){
int n;cin >> n;
priority_queue<cmp> pq;
for(int i = 0; i < n; i++){
int a;cin >> a;
cmp c;
c.num = a;
pq.push(c);
}
int sum = 0;
while(pq.size() > 1){
int a = pq.top().num;
pq.pop();
int b = pq.top().num;
pq.pop();
sum += a + b;
cmp c;
c.num = a + b;
pq.push(c);
}
cout << pq.top().num << '\n';
cout << sum << '\n';
}
```
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n;cin >> n;
priority_queue<int ,vector<int>, greater<int> > pq;
#priority_queue<int ,deque<int>, greater<int> > pq;
for(int i = 0; i < n; i++){
int a;cin >> a;
pq.push(a);
}
int sum = 0;
while(pq.size() > 1){
int a = pq.top();
pq.pop();
int b = pq.top();
pq.pop();
sum += a + b;
pq.push(a + b);
}
cout << pq.top() << '\n';
cout << sum << '\n';
}
```
# P-4-10
https://zerojudge.cchs.chc.edu.tw/Submissions
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
int p[100005];
bool play(int f){
int now = f;
int c = 0;
for(int i = 0; i < n; i++){
if(p[i] > f){
return 0;
}
else if(p[i] > now){
c++;
now = f - p[i];
}
else{
now -= p[i];
}
if(c > m){
return 0;
}
}
return 1;
}
signed main(){
cin >> n >> m;
for(int i = 0; i < n; i++){
cin >> p[i];
}
int f = 0;
for(int j = (1e18 - f) / 2; j > 0; j >>= 1){
while(play(f+j) == 0){
f += j;
}
}
f += 1;
cout << f << '\n';
}
```
# P-4-11
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a326
## 解法1
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n;
cin >> n;
vector<pair<int,int>> vc;
for(int i = 0; i < 2*n; i++){
int x;
cin >> x;
vc.push_back({x,i % 2});
}
sort(vc.begin(), vc.end());
auto start = vc.begin();
int previous_state;
int state = 1;
int ans = 0;
for(auto it = next(vc.begin()); it != vc.end(); it++){
if(it -> second == 1){
previous_state = state;
state--;
}
else{
previous_state = state;
state++;
}
if(state == 0 and previous_state > 0){
ans += it -> first - start -> first;
}
else if(state == 1 and previous_state == 0){
start = it;
}
}
cout << ans << '\n';
}
```
## 解法2
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n;
cin >> n;
vector<pair<int,int> > vc;
for(int i = 0 ;i < n; i++){
int l, r;
cin >> l >> r;
vc.push_back({l,r});
}
sort(vc.begin(),vc.end());
int total = 0;
pair<int,int> last = vc[0];
for(int i = 1; i < n; i++){
if(vc[i].first > last.second){
total += last.second - last.first;
last = vc[i];
}
last.second = max(last.second, vc[i].second);
}
total += last.second - last.first;
cout << total << '\n';
}
```
# P-4-15
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a327
## 解法1:掃描線
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
int dis(pair<int,int> a, pair<int,int> b){
return abs(a.first - b.first) + abs(a.second - b.second);
}
signed main(){
int n;
cin >> n;
vector<pair<int,int> > vc;
for(int i = 0; i < n; i++){
int x, y;
cin >> x >> y;
vc.push_back({x,y});
}
sort(vc.begin(),vc.end());
int d = INT_MAX;
for(int i = 0; i < n-1; i++){
for(int j = i+1; j < n; j++){
if(abs(vc[i].first - vc[j].first) > d)break;
d = min(d, dis(vc[i], vc[j]));
}
}
cout << d << '\n';
}
```
## 解法二:掃描線+set二分搜
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
int dis(pair<int,int> a, pair<int,int> b){
return abs(a.first - b.first) + abs(a.second - b.second);
}
signed main(){
int n;
cin >> n;
vector<pair<int,int> > vc;
for(int i = 0; i < n; i++){
int x, y;
cin >> x >> y;
vc.push_back({x,y});
}
sort(vc.begin(),vc.end());
set<pair<int,int> > st;
st.insert({vc[0].second,vc[0].first});
int d = INT_MAX;
for(int i = 1, l = 0; i < n;i++){
while(l < i && (vc[i].first - vc[l].first) > d){
st.erase({vc[l].second,vc[l].first});
l++;
}
auto itdown = st.lower_bound({vc[i].second - d, 0});
auto itup = st.upper_bound({vc[i].second + d, 0});
for(auto it = itdown; it != itup; it++){
d = min(d, dis(vc[i], {it->second,it->first}) );
}
st.insert({vc[i].second, vc[i].first});
}
cout << d << '\n';
}
```
## 解法3:分治
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
vector<pair<int,int> > vc;
int dis(pair<int,int> a, pair<int,int> b){
return abs(a.first - b.first) + abs(a.second - b.second);
}
bool cmp(pair<int,int> a, pair<int,int> b){
return a.second < b.second;
}
#define m (l+r)/2
int cqd(int l, int r){
if(r - l == 1){
return INT_MAX;
}
int ld = cqd(l,m);
int rd = cqd(m,r);
int d = min(ld, rd);
vector<pair<int,int> > tmp;
for(int i = l; i < r; i++){
if((vc[i].first - vc[m].first)*(vc[i].first - vc[m].first) < d){
tmp.push_back(vc[i]);
}
}
sort(tmp.begin(),tmp.end(),cmp);
for(int i = 0 ; i < tmp.size() ;i++){
for(int j = i + 1; j < tmp.size(); j++){
if((tmp[i].second - tmp[j].second)*(tmp[i].second - tmp[j].second) > d){
break;
}
d = min(d, dis(tmp[i], tmp[j]));
}
}
return d;
}
signed main(){
cin >> n;
for(int i = 0; i < n; i++){
int x,y;
cin >> x >> y;
vc.push_back({x,y});
}
sort(vc.begin(),vc.end());
cout << cqd(0,n) << '\n';
}
```
<!--
## 解法4:隨機算法
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define e 1000000000
int n;
vector<int> vc;
int dx[25] = {-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2};
int dy[25] = {-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2};
int dis(int a, int b){
int ax = a / e;
int ay = a % e;
int bx = b / e;
int by = b % e;
return abs(ax - bx) + abs(ay - by);
}
// abs(a.x - b.x) + abs(a.y - b.y);
signed main(){
cin >> n;
for(int i = 0; i < n; i++){
int x,y;
cin >> x >> y;
vc.push_back(e*(x +100000000)+ (y + 100000000));
}
shuffle(vc.begin(),vc.end(),mt19937(random_device()()));
int d = dis(vc[0], vc[1]);
unordered_map<int,int> mp;
int nx = (vc[0] / e) / (d / 2);
int ny = (vc[0] % e) / (d / 2);
mp.insert({nx * e+ ny , vc[0]});
nx = (vc[1] / e) / (d / 2);
ny = (vc[1] % e) / (d / 2);
mp.insert({nx * e+ ny, vc[1]});
for(int i = 2; i < n; i++){
bool flag = 0;
int nx = (vc[i] / e) / (d / 2);
int ny = (vc[0] % e) / (d / 2);
for(int j = 0; j < 25; j++){
auto it = mp.find({(nx + dx[j]) * e + ny + dy[j]});
if(it != mp.end()){
if(dis(vc[i], it->second) < d){
d = dis(vc[i], it -> second);
flag = 1;
}
}
}
if(flag){
mp.clear();
for(int j = 0; j <= i; j ++){
nx = (vc[j] / e) / (d / 2);
ny = (vc[j] % e) / (d / 2);
mp.insert({nx * e + ny,vc[j]});
}
}
else{
nx = (vc[i] / e) / (d / 2);
ny = (vc[i] % e) / (d / 2);
mp.insert({nx * e + ny, vc[i]});
}
}
cout << d << '\n';
}
```
-->
# P-5-4
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a333
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[100005];
#define m (l+r)/2
int dc(int l, int r){
if(r - l == 1){
return 0;
}
int c = 0;
c += dc(l, m);
c += dc(m, r);
vector<int> tmp;
for(int i = m; i < r; i++){
tmp.push_back(a[i]);
}
tmp.push_back(INT_MAX);
sort(tmp.begin(), tmp.end());
for(int i = l; i < m; i++){
auto it = lower_bound(tmp.begin(),tmp.end(),a[i]);
if(it != tmp.end()){
c += it - tmp.begin();
}
}
return c;
}
signed main(){
cin >> n;
for(int i = 0; i < n; i++){
cin >> a[i];
}
cout << dc(0, n) << '\n';
return 0;
}
```
# P-6-1
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a335
## bottom-up
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[100005];
int dp[100005];
signed main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
dp[1] = a[1];
dp[2] = a[2];
for(int i = 3; i <= n; i++){
dp[i] = a[i] + min(dp[i-1], dp[i-2]);
}
cout << dp[n] << '\n';
}
```
## top-down
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
int p[100005];
int dp[100005]={-1};
int f(int x){
int a, b;
if(dp[x-1] > 0){
a = dp[x-1];
}
else{
a = f(x-1);
dp[x-1] = a;
}
if(dp[x-2] > 0){
b = dp[x-2];
}
else{
b = f(x - 2);
dp[x-2] = b;
}
return p[x] + min(a, b);
}
signed main(){
int n;
cin >> n;
for(int i = 0; i < n; i++){
cin >> p[i];
}
dp[0] = p[0];
dp[1] = p[1];
cout << f(n-1) << '\n';
}
```
# P-6-2
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a336
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[100005];
int dp[100005];
signed main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
dp[0] = 0;
dp[1] = a[1];
dp[2] = max(a[2], a[1]);
for(int i = 3; i <= n; i++){
dp[i] = max(dp[i-1], max(dp[i-2] + a[i], dp[i-3] + a[i]));
}
cout << dp[n] << '\n';
}
```
# p-6-3
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a337
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[100005];
int dp[100005];
signed main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
dp[0] = INT_MAX;
dp[1] = a[1];
dp[2] = a[2];
for(int i = 3; i <= n; i++){
dp[i] = a[i] + min(dp[i-3], min(dp[i-2], dp[i-1]));
}
cout << min(dp[n], dp[n-1]) << '\n';
}
```
# p-6-6
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a340
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n ,m; cin >> n >> m;
int a[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> a[i][j];
}
}
int dp[n][m];
dp[0][0] = a[0][0];
for(int i = 1; i < n; i++){
dp[i][0] = dp[i-1][0] + a[i][0];
}
for(int i = 1; i < m; i++){
dp[0][i] = dp[0][i-1] + a[0][i];
}
for(int i = 1; i < n; i++){
for(int j = 1; j < m; j++){
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j];
}
}
// for(int i = 0; i < n; i++){
// for(int j = 0; j < m; j++){
// cout << dp[i][j] << ' ';
// }cout << '\n';
// }
cout << dp[n-1][m-1] << '\n';
}
```
# p-6-7
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a341
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
string s1, s2;
cin >> s1 >> s2;
int n = s1.size();
int m = s2.size();
int dp[n+1][m+1];
for(int i = 0; i <= n; i++){
dp[i][0] = 0;
}
for(int i = 0; i <= m; i++){
dp[0][i] = 0;
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(s1[j-1] == s2[i-1]){
dp[j][i] = dp[j-1][i-1] + 1;
}
else{
dp[j][i] = max(dp[j-1][i], dp[j][i-1]);
}
}
}
cout << dp[n][m] << '\n';
}
```
## 滾動
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
string s1, s2;
cin >> s1 >> s2;
int n = s1.size();
int m = s2.size();
int dp[n+1][2];
for(int i = 0; i <= n; i++){
dp[i][0] = 0;
dp[i][1] = 0;
}
int from = 0, to = 1;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(s1[j-1] == s2[i-1]){
dp[j][to] = dp[j-1][from] + 1;
}
else{
dp[j][to] = max(dp[j-1][to], dp[j][from]);
}
}
swap(from, to);
}
cout << dp[n][from] << '\n';
}
```
# p-6-8
## global alignment
先把子問題寫出來
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
int val(char a, char b){
if(a == b){
return 8;
}
else if(a == '-' or b == '-'){
return -3;
}
else{
return -5;
}
}
signed main(){
string s1, s2;
cin >> s1 >> s2;
int n = s1.size();
int m = s2.size();
int dp[n+1][m+1];
for(int i = 0; i <= n; i++){
dp[i][0] = i * -3;
}
for(int i = 0; i <= m; i++){
dp[0][i] = i * -3;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dp[i][j] = max(dp[i-1][j-1] + val(s1[i-1], s2[j-1]),
max(dp[i-1][j] + val(s1[i-1], '-'),
dp[i][j-1] + val('-', s2[j-1])));
}
}
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
cout << dp[i][j] << ' ';
}cout << '\n';
}
cout << dp[n][m] << '\n';
}
```
## local alignment
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
int val(char a, char b){
if(a == b){
return 8;
}
else if(a == '-' or b == '-'){
return -3;
}
else{
return -5;
}
}
signed main(){
string s1, s2;
cin >> s1 >> s2;
int n = s1.size();
int m = s2.size();
int dp[n+1][m+1];
for(int i = 0; i <= n; i++){
dp[i][0] = 0;
}
for(int i = 0; i <= m; i++){
dp[0][i] = 0;
}
int max_score = INT_MIN;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dp[i][j] = max(val(s1[i-1], s2[j-1]),
max(dp[i-1][j-1] + val(s1[i-1], s2[j-1]),
max(dp[i-1][j] + val(s1[i-1], '-'),
dp[i][j-1] + val('-', s2[j-1]))));
max_score = max(max_score, dp[i][j]);
}
}
// for(int i = 0; i <= n; i++){
// for(int j = 0; j <= n; j++){
// cout << dp[i][j] << ' ';
// }cout << '\n';
// }
cout << max_score << '\n';
}
```
這題懶得寫滾動DP了
# p-6-9
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a343
```cpp=
#include<bits/stdc++.h>
using namespace std;
// #define int long long
int dp[101][100005];
int w[101];
int val[101];
signed main(){
int n, W;
cin >> n >> W;
for(int i = 1; i <= n; i++){
cin >> w[i];
}
for(int i = 1; i <= n; i++){
cin >> val[i];
}
for(int i = 1; i <= n; i++){
for(int j = 0; j < w[i]; j++){
dp[i][j] = dp[i-1][j];
}
for(int j = w[i]; j <= W; j++){
dp[i][j] = max(dp[i-1][j], val[i] + dp[i-1][j - w[i]]);
}
}
cout << dp[n][W] << '\n';
}
```
## 滾動寫法(一維)
從後到前
```cpp=
#include<bits/stdc++.h>
using namespace std;
// #define int long long
int dp[100005];
int w[101];
int val[101];
signed main(){
int n, W;
cin >> n >> W;
for(int i = 1; i <= n; i++){
cin >> w[i];
}
for(int i = 1; i <= n; i++){
cin >> val[i];
}
for(int i = 1; i <= n; i++){
for(int j = W; j >= w[i]; j--){
dp[j] = max(dp[j], val[i] + dp[j - w[i]]);
}
}
cout << dp[W] << '\n';
}
```
# P-6-10
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a344
```cpp=
#include<bits/stdc++.h>
using namespace std;
// #define int long long
int dp[100005];
int w[101];
int val[101];
signed main(){
int n, W, S;
cin >> n >> W >> S;
int sum = 0;
for(int i = 1; i <= n; i++){
cin >> w[i];
sum += w[i];
}
for(int i = 1; i <= n; i++){
for(int j = W - S; j >= w[i]; j--){
dp[j] = max(dp[j], w[i] + dp[j - w[i]]);
}
}
cout << max(0,sum - dp[W - S]) << '\n';
}
```
# p-6-11
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a345
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000009
int dp[101];
signed main(){
int n;
cin >> n;
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++){
for(int j = 0; j < n; j++){
dp[i] = (dp[i] + ((dp[j] % mod ) * (dp[i - 1 - j] % mod)) % mod) % mod;
}
}
cout << dp[n] << '\n';
}
```
# p-6-13
```cpp=
```
# p-6-15
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a349
## 二分搜
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> vc;
for(int i = 0; i < n; i++){
int x;
cin >> x;
auto it = lower_bound(vc.begin(),vc.end(),x);
if(it == vc.end()){
vc.push_back(x);
}
else{
*it = x;
}
}
cout << vc.size() << '\n';
}
```
# p-6-17
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a351
```cpp=
#include<bits/stdc++.h>
using namespace std;
int p[202];
int dp[202][202];
int f(int l, int r){
if(r - l == 1){
return 0;
}
if(dp[l][r] != 0){
return dp[l][r];
}
else{
int minn = INT_MAX;
for(int i = l+1; i < r; i++){
minn = min(minn, f(l, i) + f(i, r));
}
dp[l][r] = minn + (p[r] - p[l]);
return dp[l][r];
}
}
int main(){
int n, L;
cin >> n >> L;
p[0] = 0;
p[n+1] = L;
for(int i = 1; i <= n; i++){
cin >> p[i];
}
cout << f(0, n+1) << '\n';
}
```
# p-7-1
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a358
## 鄰接矩陣
```cpp=
#include<bits/stdc++.h>
using namespace std;
int g[101][101];
int vis[101];
int main(){
int n, m;
cin >> n >> m;
int s; cin >> s;
for(int i = 0; i < m ;i++){
int x, y;
cin >> x >> y;
g[x][y] = 1;
}
int sum = 0;
int num = 0;
int step = 1;
vis[s] = 1;
queue<pair<int,int> > q;
q.push({s,0});
while(q.size()){
int now = q.front().first;
int depth =q.front().second;
q.pop();
for(int i = 0; i < n; i++){
if(g[now][i] == 1 and vis[i] == 0){
q.push({i, depth + 1});
vis[i] = 1;
num += 1;
sum += depth + 1;
}
}
}
cout << num << '\n' <<sum << '\n';
}
```
## 鄰接串列
```cpp=
#include<bits/stdc++.h>
using namespace std;
vector<int> g[101];
int vis[101];
int main(){
int n, m;
cin >> n >> m;
int s; cin >> s;
for(int i = 0; i < m ;i++){
int x, y;
cin >> x >> y;
g[x].push_back(y);
}
int sum = 0;
int num = 0;
int step = 1;
vis[s] = 1;
queue<pair<int,int> > q;
q.push({s,0});
while(q.size()){
int now = q.front().first;
int depth =q.front().second;
q.pop();
for(int i : g[now]){
if(vis[i] == 0){
q.push({i, depth + 1});
vis[i] = 1;
num += 1;
sum += depth + 1;
}
}
}
cout << num << '\n' <<sum << '\n';
}
```
# P-7-2
https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a359
```cpp=
#include<bits/stdc++.h>
using namespace std;
int val[50005];
vector<int> g[50005];
int vis[50005];
int DFS(int now){
vis[now] = 1;
int r = val[now];
for(int i : g[now]){
if(vis[i] == 0){
r += DFS(i);
}
}
return r;
}
int main(){
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++){
cin >> val[i];
}
for(int i = 0; i < m; i++){
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
int ans = 0;
for(int i = 0; i < n; i++){
if(vis[i] == 0)
ans = max(ans, DFS(i));
}
cout << ans <<'\n';
}
```
# ZeroJudge：f167. m4a1-社團 Club
https://zerojudge.tw/ShowProblem?problemid=f167
topological sort
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> g[1005];
int in[1005];
signed main(){
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
int x, y;
cin >> x >> y;
g[x].push_back(y);
in[y] ++;
}
queue<int> qu;
int st;
vector<int> seque;
for(int i = 1; i <= n; i++){
if(in[i] == 0)qu.push(i);
}
while(!qu.empty()){
int now = qu.front();
qu.pop();
seque.push_back(now);
for(int i : g[now]){
in[i]--;
if(in[i] == 0){
qu.push(i);
}
}
}
if(seque.size() == n){
cout << "YES" << '\n';
for(int i = 0; i < n; i++){
cout << seque[i] << '\n';
}
}
else{
cout << "NO" << '\n';
}
}
```
# TIOJ 1092. A.跳格子遊戲
https://tioj.ck.tp.edu.tw/problems/1092
topological sort
```cpp=
#include<bits/stdc++.h>
using namespace std;
vector<int> g[10005];
int out[10005];
int win[10005];
int main(){
int n, e;
while(cin >> n >> e){
if(n == 0 and e == 0){break;}
for(int i = 0; i < n; i++){
g[i].clear();
}
memset(out,0,sizeof(out));
memset(win,0,sizeof(win));
for(int i = 0; i < e; i++){
int x, y; cin >> x >> y;
g[y].push_back(x);
out[x]++;
}
string s;
cin >> s;
queue<int> topo;//0 win 1 lose
topo.push(n);
win[n] = 0;
while(!topo.empty()){
int now = topo.front();
topo.pop();
for(int i : g[now]){
out[i]--;
if(out[i] == 0){
topo.push(i);
}
if(win[now] == 0){
win [i] = 1;
}
}
}
if (win[1] == 0) {
cout << (s == "Mimi" ? "Mimi" : "Moumou") << '\n';
} else {
cout << (s == "Mimi" ? "Moumou" : "Mimi") << '\n';
}
}
}
```
# 1290 . F.不定向邊
https://tioj.ck.tp.edu.tw/problems/1290
```cpp=
#include<bits/stdc++.h>
using namespace std;
struct node
{
int val;
int to;
/* data */
};
vector<node> g[1005];
int used[1005];
int cost[1005];
int main(){
int n, m;
while(cin >> n >> m){
int st, ed;
cin >> st >> ed;
for(int i = 0; i < 1005; i++){
g[i].clear();
cost[i] = INT_MAX;
used[i] = 0;
}
for(int i = 0; i < m; i++){
int a, b ,c;
cin >> a >> b >> c;
node tmp;
tmp.val = c;
tmp.to = b;
g[a].push_back(tmp);
tmp.to = a;
g[b].push_back(tmp);
}
cost[st] = 0;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int>>> pq;
pq.push({0, st});
while(!pq.empty()){
int now = pq.top().second;
pq.pop();
if(used[now] == 1) continue;
used[now] = 1;
for(auto i : g[now]){
if(cost[now] + i.val < cost[i.to]){
cost[i.to] = cost[now] + i.val;
pq.push({cost[i.to], i.to});
}
}
}
if(cost[ed] == INT_MAX){
cout << "He is very hot" << '\n';
}
else{
cout << cost[ed] << '\n';
}
}
}
```
# UVa 10986 Sending email
https://vjudge.net/problem/UVA-10986
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
int val;
int to;
};
vector<node> g[20000];
int cost[20000];
int used[20000];
signed main(){
int t;
cin >> t;
for(int u = 1; u <= t; u++){
int n, m, st, ed;
cin >> n >> m >> st >> ed;
for(int i = 0; i < 20000; i++){
g[i].clear();
cost[i] = INT_MAX;
used[i] = 0;
}
for(int i = 0; i < m; i++){
int x, y, z;
cin >> x >> y >> z;
node tmp;
tmp.to = y;
tmp.val = z;
g[x].push_back(tmp);
tmp.to = x;
g[y].push_back(tmp);
}
priority_queue<pair<int,int> ,vector<pair<int,int>> , greater<pair<int,int>>> pq;
pq.push({0,st});
cost[st] = 0;
while(!pq.empty()){
int now = pq.top().second;
pq.pop();
if(used[now] == 1){continue;}
used[now] = 1;
for(auto i : g[now]){
// cout << i.val << ' ' << cost[now] << ' ' << cost[i.to] << '\n';
if(i.val + cost[now] < cost[i.to]){
cost[i.to] = i.val + cost[now];
pq.push({cost[i.to], i.to});
}
}
}
cout << "Case #"<<u<<": ";
if(cost[ed] == INT_MAX){
cout << "unreachable" << '\n';
}
else{
cout << cost[ed] << '\n';
}
}
}
```
# UVA 11015 - 05-2 RENDEZVOUS
https://vjudge.net/problem/UVA-11015
Floyd-Warshall
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n, m;
int c = 0;
while(cin >> n >> m){
if(n == 0)break;
c++;
string s[n+1];
vector<vector<int> > g(25,vector<int> (25));
for(int i = 1; i <= n; i++){
cin >> s[i];
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(i == j) g[i][j] = 0;
else{
g[i][j] = INT_MAX;
}
}
}
for(int i = 0; i < m; i++){
int a, b, c;
cin >> a >> b >> c;
g[a][b] = c;
g[b][a] = c;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int k = 1; k <= n; k++){
if (g[i][k] != INT_MAX && g[k][j] != INT_MAX) {
g[j][k] = min(g[j][k], g[j][i] + g[i][k]);
}
}
}
}
string ans;
int minn = INT_MAX;
for(int i = 1; i <= n; i++){
int tmp = 0;
for(int j = 1; j <= n; j++){
tmp += g[i][j];
}
if(tmp < minn){
minn = tmp;
ans = s[i];
}
}
cout << "Case #"<<c<<" : "<<ans << '\n';
}
}
```
# UVa 558 - Wormholes
https://vjudge.net/problem/UVA-558
SPFA負環判斷
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
struct node{
int val;
int to;
};
vector<node> g[1005];
int dis[1005];
int inq[1005];
int times[1005];
int spfa(){
queue<int> q;
for(int i = 0; i <= n; i++){dis[i] = INT_MAX; inq[i] = 0; times[i] = 0;}
dis[0] = 0;
inq[0] = 1;
q.push(0);
while(!q.empty()){
int now = q.front();
inq[now] = 0;
times[now]++;
if(times[now] > n) return true;
q.pop();
for(auto i : g[now]){
if(dis[now] != INT_MAX and dis[now] + i.val < dis[i.to]){//前面那個應該可以不用
dis[i.to] = dis[now] + i.val;
if(inq[i.to] == 0){
inq[i.to] = 1;
q.push(i.to);
}
}
}
}
return false;
}
signed main(){
int c;
cin >> c;
while(c--){
cin >> n >> m;
for(int i = 0; i <= n; i++)g[i].clear();
for(int i = 0; i < m; i++){
int x, y, t;
cin >> x >> y >> t;
node tmp; tmp.to = y; tmp.val = t;
g[x].push_back(tmp);
}
if(spfa()) cout << "possible\n";
else cout << "not possible\n";
}
}
```
# NEOJ 48 二元搜尋樹
BST 前序轉後續
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
int val;
node* lc;
node* rc;
node(int x){
val = x;lc = nullptr; rc = nullptr;
}
};
void bst_insert(node *root, int x){
if(x <= root->val){
if(root->lc == nullptr){
node *tmp = new node(x);
root->lc = tmp;
}
else{
bst_insert(root->lc, x);
}
}
else{
if(root->rc == nullptr){
node *tmp = new node(x);
root->rc = tmp;
}
else{
bst_insert(root->rc, x);
}
}
}
void postorder(node *root){
if(root->lc != nullptr){
postorder(root->lc);
}
if(root->rc != nullptr){
postorder(root->rc);
}
cout << root->val << '\n';
}
int main(){
cin >> n;
int x;
cin >> x;
node *root = new node(x);
for(int i = 1; i < n; i++){
cin >> x;
bst_insert(root, x);
}
postorder(root);
}
```
#
```cpp=
```
#
```cpp=
```
#
```cpp=
```
#
```cpp=
```
#
```cpp=
```
Google Drive
Gist
Clipboard
Sign in with Wallet
