期待已久暑假的重头戏终于算是打响了第一枪吧...第一把不出所料的被吊打了...被满场的数学题和自己的菜鸡英语疯狂支配。补题的话，估计只能量力而行了吧 —— 一个题解都推不出来、标程都看不懂的鶸。

A B C D E F G H I J

目前来说再补题可能只会做 C、H...也可能就这样了。

比赛地址： https://ac.nowcoder.com/acm/contest/881#question

【A】 Equivalent Prefixes 单调栈

定义两个数组“相等”的概念：\([1, m]的范围内任取子区间[l, r]都满足区间最小值所在的位置（下标）相同\)。那么给定两个数组，问m的最大取值是多少。

读题把队友全演了...前两发wa都是题读错了，然后后面怎么都走不出原来的想法。后面队友完全推倒重写单调栈可算是过了。然后题解说的笛卡尔树也是一头雾水，于是...单调栈重写了一遍。以下为赛后补题代码：

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 1e5+5; int a[maxn], b[maxn]; int main() { int n; while(~scanf("%d", &n)) { for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for(int i = 1; i <= n; i++) { scanf("%d", &b[i]); } int flag = 1; stack<int> sa, sb; for(int i = 1; i <= n; i++) { while(!sa.empty() && a[i] < a[sa.top()]) { sa.pop(); } sa.push(i); while(!sb.empty() && b[i] < b[sb.top()]) { sb.pop(); } sb.push(i); if(sa.size() != sb.size()) { printf("%d\n", i-1); flag = 0; break; } } if(flag == 1) { printf("%d\n", n); } } return 0; }

【B】 Integration 数学

众所周知：\(\int^{\infty}_{0} \frac{1}{1+x^2} dx = \frac{\pi}{2}\) 。然后给你 n 个数，求：\[\frac{1}{\pi} \int^{\infty}_{0} \frac{1}{\prod^{n}_{i=1}(a_i^2+x^2)} dx\]

然后得到的大概会是个分数，需要把 \(\frac{p}{q}\) 的形式化成 \(p*q^{-1} mod (1e^9+7)\)。

高数60+菜鸡飘过，推不出来也不怪我对吧...

令：\[c_i = \frac{1}{\prod_{j\neq i}(a_j^2 - a_i^2)}\]

则：\[\frac{1}{\prod(a_i^2 + x^2)} = \sum \frac{c_i}{a_i^2+x^2}\]

而：\[\int^{\infty}_{0}\frac{c_i}{a_i^2+x^2}dx = \frac{c_i}{2a_i}\pi\]

题解万岁

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 1e3+5; ll _c[maxn]; ll a[maxn]; ll q_pow(ll a, ll b) { ll ans = 1; while(b) { if(b & 1) { ans = ans * a % mod; } a = a * a % mod; b >>= 1; } return ans; } int main() { int n; while(~scanf("%d", &n)) { ll ans = 0; for(int i = 0; i <= n; i++) { _c[i] = 1; } for(int i = 1; i <= n; i++) { scanf("%lld", &a[i]); } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(i == j) { continue; } _c[i] = _c[i] * (a[j]*a[j]%mod - a[i]*a[i]%mod + mod) % mod; } _c[i] = _c[i] * 2ll * a[i] % mod; ans = (ans + q_pow(_c[i], mod-2)) % mod; } printf("%lld\n", ans); } return 0; }

【C】 Euclidean Distance 数学

思路和题解均为转载 侵删https://blog.csdn.net/Dillonh/article/details/96501358

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 1e4+5; ll a[maxn]; bool cmp(ll a, ll b) { return a > b; } ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b); } int main() { int n, m; while(~scanf("%d%d", &n, &m)) { for(int i = 1; i <= n; i++) { scanf("%lld", &a[i]); } sort(a+1, a+1+n, cmp); int id = n; int rst = m; for(int i = 1; i < n; i++) { if(i*(a[i]-a[i+1]) > rst) { id = i; break; } rst = rst - i*(a[i]-a[i+1]); } ll x = 1ll * (id*a[id]-rst) * (id*a[id]-rst); for(int i = id+1; i <= n; i++) { x = x + 1ll*id*a[i]*a[i]; } ll y = 1ll * (id * m * m); ll z = gcd(x, y); x = x / z; y = y / z; if(x == 0 || y == 1) { printf("%lld\n", x); } else { printf("%lld/%lld\n", x, y); } } return 0; }

【E】 ABBA 动态规划DP

有一个长度为 \(2(n+m)\)的字符串，它的子序列可以拆分成：“n 个AB、m 个BA”。问总共有多少种排序方式。

emmm...可能还是 dp 刷的少了，想到是 dp 但是没想到是按 A、B 的个数进行转移。

\(dp[i][j] 表示前缀有 i 个 A、 j 个 B\) 然后跑 \(n^2\) 每次都要按 A、B 插入进行转移，边界需要处理比较麻烦。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 2e3+5; int n, m; int dp[maxn][maxn]; // dp[i][j] 表示前缀有 i 个 A、 j 个 B int main() { while(~scanf("%d%d", &n, &m)) { int l = n+m; for(int i = 0; i <= l+1; i++) { for(int j = 0; j <= l+1; j++) { dp[i][j] = 0; } } dp[0][0] = 1; for(int i = 0; i <= l; i++) { for(int j = 0; j <= l; j++) { if(i <= n-1 || i-n <= min(j, m)-1) { // 因为 i 从 0 开始，所以最大只能到 n-1；后边也同理 dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % mod; } if(j <= m-1 || j-m <= min(i, n)-1) { dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % mod; } } } printf("%d\n", dp[l][l]); } return 0; }

【F】 Random Point in Triangle 数学（暴力）

给定三角形的三点，现在有一个点 P 会随机落在三角形内，问 期望值 \(E = max\{S_{PAB},S_{PBC},S_{PCA}\}\)，输出的答案需要乘以 36。

这个乘 36 就给的很精髓了...因为数据太大，所以不能直接用海伦公式（反正我WA了），所以就用 longlong 和割补法去消除误差。然后通过计算（随机数统计然后再猜一猜也行）发现答案应该是三角形面积的 \(\frac{11}{2}\)。别问为什么，问就是队友做的。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 5; struct node { ll x, y; bool operator < (const node &a) const { return x < a.x; } }p[maxn]; int main() { ll x1, x2, x3, y1, y2, y3; while(~scanf("%lld%lld%lld%lld%lld%lld", &p[1].x, &p[1].y, &p[2].x, &p[2].y, &p[3].x, &p[3].y)) { for(int i = 1; i <= 3; i++) { p[i].x += 100000000; p[i].y += 100000000; } sort(p+1, p+1+3); ll m, n; ll s1, s2, s3; m = p[1].y + p[2].y; n = p[2].x - p[1].x; s1 = m * n; m = p[3].y + p[2].y; n = p[3].x - p[2].x; s2 = m * n; m = p[3].y + p[1].y; n = p[3].x - p[1].x; s3 = m * n; ll ans = abs(s1 + s2 - s3); printf("%lld\n", ans*11ll); } return 0; }

【J】 Fraction Comparision 暴力

给定两个分数，让你判断哪个更大。

显然直接除法的话...精度不够对吧，然后就想着用\(\_\_int128\)了。然后队伍里没一个会读入的，然后就先读入 longlong ，计算的时候在强转就行了。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; int main() { ll x, a, y, b; while(~scanf("%lld%lld%lld%lld", &x, &a, &y, &b)) { __int128 ans1 = (__int128)x*b, ans2 = (__int128)y*a; if(ans1 > ans2) { printf(">\n"); } else if(ans1 == ans2){ printf("=\n"); } else { printf("<\n"); } } return 0; }

相信我，我一定会补题的【咕咕咕】。

转载于:https://www.cnblogs.com/Decray/p/11210886.html