美团笔试
2h
5算法题
一
题目大意
给出当前是星期几，当前时间，求前x分钟是周几和时间
思路
暴力
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const int maxn = 2e5+5;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
using namespace std;
int main()
{
int d;
int h, m;
int pre;
scanf("%d", &d);
scanf("%d:%d", &h, &m);
scanf("%d", &pre);
int sum = h*60+m;
while(pre)
{
int t = min(sum, pre);
sum -= t;
pre -= t;
if(pre == 0)break;
if(sum == 0)
sum = 24*60;
d--;
if(d == 0)
d = 7;
}
printf("%d\n", d);
printf("%02d:%02d\n", sum/60, sum%60);
return 0;
}
二
题目大意
有n个人赛跑，给出出发顺序和到达终点顺序，若x出发顺序比y晚，但是到达终点顺序比y早，则表明x超越了y，比赛将奖励有超越的人，求奖励的人数
思路
暴力
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const int maxn = 1e5+5;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
using namespace std;
int n;
map<int, int> be, ed;
int main()
{
IO;
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
be[x] = i;
}
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
ed[x] = i;
}
int ans = 0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j)continue;
if(be[i]>be[j] && ed[i]<ed[j])
{
ans++; break;
}
}
}
cout<<ans<<"\n";
return 0;
}
三
题目大意
现在有n个bug，你需要修掉这n个bug，但是你比较懒，你第一天修x个，第二天修x/k个，第三天修x/(k2)个，第n天修x/(kn-1)个，只要k大于1，则总有一天修0个，现在给出k，你需要求出最小的x，使得能够修完这n个bug，n的范围是1e9
思路
二分答案
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const int maxn = 1e5+5;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
using namespace std;
int n, k;
int check(int x)
{
int sum = 0;
sum += x;
int t = k;
while(x/t)
{
sum += x/t;
t *= k;
}
return sum>=n;
}
int main()
{
cin>>n>>k;
int l = 1, r = n+1;
while(l<r)
{
int mid = (l+r)>>1;
if(check(mid))
r = mid;
else
l = mid+1;
}
cout<<l<<"\n";
return 0;
}
四
题目大意
有一个正四面体，顶点为S，A，B，C，每两个点都有连边，可以看成是一个完全图，现在你从S出发，走K步，求出最后回到S的方法数，对1e9取模，K的范围是1e6
思路
简单DP，状态转移方程看代码
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const int maxn = 1e6+5;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
using namespace std;
ll dp[4][maxn];
int main()
{
int k;
cin>>k;
dp[0][0] = 1;
for(int i=1;i<4;i++)dp[i][0] = 0;
for(int i=1;i<=k;i++)
{
dp[0][i] = (dp[1][i-1] + dp[2][i-1] + dp[3][i-1]) % mod;
dp[1][i] = (dp[0][i-1] + dp[2][i-1] + dp[3][i-1]) % mod;
dp[2][i] = (dp[0][i-1] + dp[1][i-1] + dp[3][i-1]) % mod;
dp[3][i] = (dp[0][i-1] + dp[1][i-1] + dp[2][i-1]) % mod;
}
cout<<dp[0][k]<<"\n";
return 0;
}
五
题目大意
一开始给你K个字符串，这K个字符串从1开始编号。你需要维护一个字符串集，初始的时候这个字符串集包含这K个字符串。然后有n次操作，操作分三种
- 在字符串集中加入第x个字符串，若原本就在字符串集中，则无变化，操作输入为-x
- 在字符串集中删除第x个字符串，操作输入为+x
- 给出一个字符串t，求当前字符串集中，每个字符串在t中出现的次数，累加和输出。操作输入为？t
思路
KMP模板题
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const int maxn = 2e5+5;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
using namespace std;
string ss[maxn];
set<int> have;
int nxt[maxn];
void getnext(string t)
{
int n = t.length();
int k = -1, i=0;
nxt[0] = -1;
while(i<n)
{
if(k==-1 || t[k]==t[i])
nxt[++i] = ++k;
else
k = nxt[k];
}
}
ll kmp(string s, string t)
{
getnext(t);
int n = s.length(), m = t.length();
ll ans = 0;
int i=0, j=0;
for(; i<n; i++)
{
while(j>0 && s[i] != t[j])
j = nxt[j];
if(s[i] == t[j])j++;
if(j==m)
{
ans++;
j = nxt[j];
}
}
return ans;
}
int main()
{
IO;
int n, k;
cin>>n>>k;
for(int i=1;i<=k;i++)
{
cin>>ss[i];
have.insert(i);
}
while(n--)
{
char a;
cin>>a;
if(a == '?')
{
string t;
cin>>t;
ll ans = 0;
for(auto v:have)
ans += kmp(t, ss[v]);
cout<<ans<<"\n";
}
else if(a == '+')
{
int x;
cin>>x;
have.insert(x);
}
else
{
int x;
cin>>x;
have.erase(x);
}
}
return 0;
}