本文主要是介绍2021牛客暑期多校训练营1，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

地址：https://ac.nowcoder.com/acm/contest/11166?&headNav=www

A Alice and Bob

地址：https://ac.nowcoder.com/acm/contest/11166/A
题意：
轮流取石头问题
题解：
直接暴力模拟
注意：
代码：

#include<bits/stdc++.h>
using namespace std;
bool f[5005][5005];
void init()
{
    for(int i=0;i<=5000;i++){
        for(int j=0;j<=5000;j++){
            if(!f[i][j]){
                for(int k=1;k+i<=5000;k++){
                    for(int s=0;s*k+j<=5000;s++){
                        f[i+k][j+s*k]=1;
                    }
                }
                for(int k=1;k+j<=5000;k++){
                    for(int s=0;s*k+i<=5000;s++){
                        f[i+s*k][j+k]=1;
                    }
                }
            }
        }
    }
}
int main()
{
    init();
    int n,a,b;
    cin>>n;
    while(n--){
        cin>>a>>b;
        if(f[a][b])printf("Alice\n");
        else printf("Bob\n");
    }
    return 0;
}

B Ball Dropping

地址：https://ac.nowcoder.com/acm/contest/11166/B
题意：
给定几个参数，求这个球能否被梯形卡住，也就是一个数学问题，求某条边长的长度。
题解：
利用辅助线，三角函数，求即可
注意：
比赛的时候想得是直接暴力二分解方程，就WA了，事实证明三角函数yyds
代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    double h,r,a,b;
    cin>>r>>a>>b>>h;
    if(b>2*r)printf("Drop\n");
    else{
        double t=atan(h/((a-b)/2));
        double x=r/cos(t)-(b/2)*tan(t);
        printf("Stuck\n%.10lf",x);
    }
    return 0;
}

C Cut the Tree

地址：https://ac.nowcoder.com/acm/contest/11166/C
题意：
题解：
注意：
代码：

D Determine the Photo Position

地址：https://ac.nowcoder.com/acm/contest/11166/D
题意：
找出连续的零的位置来放置连续的位置
题解：
暴力模拟
注意：
代码：

#include<bits/stdc++.h>
using namespace std;
char matrix[2010][2010];
int num[2010];
int main()
{
    int n,m;string a;
    cin>>n>>m;
    memset(num,0,sizeof(num));
    for(int i=0;i<n;i++){
        int ans=0;
        for(int j=0;j<n;j++){
            cin>>matrix[i][j];
            if(matrix[i][j]!='0'){
                num[ans]++;
                ans=0;
            }
            else ans++;
        }
        num[ans]++;
    }
    cin>>a;
    int ans=0;
    for(int i=m;i<=2010;i++){
        if(!num[i])continue;
        ans+=num[i]*(i-m+1);
    }
    printf("%d",ans);
}

E Escape along Water Pipe

地址：https://ac.nowcoder.com/acm/contest/11166/E
题意：
题解：
注意：
代码：

F Find 3-friendly Integers

地址：https://ac.nowcoder.com/acm/contest/11166/F
题意：
若子串中是存在3的倍数，则该数属于友好的
题解：
暴力+模拟
因为连续的前缀和%3只有3种可能0,1,2，那么数位只要大于3就一定存在%3==0，即是友好的数，则只要对100以内的数进行暴力即可
注意：
define int long long signed main()之后，int 类型都变成long long 所以printf("%d",ans);会WA
代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool judge(int x){
    if(x%3==0||x%10%3==0||(x/10!=0&&x/10%3==0))
        return 1;
    return 0;
}
signed main(){
    int n,l,r;
    cin>>n;
    while(n--)
    {
        cin>>l>>r;
        int ans=0;
        if(l>=100)ans=r-l+1;
        else if(r>=100){
            ans+=r-100;
            for(int i=l;i<=100;i++)
                if(judge(i))ans++;
        }
        else {
            for(int i=l;i<=r;i++)
                if(judge(i))ans++;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

G Game of Swapping Numbers

地址：https://ac.nowcoder.com/acm/contest/11166/G
题意：
给定两列N个数组，有k次交换，可对a数组进行两两交换，求交换后使得两数组之间差值的最大和
题解：
注意判断交换后与交换前的变化，利用这个差值最大化来进行贪心
注意：
记得需要特判，n=2时，无法利用贪心，必须交换
代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int a[maxn],b[maxn];
int main()
{
    int n,k;
    cin>>n>>k;
    long long ans=0;
    for(int i=1;i<=n;i++)cin>>a[i];
    if(n==2){
        if(k%2)swap(a[1],a[2]);//没有最优解
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        if(a[i]>b[i])swap(a[i],b[i]);
        ans+=b[i]-a[i];
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    for(int i=1;i<=n&&i<=k;i++)
    {
        int t=2*(a[n+1-i]-b[i]);
        if(t>0)ans+=t;
        else break;//剩下的越来越小
    }
    printf("%lld",ans);
    return 0;
}

H Hash Function

地址：https://ac.nowcoder.com/acm/contest/11166/H
题意：
找出一连串数字对某一个尽可能小的数取余之后他们的余数都各不相同
题解：
卷积，将他们每两个数的差是否存在表示出来，然后挨个的进行遍历，不断的找某个数的倍数，当在整个值域中都不存在，则表示这个数就是要找的那个数了
注意：
代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 2e6 + 5;
const int MAX = 5e5 + 5;
#define PI acos(-1.0)

struct Complex {
    double x, y;

    Complex(double _x = 0.0, double _y = 0.0) {
        x = _x;
        y = _y;
    }

    Complex operator+(const Complex &b) const {
        return Complex(x + b.x, y + b.y);
    }

    Complex operator-(const Complex &b) const {
        return Complex(x - b.x, y - b.y);
    }

    Complex operator*(const Complex &b) const {
        return Complex(x * b.x - y * b.y, x * b.y + y * b.x);
    }
};

int n, num[maxn], vis[maxn], len = 1 << 20;
void FFT(Complex *a,int inv,int len)
{
    for(int i=0,j=0;i<len;i++){

        if(j>i)swap(a[i],a[j]);//翻转位置
        int k=len;
        while(j&(k>>=1))j&=~k;
        j|=k;
    }
    for(int i=2;i<=len;i<<=1)//i表示合并到哪一层
    {
        Complex wn(cos(-inv*2*PI/i),sin(-inv*2*PI/i));
        for(int j=0;j<len;j+=i){//j表示枚举合并区间
            Complex w(1,0);
            for(int k=j;k<j+i/2;k++,w=w*wn){//枚举区间的下标
                Complex l=a[k],r=w*a[k+i/2];
                a[k]=l+r;a[k+i/2]=l-r;
            }
        }
    }
    if(inv==-1){
        for(int i=0;i<len;i++)
            a[i].x/=len;
    }
    return ;
}
Complex a[maxn], b[maxn];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &num[i]);
        a[num[i]].x = 1;//标记有这个数
        b[MAX - num[i]].x = 1;//构建-i,但是数组不能为负数，用MAX-i代替来构建多项式
    }
    FFT(a, 1, len);
    FFT(b, 1, len);
    for (int i = 0; i < len; i++) {
        a[i] = a[i] * b[i];//乘起来
    }
    FFT(a, -1, len);
    for (int i = 0; i <= len; i++) {
        int x = int(a[i].x + 0.5);//四舍五入
        if (x > 0)vis[abs(MAX - i)] = 1;//可行
    }//得到的数组vis[i]表示差值i是否存在
    for (int i = n; i <= MAX; i++) {
        int flag = true;
        for (int j = i; j <= MAX; j += i)//i的倍数
        {
            if (vis[j] == true) {
                flag = false;
                break;
            }
        }
        if (flag == true) {//说明并没有找到是他们差值的约数
            printf("%d", i);
            break;
        }
    }
    return 0;
}

I Increasing Subsequence

地址：https://ac.nowcoder.com/acm/contest/11166/I
题意：
题解：
注意：
代码：

J Journey among Railway Stations

地址：https://ac.nowcoder.com/acm/contest/11166/J
题意：
题解：
注意：
代码：

K Knowledge Test about Match

地址：https://ac.nowcoder.com/acm/contest/11166/K
题意：
题解：
注意：
代码：

这篇关于2021牛客暑期多校训练营1的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！