题解--2021牛客暑期多校训练营1

D-Determine the Photo Position

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

　　签到。给一个由 '0' 和 '1' 组成，大小为 n*n 的二维数组。问有几个位置满足连续 '0' 的数量不少于 m。
　　 $图片说明$ 遍历数组，变量 cur 记录该行遍历到当前列时遇到的连续'0'的数量，当 cur 不少于 m 时，记录方案数的变量 ans++。

　　代码:

#include<bits/stdc++.h>

using namespace std; 
using ld=long double; using ll=long long; using ull=unsigned long long; using pii=std::pair<int, int>; using pll=std::pair<long long, long long>; using pil=std::pair<int, long long>; using pli=std::pair<long long, int>; 
inline bool wstr(std::string &_var, bool _ed=0){ std::string _tmp; auto _ch=getchar(); { while(_ch<=32-_ed) if(_ch==-1){return 0; }else{_ch=getchar(); } } { while(((_ch!=' ')|_ed)&&_ch!='\n'&&_ch>=0) _tmp+=(char)_ch, _ch=getchar(); } _var=_tmp; return 1; } 
#define wsln(_var) wstr(_var, 1)

const int mod=1e9+7; 

string g[2001]; 

int main() { 
    int n, m; cin>>n>>m; 
    string s; 

    for(int i=1; i<=n; i++) wstr(g[i]); 
    wstr(s); 

    if(n<m) {
        puts("0");
        return 0;
    }

    int ans=0;
    for(int i=1;i<=n;i++) for(int j=0,cur=0; j<=n; j++) { 
        cur=g[i][j]=='0'? cur+1 : 0; 
        if(cur>=m) ans++; 
    } 

    cout<<ans<<endl; 

    return 0; 
}

B-Ball Dropping

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

　　比较复杂的几何题，于等腰梯形的下底右(左)侧一点作垂直于上底的垂线，得到垂线与斜边的夹角的三角函数值(正/余弦，正/余切均可) f1 。从圆心作垂直于斜边的垂线(会等于 r)，再从该垂点做一条平行于上下边的直线，利用之前得到的三角函数值以及夹角与 "等腰梯形的下底右(左)侧一点作垂直于上底的垂线，得到垂线与斜边的夹角"之值相等的情况，通过 f1 算出点到梯形中线的距离 len ，以及圆心到直线的距离 ans1。由 len 与 b/2 的差和 f1 得到下底到直线的距离 ans2。得到 ans=ans1+ans2。
　　容易发现，当且仅当 2r<b 时，球会漏出。当 2r=b 时，答案为 0。

　　示意图:
图片说明

　　代码:

#include<bits/stdc++.h>

using namespace std; 

const int mod=1e9+7; 

int main() { 
    double r,a,b,h,m; scanf("%lf %lf %lf %lf",&r, &a, &b, &h); 
    m=(a-b)/2; 
    if(r*2<=b) { 
        puts(r*2==b? "Stuck\n0" : "Drop"); 
        return 0; 
    } 

    double sinx=m/sqrt(m*m+h*h), cosx=sinx*h/m; 

    printf("Stuck\n%.10lf\n", r*sinx+(r*cosx-b/2)/(m/h)); 

    return 0; 
}

F-Find 3-friendly Integers

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

　　每次给一组 L, R，输出区间 [L, R] 内其转为字符串后子串转化为整数能被 3 整除的整数的数量。由于常数范围达 1e18，每次查询的复杂度必须接近 $图片说明$ 。
　　找规律发现，当 n>=100 时，将每一位对 3 取模，总能满足 {count(0)>=1, count(1)>=3, count(1)>=1 && count(2)>=1} 中的一种情况，使得所有满足 n>=100 的整数 n 都满足 3-友好。因此只需打表处理 n<100 的情况即可。

代码:

#include<bits/stdc++.h>

using namespace std; 
using ld=long double; using ll=long long; using ull=unsigned long long; using pii=std::pair<int, int>; using pll=std::pair<long long, long long>; using pil=std::pair<int, long long>; using pli=std::pair<long long, int>; 

const int mod=1e9+7; 

int fx[100]={0}; 
inline void init() { 
    for(int i=1; i<=99; i++) fx[i]=fx[i-1]+((i%3==0)|((i%10)%3==0)|((i>=10)&((i/10)%3==0))); 
} 

inline ull calc(ll a) { 
    return a<=99? fx[a] : fx[99]+a-99; 
} 

inline void solve() { 
    ll l, r; scanf("%lld%lld", &l, &r); 
    printf("%lld\n", calc(r)-calc(l-1)); 
} 

int main() { 
    //ios::sync_with_stdio(false); cin.tie(0); 
    init(); 
    int cases; cin>>cases; 
    while(cases--) solve(); 

    return 0; 
}