G - 签到题
A - 简单题
题意就是给一堆区间把所有相交的区间合并,找出合并后,所有区间后的空隙有多少
void solve() {
cin >> n;
vector<pii> a;
for (int i = 1, x, y; i <= n; i++) {
cin >> x >> y;
a.push_back({x - y, x + y});
}
sort(ALL(a));
//ALL就是a.begin(), a.end()
vector<pii> ans;
for (int i = 0; i < n; i++) {
if (!ans.size() || ans.back().y < a[i].x)
ans.push_back(make_pair(a[i].x, a[i].y));
//如果当前区间的左区间和下一个的右区间不相交则暂时将他放入数组
//不直接算的原因是由于害怕后面有超级大区间将前面的区间囊括
else
ans.back().y = max(ans.back().y, a[i].y),
ans.back().x = min(ans.back().x, a[i].x);
// 如果相交,融合两个区间
}
ll res = 0;
for (int i = ans.size() - 1; i >= 1; i--) {
if (ans[i].x > ans[i - 1].y) res += ans[i].x - ans[i - 1].y;
//由于从前往后的超级大区间已经被排除完。
//当前可从后往前,判断刚刚前面担心的超级大区间,没有就可以直接计算出值
}
cout << res << endl;
return;
}
D-几何题
比赛时理解错题意,现在大概了解题意,看楼下大佬画的图恍然大悟 不会证明,蹲一手证明。 大佬题解: https://blog.nowcoder.net/n/34a8ced47a0f481ba5337ca3a587ea10
void solve() {
double r, x, y, d;
cin >> r >> x >> y >> d;
double u = sqrt(x * x + y * y);
double ax = acos((u + d) / r), bx = acos((u - d) / r);
printf("%.13lf\n", r * (bx - ax));
return;
}
I期望dp
一道简单的区间dp
ll res[20];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
for (int k = 1; k <= 13; k += 2) {
vector<vll> dp(130, vll(20));
dp[0][k] = 1;
for (int i = 1; i <= 121; i++)
for (int j = 1; j <= 13; j += 2)
dp[i][j] = ((dp[i - 1][j] * (124 - i - 3 * j) % MOD +
dp[i - 1][j + 2] * (3 * j + 6) % MOD) %
MOD) *
quick_Pow((124 - i), MOD - 2, MOD) % MOD;
ll ans = 0;
for (ll i = 1; i <= 121; i++)
ans = (ans +
i * dp[i - 1][1] * 3 % MOD * quick_Pow(124 - i, MOD - 2, MOD) % MOD) %
MOD;
res[k] = ans;
}
int t;
cin >> t;
while (t--) solve();
return 0;
}
int num;
void solve() {
string s;
cin >> s;
int cnt = 13;
for (int i = 0; i < 13; i++)
for (int j = i + 1; j < 13; j++)
if (s[i * 2] == s[j * 2] && s[i * 2 + 1] == s[j * 2 + 1]) cnt -= 2;
cout << "Case #" << ++num << ": ";
cout << res[cnt] << endl;
return;
}