牛客多校赛题解 （一）

1. Ball Dropping

题目链接：https://ac.nowcoder.com/acm/contest/11166/B

题目大意

给你一个中间空的等腰梯形。
然后有一个圆，问你是否能从中间穿过梯形。

解题思路：

很明显，当圆的直径大于b时，就不可能掉下去，因此，这道题我们可以通过相似三角形解决

我们可以得出公式：

求解得：

继续计算：

ACCode:

#include <bits/stdc++.h>
using namespace std;
 
long double r, a, b, h;
 
int main() {
    scanf("%Lf %Lf %Lf %Lf", &r, &a, &b, &h);
    if (a < b) swap(a, b);
 
    if ((r * 2.0) <= b) printf("Drop");
        else {
            printf("Stuck\n");
            long double beta = b * h / (a - b);
            long double side = sqrt((a / 2) * (a / 2) + (beta + h) * (beta + h));
            printf("%Lf", side * r / (a / 2) - beta);
        }
 
    return 0;
}

2. Find 3-friendly Integers

题目大意：

给定一个区间，问这个区间里的数，有多少个是满足子串是三的倍数的

解题思路：

通过演算，我发现三位数一定是满足的，因此只需要判断0-99是否满足，因为只有一百的数据量，直接打表就好，再利用前缀和快速求解

ACCode：

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2021-07-22 23:07:00
 * @Description: 
 * @Website: https://grimoire.cn
 * Copyright (c) Mr.Sen All rights reserved.
 */
#include <iostream>
using namespace std;

long long dp[105] = {0, 0, 0, 1, 1, 1, 2, 2, 2, 3}; //前缀和数组  个位数直接打表
long long t, lef, rig;

long long ans(long long x)
{
    if (x <= 99)
        return dp[x];
    else
        return x - 99 + dp[99];
}
int main()
{
    for (int i = 10; i <= 99; i++)
    {
        if (i % 10 % 3 == 0 || i / 10 % 3 == 0 || i % 3 == 0)
        {
            dp[i] = dp[i - 1] + 1;
        }
        else
        {
            dp[i] = dp[i - 1];
        }
    }
    cin >> t;
    while (t--)
    {
        cin >> lef >> rig;
        cout << ans(rig) - ans(lef - 1) << endl;
    }
    return 0;
}