牛客练习赛13
A.幸运数字Ⅰ
这题很简单啊，能明显答案只有三种情况，-1或4或7。
想44,77,47......这些都没有4和7优（数量上和字典序上）
我们只要找出4和7的个数，判断一下是否为-1。如果4的个数>=7的个数就输出4，否则7
时间复杂度：O(n)
#include<bits/stdc++.h>
using namespace std;
int a,b;
char s[5005];
int main()
{
scanf("%s",s+1);
int n=strlen(s+1);
for(int i=1;i<=n;i++)
if(s[i]=='4')a++;
else if(s[i]=='7')b++;
if(a==0&&b==0)cout<<-1;
else if(a>=b)cout<<4;
else cout<<7;
return 0;
}B. 幸运数字Ⅱ
首先，我们发现l和r很大，直接O(n)枚举会T，怎么办？
我们发现l到r中有很多连续的数，他们的next()是一样的，我们可以把这些数一起计算。
还有就是要把幸运数字给晒出了，我们假设现在有一个幸运数字a，我们就能构造出a * 10+4和a * 10+7是幸运数字
时间复杂度：O(50)
#include<bits/stdc++.h>
using namespace std;
int l,r,cnt,a[10005];
void dfs(long long x)
{
if(x>1000000000)return;
a[++cnt]=(int)x;
dfs(x*10+4);
dfs(x*10+7);
}
int main()
{
dfs((long long)4);
dfs((long long)7);
sort(a+1,a+cnt+1);
scanf("%d%d",&l,&r);
long long ans=0;
for(int i=1;i<=cnt;i++)
if(a[i]>=l)
{
if(a[i]>=r){ans+=a[i]*(r-l+1); break;}
else ans+=a[i]*(a[i]-l+1),l=a[i]+1;
}
cout<<ans;
return 0;
}C.幸运数字Ⅲ
这题难度中等。
我一看到题目说，k<=1000000000就知道这题肯定有什么特殊的性质。
果然，当x为奇数时，a[x]=4,a[x+1]=7,a[x+2]=7的话，就会陷入循环。
同样的,当x为偶数时，a[x-1]=4,a[x]=4,a[x+1]=7的话，也会陷入循环。
陷入循环的话就好做了，直接把k%2就行了。
没进入循环的话，就线性扫过去就好了
时间复杂度：O(n)
#include<bits/stdc++.h>
using namespace std;
int n,k;
char s[1000005];
int main()
{
scanf("%d%d",&n,&k);
scanf("%s",s+1);
for(int i=1;i0;i++)
if(s[i]=='4'&&s[i+1]=='7')
{
if(i%2==1)
{
if(s[i+2]=='7')k%=2;
}
else
{
if(s[i-1]=='4')k%=2;
}
if(k)
{
k--;
if(i%2==1)s[i+1]='4';
else s[i]='7';
}
}
printf("%s",s+1);
return 0;
}D.幸运数字Ⅳ
这题是好题，有思维难度。
我们需要发现 这是大于k（
）的。
所以只有最后13个数会换顺序，前面的数都是不变的。
所以前面的数位置=值，即一个数值是幸运数字，它的位置也是幸运数字。
我们对于后13个数，直接13*13暴力判断每一位上的数应该是从哪一位换过来的，再统计一下就好了
时间复杂度：O(13*13)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,m,cnt,q,p,ans,x,tmp,a[N],jc[N];
bool vis[N];
void dfs(int x)
{
if(x>1000000000)return;
a[++cnt]=x;
dfs(x*10+4);
dfs(x*10+7);
}
bool pd(int x)
{
if(a[lower_bound(a+1,a+cnt+1,x)-a]==x)return true;
return false;
}
signed main()
{
dfs(4);
dfs(7);
a[++cnt]=4444444444;
sort(a+1,a+cnt+1);
scanf("%lld%lld",&n,&m);
jc[0]=1;
for(int i=1;i<=13;i++)jc[i]=jc[i-1]*i;
q=1;
for(int i=1;i<=13;i++)
{
q*=i;
p=i;
if(q>=m)break;
}
if(p>n)
{
puts("-1");
return 0;
}
for(int i=1;i<=cnt;i++)
{
if(a[i]>=n-p+1)break;
ans++;
}
for(int i=n-p+1;i<=n;i++)
{
x=m/jc[n-i]+(m%jc[n-i]!=0);
int gs=0;
int j;
for(j=1;j<=p;j++)
if(!vis[j])
if(++gs==x)
{
vis[j]=true;
break;
}
if(pd(i)&&pd(n-p+j))ans++;
m%=jc[n-i];
if(!m)m=jc[n-i];
}
cout<<ans;
return 0;
}E:乌龟跑步
一道简单的dp题。
表示前i个操作，改变了j次，当前在k，方向是向前（后）的。
注意，因为是可以往回走的，所以我们可以把起点设在200的位置，这样就不用开map了。
if(s[i]=='T')
{
f[i][j][k][1]|=f[i-1][j][k][0];//转头
f[i][j][k][0]|=f[i-1][j][k][1];//转头
if(j>0)
{
f[i][j][k][1]|=f[i-1][j-1][k-1][1];//转头变成向前走
f[i][j][k][0]|=f[i-1][j-1][k+1][0];//转头变成向前走
}
}
else{
f[i][j][k][1]|=f[i-1][j][k-1][1];//向前走
f[i][j][k][0]|=f[i-1][j][k+1][0];//向前走
if(j>0)
{
f[i][j][k][1]|=f[i-1][j-1][k][0];//向前走变成转头
f[i][j][k][0]|=f[i-1][j-1][k][1];//向前走变成转头
}
}时间复杂度：O(n * m * 200 * 2)
#include<bits/stdc++.h>
using namespace std;
const int N=135;
int n,m,f[N][N][305][2];
char s[N];
int main()
{
scanf("%s%d",s+1,&n);
int m=strlen(s+1);
f[0][0][200][1]=1;
for(int i=1;i<=m;i++)
for(int j=0;j<=min(i,n);j++)
for(int k=100;k<=300;k++)
{
if(s[i]=='T')
{
f[i][j][k][1]|=f[i-1][j][k][0];
f[i][j][k][0]|=f[i-1][j][k][1];
if(j>0)
{
f[i][j][k][1]|=f[i-1][j-1][k-1][1];
f[i][j][k][0]|=f[i-1][j-1][k+1][0];
}
}
else{
f[i][j][k][1]|=f[i-1][j][k-1][1];
f[i][j][k][0]|=f[i-1][j][k+1][0];
if(j>0)
{
f[i][j][k][1]|=f[i-1][j-1][k][0];
f[i][j][k][0]|=f[i-1][j-1][k][1];
}
}
}
int ans=0;
for(int j=100;j<=300;j++)
if(f[m][n][j][0]||f[m][n][j][1])ans=max(ans,abs(200-j));
cout<<ans;
return 0;
}F.m皇后
这题相对简单，看到这题就知道只要拍一下序，统计一下就好了。
比如要统计每个点上方和下方是否有点这个问题。
我们就只要按x轴排序，这时x轴相同的就会在一起了，我们就可以方便的判断每个点上方和下方是否有点这个问题了。
其他的同理。
时间复杂度：O(nlog(n))
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m,sum[N],ans[20];
struct node{
int x,y,id;
}a[N];
bool cmp1(node a,node b)
{
return a.x==b.x?a.y<b.y:a.x<b.x;
}
bool cmp2(node a,node b)
{
return a.y==b.y?a.x<b.x:a.y<b.y;
}
bool cmp3(node a,node b)
{
return a.y-a.x==b.y-b.x?a.x<b.x:a.y-a.x<b.y-b.x;
}
bool cmp4(node a,node b)
{
return a.y+a.x==b.y+b.x?a.x<b.x:a.y+a.x<b.y+b.x;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
a[i].id=i;
}
sort(a+1,a+m+1,cmp1);
for(int i=2;i<=m;i++)
if(a[i].x==a[i-1].x)
{
sum[a[i].id]++;
sum[a[i-1].id]++;
}
sort(a+1,a+m+1,cmp2);
for(int i=2;i<=m;i++)
if(a[i].y==a[i-1].y)
{
sum[a[i].id]++;
sum[a[i-1].id]++;
}
sort(a+1,a+m+1,cmp3);
for(int i=2;i<=m;i++)
if(a[i].y-a[i].x==a[i-1].y-a[i-1].x)
{
sum[a[i].id]++;
sum[a[i-1].id]++;
}
sort(a+1,a+m+1,cmp4);
for(int i=2;i<=m;i++)
if(a[i].x+a[i].y==a[i-1].x+a[i-1].y)
{
sum[a[i].id]++;
sum[a[i-1].id]++;
}
for(int i=1;i<=m;i++)ans[sum[i]]++;
for(int i=0;i<=8;i++)printf("%d ",ans[i]);
return 0;
}
投递携程等公司10个岗位 >