# 112北二區學科能力競賽
題目連結：Zerojudge(https://zerojudge.tw/)，Problem m601 ~ m608
## 前情提要
a是上午的題目(3hr)
pdf: https://drive.google.com/file/d/1NXjsJSPR9pBFUljCxj3qPSG3GsIYSYR6/view?usp=sharing
b是下午的題目(2hr)
pdf: https://drive.google.com/file/d/1dkE51sJpJitSWKsT8mkdhPPOxG52CU1k/view?usp=sharing
其中6a跟3b因為太難(應該啦)所以沒放在ZJ
但上面的pdf裡面有
## 1a
太簡單了不說明
反正就是畢氏定理跟一些簡單東西
:::spoiler code
```cpp=
#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
#define F first
#define S second
#define pLL pair<LL, LL>
using namespace std;
using LL = long long;
int main() {
LL n;
cin >> n;
pLL arr[n];
for(auto &i : arr) cin >> i.F >> i.S;
for(LL i = 1; i < n; i ++ ) {
LL c = arr[i-1].S, b = arr[i].F - arr[i-1].F;
double a = arr[i].S / 2.0;
if(c*c-b*b < a*a) {
cout << arr[i].F << endl;
return 0;
}
}
cout << -1 << endl;
}
```
:::
## 2a
這題顯然有很多解法
這裡提供一個比較好看的解法：
窮舉每個點`p`與其他所有點的向量
如果`p`為教練，則所有向量的方向都將不同
如果`p`為球員，則有一個向量的方向與其他的不同(如果把方向相反當成同方向的話)
如果在這之中沒有教練則為無解
並且每個`p`與其他點的向量都會是同一個方向
比賽時因為想不到好的解法，所以用了map還有很多很醜的東西
雖然過了但就是挺耗時間的
(下面有code但不建議參考)
:::spoiler code
```cpp=
#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
#define F first
#define S second
#define pLL pair<LL, LL>
#define mkp make_pair
#define pb emplace_back
#define LL loli
#define loli long long
using namespace std;
template<typename T> using Vec = vector<T>;
template<typename T> using Mat = Vec<Vec<T> >;
const LL mod = 1e9+7, inf = 9e18, maxN = 0;
LL TT = 1;
vector<pLL> vec;
pLL f(pLL a) {
LL g = __gcd(a.F, a.S);
a.F /= g, a.S /= g;
if(a.F < 0) a.F = -a.F, a.S = -a.S;
if(a.F == 0) a.S = labs(a.S);
return a;
}
void solve() {
LL N;
cin >> N;
vec.resize(N);
for(auto &i : vec) cin >> i.F >> i.S;
for(int i=0; i<N; i++) {
set<pLL> st;
for(int j=0; j<N; j++) if(i != j) st.insert(f(mkp(vec[j].F-vec[i].F, vec[j].S-vec[i].S)));
if(st.size() <= 2) continue;
cout << vec[i].F << ' ' << vec[i].S << endl;
return;
}
cout << "-1 -1" << endl;
}
int main() {
// IO;
// cin >> TT;
for(int cs=0; cs<TT; cs++) {
solve();
}
}
```
:::
:::spoiler 當時比賽中寫的醜醜的code
```cpp=
#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
#define F first
#define S second
#define pLL pair<LL, LL>
using namespace std;
using LL = long long;
int main() {
LL n;
cin >> n;
pLL arr[n];
for(auto &i : arr)
cin >> i.F >> i.S;
map<pLL, LL> mp;
for(LL i = 0; i < n; i ++ ) {
for(LL j = i+1; j < n; j ++ ) {
LL x = arr[j].F - arr[i].F;
LL y = arr[j].S - arr[i].S;
if(x == 0)
y = 1;
else if(y == 0)
x = 1;
else {
LL g = __gcd(x, y);
x /= g, y /= g;
if(x < 0)
x = -x, y = -y;
}
mp[{x, y}] ++ ;
}
}
if(mp.size() == 1) {
cout << -1 << " " << -1 << endl;
return 0;
}
LL cnt = -1;
pLL v = {-1, -1};
for(auto &i : mp)
if(i.S > cnt) {
cnt = i.S;
v = i.F;
}
map<pLL, LL> mp2;
for(LL i = 0; i < n; i ++ ) {
for(LL j = i+1; j < n; j ++ ) {
LL x = arr[j].F - arr[i].F;
LL y = arr[j].S - arr[i].S;
if(x == 0)
y = 1;
else if(y == 0)
x = 1;
else {
LL g = __gcd(x, y);
x /= g, y /= g;
if(x < 0)
x = -x, y = -y;
}
if(v.F != x || v.S != y) {
mp2[arr[i]] ++ ;
mp2[arr[j]] ++ ;
}
}
}
cnt = -1;
pLL ans;
for(auto &i : mp2)
if(i.S > cnt) {
cnt = i.S;
ans = i.F;
}
cout << ans.F << " " << ans.S << endl;
}
```
:::
## 3a
注意一個性質：
如果我們以`(x,y)`為`3*3`的左上角做翻轉，那`(x-1,y-1)`以左上的格子都不會被翻到
那我們就可以由左往右由上往下，窮舉`(0, 0)`到`(m-3, n-3)`為`3*3`的左上角做翻轉
如果該格為`1`則翻轉，否則不轉
由於`m*n`只到`25`，所以這樣時間是好的
最後檢查是否所有格子皆為`0`，是則輸出操作次數，否則輸出`-1`
話說我當時好像是用暴搜解的來著
:::spoiler code
```cpp=
#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
#define F first
#define S second
#define pLL pair<LL, LL>
#define mkp make_pair
#define pb emplace_back
#define LL loli
#define loli long long
using namespace std;
template<typename T> using Vec = vector<T>;
template<typename T> using Mat = Vec<Vec<T> >;
const LL mod = 1e9+7, inf = 9e18, maxN = 0;
int TT = 1;
void solve() {
LL n, m;
cin >> n >> m;
vector<vector<LL> > mat(n, vector<LL>(m, 0));
for(auto &i : mat) for(auto &j : i) cin >> j;
LL cnt=0;
for(LL i=0; i<n-2; i++) {
for(LL j=0; j<m-2; j++) {
if(mat[i][j]) {
cnt ++ ;
for(LL a=0; a<3; a++) for(LL b=0; b<3; b++) mat[i+a][j+b] = 1-mat[i+a][j+b];
}
}
}
bool bln = 0;
for(auto &i : mat) for(auto &j : i) if(j) bln=1;
cout << (!bln ? cnt : -1) << endl;
}
int main() {
// IO;
// cin >> TT;
for(int cs=0; cs<TT; cs++) {
solve();
}
}
```
:::
:::spoiler 當時比賽中寫的暴搜code
```cpp=
#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
#define F first
#define S second
#define pLL pair<LL, LL>
using namespace std;
using LL = long long;
int main() {
LL n;
cin >> n;
pLL arr[n];
for(auto &i : arr)
cin >> i.F >> i.S;
map<pLL, LL> mp;
for(LL i = 0; i < n; i ++ ) {
for(LL j = i+1; j < n; j ++ ) {
LL x = arr[j].F - arr[i].F;
LL y = arr[j].S - arr[i].S;
if(x == 0)
y = 1;
else if(y == 0)
x = 1;
else {
LL g = __gcd(x, y);
x /= g, y /= g;
if(x < 0)
x = -x, y = -y;
}
mp[{x, y}] ++ ;
}
}
if(mp.size() == 1) {
cout << -1 << " " << -1 << endl;
return 0;
}
LL cnt = -1;
pLL v = {-1, -1};
for(auto &i : mp)
if(i.S > cnt) {
cnt = i.S;
v = i.F;
}
map<pLL, LL> mp2;
for(LL i = 0; i < n; i ++ ) {
for(LL j = i+1; j < n; j ++ ) {
LL x = arr[j].F - arr[i].F;
LL y = arr[j].S - arr[i].S;
if(x == 0)
y = 1;
else if(y == 0)
x = 1;
else {
LL g = __gcd(x, y);
x /= g, y /= g;
if(x < 0)
x = -x, y = -y;
}
if(v.F != x || v.S != y) {
mp2[arr[i]] ++ ;
mp2[arr[j]] ++ ;
}
}
}
cnt = -1;
pLL ans;
for(auto &i : mp2)
if(i.S > cnt) {
cnt = i.S;
ans = i.F;
}
cout << ans.F << " " << ans.S << endl;
}
```
:::
## 4a
好玩題目
先判斷臘腸總數是否為`n(n+1)/2`，其中`n`為整數，如果不是則可直接輸出`-1`，否則繼續
再來，我們可以注意到`m`為`3`或`4`，仔細想想就可以發現原因
可以從最上面的打結處將此串臘腸分割成`2`條無分支的臘腸條
注意操作分割時其實就是將一陣列與另一陣列反轉後相接
再來，我們針對其中一串進行切割
靠一點點的感覺就能知道，如果我們從`n`往下判斷是否可以切成此長度
我們可以將此串切成長度為`1~n`中其中幾個不重複數字的長度
沒切到的數字即為另一條要切的長度
:::spoiler code
```cpp=
#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
#define F first
#define S second
#define pLL pair<LL, LL>
#define pb emplace_back
using namespace std;
using LL = long long;
int main() {
LL m;
cin >> m;
LL k[m], sum = 0;
for(LL i = 0; i < m; i ++ )
cin >> k[i], sum += k[i];
vector<LL> mat[m];
for(LL i = 0; i < m; i ++) {
for(LL j = 0; j < k[i]; j ++ ) {
LL num;
cin >> num;
mat[i].pb(num);
}
}
LL n = 1;
for(LL k = 0; ; n ++ ) {
k += n;
if(k > sum) {
cout << -1 << endl;
return 0;
}
if(k == sum)
break;
}
LL a = k[0] + k[1], b = k[2];
if(m == 4)
b += k[3];
vector<LL> A, B;
for(LL i = k[0]-1; i >= 0; i -- )
A.pb(mat[0][i]);
for(auto &i : mat[1])
A.pb(i);
for(LL i = k[2]-1; i >= 0; i -- )
B.pb(mat[2][i]);
if(m == 4) {
for(auto &i : mat[3])
B.pb(i);
}
bool used[n + 1];
memset(used, 0, sizeof(used));
vector<LL> ans[n+1];
for(LL i = n, l = 0; i >= 1; i -- ) {
if(a >= i) {
a -= i;
used[i] = 1;
for(LL j = 0; j < i; j ++ ) {
ans[i].pb(A[l]);
l ++ ;
}
}
}
for(LL i = 1, l = 0; i <= n; i ++ ) {
if(!used[i]) {
used[i] = 1;
for(LL j = 0; j < i; j ++ ) {
ans[i].pb(B[l]);
l ++ ;
}
}
}
cout << n << endl;
for(LL i = 0; i < n; i ++ ) {
for(auto &j : ans[i+1])
cout << j << " ";
cout << endl;
}
}
```
:::
## 5a
其實這題也是滿水的
就直接從1跑到N然後做質因數分解存在陣列裡面
最後處理一下輸出格式就好
比較難的地方可能只有題目會讓你想的太難
還有就是分析複雜度的部分
因為質數有很多有關數論的證明跟複雜度要背
不熟的話可能會被題目嚇到然後不敢寫這題
時間複雜度計算：
跑N的質因數分解複雜度為$\sqrt N$
所以整體大概會是$N\sqrt N$
如果N到5e5的話$N\sqrt N$大概會到3e8
算是卡在1秒邊但因為ZJ開2秒所以可以過
同時這個複雜度是上界並且有滿多k的操作會比$k \sqrt k$ 快
所以甚至可以在1秒內完成
::: spoiler code
```cpp=
#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
#define F first
#define S second
#define pLL pair<LL, LL>
#define pb emplace_back
using namespace std;
using LL = long long;
const LL maxN = 5e5+5;
int main() {
IO;
LL n;
cin >> n;
vector<LL> ans(maxN, 0);
for(LL i = 2; i <= n; i ++ ) {
LL p = i;
for(LL j = 2; j * j <= p; j ++ ) {
while(p % j == 0) {
p /= j;
ans[j] ++ ;
}
}
if(p != 1)
ans[p] ++ ;
}
LL tmp = -1, cnt = 0;
for(LL i = 0; i < maxN; i ++ ) {
if(!ans[i])
continue;
if(tmp == -1) {
tmp = ans[i];
cnt = 1;
continue;
}
if(ans[i] == tmp)
cnt ++ ;
else {
if(cnt > 1)
cout << cnt << '*';
cout << tmp << " ";
tmp = ans[i];
cnt = 1;
}
}
if(cnt > 1)
cout << cnt << '*';
cout << tmp << endl;
}
```
:::
## 6a
這題頗難，同時我不會
但應該是跟LCA有關
加上一些神奇東西
## 1b
~~我懷疑這題跟2a是出題者同時想到的~~
其實就跟2a的想法有點像，只是多了一些步驟
我們可以選三個點a, b, c然後決定其中兩條線
並用這兩條線去判斷是不是所有人都在這兩條線上
這樣解在ZJ上是95%但賽中是AC的
很神奇
::: spoiler code
:::
::: spoiler 當時比賽中寫的code(ZJ 95%)
```cpp=
#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
#define F first
#define S second
#define pLL pair<LL, LL>
using namespace std;
using LL = long long;
int main() {
LL n;
cin >> n;
pLL arr[n];
for(auto &i : arr)
cin >> i.F >> i.S;
uniform_int_distribution<LL> dis(0, n-1);
mt19937 mt(rand());
LL a[3];
pLL p, v;
while(1) {
for(LL i = 0; i < 3; i ++ ) {
a[i] = dis(mt);
}
if(a[0] == a[1] || a[0] == a[2] || a[1] == a[2])
continue;
LL x1 = arr[a[1]].F - arr[a[0]].F, y1 = arr[a[1]].S - arr[a[0]].S;
if(x1 == 0) y1 = 1;
else if(y1 == 0) x1 = 1;
else {LL g = __gcd(x1, y1); x1 /= g, y1 /= g; if(x1 < 0) x1 = -x1, y1 = -y1;}
LL x2 = arr[a[2]].F - arr[a[0]].F, y2 = arr[a[2]].S - arr[a[0]].S;
if(x2 == 0) y2 = 1;
else if(y2 == 0) x2 = 1;
else {LL g = __gcd(x2, y2); x2 /= g, y2 /= g; if(x2 < 0) x2 = -x2, y2 = -y2;}
if(x1 != x2 || y1 != y2)
continue;
p = arr[a[0]];
v = {x1, y1};
break;
}
char A = 'A', B = 'B';
for(LL i = 0; i < n; i ++ ) {
LL x1 = arr[i].F - p.F, y1 = arr[i].S - p.S;
if(x1 == 0 && y1 == 0) {
cout << A << endl;
continue;
}
if(x1 == 0) y1 = 1;
else if(y1 == 0) x1 = 1;
else {LL g = __gcd(x1, y1); x1 /= g, y1 /= g; if(x1 < 0) x1 = -x1, y1 = -y1;}
if(v.F == x1 && v.S == y1) {
cout << A << endl;
}
else {
if(i == 0)
swap(A, B);
cout << B << endl;
}
}
}
```
:::
## 2b
這題很好玩，因為不是平常會遇到的題目
感覺也是有很多神奇作法的題目
反正我賽中是拿0%，現在也還沒AC
我們知道只有10個數字要處理
那我們就可以對每個數字去找他們的特點
例：1的x軸不會動，之類的
那我們在仔細觀察
可以發現除了1以外，我們都可以利用王老先生的路徑找到整個數字的長或寬
並推出整個七段顯示器的大小跟每一線段的座標值
## 3b
這題頗難，我也不會
但滿分應該是2-SAT
喇分的話可以暴搜或dp
## 4b
這題有點像輾轉相除法的感覺
因為你可以發現當把一個分數用1去除他的時候其實是取倒數
我們只要維護兩個數字p, q表示一開始的分數是$\frac{p}{q}$
只要把整數提出來然後再把它變成倒數
一直重複以上動作即可AC
:::spoiler code
```cpp=
#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
#define F first
#define S second
#define pLL pair<LL, LL>
#define pb emplace_back
using namespace std;
using LL = long long;
int main() {
string str;
cin >> str;
LL pos = str.length() - str.find('.')-1;
LL a = 0, b = 1;
for(auto &i : str) {
if(i == '.')
continue;
a = a * 10 + i - '0';
}
for(LL i = 0; i < pos; i ++ )
b *= 10;
vector<LL> vec;
if(a == 0) {
cout << 0 << endl;
return 0;
}
LL g = __gcd(a, b);
a /= g, b /= g;
while(1) {
vec.pb((LL)(a/b));
a %= b;
if(!a)
break;
swap(a, b);
}
for(LL i = 0; i < vec.size(); i ++ ) {
if(i == 1)
cout << ";";
else if(i != 0)
cout << ",";
cout << vec[i];
}
cout << endl;
}
```
:::
Sign in with Wallet
Connect another wallet