美团笔试全是大题,还是比较适合我的,一共五题。

<>第一题

<>题意

给你一个日期包星期几以及时和分,然后一个时间n,问n分钟之前是星期几和几时几分。

<>分析

暴力一点,数据也不大,先算出当前的总分钟,然后减去n,不断+1440直到为正。注意一下格式,输出的时候要补0。

<>代码
#include <cstdio> #include <iostream> using namespace std; int x, h, m, n, t;
int main() { scanf("%d",&x); scanf("%d:%d",&h,&m); scanf("%d",&n); t=h*60+m; t-=
n; while (t<0) { t+=1440; x--; if (x==0) x=7; } printf("%d\n",x); h=t/60; m=t%60
; if (h<10) printf("0%d:",h); else printf("%d:",h); if (m<10) printf("0%d\n",m);
else printf("%d\n",m); return 0; }
<>第二题

<>题意

有1e5个人跑步,给一个数组a,a[i]表示第i个出发的人是谁,数组b,b[i]表示第i个到达的人是谁。求超过别人的人有多少?

<>分析

这个题的数据我严重怀疑是假的,一开始想了一会,没啥太多想法,然后准备暴力做一下,O(n^2)复杂度,没想到直接过了,很奇怪。

用一个map记录编号为i的人出发的次序,用另一个map记录编号为i的人到达的次序。两重循环,判断第i个人有没有超过别人,遍历j个人,如果第i个人开始比j晚,结束比j早那么就超过了别人,答案+1。
#include <cstdio> #include <iostream> #include <map> using namespace std; int n
, ans=0; int a[100005]; int b[100005]; map<int, int> st; map<int, int> en; int
main() { scanf("%d",&n); for (int i=1; i<=n; ++i) { scanf("%d",&a[i]); st[a[i]]
= i; } for (int i=1; i<=n; ++i) { scanf("%d",&b[i]); en[b[i]] = i; } for (int i=
1; i<=n; ++i) { for (int j=1; j<=n; ++j) { if (i==j) continue; if (st[i] > st[j]
&& en[i] < en[j]) { ans++; break; } } } printf("%d\n",ans); return 0; }
<>第3题

<>题意

好像是给定n和k,求一个最小的x使得x/k+x/k2+...+x/km>=nx/k + x/k^{2} + ... + x/k^{m} >= nx/k+x/k
2+...+x/km>=n。

<>分析

二分这个x,判断的复杂度是lgn,二分也是lgn。很快就算出来了。

<>代码
#include <cstdio> #include <iostream> typedef long long ll; using namespace std
; ll n, k; bool judge(ll x) { ll t=1, s=0; while(x/t) { s+=x/t; t*=k; } return s
>=n; } int main() { scanf("%lld%lld",&n, &k); ll l=1, r=n, m; while(l<r) { m=(l+
r)/2; if (judge(m)) r=m-1; else l=m+1; } while(!judge(l)) l++; printf("%lld\n",l
); return 0; }
<>第四题

<>题意

有一个正四面体,顶为S,底为ABC。总共有六条路SA,SB,SC,AB,AC,BC。从S出发,问经过k步后,能返回S的路有多少条。

<>分析

一个比较简单的dp,dp[i][j]中i表示走i步,j表示经过i步后到达的顶点,0123分别表示SABC。然后状态转移也很简单,具体看代码。

<>代码
#include <cstdio> #include <iostream> #include <cstring> const int MOD = 1e9+7;
using namespace std; int k; int dp[1000005][10]; int main() { memset(dp,0,sizeof
(dp)); scanf("%d",&k); dp[0][0]=1; dp[1][1]=1; dp[1][2]=1; dp[1][3]=1; for (int
i=1; i<=k; ++i) { dp[i][0] = ((dp[i-1][1]%MOD+dp[i-1][2]%MOD)%MOD+dp[i-1][3]%MOD
)%MOD; dp[i][1] = ((dp[i-1][0]%MOD+dp[i-1][2]%MOD)%MOD+dp[i-1][3]%MOD)%MOD; dp[i
][2] = ((dp[i-1][0]%MOD+dp[i-1][1]%MOD)%MOD+dp[i-1][3]%MOD)%MOD; dp[i][3] = ((dp
[i-1][0]%MOD+dp[i-1][1]%MOD)%MOD+dp[i-1][2]%MOD)%MOD; } printf("%d\n",dp[k][0]%
MOD); return 0; }
<>第五题

<>题意

给一个k个大小字符串集合,一开始全在集合中,然后动态操作,一个操作是增加第x个字符串(k个里面的),第二个是删除,第三个是询问字符串S。询问的结果是以S为母串,在集合里的串为子串的匹配和。

<>分析

emm看起来像AC自动机,奈何我不会,写了个暴力,居然WA了,然后改了改还是WA。。。难道是我题目读错了,后面不太想写了,就结束了。

技术
©2019-2020 Toolsou All rights reserved,
份额已超宁德时代!LG化学确认将分拆电池业务部门Qt学习7——模态和非模态对话框数字滚动抽奖小程序vue 监听 Treeselect 选择项的改变 dedecms网站被黑 劫持到其他网站如何解决内存溢出和内存泄漏的区别、产生原因以及解决方案SQL Server 数据库词汇表1190 反转每对括号间的子串 leetcode蝗灾虫群上亿只很少发生碰撞 蝗虫要成自动驾驶功臣最优化方法总结:公式解、数值优化、求解思想