文章目录

2019-2020 ICPC Asia Taipei-Hsinchu Regional ContestA.Rush Hour PuzzleC.Are They All Integers?D.TapiokaE.The League of Sequence DesignersH.Mining aJ.Automatic Control MachineK.Length of Bundle RopeL. Largest Quadrilateral

2019-2020 ICPC Asia Taipei-Hsinchu Regional Contest

A. Rush Hour Puzzle B. The Power Monitor System C. Are They All Integers? D. Tapioka E. The League of Sequence Designers F. Miss Sloane G. Optimal Selection H. Mining a I. The Spectrum J. Automatic Control Machine K. Length of Bundle Rope L. Largest Quadrilateral M. DivModulo

A.Rush Hour Puzzle

题意： 游戏大模拟 题解： 模拟 代码：

#include <bits/stdc++.h> using namespace std; const int N = 6; const int SEED = 31; int a[N][N]; int m; set<uint64_t> f; struct Car { bool is_vertical; int lx, ly, rx, ry; // or upos dpos Car() : lx(INT_MAX), ly(INT_MAX), rx(0), ry(0) {} } p[10 + 5]; struct Stat { int st[N][N]; void copy() { memcpy(st, a, sizeof(a)); } void paste() { memcpy(a, st, sizeof(a)); } Stat() { memset(st, 0, sizeof(st)); } }; uint64_t encode() { uint64_t seed = 0; for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) seed = (seed + a[i][j]) * SEED; return seed; } void init_car() { for (int i = 1; i <= m; ++i) p[i] = Car(); for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) { int x = a[i][j]; p[x].lx = min(p[x].lx, i); p[x].ly = min(p[x].ly, j); p[x].rx = max(p[x].rx, i); p[x].ry = max(p[x].ry, j); if (p[x].lx == p[x].rx) p[x].is_vertical = false; if (p[x].ly == p[x].ry) p[x].is_vertical = true; } } int bfs() { queue<pair<int, Stat> > que; Stat temp; temp.copy(); que.push(make_pair(0, temp)); while (!que.empty()) { int step = que.front().first; if (step > 8) { return -1; } if (a[2][5] == 1) { return step + 2; } temp = que.front().second; que.pop(); temp.paste(); uint64_t code = encode(); if (f.count(code)) continue; f.insert(code); init_car(); for (int t = 1; t <= m; ++t) { if (p[t].is_vertical) { int lx = p[t].lx; int rx = p[t].rx; int y = p[t].ly; if (0 < lx && a[lx - 1][y] == 0) { a[lx - 1][y] = t; a[rx][y] = 0; temp.copy(); que.push(make_pair(step + 1, temp)); a[rx][y] = t; a[lx - 1][y] = 0; } if (rx + 1 < N && a[rx + 1][y] == 0) { a[rx + 1][y] = t; a[lx][y] = 0; temp.copy(); que.push(make_pair(step + 1, temp)); a[lx][y] = t; a[rx + 1][y] = 0; } } else { int x = p[t].lx; int ly = p[t].ly; int ry = p[t].ry; if (0 < ly && a[x][ly - 1] == 0) { a[x][ly - 1] = t; a[x][ry] = 0; temp.copy(); que.push(make_pair(step + 1, temp)); a[x][ly - 1] = 0; a[x][ry] = t; } if (ry + 1 < N && a[x][ry + 1] == 0) { a[x][ry + 1] = t; a[x][ly] = 0; temp.copy(); que.push(make_pair(step + 1, temp)); a[x][ry + 1] = 0; a[x][ly] = t; } } } } return -1; } int main() { ios::sync_with_stdio(false); for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) { cin >> a[i][j]; m = max(a[i][j], m); } init_car(); cout << bfs() << endl; }

C.Are They All Integers?

题意： 签到 题解： 签到 代码：

#include <bits/stdc++.h> using namespace std; typedef long long LL; int const N = 2e5 + 10; int n, m, T, a[N]; int main() { cin >> n; for (int i = 1; i <=n ; ++i) cin >> a[i]; int flg = 1; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { for (int k = 1; k <= n; ++k) { if (i == j || i == k || j == k) continue; if ((a[i] - a[j]) % a[k] != 0) flg = 0; } } } if (flg) cout << "yes\n"; else cout << "no\n"; return 0; }

D.Tapioka

题意： 签到 题解： 签到 代码：

#include <bits/stdc++.h> using namespace std; typedef long long LL; int const N = 2e5 + 10; int n, m, T, a[N]; string s1 = "tapioka", s2 = "bubble"; int main() { vector<string> res; string s; while(cin >> s) { if (s != s1 && s != s2) res.push_back(s); } if (res.empty()) cout << "nothing"; else { for (auto r: res) cout << r << " "; } return 0; }

E.The League of Sequence Designers

题意： 对于问题$ma{x}_{1<=l<=r<=n}(r-l+1){\sum }_{l<=i<=r}{a}_i$ 给定一段错误代码，输入一个k和l，要求构造出一个长度大于等于l的序列，使得错误代码和正确代码算出来的结果差的绝对值恰好为k。 ​给你一个k和l，k 题解： 观察错误代码错误的原因：错误代码要找到连续的子段，子段的和为正数，然后求出字段和乘上长度，一旦发现负数，那么就改变子段的左区间。而其实改变子段的左区间这个操作不对，可能导致子段的长度变小。因此构造的时候，就要让错误代码找出来的子段长度更小，正确代码找到子段长度更大一些。由于n最大只有1999，因此如果长度大于1999则无法找到答案。为了保证在长度小于等于1999时能够找到这样的合法序列，序列长度取1999.为了保证错误代码找到的子段长度更短，因此第一个数字取-1，这样：错误代码不取第一个，正确代码取第一个，就会导致计算出来的结果不一致。构造方式如下： [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XB9TO4L2-1601731564497)(https://i.loli.net/2020/10/03/bLHDeod2mNI68tU.jpg)] 代码：

#include <bits/stdc++.h> using namespace std; typedef long long LL; int const N = 2e5 + 10; int k, l, T, a[N]; int main() { cin >> T; while(T--) { cin >> k >> l; if (l >= 2000) { cout << -1 << endl; continue; } int sum_suf = 1999 + k; cout << 1999 << endl; cout << -1 << " "; int avg = sum_suf / 1997; for (int i = 2; i <= 1998; ++i) { cout << avg << " "; } cout << sum_suf - avg * 1997 << endl; } return 0; }

H.Mining a

题意： 给定一个式子$\frac{1}{n}=\frac{1}{axorb}+\frac{1}{b}$, 给定n，能够求出很多对(a, b)满足这个式子。要求给出最大的那个a。 题解： 推导如下： [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rYaFSQNb-1601731564500)(https://i.loli.net/2020/10/03/DlT8pYMZL6AW34k.jpg)] 因此，枚举$n^2$的约数即可。 对于给定的异或的式子：

线性基位运算性质:把每一位隔开算异或没有，用其他式子转化，然后就能够得到很多形如$k+\frac{a}{b}$的式子，a是一个确定值，那么枚举a的约数，或者质因数等方法

代码：

#include <bits/stdc++.h> using namespace std; typedef long long LL; int const N = 2e5 + 10; int m, T, a[N]; LL n_2, n; int main() { cin >> T; while(T--) { scanf("%lld", &n); n_2 = n * n; vector<int> divisor; for (int i = 1; i <= n_2 / i; ++i) { // 枚举到sqrtx(x) if (n_2 % i == 0) { // 如果能够整除 divisor.push_back(i); // 放入i if (i != n_2 / i) divisor.push_back(n_2 / i); // x/i不等于i，也放入答案中 } } LL res = -1; int len = divisor.size(); for (int i = 0; i < len; ++i) { int d = divisor[i]; res = max(res, (n + d) ^ (n * n / d + n)); } printf("%lld\n", res); } return 0; }

J.Automatic Control Machine

题意： 有n个物品，每个物品都有m个特征，问最少选择多少个物品，使得所有的特征都能够被选到。 题解： 由于本题物品的数目和特征的数目都非常小，因此直接dfs暴力枚举选择了哪些物品即可。 代码：

#include <bits/stdc++.h> using namespace std; typedef long long LL; int const N = 2e5 + 10; int n, m, T; bitset<600> a[N]; int res; void dfs(int u, bitset<600> now, int cnt) { if (now.count() == m) { res = min(res, cnt); return; } for (int i = u + 1; i <= n; ++i) { bitset<600> next_now = now | a[i]; dfs(i, next_now, cnt + 1); } return; } int main() { cin >> T; while(T--) { res = 1e9; scanf("%d%d", &m, &n); for (int i = 1; i <= n; ++i) { string s; cin >> s; a[i] = bitset<600> (s); } res = 1e9; dfs(0, 0, 0); if (res == 1e9) res = -1; printf("%d\n", res); } return 0; }

K.Length of Bundle Rope

题意： 合并果子签到题 题解： 签到 代码：

#include <bits/stdc++.h> using namespace std; typedef long long LL; int const N = 2e5 + 10; int n, m, T, a[N]; priority_queue<int, vector<int>, greater<int> > q; int main() { cin >> T; while(T--) { cin >> n; for (int i = 1; i <= n; ++i) { int t; cin >> t; q.push(t); } int res = 0; while(q.size()) { if (q.size() == 1) break; int t = q.top(); q.pop(); t += q.top(); res += t; q.pop(); q.push(t); } // res += q.top(); q.pop(); cout << res << endl; } return 0; }

L. Largest Quadrilateral

题意： 计算几何xxxxx 题解： 队友说是旋转卡壳xxxx，不懂，贴上队友代码 代码：

#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <vector> using namespace std; const int N = 5009; int T, n; typedef long long LL; struct point{ LL x, y; point(){} point(LL _x, LL _y):x(_x), y(_y){} bool operator < (point B)const{ if(x != B.x)return x < B.x; else return y < B.y; } LL operator * (point B)const{ return x * B.y - y * B.x; } point operator - (point B)const{ return point(x - B.x, y - B.y); } bool operator == (point B)const{ if(x == B.x && y == B.y)return true; else return false; } void input(){ scanf("%lld%lld", &x, &y); } }; vector<point> ConvexHull(vector<point> p){ vector<point>ch(n + 1);//必須使用後靜態，不然後面無法訪問（因爲其中并沒有pushback東西） sort(p.begin(), p.end()); p.erase(unique(p.begin(), p.end()), p.end()); int n = p.size(); int m = 0; for(int i = 0; i < n; i++) { while(m > 1 && (ch[m - 1]- ch[m - 2]) * (p[i] - ch[m - 2]) <= 0)//邊上可有點 m--; ch[m++] = p[i]; } int k = m; for(int i = n - 2; i >= 0; i--) { while(m > k && (ch[m - 1]- ch[m - 2])*(p[i] - ch[m - 2]) <= 0) m--; ch[m++] = p[i]; } if(n > 1)m--;//ch[m] = ch[0] ch.resize(m);//resize 不會初始化ch[0]...ch[m - 1] return ch; } typedef point Vector; vector<point>v1; LL solve(point U, point V){ vector<point>X; int flagu = 0, flagv = 0; for(auto p:v1){ if(p == U){ flagu++; if(flagu > 1)X.push_back(p); } else if(p == V){ flagv++; if(flagv > 1)X.push_back(p); } else X.push_back(p); } LL max1 = 0, max2 = 0, ans = 0, min1 = 1e18, min2 = 1e18; for(auto p:X){ LL tmp = (V - U) * (p - U); if(tmp > 0){ max1 = max(max1, tmp); min1 = min(min1, tmp); } else{ max2 = max(max2, abs(tmp)); min2 = min(min2, abs(tmp)); } LL q = 0; if(max1 == 0 || max2 == 0){ if(flagu > 1|| flagv > 1)q = max1 + max2; else q = max(max1 - min1, max2 - min2); } else q = max1 + max2; ans = max(ans, q); } return ans; }/* 計算面積的時候用叉乘沒有誤差，用距離計算會出現小數誤差！ 這裏還要注意防備四邊形為只有對踵點一側的凹四邊形的情況 */ int main(){ cin >> T; while(T--){ cin >> n; v1.clear(); vector<point>B; for(int i = 0; i < n; i++){ point p; p.input(); v1.push_back(p); B.push_back(p); } B = ConvexHull(B); int m = B.size(); if(m <= 2){ printf("0\n"); continue; } int j = 1; LL ans = 0; for(int i = 0; i < m; i++){//優化旋轉卡殼 while(abs((B[i] - B[(j + 1) % m]) * (B[(i + 1) % m] - B[(j + 1) % m])) > abs((B[i] - B[j]) * (B[(i + 1) % m] - B[j])) ){ j = (j + 1) % m; } ans = max(ans, solve(B[i], B[j])); } if(ans & 1)printf("%lld.5\n", ans / 2); else printf("%lld\n", ans / 2); } return 0; } /* 繁體中文真刺激。。。 */