ACM/ICPC

Codeforces Round #664 https://codeforces.com/contest/1395 A 题意 给四种颜色的球，可以把一个红色一个蓝色一个绿色染成白色，问能不能变成回文串 #include <cstdio> #include <stack> #include <set> #include <cmath> #include <map> #include <time.h> #include <vector> #include <iostream> #include <string> #include <cstring> #include <algorithm> //#include <memory.h> #include <cstdlib> #include <queue> #include <iomanip> #include <cassert> #include <unordered_map> #define P pair<int, int> #define LL long long #define LD long double #define PLL pair<LL, LL> #define mset(a, b) memset(a, b, sizeof(a)) #define rep(i, a, b) for (int i = a; i < b; i++) #define PI acos(-1.0) #define random(x) rand() % x #define debug(x) cout << #x << " " << x << "\n" using namespace std; const int inf = 0x3f3f3f3f; const LL __64inf = 0x3f3f3f3f3f3f3f3f; #ifdef DEBUG const int MAX = 2e3 + 50; #else const int MAX = 2e6 + 500; #endif const int mod = 1e9 + 7; void file_read() { #ifdef DEBUG freopen("in", "r", stdin); // freopen("out", "w", stdout); #endif } int main() { file_read(); int T; LL a, b, c, d; scanf("%d", &T); while (T--) { cin >> a >> b >> c >> d; LL tot = a + b + c + d; if(tot & 1) { int odd = (a & 1) + (b & 1) + (c & 1) + (d & 1); if(odd == 1) { puts("Yes"); continue; } if(a > 0 and b > 0 and c > 0) { a--, b--, c--, d+=3; odd = (a & 1) + (b & 1) + (c & 1) + (d & 1); if(odd == 1) { puts("Yes"); continue; } } puts("No"); continue; } else { int odd = (a & 1) + (b & 1) + (c & 1) + (d & 1); if(odd == 0 ) { puts("Yes"); continue; } if(a > 0 and b > 0 and c > 0 and d > 0) { a--, b--, c--, d += 3; odd = (a & 1) + (b & 1) + (c & 1) + (d & 1); if(odd == 0) { puts("Yes"); continue; } } puts("No"); } } return 0; } B 题意 ...

Gym - 102501D Gnalcats https://codeforces.com/gym/102501/problem/D 题意 给两种栈操作判断是否相等,如果两个操作都fail，也认为相等 Solution 模拟，每个氨基酸一个hash值。通过判断最后栈元素是否对应hash相等，判断操作是否相等 #include <cstdio> #include <stack> #include <set> #include <cmath> #include <map> #include <time.h> #include <vector> #include <iostream> #include <string> #include <cstring> #include <algorithm> //#include <memory.h> #include <cstdlib> #include <queue> #include <iomanip> #include <cassert> #include <unordered_map> #define P pair<int, int> #define LL long long #define LD long double #define PLL pair<LL, LL> #define mset(a, b) memset(a, b, sizeof(a)) #define rep(i, a, b) for (int i = a; i < b; i++) #define PI acos(-1.0) #define random(x) rand() % x #define debug(x) cout << #x << " " << x << "\n" using namespace std; const int inf = 0x3f3f3f3f; const LL __64inf = 0x3f3f3f3f3f3f3f3f; #ifdef DEBUG const int MAX = 2e3 + 50; #else const int MAX = 1e6 + 50; #endif const int mod = 1e9 + 7; void file_read() { #ifdef DEBUG freopen("in", "r", stdin); // freopen("out", "w", stdout); #endif } #define ULL unsigned long long struct DNA { struct Node { int l, r; unsigned LL val; Node(){} Node(int l, int r, unsigned LL val) : l(l), r(r), val(val) {} bool complex() const { return l and r; } }tr[MAX]; stack<int> stk; int tot; int num; DNA() : tot(1), num(1) { for(int i = 1; i <= (int)1e5; i++) { tr[tot] = Node(0, 0, num++); stk.push(tot); tot++; } } ULL hash(int u, int v) { ULL base = 131; return tr[u].val * base + tr[v].val; } bool op_C() { auto u = stk.top(); tr[tot] = tr[u]; stk.push(tot); tot++; return true; } bool op_D() { stk.pop(); return true; } bool op_L() { auto u = stk.top(); stk.pop(); if(!tr[u].complex()) return false; // tr[tot] = tr[tr[u].l]; // stk.push(tot); stk.push(tr[u].l); return true; } bool op_P() { auto u = stk.top(); stk.pop(); auto v = stk.top(); stk.pop(); tr[tot] = Node(u, v, hash(u, v)); stk.push(tot); tot++; return true; } bool op_R() { auto u = stk.top(); stk.pop(); if(!tr[u].complex()) return false; // tr[tot] = tr[tr[u].r]; // stk.push(tot++); stk.push(tr[u].r); return true; } bool op_S() { auto u = stk.top(); stk.pop(); auto v = stk.top(); stk.pop(); stk.push(u); stk.push(v); return true; } bool op_U() { auto u = stk.top(); stk.pop(); if(!tr[u].complex()) return false; stk.push(tr[u].r); stk.push(tr[u].l); return true; } bool op(const string &s) { bool res = true; for(auto c : s) { switch (c) { case 'C':res &= op_C(); break; case 'D':res &= op_D(); break; case 'L':res &= op_L(); break; case 'P':res &= op_P(); break; case 'R':res &= op_R(); break; case 'S':res &= op_S(); break; case 'U':res &= op_U(); break; default: break; } } return res ; } }; DNA A, B; int main() { file_read(); string s, t; cin >> s >> t; A = DNA(); B = DNA(); bool a = A.op(s); bool b = B.op(t); if(a ^ b) { puts("False"); return 0; } if(!a and !b) { puts("True"); return 0; } while(!A.stk.empty() and !B.stk.empty()) { auto u = A.stk.top(); A.stk.pop(); auto v = B.stk.top(); B.stk.pop(); if(A.tr[u].val != B.tr[v].val) { puts("False"); return 0; } } if(!A.stk.empty() || !B.stk.empty()) { puts("False"); return 0; } puts("True"); return 0; } Gym - 102501J https://codeforces.com/gym/102501/problem/J ...

Gym 102460L Largest Quadrilateral Largest Quadrilateral 题意 给$n$个点从中选出四个点，使得面积最大 Solution 首先，肯定是求凸包，要求的点一定在凸包上。 不难联想到凸包对每个边求最大三角形面积的问题，也就是旋转卡壳。 可以将问题转化为，对凸包的每一个对角线$A_iA_j$，求最大面积的两个三角形，$\triangle{A_iA_jP}$, $\triangle{A_iA_jQ}$, 然后就可以枚举对角线，旋转卡壳算最大面积 细节 输出的格式 凸包上应该留下共线的点 #include <cstdio> #include <stack> #include <set> #include <cmath> #include <map> #include <time.h> #include <vector> #include <iostream> #include <string> #include <cstring> #include <algorithm> //#include <memory.h> #include <cstdlib> #include <queue> #include <iomanip> #include <cassert> // #include <unordered_map> #define P pair<int, int> #define LL long long #define LD long double #define PLL pair<LL, LL> #define mset(a, b) memset(a, b, sizeof(a)) #define rep(i, a, b) for (int i = a; i < b; i++) #define PI acos(-1.0) #define random(x) rand() % x #define debug(x) cout << #x << " " << x << "\n" using namespace std; const int inf = 0x3f3f3f3f; const LL __64inf = 0x3f3f3f3f3f3f3f3f; #ifdef DEBUG const int MAX = 2e3 + 50; #else const int MAX = 1e6 + 50; #endif const int mod = 1e9+9; void file_read(){ #ifdef DEBUG freopen("in", "r", stdin); // freopen("out", "w", stdout); #endif } template<typename type> struct Vec { type x, y; Vec() {} Vec(type x, type y) : x(x), y(y) {} friend istream & operator >> (istream &in, Vec &A) { in >> A.x >> A.y; return in; } friend Vec operator - (const Vec &A, const Vec &B) { return Vec(A.x-B.x, A.y-B.y); } friend Vec operator + (const Vec &A, const Vec &B) { return Vec(A.x + B.x, A.y + B.y); } friend type det(const Vec &A, const Vec &B) { return A.x * B.y - A.y * B.x; } friend type dot(const Vec &A, const Vec &B) { return A.x * B.x + A.y * B.y; } friend bool operator < (const Vec &A, const Vec &B) { if(A.x != B.x) return A.x < B.x; return A.y < B.y; } friend type area(const Vec &A, const Vec &B) { return abs(det(A, B)); } friend type operator == (const Vec &A, const Vec &B) { return A.x == B.x and A.y == B.y; } }; template<typename type> vector<Vec<type>> convex_hull(vector<Vec<type>> &pt) { sort(pt.begin(), pt.end()); int n = pt.size(); vector<Vec<type>> res(2*n); int k = 0 ; for(int i = 0; i < n; i++) { while(k > 1 and det(res[k-1]-res[k-2], pt[i]-res[k-1]) < 0) // <=会wa k--; res[k++] = pt[i]; } for(int i = n-2, t = k; i >= 0; i--) { while(k > t and det(res[k-1]-res[k-2], pt[i]-res[k-1]) < 0) // <=会wa k--; res[k++] = pt[i]; } res.resize(k-1); return res; } struct ModI { int i, n; ModI(int n ) : i(0), n(n) { assert(n > 0) ;} ModI(int i, int n) : i(i%n), n(n) { assert(n > 0); } ModI operator ++ ( int ) { ModI row = ModI(i, n); i = (i + 1) % n; return row; } ModI operator + (int x) { ModI res = ModI(i, n); res.i = (res.i + x) % n; return res; } int operator = (int x) { return i = x; } bool operator < (int x) const { return i < x; } bool operator == (const ModI &other) const { return i == other.i; } operator int () { return i; } }; template<typename type> type area(const Vec<type> &A, const Vec<type> &B, const Vec<type> &C) { return area(A-B, A-C); } template<typename type> type rotateCalipers(vector<Vec<type>> pt) { int n = pt.size(); type res = 0; for(int i = 0; i < pt.size(); i++) { ModI p1 = ModI(i+1, n); ModI p2 = ModI(i+3, n); for(ModI j = ModI(i+2, n); j+1 != i; j++) { while(p1+1 != j and area(pt[p1], pt[i], pt[j]) < area(pt[p1+1], pt[i], pt[j])) p1 ++; if(j == p2) p2++; while(p2+1 != i and area(pt[p2], pt[i], pt[j]) < area(pt[p2+1], pt[i], pt[j])) p2 ++; auto cur = area(pt[p1], pt[i], pt[j]) + area(pt[p2], pt[i], pt[j]); res = max(res, cur); } } return res; } void out(LL ans) { if(ans & 1) { printf("%lld.5\n", ans >> 1); } else { printf("%lld\n", ans >> 1); } } int main() { file_read(); int T; scanf("%d", &T); while (T--) { int n; scanf("%d", &n); vector<Vec<LL>> pt(n); for(int i = 0; i < n; i++) cin >> pt[i]; auto ch = convex_hull(pt); if(ch.size() < 3) { printf("0\n"); continue; } if(ch.size() == 3) { LL ans = 0; LL A = area(ch[0], ch[1], ch[2]); for(auto p : pt) { if(p == ch[0] or p == ch[1] or p == ch[2]) continue; auto a = area(p, ch[1], ch[2]); a = min(a, area(p, ch[0], ch[2])); a = min(a, area(p, ch[0], ch[1])); ans = max(ans, A-a); } out(ans); continue; } LL res = rotateCalipers(ch); out(res); } return 0; }

Codeforces Round #663 http://codeforces.com/contest/1391 C 题意 对于一个排列${p_1, p_2, \dots, p_n}$，对于每个数字$p_i$，向前找第一个大于$p_i$的$p_j$，$i$和$j$连一条边，向后同理。求多少种排列生成的图是有环的 Solution 对于$p_i$，如果存在$p_j>p_i(j<i)$, $p_k>p_i(k>i)$，那么就是存在环的 那么对于$\forall i$都不成立时，就没有环 此时就是序列的特点就是,数字$n$左边和右边向两边递减 因此排列数就是$n!-2^{n-1}$ #include <cstdio> #include <stack> #include <set> #include <cmath> #include <map> #include <time.h> #include <vector> #include <iostream> #include <string> #include <cstring> #include <algorithm> #include <cstdlib> #include <queue> #include <iomanip> #include <cassert> #define P pair<int, int> #define LL long long #define LD long double #define PLL pair<LL, LL> #define mset(a, b) memset(a, b, sizeof(a)) #define rep(i, a, b) for (int i = a; i < b; i++) #define PI acos(-1.0) #define random(x) rand() % x #define debug(x) cout << #x << " " << x << "\n" using namespace std; const LL inf = 0x3f3f3f3f3f3f3f3f; #ifdef DEBUG const int MAX = 2e3 + 50; #else const int MAX = 2e6 + 50; #endif const int mod = 1e9+7; void file_read(){ #ifdef DEBUG freopen("in", "r", stdin); #endif } int main(){ file_read(); LL n; scanf("%lld\n", &n); LL fact = 1; for(LL i = 1; i <= n; i++) { fact = fact * i % mod; } LL pow2 = 1; for(int i = 1; i < n; i++) { pow2 = pow2 * 2 % mod; } LL res = (fact - pow2) % mod; if(res < 0) res += mod; printf("%lld\n", res); } D 题意 ...

Codeforces Round #660 https://codeforces.com/contest/1388 E 题意 平面上有一些线段，将他们投影到$x$轴上，使得彼此不想交(但是可以挨着)，设最左边的点和最右边的点的横坐标分别是$x_l, x_r$， 求$min{x_r-x_l}$ Solution 首先对于两个线段$s_1, s_2$, 并且$s_1.y < s_2.y$, 交叉连接他们的左右端点，得到一个向量集合$bound$，对投影向量限制限制。 因此先两两枚举，得到投影向量的可行的取值。 而且最优的投影向量，是集合$bound$中的某一项 因此，对剩下的可行的投影向量, 假设当前枚举的方向是$k_i$，计算 $$ max{x_j+y_jKi}-min{x_j+y_jk_i} $$ 计算这个式子可以用Convex hull trick, 然后不断更新ans #include <cstdio> #include <stack> #include <set> #include <cmath> #include <map> #include <time.h> #include <vector> #include <iostream> #include <string> #include <cstring> #include <algorithm> #include <memory.h> #include <cstdlib> #include <queue> #include <iomanip> #include <bitset> #include <unordered_map> #include <assert.h> #include <list> #define P pair<int, int> #define LL long long #define LD long double #define PLL pair<LL, LL> #define mset(a, b) memset(a, b, sizeof(a)) #define rep(i, a, b) for (int i = a; i < b; i++) #define PI acos(-1.0) #define random(x) rand() % x #define debug(x) cout << #x << " " << x << "\n" using namespace std; const int inf = 0x3f3f3f3f; const LL __64inf = 0x3f3f3f3f3f3f3f3f; #ifdef DEBUG const int MAX = 1e3 + 50; #else const int MAX = 1e6 + 50; #endif const int mod = 998244353; void file_read(){ #ifdef DEBUG freopen64("in", "r", stdin); #endif } struct Seg { double xl, xr, y; Seg(double xl, double xr, double y) : xl(xl), xr(xr), y(y) {} }; vector<Seg> seg; vector<pair<double, double>> bd; void bound() { for(int i = 0; i < seg.size(); i++) { for(int j = i+1; j < seg.size(); j++) { if(seg[i].y == seg[j].y) continue; auto s1 = seg[i]; auto s2 = seg[j]; if(s1.y > s2.y) swap(s1, s2); double beta1 = (s1.xr - s2.xl) / (s2.y - s1.y); double beta2 = (s1.xl - s2.xr) / (s2.y - s1.y); bd.emplace_back(beta2, beta1); } } } void filter(vector<double> &theta) { double cur = -__64inf; for(auto x : bd) { if(x.first >= cur) { theta.push_back(x.first); if(cur > -__64inf) theta.push_back(cur); } cur = max(cur, x.second); } theta.push_back(cur); } double cross(pair<double, double> A, pair<double, double> B) { return (A.first - B.first) / (B.second - A.second); } template<typename Cmp_1, typename Cmp_2> struct Convex { int top; vector<pair<double, double>> pts; vector<double> X; pair<double, double> stk[3000]; Cmp_1 cmp_1; Cmp_2 cmp_2; Convex(vector<Seg> &seg) : cmp_1(Cmp_1()), cmp_2(Cmp_2()) { for(auto s : seg) { pts.emplace_back(s.xl, s.y); pts.emplace_back(s.xr, s.y); } sort(pts.begin(), pts.end(), [this](const pair<double, double> &A, const pair<double, double> &B){ if(abs(A.second - B.second) < 1e-8 ) return this->cmp_1(A.first, B.first);//return A.first < B.first; // return A.second > B.second; return this->cmp_2(A.second, B.second); }); int i = 0; top = 0; stk[top++] = pts[0]; while(i < pts.size() and abs(pts[i].second-pts[0].second) < 1e-8) i++; if(i == pts.size()) { X.push_back(-__64inf); return ; } stk[top++] = pts[i++]; while(i < pts.size()) { int j = i; while(j < pts.size() and abs(pts[j].second-pts[i].second) < 1e-8) j++; if(j == pts.size()) break; auto cur = pts[j]; while(top >= 2) { double cross_x = cross(stk[top-1], stk[top-2]); double cross_cur = cross(cur, stk[top-2]); if(cross_cur < cross_x) top--; else break; } stk[top++] = cur; i = j+1; } X.push_back(-__64inf); for(int i = 1; i < top; i++) { X.push_back(cross(stk[i-1], stk[i])); } } double query(double a) { int idx = lower_bound(X.begin(), X.end(), a)- X.begin(); idx--; return stk[idx].first + stk[idx].second * a; } }; struct Less { bool operator () (double A, double B) { return A < B; } }; struct Great { bool operator () (double A, double B) { return A > B; } }; int main(){ #ifdef DEBUG freopen64("in", "r", stdin); #endif int n; scanf("%d", &n); set<double> Y; for(int i = 0; i < n; i++) { double xl, xr, y; scanf("%lf%lf%lf", &xl, &xr, &y) ; seg.emplace_back(xl, xr, y); Y.insert(y); } if(Y.size() == 1) { double Min = __64inf, Max = -__64inf; for(auto s : seg) { Min = min(s.xl, Min); Max = max(Max, s.xr); } printf("%.10f\n", Max-Min); return 0; } bound(); vector<double> theta; sort(bd.begin(), bd.end()); filter(theta); #ifdef DEBUG for(auto t : theta) printf("%.2f ", t); puts(""); #endif double ans = __64inf; Convex<Less, Great> left(seg); Convex<Great, Less> right(seg); for(auto x : theta) { double l = left.query(x); double r = right.query(x); ans = min(ans, r-l); } printf("%.10f\n", ans); } A B C D A B C D ...