2019-2020 ICPC Asia Taipei-Hsinchu Regional Contest
===
比賽鏈結
---
https://codeforces.com/gym/102460/
比賽影片
---
{%youtube px2wM4IfgI8 %}
記分板
---
題解
---
### A. Rush Hour Puzzle
---
#### 題目摘要
有至多10台車，垂直或水平地擺放至6 $\times$ 6的平面中，並定義出口在第3列的最右邊，車子有分兩種，長度2或3的。而你的目標是在10步內將1號車(長度為2)出去，問能不能達成
#### 想法
隱式圖，把每一種車子擺列狀況當成狀態，題目可以轉換成把目標車移出去的最短路
首先，我們可以去掉最後移出的兩步，再來，觀察到車子的狀態不會太多，所以直接BFS亂做就好
:::spoiler 實作
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define F first
#define S second
void solve() {
vector a(6, vector<int>(6, 0));
int mx = 0;
rep (i, 0, 6) rep (j, 0, 6) {
cin >> a[i][j];
mx = max(mx, a[i][j]);
}
vector<pair<pii, pii>> car(mx + 1);
pii h = {-1, -1}, t;
rep (i, 0, 6) rep (j, 0, 6) {
if (a[i][j] == 1) {
t = {i, j};
if (h.F == -1) h = t;
}
}
if (h.F != 2 || t.F != 2) {
cout << -1 << '\n';
return;
}
if (a[2][4] == 1 && a[2][5] == 1) {
cout << 2 << '\n';
exit(0);
}
map<vector<vector<int>>, int> mp;
queue<pair<vector<vector<int>>, int>> q;
q.push({a, 0});
mp[a] = 1;
while (!q.empty()) {
auto [cur, d] = q.front();
q.pop();
auto check = [&]() -> void {
if (cur[2][4] == 1 && cur[2][5] == 1) {
cout << d + 2 << '\n';
exit(0);
}
};
check();
if (d == 8) continue;
vector<pair<pii, pii>> car(mx + 1, {{-1, -1}, {-1, -1}});
rep (i, 0, 6) rep (j, 0, 6) if (cur[i][j]) {
car[cur[i][j]].S = {i, j};
if (car[cur[i][j]].F.F == -1) car[cur[i][j]].F = {i, j};
}
d++;
rep (i, 1, mx + 1) {
auto [h, t] = car[i];
if (h.F == t.F) {
if (h.S != 0 && cur[h.F][h.S - 1] == 0) {
rep (i, h.S - 1, t.S) swap(cur[h.F][i], cur[h.F][i + 1]);
check();
if (mp[cur] == 0) {
q.push({cur, d});
mp[cur] = 1;
}
for (int i = t.S; i >= h.S; --i) swap(cur[h.F][i], cur[h.F][i - 1]);
}
if (t.S != 5 && cur[h.F][t.S + 1] == 0) {
for (int i = t.S + 1; i > h.S; --i) swap(cur[h.F][i], cur[h.F][i - 1]);
check();
if (mp[cur] == 0) {
q.push({cur, d});
mp[cur] = 1;
}
rep (i, h.S, t.S + 1) swap(cur[h.F][i], cur[h.F][i + 1]);
}
} else {
if (h.F != 0 && cur[h.F - 1][h.S] == 0) {
rep (i, h.F - 1, t.F) swap(cur[i][h.S], cur[i + 1][h.S]);
check();
if (mp[cur] == 0) {
q.push({cur, d});
mp[cur] = 1;
}
for (int i = t.F; i >= h.F; --i) swap(cur[i][h.S], cur[i - 1][h.S]);
}
if (t.F != 5 && cur[t.F + 1][h.S] == 0) {
for (int i = t.F + 1; i > h.F; --i) swap(cur[i][h.S], cur[i - 1][h.S]);
check();
if (mp[cur] == 0) {
q.push({cur, d});
mp[cur] = 1;
}
rep (i, h.F, t.F + 1) swap(cur[i][h.S], cur[i + 1][h.S]);
}
}
}
}
cout << -1 << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
}
```
:::
### B. The Power Monitor System (待補)
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### C. Are They All Integers?
---
#### 題目摘要
問對於一個序列，任取3項的兩項差除以第三項是否為整數
#### 想法
簽到，$N^3$爆做
:::spoiler 實作
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
int main() {
int n; cin >> n;
vector<int> a(n);
rep (i, 0, n) cin >> a[i];
bool f = 1;
rep (i, 0, n) rep (j, 0, n) rep (k, 0, n) {
if (i != j && j != k && i != k) f &= (((a[i] - a[j]) % a[k]) == 0);
}
cout << (f ? "yes" : "no");
}
```
:::
### D. Tapioka
---
#### 題目摘要
給定一坨字串s由空格分開，把所有"tapioka" 跟 "bubble" 刪掉後輸出
#### 想法
直接實作
:::spoiler 實作
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
int main() {
string b = "bubble";
string t = "tapioka";
vector<string> ans;
string s;
while(cin >> s){
if(s!=b && s!=t){
ans.push_back(s);
}
}
for(auto v : ans){
cout << v << ' ';
}
if(ans.empty()){
cout << "nothing";
}
}
```
:::
### E. The League of Sequence Designers
---
#### 題目摘要
題目給一個要算序列中序列中最大的區間和乘區間長度的問題，並給一個錯誤的程式碼：當現在累積的和<0，就放棄這些和，否則拿這個和去更新答案。而你會拿到長度下界$L$與誤差值$k$，問你能不能構出一筆序列為$n(n>=L)$使得正確答案與錯誤答案差$k$。若能，請輸出序列，否則輸出-1
#### 想法
要滿足條件，一定要一些正數和負數，但一堆正數實在是太難想了，所以就往只有一個正數的方向想
假設$x$為那一正數，那$x$就是錯誤解的答案，而$x+k$就是正解，而只要讓序列長度為$x+k$的因數就能夠出解了。另外，序列元素的大小有限制，對於長度要找出適當$x$才行
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lim=2000;
const ll MAX=1000000;
void solve(){
ll k;
int L;
cin >> k >> L;
for(int i=max(L, 3);i<=lim;i++){
ll sum=(MAX+k)/i;
ll x=sum*i-k;
if (sum+2<=x){
ll dif=x-sum;
vector<int> ans(i, 0);
ans[0]=x;
for(int j=1;j<i;j++){
if (dif>MAX){
ans[j]=-MAX;
dif-=MAX;
}else{
ans[j]=-dif;
dif=0;
}
}
if (dif!=0) continue;
reverse(ans.begin(), ans.end());
cout << i << '\n';
for(auto x:ans){
cout << x << ' ';
}
cout << '\n';
return;
}
}
cout << -1 << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--) solve();
}
```
:::
### F. Miss Sloane (待補)
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### G. Optimal Selection (待補)
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### H. Mining a
---
#### 題目摘要
給你數字$n$，輸出滿足$\frac{1}{n}=\frac{1}{a\oplus b}+\frac{1}{b}$的最大$a$
#### 想法
賽中盲猜$b=n+1$時$a$最大，但這題好像要拆成
\begin{array}
\\(a\oplus b)\times b=nb+n(a\oplus b)\\
n^2=((a\oplus b)-n)\times(b-n)
\end{array}
因此只要枚舉$n^2$的因數就能求答案了
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
ll n;
cin >> n;
ll ans=n*(n+1);
ans^=(n+1);
cout << ans << '\n';
}
int main(){
int t;
cin >> t;
while(t--) solve();
}
```
:::
### I. The Spectrum (待補)
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### J. Automatic Control Machine
---
#### 題目摘要
給你$m$個長度為$n$的01序列，問能不能選一些序列使它們全or起來後的序列所有元素為1。若能，輸出選的最少個數，否則輸出-1
#### 想法
$2^m$枚舉，用bitset來確認有沒有全部覆蓋
:::spoiler 實作
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
void solve() {
int n, m; cin >> n >> m;
vector<bitset<505>> bst(m);
rep (i, 0, m) rep (j, 0, n) {
char c; cin >> c;
bst[i][j] = c - '0';
}
// bitset<505> check;
// rep (i, 0, n) check[i] = 1;
int ans = m + 1;
rep (bit, 0, 1 << m) {
bitset<505> hehe;
rep (i, 0, m) if (bit >> i & 1) hehe |= bst[i];
if (hehe.count() == n) ans = min(ans, __builtin_popcount(bit));
}
if (ans == m + 1) ans = -1;
cout << ans << '\n';
}
int main() {
int t; cin >> t;
while (t--) {
solve();
}
}
```
:::
### K. Length of Bundle Rope
---
#### 題目摘要
裸霍夫曼編碼。
#### 想法
簽到，用Priority_queue實作
:::spoiler 實作
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
void solve() {
int n; cin >> n;
vector<ll> a(n);
rep (i, 0, n) cin >> a[i];
priority_queue<ll, vector<ll>, greater<ll>> pq;
rep (i, 0, n) pq.push(a[i]);
ll ans = 0;
while (pq.size() > 1) {
ll a = pq.top();
pq.pop();
ll b = pq.top();
pq.pop();
ans += a + b;
pq.push(a + b);
}
cout << ans << '\n';
}
int main() {
int t; cin >> t;
while (t--) {
solve();
}
}
```
:::
### L. Largest Quadrilateral
---
#### 題目大綱
給你二維座標上的一堆點(有重點)，求最大四邊形(若選的四個點讓四邊形退化成三角形也是合法的)
#### 想法
賽中想成枚舉四邊形的一個點，將與其他點的向量拿出來排序，考慮到兩向量在固定象限中，所夾的面積具單調性，所以能用deque去維護目前選的對角線應該拿哪條向量來外積，複雜度$O(n^2\log n)$，但被卡了QQ
而正解只要枚舉對角線用旋轉卡尺維護兩邊的最大面積，複雜度$O(n^2)$
:::spoiler 實作
```cpp=
pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
#define F first
#define S second
const int BUF_SZ = 1 << 15;
inline namespace Input {
char buf[BUF_SZ];
int pos;
int len;
char next_char() {
if (pos == len) {
pos = 0;
len = (int)fread(buf, 1, BUF_SZ, stdin);
if (!len) { return EOF; }
}
return buf[pos++];
}
ll read_int() {
ll x;
char ch;
int sgn = 1;
while (!isdigit(ch = next_char())) {
if (ch == '-') { sgn *= -1; }
}
x = ch - '0';
while (isdigit(ch = next_char())) { x = x * 10 + (ch - '0'); }
return x * sgn;
}
}// namespace Input
inline namespace Output {
char buf[BUF_SZ];
int pos;
void flush_out() {
fwrite(buf, 1, pos, stdout);
pos = 0;
}
void write_char(char c) {
if (pos == BUF_SZ) { flush_out(); }
buf[pos++] = c;
}
void write_int(ll x) {
static char num_buf[100];
if (x < 0) {
write_char('-');
x *= -1;
}
int len = 0;
for (; x >= 10; x /= 10) { num_buf[len++] = (char)('0' + (x % 10)); }
write_char((char)('0' + x));
while (len) { write_char(num_buf[--len]); }
}
// auto-flush output when program exits
void init_output() { assert(atexit(flush_out) == 0); }
}// namespace Output
inline pii operator-(pii x, pii y){return {x.F-y.F, x.S-y.S};}
inline ll dot(pii x, pii y){return x.F*y.F+x.S*y.S;}
inline ll cross(pii x, pii y){return x.F*y.S-x.S*y.F;}
inline ll area(pii x, pii y, pii z){return abs(cross(x-z, y-z));}
void output(ll x){
write_int((x>>1));
if (x&1) write_char('.'), write_char('5');
write_char('\n');
}
int n;
inline int nex(int x, int d=1){
x+=d;
if (x>=n) x-=n;
return x;
}
void solve(){
n=read_int();
vector<pii> pos(n);
for(auto &[x, y]:pos){
x=read_int();
y=read_int();
}
sort(pos.begin(), pos.end());
vector<pii> hull;
for(int _=0;_<2;_++){
for(int i=0;i<n;i++){
while(hull.size()>=2&&cross(pos[i]-hull.end()[-2], hull.back()-hull.end()[-2])<0) hull.pop_back();
hull.push_back(pos[i]);
}
hull.pop_back();
reverse(pos.begin(), pos.end());
}
if (hull.size()<3) cout << 0 << '\n';
else if (hull.size()==3){
ll ans=0;
ll A=area(hull[1], hull[2], hull[0]);
for(int i=0;i<n;i++) if (pos[i]!=hull[0]&&pos[i]!=hull[1]&&pos[i]!=hull[2]) ans=max(ans, A-min({area(hull[0], hull[1], pos[i]), area(hull[1], hull[2], pos[i]), area(hull[0], hull[2], pos[i])}));
output(ans);
}else{
ll ans=0;
n=hull.size();
for(int i=0;i<n;i++){
int p1=nex(i);
int p2=nex(i, 3);
for(int j=nex(i, 2);nex(j)!=i;j=nex(j)){
while(nex(p1)!=j&&area(hull[i], hull[j], hull[nex(p1)])>area(hull[i], hull[j], hull[p1])) p1=nex(p1);
while(nex(p2)!=i&&area(hull[i], hull[j], hull[nex(p2)])>area(hull[i], hull[j], hull[p2])) p2=nex(p2);
ans=max(ans, area(hull[i], hull[j], hull[p1])+area(hull[i], hull[j], hull[p2]));
}
}
output(ans);
}
}
int main(){
init_output();
int _t;
_t=read_int();
while(_t--) solve();
}
```
:::
### M. DivModulo (待補)
---
#### 題目大綱
定義 $dmod$ 如下 $A\ (dmod\ p)= a*p^x\ (dmod\ p) \equiv a \mod p$
給 $M,N,D$ 求 $\binom{N}{M}\ dmod\ D$ 的值
#### 想法
:::spoiler 實作
```cpp=
```
:::
Sign in with Wallet
Connect another wallet