题目一
题目描述
小团最近在玩手机上的四川麻将。四川麻将的一种玩法是玩家摸完牌之后选择三张花色一样的牌按某种顺序换给其他人。为了尽可能破坏对手的游戏体验，小团每次都会选择不连续的三张牌换出去。比如小团手上有14568这5张条子，则他可能会选择158这三张条子换出去。爱思考的小团马上对这个问题进行了推广。
小团把这个问题进行了简化，现在他给了你一个可重集合，并希望你从中选出一个尽可能大的子集使得其中没有两个数是“连续”的（连续是指即这两个数之差的绝对值不超过1）。
输入描述
第一行有一个整数n（1<=n<=100000），代表小团给你的可重集大小。
第二行有n个空格隔开的整数（范围在1到200000之间），代表小团给你的可重集。
输出描述
输出满足条件的最大子集的大小。
样例输入
6
1 2 3 5 6 7样例输出
4视频链接：追月无痕-美团3.5笔试题目一
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, a[N], dp[N];
int main() {
scanf("%d", &n);
for (int i = 1 ; i <= n ; i ++) scanf("%d", &a[i]);
sort(a + 1, a + n + 1);
int m = unique(a + 1, a + n + 1) - a;
dp[0] = 0, dp[1] = 1;
for (int i = 2 ; i <= m ; i ++) {
dp[i] = dp[i - 1]; // 不选这个数
if (a[i] > a[i - 1] + 1) {
dp[i] = max(dp[i], dp[i - 1] + 1); // 尝试把当前这个数加入到 i-1
}
dp[i] = max(dp[i], dp[i - 2] + 1);
}
int ans = 0;
for (int i = 1 ; i <= m ; i ++) ans = max(ans, dp[i]);
cout << ans << endl;
return 0;
}题目二
题目描述
最大子段和是一个经典问题，即对于一个数组找出其和最大的子数组。
现在允许你在求解该问题之前翻转这个数组的连续一段（如翻转{1,2,3,4,5,6}的第三个到第五个元素组成的子数组得到的是{1,2,5,4,3,6}），则翻转后该数组的最大子段和最大能达到多少？
输入描述
第一行有一个正整数n(1<=n<=100000)，代表数组长度。
第二行有n个空格隔开的整数(-1000<=ai<=1000)，代表给出数组。
输出描述
输出一个整数，代表若允许你翻转一个子数组 ，则翻转后所得数组的最大子段和最大能到多少。
样例输入
6
-1 3 -5 2 -1 3样例输出
7视频链接：追月无痕-美团3.5笔试题目二
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, a[N], sum[N], mx[N], mval[N];
int main() {
scanf("%d", &n);
for (int i = 1 ; i <= n ; i ++)
scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i];
int ans = 0;
for (int i = 1, s = 0 ; i <= n ; i ++) {
s += a[i];
if (s < 0) s = 0; // 求最大
mx[i] = max(mx[i - 1], s);
mval[i] = max(mval[i - 1], mx[i] - sum[i]);
ans = max(ans, sum[i] + mval[i - 1]);
// sum[i] + max(mx[j - 1] - sum[j - 1]);
// for (int j = 1 ; j < i ; j ++) {
// ans = max(ans, sum[i] - sum[j - 1] + mx[j - 1]);
// }
}
cout << ans << "\n";
return 0;
}题目三
题目描述
小美在学做麻婆豆腐。但她的刀工不是很好，切豆腐的时候容易切歪。为了切出更均匀的豆腐，小美想在每一次下刀之后知道切出来的豆腐块中体积最大的那块有多大。
输入描述
第一行有两个空格隔隔开的整数n,m(1<=n,m<=1000)，代表这块豆腐最开始是长宽高均为n厘米的正方体，而小美总共切了m刀。
第二行有m个以空格隔开的小写字母。每个字母都是x,y,z中的一个。第i个代表小美切的第i刀垂直于哪个坐标轴。
第三行有m个大于0且小于n的正整数，数字间有空格隔开。第 i 个代表小美切的第 i 刀所在平面到豆腐的右上角（或者你可以任选一个角并固定，不难证明无论选哪个角答案均相同）的距离。
为了切出美观的豆腐，小美提前把豆腐塞进了冷冻室，所以在切的时候豆腐不会产生形变且切出来的豆腐块不会产生位移。小美每次下刀都会把整块豆腐切开，不存在切到一半收刀这种情况，所以切出来的每块小豆腐都是边长为正整数的长方体。
输出描述
输出m行，每行一个整数，代表在小美切下第 i 刀后形成的豆腐块中体积最大的那块的体积。
样例输入
2 3
x y z
1 1 1样例输出
4
2
1视频链接：追月无痕-美团3.5笔试题目三
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m, d[N];
char op[N];
int v[3][N], tot[3], mx[3];
int main() {
cin >> n >> m;
for (int i = 1 ; i <= m ; i ++) cin >> op[i];
for (int i = 1 ; i <= m ; i ++) cin >> d[i];
for (int i = 0 ; i < 3 ; i ++) tot[i] = 1, v[i][1] = mx[i] = n;
for (int t = 1 ; t <= m ; t ++) {
int id = op[t] - 'x';
int idx = -1, L = -1, R = -1;
for (int i = 1, l = 0 ; i <= tot[id] ; i ++) {
int r = l + v[id][i];
if (r > d[i]) {
idx = i, L = d[i] - l, R = r - d[i];
break;
}
}
tot[id] ++;
for (int i = tot[id] ; i > idx ; i --) v[id][i] = v[id][i - 1];
// idx, idx + 1
v[id][idx] = L;
v[id][idx + 1] = R;
mx[id] = 0;
for (int i = 1 ; i <= tot[id] ; i ++) mx[id] = max(mx[id], v[id][i]);
cout << mx[0] * mx[1] * mx[2] << endl;
}
return 0;
}题目四
题目描述：
小团在努力地刷题。在刷题的过程中小团碰到了一道经典的数据结构题，即给出一个长度为n的数组，你需要进行m次数组上的区间操作，操作包含将区间内所有数加上一个值和查询一个区间内所有数的和。现在他想知道，如果允许重新排列初始数组中的元素并依次进行操作，则操作中所有查询区间和的答案之和能够达到多大？
输入描述
第一行有两个数n,m(1<=n<=5000,1<=m<=500)，代表数组长度和操作次数。
第二行有n个数，代表初始数组中的元素。
接下来m行每行形如1 l r或2 l r k，分别代表查询下标属于[l,r]的元素之和这一操作和将下标属于[l,r]的元素全部加上一个定值k。其中l,r,k满足1<=l<=r<=n，1<=k<=5000。
数字间两两均有空格隔开。
输出描述
输出一个整数，即若允许你重新排列初始数组，则进行m次操作后产生的所有输出之和最大能够达到多少？
视频链接：追月无痕-美团3.5笔试题目四
代码
#include <bits/stdc++.h>
using namespace std;
#define ls (rt << 1)
#define rs (rt << 1 | 1)
const int N = 5005;
int n, a[N], cnt[N], tag[N];
LL sum[N << 2], add[N << 2];
void pushup(int rt) {
sum[rt] = sum[ls] + sum[rs];
}
void pushdown(int rt, int l, int r) {
if (add[rt]) {
int mid = (l + r) >> 1;
sum[ls] += add[rt] * (mid - l + 1);
sum[rs] += add[rt] * (r - mid);
add[ls] += add[rt], add[rs] += add[rt];
add[rt] = 0;
}
}
void update(int rt, int l, int r, int ql, int qr, int x) {
if (l == ql && qr == r) {
sum[rt] += 1LL * x * (r - l + 1);
add[rt] += x;
return ;
}
pushdown(rt, l, r);
int mid = (l + r) >> 1;
if (qr <= mid) update(ls, l, mid, ql, qr, x);
else if (ql > mid) update(rs, mid + 1, r, ql, qr, x);
else update(ls, l, mid, ql, mid, x), update(rs, mid + 1, r, mid + 1, qr, x);
pushup(rt);
}
LL query(int rt, int l, int r, int ql, int qr, int x) {
if (l == ql && qr == r) return sum[rt];
pushdown(rt, l, r);
int mid = (l + r) >> 1;
if (qr <= mid) return query(ls, l, mid, ql, qr);
else if (ql > mid) return query(rs, mid + 1, r, ql, qr);
else return query(ls, l, mid, ql, mid) + query(rs, mid + 1, r, mid + 1, qr);
}
int main() {
cin >> n;
for (int i = 1 ; i <= n ; i ++) cin >> a[i];
LL ans = 0;
for (int i = 1 ; i <= m ; i ++) {
int op, l, r, k; cin >> op >> l >> r;
if (op == 1) {
tag[l] ++, tag[r + 1] --;
ans += query(1, 1, n, l, r);
} else if (op == 2) {
cin >> k;
update(1, 1, n, l, r, k);
}
}
for (int i = 1 ; i <= n ; i ++) cnt[i] = cnt[i - 1] + tag[i];
sort(cnt + 1, cnt + n + 1);
sort(a + 1, a + n + 1);
for (int i = 1 ; i <= n ; i ++) ans += 1LL * cnt[i] * a[i];
cout << ans << "\n";
return 0;
}题目五
题目描述
小团在上课时发现了他手机内置的一个小游戏，名为XaYb。游戏程序首先会随机一个不包含重复数字的长度为n的数字串s，而玩家需要通过询问来推理出s的内容。玩家可以进行任意轮询问，每轮询问时玩家需要输入一个长度为n且不包含重复数字的数字串t，然后游戏程序会给出两个数字作为答案，第一个是s和t有多少个位置上的数字相同（记为a），第二个是t中有多少个数字在s中出现了但位置是错的（记为b）。
比如s=7926时，若玩家询问串t=7246，则游戏会返回a=2,b=1，因为s和t的第一位和第四位相同，t的第二位在s中出现但不在第二位。又比如s=1532,t=4521，则游戏会返回a=1,b=2，因为s和t的第二位相同，t的第三位和第四位在s中出现但分别在s的第四位和第一位。
长期睡眠不足的小团无法进行有效的推理，于是他决定先随机进行m次猜测，收集结果并找出字典序最小（本题中等价于其对应的数值最小）的满足这m次询问所得答案的串（记为r）。
现在你的任务是写一个程序帮助小团从m个询问及答案中找到r这个串并将其输出。如果对应的串不可能存在，请输出"?"号
样例输入
4 5
1234 3 0
1204 3 0
5678 0 1
5679 0 0
5670 0 0样例输出
1284视频链接：追月无痕-美团3.5笔试题目五
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
struct node {
string s;
int a, b;
} v[N];
int n, m, use[10];
string path, ans = "?";
void check() {
vector<int> pa(10, -1);
for (int i = 0 ; i < n ; i ++) pa[path[i] - '0'] = i;
for (int i = 1 ; i <= m ; i ++) {
vector<int> pb(10, -1);
for (int j = 0 ; j < n ; j ++) pb[v[i].s[j] - '0'] = j;
int a = 0, b = 0;
for (int j = 0 ; j < 10 ; j ++) {
if (pa[j] != -1 && pb[j] != -1) {
if (pa[j] == pb[j]) a ++;
else b ++;
}
}
if (v[i].a != a || v[i].b != b) return ;
}
if (ans == "?" || path < ans) ans = path;
}
void dfs(int x) {
if (x > n) { check(); return ; }
for (int i = 0 ; i <= 9 ; i ++) {
if (use[i]) continue;
path.push_back(i + '0');
use[i] = 1;
dfs(x + 1);
use[i] = 0;
path.pop_back();
}
}
int main() {
cin >> n >> m;
for (int i = 1 ; i <= m ; i ++) cin >> v[i].s >> v[i].a >> v[i].b;
dfs(1);
cout << ans << "\n";
return 0;
}
