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