【题解】2020牛客寒假算法基础集训营5

野性酷女 2023-07-05 10:26 8阅读 0赞

> 比赛链接：[https://ac.nowcoder.com/acm/contest/3006][https_ac.nowcoder.com_acm_contest_3006]  
> 其他比赛题解：  
> [【题解】2020牛客寒假算法基础集训营1][2020_1]  
> [【题解】2020牛客寒假算法基础集训营2][2020_2]  
> [【题解】2020牛客寒假算法基础集训营3][2020_3]  
> [【题解】2020牛客寒假算法基础集训营4][2020_4]

### 试题目录 ###

*  A - 模板（签到）
 *  E - Enjoy the game（思维+规律）
 *  I - I题是个签到题（签到）
 *  J - 牛牛战队的秀场（计算几何）

# A - 模板（签到） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3006/A][https_ac.nowcoder.com_acm_contest_3006_A]

*  **思路：** 两个字符串差值加上相同长度字符串相应下标的不同字符数量。

**Code：**

#include <iostream>
    using namespace std;
    typedef long long ll;
    int main(){ 
        int n,m;    cin>>n>>m;
        string s1,s2;    cin>>s1>>s2;
        ll ans=max(n,m)-min(n,m);
        for(int i=0;i<min(n,m);i++){ 
            if(s1[i]!=s2[i])
                ans++;
        }
        cout<<ans<<endl;
        return 0;
    }

# E - Enjoy the game（思维+规律） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3006/E][https_ac.nowcoder.com_acm_contest_3006_E]

*  **思路：** 如果是奇数，那么先手Bob肯定赢（一开始就取1），也就是说要取的时候刚好是个奇数就能赢，那我们就要尽可能让Bob取到，这就是突破口。当为偶数时，Bob不能取奇数个，那么Bob只能取偶数，比如 n==10，Bob取2，把2当成1， 我们可以发现规律，10 可以变成 5 个 2，可以看成 Bob 一开始取的就是奇数。可以发现规律，只要是 2 的幂次方，Alice 必胜，否则 Bob 必胜。

**Code：**

#include <iostream>
    using namespace std;
    typedef long long ll;
    int main(){ 
        ll n;    cin>>n;
        while(n%2==0)
            n/=2;
        if(n==1)    cout<<"Alice"<<endl;
        else    cout<<"Bob"<<endl;
        return 0;
    }

# I - I题是个签到题（签到） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3006/I][https_ac.nowcoder.com_acm_contest_3006_I]

*  **思路：** 这简直就是个乌龙题。。。本来是一道签到题，毒瘤出题人题意表述不清楚，还改了数据，乱糟糟。。。一开始我以为是前三个是签到题，提交错误。好了，我以为应该是前三多，可以并列。结果出题人该数据，又变为要求前三个，导致后面一直以为是前三多，没ac出来，耻辱。。。

**Code：**

#include <iostream>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    struct node{ 
        int num;
        ll val;
    }a[15];
    bool cmp(node a,node b){ ;
        return a.val>=b.val;
    }
    int main(){ 
        int n,m;    cin>>n>>m;
        int vis1=0,vis2=0;
        for(int i=1;i<=n;i++){ 
            cin>>a[i].val;
            if(i==9){ 
                if(a[i].val>=m*0.8)
                    vis1=1;
            }
            a[i].num=i;
        }
        sort(a+1,a+1+n,cmp);
        for(int i=1;i<=3;i++){ 
            if(a[i].num==9)
                vis2=1;
        }
        if(vis1 || vis2)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
        return 0;
    }

# J - 牛牛战队的秀场（计算几何） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3006/J][https_ac.nowcoder.com_acm_contest_3006_J]

*  **思路：** 画个图就出来了，初中知识吧。要注意的就是浮点数计算的时候转型记得乘以1.0，要不然会丢失精度。

**Code：**

#include <iostream>
    #include <cmath>
    #define pi acos(-1)
    using namespace std;
    int main(){ 
        int n,r;    cin>>n>>r;
        int i,j;    cin>>i>>j;
        int dis=max(j,i)-min(j,i);
        double ans = (2.0*r*sin((180*1.0/n)*pi/180))*min(dis,n-dis);
        printf("%.6lf",ans);
        return 0;
    }

[https_ac.nowcoder.com_acm_contest_3006]: https://ac.nowcoder.com/acm/contest/3006
[2020_1]: https://blog.csdn.net/weixin_44668898/article/details/104284030
[2020_2]: https://blog.csdn.net/weixin_44668898/article/details/104286708
[2020_3]: https://blog.csdn.net/weixin_44668898/article/details/104291713
[2020_4]: https://blog.csdn.net/weixin_44668898/article/details/104292168
[https_ac.nowcoder.com_acm_contest_3006_A]: https://ac.nowcoder.com/acm/contest/3006/A
[https_ac.nowcoder.com_acm_contest_3006_E]: https://ac.nowcoder.com/acm/contest/3006/E
[https_ac.nowcoder.com_acm_contest_3006_I]: https://ac.nowcoder.com/acm/contest/3006/I
[https_ac.nowcoder.com_acm_contest_3006_J]: https://ac.nowcoder.com/acm/contest/3006/J