1. 小美的因子查询
题目链接：校招笔试真题_算法工程师、大数据开发工程师_牛客网
小美对偶数因子很感兴趣，她将进行 T 次询问，每次都会给出一个正整数 x，请你告诉她 x 是否存在至少一个偶数因子。也就是说 x 是否存在某个因子是偶数。
思路：一个数若存在因子是偶数则因子一定能被2整除，进而这个数一定能被2整除，所以只需要对每次询问判断这个数字是否能被2整除即可。
#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;
while (t--) {
int x;
cin>>x;
if(x%2==0) cout<<"YES"<<endl;
else cout<<"NO"<<endl;;
}
return 0;
}2. 小美的密码
题目链接：校招笔试真题_算法工程师、大数据开发工程师_牛客网
小美准备登录美团，需要输入密码，小美忘记了密码，只记得密码可能是 nn 个字符串中的一个。小美会按照密码的长度从小到大依次尝试每个字符串，对于相同长度的字符串，小美随机尝试，并且相同的密码只会尝试一次。小美想知道，她最少需要尝试多少次才能登录成功，最多需要尝试多少次才能登录成功。
思路：由于是按照密码的长度由长到短来尝试，所以答案是正确密码在所有密码中有可能出现的最前位置和最后位置，只需要统计长度小于正确密码的密码个数（假设为x）和长度等于正确密码的密码个数（假设为y），则答案就是x+1和x+y。
#include <bits/stdc++.h>
#include <string>
using namespace std;
vector<string> v;
map<string, int> mp;
bool cmp(string s1, string s2) {
return s1.size() < s2.size();
}
int main() {
int n;
cin >> n;
string s;
cin >> s;
for(int i=0; i<n; i++)
{
string ss;
cin>>ss;
mp[ss] += 1;
if (mp[ss] == 1) v.push_back(ss);
}
sort(v.begin(), v.end(),cmp);
int mx = 0;
int mn = 0;
for (int i=0; i<v.size(); i++) {
// cout<<v[i]<<endl;
if (v[i].size()<s.size())
{
mn++;
mx++;
}
else if(v[i].size()==s.size()) mx++;
}
cout<<mn+1<<" " <<mx<<endl;
return 0;
}
// 64 位输出请用 printf("%lld")注：上面代码是排序后遍历，也可以在输入的时候进行计数，用时更短。
3. 小美的数组删除
题目链接：校招笔试真题_算法工程师、大数据开发工程师_牛客网
小美有一个长度为 n 的数组 a1,a2,…,an，他可以对数组进行如下操作：
1. 删除第一个元素 a1，同时数组的长度减一，花费为 x。
2. 删除整个数组，花费为 k×MEX(a)（其中 MEX(a)MEX(a) 表示 a 中未出现过的最小非负整数。例如 [0,1,2,4] 的 MEX 为 3 ）。
小美想知道将 a 数组全部清空的最小代价是多少，请你帮帮他吧。
思路：刚看到题目以为是dp，但是看了下例子发现由于删除操作是删掉所有的元素，所以遍历一边就行。在每个位置上更新MEX，计算当前花费，取最小。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[200010];
map<int,int> mp;
int main()
{
int t;
cin>>t;
while(t--){
mp.clear();
int n,k,x;
cin>>n>>k>>x;
for(int i=1; i<=n; i++)
{
cin>>a[i];
mp[a[i]] += 1;
}
int now = 0;
for(int i=0; i<=n; i++)
{
if(mp[i] == 0)
{
now = i;
break;
}
}
ll ans = 1e15 + 10;
ll sum = 0;
for(int i=1; i<=n; i++) {
ans = min(ans, sum + now * k);
if(a[i]<now && mp[a[i]] - 1 == 0)
{
now = a[i];
mp[a[i]] = 0;
}
else mp[a[i]]--;
sum += x;
}
ans = min(ans, sum);
cout <<ans<<endl;
}
}4. 小美和大富翁
题目链接：校招笔试真题_算法工程师、大数据开发工程师_牛客网
小美在玩《大富翁》游戏，游戏中有 n+1 个城市排成一排，编号从 0 到 n ，第 i 个城市上有一个数字 ai ，表示到达第 i 个城市可以获得 ai 枚金币。
每一轮开始时小美会获得四张卡牌，分别可以跳跃 1、2、3、4 个城市，例如小美可以从城市1跳跃 3 个城市到达城市4。当小美使用完这 4 张卡牌后，会开启新的一轮。
初始时，小美拥有 0 枚金币，在任意时刻，小美的金币数量都必须大于等于 0 ，小美想知道她从第 0 个城市出发，到达第 n 个城市最多可以获得多少枚金币。
思路：题目的大概意思是从位置0开始，每次只能选择前进1/2/3/4步，不能重复选择相同的步数，只有将这四个选择都选过一次后才能将选项重置，开始积分为0，每跳一步获得一个积分ai，问到达最后一个位置能积攒的最大积分。因此可以发现前进的步骤一定是以10步为一个单位，若中间任意一次不能到达则一定输出-1，这里将n分为多个10，用4的全排列处理每一个步骤的所有情况，最后若有不足10的部分，使用dfs判断能否到达最后位置。
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll vis[10];
ll a[100010];
ll ans;
ll flag;
ll n, nn;
ll x[10] = {1,2,3,4};
void dfs(ll pos, ll val) {
// cout << pos << " " << val << endl;
if (pos == nn) {
if (!flag) {
flag = 1;
ans = val;
return;
}
ans = max(ans, val);
return;
}
if (pos > n) {
return;
}
if (vis[1] == 1 && vis[2] == 1 && vis[3] == 1 && vis[4] == 1) {
for (ll i = 1; i <= 4; i++) vis[i] = 0;
}
for (ll i = 1; i <= 4; i++) {
if (vis[i] == 0 && val + a[pos+i] >= 0) {
vis[i] = 1;
dfs(pos + i, val + a[pos+i]);
vis[i] = 0;
}
}
return;
}
int main() {
cin >> n;
for (ll i = 1; i <= n; i++) cin >> a[i];
nn = n;
if(n <= 10) dfs(0, 0);
else{
ll m = n / 10;
for (ll i=0; i<m; i++) {
ll mx = -1;
ll res = ans;
do {
flag = 1;
res = ans;
ll pos = i * 10;
for (ll j=0; j<4; j++) {
if (res + a[pos+x[j]] >= 0)
{
res += a[pos+x[j]];
pos += x[j];
}
else{
flag = 0;
break;
}
}
if (!flag) continue;
mx = max(mx, res);
} while(next_permutation(x, x+4));
// cout << mx << endl;
for(ll i=0; i<4; i++) x[i] = i + 1;
if (mx == -1) {
cout<<"-1"<<endl;
return 0;
}
ans = mx;
}
if (n % 10) {
nn = n;
flag = 0;
dfs(10 * m, ans);
if (!flag) {
cout<<"-1"<<endl;
return 0;
}
}
}
if (ans == -1) cout << "-1" << endl;
else cout << ans << endl;
return 0;
}我这个代码写的很乱，大家只参考思路吧。
看到还有人用状压dp来做，转移方程dp[i][1101] = max(dp[i - 1][1100] + a[i - 1], dp[i - 3][1001] + a[i - 3], dp[i - 4][0101] + a[i - 4]) ，贴下他的代码牛客网公司真题_免费模拟题库_企业面试|笔试真题
#include <bits/stdc++.h>
using namespace std;
int t, n, k, x, a[100200];
long long dp[100200][20];
int main() {
ios::sync_with_stdio(false);
cout.tie(0), cin.tie(0);
cin >> n;
for (int i = 1;i <= n; i ++) { // 注意 while 处理多个 case
cin >> a[i];
}
memset(dp, -1, sizeof(dp));
dp[0][0] = 0;
for (int i = 1;i <= n;i ++) {
for (int x = 0;x < 16;x ++)
{
for (int j = 0;j < 4;j ++) {
if (x >> j & 1 and i - j - 1 >= 0 and 0 <= dp[i - j - 1][x ^ (1 << j)] )
{
dp[i][x] = max(dp[i][x], dp[i - j - 1][x ^ (1 << j)] + a[i - j - 1]);
}
}
}
if (i % 10 == 0) {
//cout << " ?" << endl;
dp[i][0] = max(dp[i][0], dp[i][15]);
}
}
//cout << dp[10][0] << " " << dp[10][15] << endl;
long long ans = -1;
for (int x = 0;x < 16;x ++)
{
//cout << dp[1][x] << endl;
ans = max(ans, dp[n][x]);
}
if (~ ans) ans += a[n];
cout << (ans >= 0 ? ans : -1) << endl;
}
作者：little_ge
链接：https://www.nowcoder.com/exam/test/83674045/submission?examPageSource=Company&pid=58084121&testCallback=https%3A%2F%2Fwww.nowcoder.com%2Fexam%2Fcompany&testclass=%E8%BD%AF%E4%BB%B6%E5%BC%80%E5%8F%91
来源：牛客网5. 小美的彩带
题目链接：校招笔试真题_算法工程师、大数据开发工程师_牛客网
小美的彩带是由一条长度为 n 的彩带一直无限循环得到的，彩带的每一个位置都有一个颜色，用 ai 表示。因此当 i>n 时，ai=ai−n。
小美每次会从左往后或从右往左剪一段长度为 x 的彩带，她想知道她每次剪下来的彩带有多少种颜色。
思路：由于彩带的长度无限，在输入的时候可以将彩带长度设定为2n，使得从左从右剪彩带互不干扰，记录每次询问的序号和左右端点，离线地处理每次询问，于是可以想到莫队。看有人说普通莫队能过，分了一个sqrt(n*n/m)的块超时，于是考虑使用树状数组加速。
#include<bits/stdc++.h>
#include <unistd.h>
using namespace std;
struct Node{
int id;
int l, r;
}q[200010];
int a[400010];
int ans[200010], t[400010];
int n, m;
map<int,int> mp; // 记录左边最后一个出现的位置
void add(int x, int y) {
for(int i=x; i<=2*n; i+=(i&(-i))){
t[i] += y;
}
}
int get(int x) {
int sum = 0;
for(int i=x; i>=1; i-=(i&(-i))) {
sum += t[i];
}
return sum;
}
int find(int x,int y) {
return get(y) - get(x-1);
}
bool cmp(Node x, Node y) {
if (x.r == y.r) {
return x.l < y.l;
}
else return x.r<y.r;
}
int main()
{
scanf("%d %d", &n,&m);
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
a[i+n] = a[i];
}
scanf("\n");
int l = 1, r = 2*n;
for (int i=0; i<m; i++) {
char c;
int x;
scanf("%c %d\n", &c,&x);
q[i].id = i;
if(c == 'L'){
if(x >= n)
{
q[i].l = 1;
q[i].r = n;
}
else {
q[i].l = l;
q[i].r = l + x - 1;
}
l = (l+x) % n;
if (l == 0) l = n;
}
else {
if(x >= n) {
q[i].l = 1;
q[i].r = n;
}
else {
q[i].r = r;
q[i].l = r - x + 1;
}
// r = (r-x) % n + n;
r=((r-x)%n+n)%n+n; // r-x可能为负值，需要调整过来
if (r == n) r = 2*n;
}
}
sort(q, q+m, cmp);
int res = 0;
r = 1;
for(int i=0; i<m; i++) {
while(r<=q[i].r) {
if (mp[a[r]]) add(mp[a[r]], -1);
add(r, 1);
mp[a[r]] = r;
r++;
}
ans[q[i].id] = find(q[i].l, q[i].r);
}
for(int i=0; i<m; i++) printf("%d\n",ans[i]);
return 0;
}