---
title: 【NCPC】112解題筆記
tags: C++
---
# 【NCPC】112解題筆記
[113官網](https://ncpc.nsysu.edu.tw/index.php) | [112初賽PDF](https://ncpc.nsysu.edu.tw/static/file/62/1062/img/4478/832180131.pdf) | [112初賽計分板](https://reg.ncpc.ntnu.edu.tw/ncpc2023/NCPC_scorboard/NCPC2023_preliminary_result.html) | [112決賽PDF](https://ncpc.nsysu.edu.tw/static/file/62/1062/img/4478/506520321.pdf) | [112決賽計分板](https://reg.ncpc.ntnu.edu.tw/ncpc2023/NCPC_scorboard/NCPC2023_final_result.html)
## 前言
- 這裡的測資執行時間指的是執行官網提供的.in和.out檔所需時間，使用CP Editor計時。為什麼不寫時間複雜度呢？因為我不太懂那個，怕錯估自己code的複雜度會很尷尬。
- 關鍵字是指跟我的做法有關的一些資料結構、演算法或數學觀念，看不懂可以先google它們，當然也可以問我。
- 如果你看完想到什麼酷炫的優化方式也請跟我說！
## 初賽
### Problem A: Cake Game
**關鍵字:** 線段相交(segment intersection)
**測資執行時間:** 163ms
這題最麻煩的部分就是判斷兩線段是否相交。我這裡使用定向（orientation）計算，簡單來說就是考量兩個相交的線段a, b，線段b的兩端點一定在a的兩側，比如a1-a2-b1是順時針方向旋轉的話，a1-a2-b2就會是逆時針方向。詳細做法可以參考[這篇文章](https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/)。
```cpp=
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int t;
struct candle{
int x;
int y;
};
candle red[4], green[4];
const int g0[] = {0,0,0};
const int g1[] = {1,2,3};
const int g2[] = {2,1,1};
const int g3[] = {3,3,2};
// 用向量算三點位置關係
int orientation(candle p, candle q, candle r){
int val = (q.y-p.y)*(r.x-q.x) - (q.x-p.x)*(r.y-q.y);
if(val==0) return 0; // 共線
return (val>0)?1:2;
}
// 檢查點r是否在線段pq上
bool on_segment(candle p, candle q, candle r){
if(r.x < max(p.x, q.x) && q.x > min(p.x, q.x)
&& r.y < max(p.y, q.y) && r.y > min(p.y, q.y)){
return true;
}
return false;
}
// 檢查線段是否相交
bool intersect(candle a1, candle a2, candle b1, candle b2){
int o1, o2, o3, o4;
// 一般情況: b1,b2在線段a不同側，a1,a2在線段b不同側
o1 = orientation(a1, a2, b1);
o2 = orientation(a1, a2, b2);
o3 = orientation(b1, b2, a1);
o4 = orientation(b1, b2, a2);
if(o1!=o2 && o3!=o4) return true;
// 特殊情況: ab共線且有重疊
if(o1==0 && on_segment(a1,a2,b1)) return true;
if(o2==0 && on_segment(a1,a2,b2)) return true;
if(o3==0 && on_segment(b1,b2,a1)) return true;
if(o4==0 && on_segment(b1,b2,a2)) return true;
return false;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while(t--){
bool g = false;
bool rg1, rg2, g1g2;
for(int i=0; i<4; i++) cin >> red[i].x >> red[i].y;
for(int i=0; i<4; i++) cin >> green[i].x >> green[i].y;
// 窮舉紅蠟燭連線
for(int i=0; i<4; i++){
for(int j=i+1; j<4; j++){
// 檢查線段red[i]red[j]
if(g) break;
int bfail = 0;
// 窮舉綠蠟燭兩條連線組合 (只考慮不會相交的情況)
for(int k=0; k<3; k++){
rg1 = intersect(red[i], red[j], green[g0[k]], green[g1[k]]);
rg2 = intersect(red[i], red[j], green[g2[k]], green[g3[k]]);
g1g2 = intersect(green[g0[k]], green[g1[k]],
green[g2[k]], green[g3[k]]);
if(rg1 || rg2 || g1g2) bfail++;
}
if(bfail==3) g = true;
}
}
if(g) cout << "G\n";
else cout << "B\n";
}
return 0;
}
```
### Problem B: Subarray Sums
**關鍵字:** 前綴和(prefix sum)
**測資執行時間:** 66ms
```cpp=
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, s, d;
int ary[5005], pre[5005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
while(n--){
cin >> s;
cin >> ary[0];
pre[0] = ary[0];
// 處理輸入順便做前綴和
for(int i=1; i<s; i++){
cin >> ary[i];
pre[i] = pre[i-1] + ary[i];
}
cin >> d;
// 窮舉子序列並求和
int sum=0, curr=0, maxr=0, cnt=0;
for(int i=0; i<s; i++){
for(int j=i; j<s; j++){
sum = pre[j] - pre[i] + ary[i];
curr = sum%d;
// 記錄最大值和出現次數
if(curr > maxr){
maxr = curr;
cnt = 1;
}
else if(curr == maxr) cnt++;
}
}
cout << cnt << '\n';
}
return 0;
}
```
### Problem D: Little Red Riding Hood
**關鍵字:** 廣度優先搜尋(breadth-first search / BFS), 戴克斯特拉演算法(Dijkstra's algorithm), 優先佇列(priority queue)
**測資執行時間:** 485ms
```cpp=
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxN = 2e5+1;
const int maxW = 1e9+1;
struct road{
int dest; // 這條路通向的村莊
int hour; // 走完這條路所需的時間
};
struct state{
int time; // 目前走了幾小時
int village; // 到幾號村莊了
int hour_left; // 白天還剩幾小時
};
// 自定義比較運算子，priority_queue才知道怎麼排序道路
bool operator>(const state& x, const state& y){
return x.time > y.time;
}
//紀錄道路連通情況，adj[i]是一個vector，裡面存了從第i村出發的所有路
vector<road> adj[maxN];
int dijkstra(int n, int a, int b){
vector<int> min_hour(n+1, maxW);
vector<int> hour_left(n+1, a);
priority_queue<state, vector<state>, greater<state>> pq;
// 先從第1村出發
min_hour[1] = 0; // 到第1村最少就是0小時
state start;
start.time = 0; // 目前用時0小時
start.village = 1; // 我們在第1村
start.hour_left = a; // 白天還剩a小時
pq.push(start);
while(!pq.empty()){
state cur = pq.top(); // 沿著目前用時最短的路徑繼續前進
pq.pop();
int cur_time = cur.time;
int village = cur.village;
int day_hours_left = cur.hour_left;
if(village==n) return cur_time; // 到阿嬤家了
// 目前村莊出去的每條路都走走看
for(road r : adj[village]){
int next_village = r.dest;
int travel_time = r.hour;
int new_time, new_hours_left;
// 天黑前可以走完的路就走一走
if(travel_time <= day_hours_left){
new_time = cur_time + travel_time;
new_hours_left = day_hours_left - travel_time;
}
// 天黑前走不完的路就先過夜再出發
else{
new_time = cur_time + day_hours_left + b + travel_time;
new_hours_left = a - travel_time;
}
// 如果這次到下個村莊的時間比之前紀錄的min_hour[next_village]還短就更新
if(new_time < min_hour[next_village]){
min_hour[next_village] = new_time;
hour_left[next_village] = new_hours_left;
pq.push({new_time, next_village, new_hours_left});
}
}
}
return -1; // 走完還是沒到終點就回傳-1
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n, m, a, b, res;
cin >> n >> m >> a >> b;
// 針對每筆測資重置道路連通情況的紀錄
for(int i = 1; i <= n; i++){
adj[i].clear();
}
for(int i = 0; i < m; i++){
int u, v, w;
road r1, r2; // 路沒有方向性，來回都可以通
cin >> u >> v >> w;
r1.dest = v;
r1.hour = w;
r2.dest = u;
r2.hour = w;
adj[u].push_back(r1);
adj[v].push_back(r2);
}
res = dijkstra(n, a, b);
cout << res << '\n';
}
return 0;
}
```
### Problem F: Drones
**關鍵字:** 動態規劃(dynamic programming)
**測資執行時間:** 31ms
我覺得DP題最難的部分是看出可以用DP...這題我花了兩個多小時寫出一個錯誤解法，又想了半天才發現可以DP。
狀態```dp[i]```代表從```0```到```i```的最低花費，轉移式為```dp[j] = min(dp[], dp[i]+cost(i+1,j))```
```cpp=
#include<bits/stdc++.h>
using namespace std;
int t, n;
const int maxN = 1001;
int outpost[maxN], dp[maxN]; //dp[i]代表從0到i的最低花費
int cost(int i, int j){
int dis = outpost[j] - outpost[i];
return 10+dis*dis;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while(t--){
cin >> n;
for(int i=0; i<n; i++){
cin >> outpost[i];
// 一開始先假設0到i的最低花費都是用一台無人機巡邏整段
dp[i] = cost(0, i);
}
for(int i=1; i<n; i++){
for(int j=0; j<i; j++){
// 看j+1到i切出來有沒有比較便宜
dp[i] = min(dp[i], dp[j]+cost(j+1,i));
}
}
cout << dp[n-1] << '\n';
}
return 0;
}
```
## 決賽
太難了我寫個兩題簡單的就要去寫111了。
### Problem A: Spiral Game
**關鍵字:** 模擬(simulation)
**測資執行時間:** 665ms
```cpp=
#include<bits/stdc++.h>
using namespace std;
int t, n, m;
int pl[151], must[5001];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int s, d, cur, sim, winner;
bool move;
cin >> t;
while(t--){
winner = -1;
memset(must, 0, sizeof(must));
memset(pl, 0, sizeof(pl));
cin >> n >> m;
while(cin >> s){
if(s==0) break;
must[s] = 1;
}
must[n] = 1;
cur = 0;
while(cin >> d){
if(d==0) break;
move = true;
sim = pl[cur];
while(sim<pl[cur]+d-1){
sim++;
if(must[sim]) move = false;
}
if(move) pl[cur] += d;
if(pl[cur]==n && winner==-1) winner = cur;
cur = (cur+1) % m;
}
cout << winner+1 << '\n';
}
return 0;
}
```
### Problem D: Jacobi Symbol
**關鍵字:** 遞迴(recursion)
**測資執行時間:** 26ms
```cpp=
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll a, n;
ll gcd(ll x, ll y){
if(!y) return x;
else return gcd(y, x%y);
}
ll solve(ll a, ll n){
a %= n;
if(gcd(a, n) != 1) return 0;
if(a == 1) return 1;
if(a == 2){
if(n%8==1 || n%8==7) return 1;
return -1;
}
if(a%2){ // odd
if(a%4==3 && n%4==3) return -(solve(n, a));
return solve(n, a);
}
int res = 1;
while(a%2==0){
res *= solve(2, n);
a /= 2;
}
res *= solve(a, n);
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
bool first;
while(cin >> n){
if(!n) break;
first = true;
while(cin >> a){
if(!a){
cout << '\n';
break;
}
if(!first) cout << ' ';
cout << solve(a, n);
first = false;
}
}
return 0;
}
```
Sign in with Wallet
Connect another wallet