美团的两道笔试题
美团中秋笔试题
4.题目描述
某天，小美在玩一款游戏，游戏开始时，有n台机器，每个机器有一个能量水平，分别为a1,a2,...,an。小美每次操作可以选择其中的一台机器，假设选择的是第i台，那小美可以将其变为(a_i+10^k)%m（0≤k≤9），
将所有机器能量变为0至少需要多少次操作？
输入描述：
第一行，两个正整数n,m，分别表示数字个数和取模数值；
第二行为n个正整数a1,a2,...,an
1≤n≤30000，2≤m≤30000，0≤a_i<m。
输出描述：
输出一行共n个整数，表示将第i台机器能量水平调为0需要多少次操作。
样例：
4 4
0 1 2 3
输出
0 2 1 1
5. 题目描述：
小美有一串项链，项链共由n颗宝石组成，每个宝石上都有一个数字。但是有一天项链不小心被弄断了
，变成了一长串，此时可以看成一个只包含数字的字符串，于是她准备将项链从某些地方切开后再重新分成多段（
每段都是原来字符串的连续子串，且不能再重新组合），
因为小美特别喜欢7这个数字，所以她希望切开后每段的数字和都尽可能被7整除。
例如，假设项链表示为12457，可以切分为124|5|7，第一段和第三段的和能被7整除。她想请你帮她算一算 ，切开后最多能有多少段的数字和能被7整除。
输入描述
一行，一个字符串s，s的每位都是数字。
1 ≤ |s| ≤ 100000，|s| 表示s的长度。
输出描述
输出一个整数，表示切开后最多能有多少段的数字和是7的倍数。
我们遍历j，只要(presum[i+1] - presum[j]) % 7 == 0，就可以认为str[i..j]是能被7整除的。将答案加1.
int main() {
string str;
getline(cin, str);
int n = str.size();
vector<int> presum(n + 1);
for (int i = 0; i < n; i++) {
presum[i + 1] = presum[i] + str[i] - '0';
}
int last = 0; // 最后一次切开的位置
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = last; j <= i; j++) {
if ((presum[i + 1] - presum[j]) % 7 == 0) {
// printf("%d,%d\n", i, j);
res ++;
last = i;
}
}
}
printf("%d\n", res);
} 
百度一面675人在聊