2022牛客寒假算法基础集训营4

写在前面

比赛链接

2022牛客寒假算法基础集训营4

也没有特别在意牛客的分数，就是来做做题目的，感受感觉一个人敲代码的感觉，但是实际上打比赛也问了队友一些知识点，途中很多次放弃，去看看游戏直播，去刷刷都有，但是也有几次回来继续做题。

这次比赛一共12题，怒砍八题之后一看排名300开外，蚌埠住了，最后排名422...rating+5...，没事，还是总结总结，总结总有好处的，就像高中时候做错题一样。下面按照比赛时候顺序来总结。

出题人把签到题都写上了签到二字..如"E-真假签到题"、“H-真真真真真签到题”、“K-小红的真真假假签到题踢”，但是我觉得这是坑人的...没想到真是签到题，出题人良心啊，所以开始的罚时多了点点，不是很影响大局。

这次除了J题一开始忘记判if，其他都是一发A，真爽！

E-真假签到题（签到）

给出一个代码

long long f(long long x){
    if(x==1)return 1;
    return f(x/2)+f(x/2+x%2);
}

给出$x$求$f(x)$的值。

直接复制粘贴肯定会超时，实际上签到题的话肯定很简单，直接放到程序里去运行前十个，发现就是"1,2,3,4,5...10"的规律，所以直接用python读入输出了

n=input()
print(n)

py刚入门一小会...没想到可以直接print(input()) 淦！

正解的话，记忆化搜索也可以

证明：实际上一个$x$，分成$x/2$和$x/2+x%2$其实就是一分为二，一直分下去的话也就变成了$x$个$1$

H-真真真真真签到题（签到）

说是计算几何吧，实际上就是一个初中生就能写的，理解好题意表示的是哪条线段就可以了，实际上就是对角线的一半，然后输出体积就可以了，找到关系，签到题秒掉。

inline void Case_Test()
{
    cin>>d;
    r=d*2.0/sqrt(3);
    printf("%.7lf",r*r*r);
}

K-小红的真真假假签到题题（思维）

这个题挺有意思的，我一开始想着找规律，先来看看题：

小红拿到了一个正整数 $x$ 。她想构造一个正整数 $y$，满足以下性质：
1）$y$ 是 $x$ 的倍数，且 $x$ 和 $y$ 不能相等。
2）$x$ 在二进制表示下（为一个01串）是 $y$ 的二进制表示的一个子串。且$x$ 和 $y$ 的二进制表示的1的个数不能相同。
3）$y$ 必须为不超过 $10^{19}$ 的正整数。
举个例子：
若 $x=5$ :
那么构造的 $y$ 不能是$5$，因为这样 $y$ 和 $x$ 相等，所以非法。
也不能是 $6$，因为这样 $y$ 不是 $x$ 的倍数，所以非法。
也不能是 $10$ ，因为这样 $y$ 的二进制表示是 1010、$x$ 的二进制表示是101，虽然 $y$ 是 $x$ 的倍数且 $x$ 的二进制是 $y$ 的一个子串，但它们的 1的个数相同，所以非法。

实际上就是给出x，求y，这个y满足是x的倍数，不能是本身，并且拥有x的子串。

一开始想的子串判的话很麻烦，实际上方法可以这么做：给出一个$x$，将其变为二进制，拥有$l$位，将其左移$l$位并且加上$x$，最后加上$x$的作用就是还是$x$的倍数($2^l+1$倍)，并且1个数也不相同，因为后面又补充了1，这样做是对的。

注意：子串一定连续，子序列可以不连续

我的代码：

inline void Case_Test()
{
    cin>>n;
    x=n;
    int p=1;
    while (x)
    {
        x/=2;p*=2;//这里的p就是上述的2^l，每次乘以2，一共l次
    }
    cout<<(p+1)*n;
}

还有更简便的方法，我们已知数据范围，直接左移30位，不论长度了。

参考代码（解法2）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    ll x;
    cin>>x;
    cout<<(x<<30)+x;
}

C-蓝彗星（差分）

题意：给出若干段'B'和'R'时间，求出现'B'但不出现'R'的时间是多少，数据范围小于$100000$

一开始还想着是哪个数据结构呢，线段树该怎么做，仔细一读题发现直接差分...

我的方法：用两个数组$b,r$对其分别区间加，最后for循环如果b[i]&&!r[i]那么就ans++

其他方法：也可以只用一个数组$a$，统计B的时候我们区间+1，统计R的时候我们区间-INF，最后统计a[i]>0即可，原理是如果-INF的话，根据数据范围来看必不可能变为正，正好满足题意

F-小红的记谱法（模拟）

尖括号’<‘代表后面所有的音比前面的音低 8 度。反尖括号'>'则代表后面所有的音比前面的音高 8 度。

这个题感觉挺好的，读好题之后直接模拟，遇到什么就做什么事，比如遇到了<那就直接增加.，但是也不能无脑增加.，如果这时候有若干个*的话，实际上这时候'<'的作用是减少*，另一种也是，题目挺好的hh。

inline void Case_Test()
{
    cin>>s;
    int l=s.length();
    string st="";
    mp['A']=6;mp['B']=7;mp['C']=1;mp['D']=2;mp['E']=3;mp['F']=4;mp['G']=5;
    for (int i=0;i<l;i++)
    {
        if (s[i]=='<')
        {
            if (st=="") st='.';
            else if (st[0]=='.') st=st+".";
            else st.erase(0,1);
        }
        else if (s[i]=='>')
        {
            if (st=="") st='*';
            else if (st[0]=='*') st=st+"*";
            else st.erase(0,1);
        }
        else
            cout<<mp[s[i]]<<st;//我是直接输出st，也可以看第二种方法
    }
}

第二种方法，代替st字符串：

我们可以用一个$cnt$控制输出，如果$cnt>0$，那么就输出$cnt$个*；如果$cnt<0$，那么就输出$-cnt$个.

if(cnt>0)for(int j=0;j<cnt;j++)cout<<'*';
else for(int j=cnt;j<0;j++)cout<<'.';

J-区间合数的最小公倍数（质因数分解）

求区间$l,r(1\leq l\leq r\leq 30000)$中所有合数的最小公倍数，答案对$1000000007$取模

题意很简单，这个数据其实不用线筛，直接$O(sqrt(n))$就可以，没关系，直接线筛

直接来看下面这个代码：

for (int i=l;i<=r;i++)
{
    if (isprime[i]) continue;
    ans=ans*i*qpow(gcd(ans,i),mod-2,mod);//除以gcd等于乘以gcd的逆元
}

这个小数据是对的，但是大数是错的，为什么？

注意！！！gcd里面的是除法！但是我们这里是取模，所以不能用gcd的方法！

所以我们用以前学到的短除法来做，找出它们的因子，然后维护每个因子的个数（这个要求是最大，才能整除所有的数），维护$2,3,5,7$因子的个数，最后答案就是$2^{a_2}\times 3^{a_3}\times 5^{a_5}\times...$

质因数分解维护数组$a$代码

inline void divide(int x)
{
    memset(b,0,sizeof b);
    int i=1;
    while (prime[i]*prime[i]<=x&&i<=num_prime)
    {
        int t=0;
        while (x%prime[i]==0)
        {
            x/=prime[i];
            t++;
        }
        if (t>a[prime[i]]) a[prime[i]]=t;//维护最大个数
        i++;
    }
    if (x>1) a[x]=Max(a[x],1ll);
}

基于上述的质因数分解，按照题意模拟就行了，没有用到除法

inline void Case_Test()
{
    cin>>l>>r;
    for (int i=l;i<=r;i++)
    {
        if (!isprime[i])
        {
            if (!flag) flag=1;//判断有没有
            divide(i);
        }
    }
    if (flag==false){cout<<-1;return;}
    ans=1;
    for (int i=1;i<=N;i++)
        if (a[i])
            ans=ans*qpow(i,a[i],mod)%mod;
    cout<<ans;
}

注意用到取模的时候，不能用gcd，因为gcd用到了除法

附上曹佬的python代码，python不用管什么数据范围了

import math
def getPrime(prime:dict):
    for i in range(2,maxn):
        if i in prime:
            continue
        #print(i)
        j=i*i
        while j<maxn:
            prime[j]=0
            j+=i

maxn:int =30005
isprime:dict={}
getPrime(isprime)
str=input().split()
l=int(str[0])
r=int(str[1])
ans=-1
bl=False
for i in range(l,r+1):
    if i not in isprime:
        continue
    if not bl:
        bl=True
        ans=i
    ans=ans*i//math.gcd(ans,i)
if (bl == True):
    print(ans%1000000007)
else:
    print(-1)

I-爆炸的符卡洋洋洒洒（DP）

01背包的变形：给出$n(1\leq n\leq 1000)$个物品和$k(1\leq k\leq 1000)$，每个物品有费用和价值$a_i,b_i(1\leq a_i,b_i\leq10^9)$，可以选若干个物品，但要求是花费要是k的倍数，求这些物品的最大的价值

一开始是懵逼的，但是可以注意到一个很重要的！别看$a_i$这么大，但是实际上有作用的就是$a_i\ mod\ k$，所有的贡献都对于$k$取模，所以最后就成为了一个二维$1000\times 1000$的循环，一维是$1...n$物品，另一维是$0...k$的花费。

我们需要打一个这样的朴素的表，但是我们要对$k$取模的话，只需要$0..k$，所以得到

按照上图，如果$k=4$，那么我们花费$4$其实就是花费$0，$花费$5$其实就是花费$1$...

inline void Case_Test()
{
    cin>>n>>k;
    for (int i=1;i<=n;i++) cin>>a[i]>>b[i],a[i]=a[i]%k;
    for (int i=1;i<=n;i++)
    {
        mem(c,0);
        for (int j=0;j<k;j++)
            if (dp[j]) c[(j+a[i])%k]=Max(c[(j+a[i])%k],dp[j]+b[i]);
        dp[a[i]]=Max(dp[a[i]],b[i]);
        for (int j=0;j<k;j++)
            dp[j]=Max(dp[j],c[j]);
    }
    if (dp[0]) cout<<dp[0];
    else cout<<-1;
}

$c$数组的就是为了不影响当前物品多次加，$dp$数组永远是这个物品之前的，最后在加进来，也可以用一个二维数组，这样的话一样的。

D-雪色光晕（计算几何——点到线段距离）

小红正在雪地中奔跑。雪地可以看成是一个二维平面，小红的初始坐标是$ (x_0,y_0)$，她每秒有个方向向量$ ( x_i,y_i)$，会沿着该方向直线奔跑$1$秒（例如，第一秒之后，小红的坐标就变成了$(x_0+x_1,y_0+y_1)$。小果站在坐标 $(x,y)$处原地不动。小红想知道，在跑步过程中，自己和小果的最短距离是多少？

重点是求点到线段距离

直接上板子

/*********************************/
// 如果经过点做直线的垂足，垂足落在线段上，则取垂线段的距离
// 否则取到线段两端点距离的最小值
//
// 参数：
// point:  存储点的xy坐标
// p1, p2: 线段的两点
// return: 点到线段的最小距离
/*********************************/
double CalculatePointToLineDistance(double point[2], const double p1[2], const double p2[2])
{
    double dis = 0.f;
    //cout<<point[0]<<" "<<point[1]<<" "<<p1[0]<<" "<<p1[1]<<" "<<p2[0]<<" "<<p2[1]<<endl;
    double dx = p2[0] - p1[0];
    double dy = p2[1] - p1[1];

    // 两直线垂直，向量表示法，转换后公示
    double k = -((p1[0] - point[0])*dx + (p1[1] - point[1])*dy) / ( dx*dx + dy*dy);
    double footX = k*dx + p1[0];
    double footY = k*dy + p1[1];

    //if垂足是否落在线段上
    if( footY >= min(p1[1], p2[1]) && footY <=max(p1[1], p2[1])
        && footX >= min(p1[0], p2[0]) && footX <=max(p1[0], p2[0] ) )
    {
        dis = sqrtf((footX-point[0])*(footX-point[0]) + (footY-point[1])*(footY-point[1]));
    }
    else 
    {
        double dis1 = sqrtf((p1[0]-point[0])*(p1[0]-point[0]) + (p1[1]-point[1])*(p1[1]-point[1]));
        double dis2 = sqrtf((p2[0]-point[0])*(p2[0]-point[0]) + (p2[1]-point[1])*(p2[1]-point[1]));

        dis = ( dis1 < dis2 ? dis1 : dis2 );
    }

    return dis;
}

点到线段的距离题解（C++）_Commander_WingT的博客-CSDN博客_c++点到线段的距离