2021牛客暑期多校训练营1

A Alice and Bob

题目描述

Alice和Bob玩游戏，有两堆石头，每一次在其中一堆石头里拿K个(k>0),从另一堆石头里面拿s*k个石头（s>=0),Alice先拿，最后无法进行操作的人输掉比赛。

解题思路

这道题设d[i][j]=0为必败态，则转为必胜态只要（i+k,j+sk)或者
（i+sk，j+k),且i有且仅有唯一对应的j。

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool d[5005][5005];
void init(){
    for(int i=0;i<=5000;i++){
        for(int j=0;j<=5000;j++){
            if(!d[i][j]){
                for(int k=1;k+i<=5000;k++)
                for(int s=0;s*k+j<=5000;s++)
                d[i+k][j+s*k]=1;
                for(int k=1;k+j<=5000;k++)
                for(int s=0;s*k+i<=5000;s++)
                d[i+s*k][j+k]=1;
            }
        }
    }
}
int main(){
    init();
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        if(d[n][m]) cout<<"Alice"<<endl;
        else cout<<"Bob"<<endl;
    }
    return 0;
}

B Ball Dropping

题目描述

平面几何计算

解题思路

相似三角形，等比
图片说明

代码实现

#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;
int main(){
    double r,a,b,h;
    scanf("%lf %lf %lf %lf",&r,&a,&b,&h);
    double h1=b*h/(a-b);
    double h2=2*r*h1/b;
    if(b<2*r){
        printf("Stuck\n");
        printf("%.10lf\n",sqrt(h2*h2+r*r)-h1);
    }
    else printf("Drop\n");
    return 0;
}

C Cut the Tree

D Determine the Photo Position

题目描述

将长度为m的字符串插入n*n的图中，仅由0和1组成，插入字符串时不能覆盖1。算插法方式有多少种

解题思路

逐行扫描，连续0的长度l>=m的话，sum总和加上l-m+1，小于不计。

代码实现

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
    int n,m,sum=0;
    cin>>n>>m;
    string a;
    while(n--){
        cin>>a;
        int l=0;
        for(int i=0;i<a.length();i++){
            if(a[i]=='0') l++;
            else{
                if(l>=m) sum=sum+l-m+1;
                l=0;
            }
        }
        if(l>=m) sum=sum+l-m+1;
        //cout<<sum<<endl;
    }
    cin>>a;
    cout<<sum<<endl;
    return 0;
}

E Escape along Water Pipe

F Find 3-friendly Integers

题目描述

3-friendly:能整除3或者任意连续位数组成的整数可以整除3
给定范围，求该范围内3-friendly的个数

解题思路

一位数：3 6 9
两位数：对能整除3或者个位数能整除3的数标记
三位数可以验证：均满足3-friendly的条件
四位数包含三位数，所以也会满足，依次类推3位数以上的均满足条件

代码实现

#include<algorithm>
#include<iostream>
#include<string>
#include<math.h>
typedef long long ll;
using namespace std;
int f[100];
int main(){
    f[0]=f[1]=f[2]=0;
    f[3]=f[4]=f[5]=1;
    f[6]=f[7]=f[8]=2;
    f[9]=3;
    for(int i=10;i<100;i++){
        if((i%10)%3==0||(i/10)%3==0||i%3==0) f[i]=f[i-1]+1;
        else f[i]=f[i-1];
    }
    int t;
    cin>>t;
    while(t--){
        ll n,m;
        cin>>n>>m;
        if(m<100) cout<<f[m]-f[n-1]<<endl;
        else if(n>=100) cout<<m-n+1<<endl;
        else cout<<f[99]-f[n-1]+m-99<<endl;
    }
    return 0;
}

G Game of Swapping Numbers

题目描述

给你两长度为n的数列a,b.可将数列a里的元素随意对调位置。求 $图片说明$ 的最大值

解题思路

第一步：去掉绝对值
如果ai<bi,将ai和bi交换，不影响结果，因为差值不变且大于0.
第二步：
保证了ai>bi,那么a数列里面的元素的符号一定是‘+’，如何对调元素使得总和增加呢？
保证a1>a2,a2<b1,那么调换后总值sum=sum+2*(b1-a2)。
根据贪心的原则，将两数组排序，计算增加总值即可。

代码实现

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll a[500005],b[500005],sum=0;
int main(){
    ll n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++){
        cin>>b[i]; if(b[i]>a[i]) swap(a[i],b[i]);
        sum=sum+abs(a[i]-b[i]);
    }
    sort(a,a+n);
    sort(b,b+n);
    for(int i=1;i<=n&&i<=k;i++) if(b[n-i]>a[i-1]) sum+=2*(b[n-i]-a[i-1]);
    cout<<sum<<endl;
    return 0;
}

H Hash Function

I Increasing Subsequence

J Journey among Railway Stations

k Knowledge Test about Match

题目描述

给定长度为n的数列a和b.a数列元素是1到n-1，b数列的元素由输入数据给出，现在可以任意排列数列b,使得它们的标准差小于%4.
图片说明

解题思路

局部最优解求整体最优解，我感觉其实就是暴力，
最外层循环多于1小于11，至于为什么我试出来的，但是正确的应该是用KM算法进行本地模拟。

代码实现

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1005;
double  w[maxn];
int n,b[maxn];
int main()
{
    for (int i = 1; i < maxn; i++) w[i] = sqrt(i);
    int t;
    cin >> t;
    while (t--){
        cin >> n;
        for (int i = 0; i < n; i++)cin>>b[i];
        sort(b, b + n);
        for (int s = 0; s < 5; s++)
            for (int i = 0; i < n; i++)
                for (int j = i + 1; j < n; j++)
                    if (w[abs(b[i] - j)] + w[abs(b[j] - i)] < w[abs(b[i] - i)] + w[abs(b[j] - j)])swap(b[i], b[j]);              
        for (int i = 0; i < n; i++) cout<<b[i]<<" ";
        cout<<endl;
    }
    return 0;
}