写在前面
比赛链接
也没有特别在意牛客的分数，就是来做做题目的，感受感觉一个人敲代码的感觉，但是实际上打比赛也问了队友一些知识点，途中很多次放弃，去看看游戏直播，去刷刷都有，但是也有几次回来继续做题。
这次比赛一共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++点到线段的距离
A-R（双指针）
这个题有837个人通过，但是我没有通过，我决定好好反思这个双指针，我另开一篇来写这个双指针的题目。