美团的两道笔试题

美团中秋笔试题
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的倍数。

思路:贪心。先求数组前缀和,然后我们枚举切开之后的下标i,并且用last保存最后一次切开的位置。
我们遍历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);
}


全部评论
万分感谢!!
点赞 回复 分享
发布于 2022-10-02 21:28 陕西

相关推荐

07-25 11:26
清华大学 Java
打开电脑,思绪又回到了7月份刚开始的时候,感觉这个月过的如梦如幻,发生了太多事,也算是丰富了我本就是平淡的人生吧太早独立的我习惯了一切都是自己做决定,拥有绝对的决定权,而且永远不会听取别人的建议。我就是那个恋爱四年出轨的男主啦,感觉既然在牛客开了这个头,那我就要做个有始有终的人。从我出轨到结束再到和女朋友和好如初真的太像一场梦了,短短的一个月我经历了太多,也成长了很多,放下了那些本就不属于我的,找回了那些我不该放弃的。我的人生丰富且多彩,但人不能一直顺,上天总会让你的生活中出点乱子,有好有坏,让你学会一些东西,让你有成长。我和女朋友的恋爱四年太过于平淡,日常除了会制造一些小浪漫之外,我们的生活...
段哥亡命职场:不得不说,我是理解你的,你能发出来足见你是个坦诚的人,至少敢于直面自己的内心和过往的过错。 这个世界没有想象中那样非黑即白,无论是农村还是城市,在看不见的阴影里,多的是这样的事。 更多的人选择站在制高点去谩骂,一方面是社会的道德是需要制高点的,另一方面,很多人不经他人苦,却劝他人善。 大部分的我们,连自己生命的意义尚且不能明晰,道德、法律、困境,众多因果交织,人会迷失在其中,只有真的走出来之后才能看明白,可是没走出来的时候呢?谁又能保证自己能走的好,走的对呢? 可是这种问题有些人是遇不到的,不去追寻,不去探寻,也就没了这些烦恼,我总说人生的意义在过程里,没了目标也就没了过程。 限于篇幅,没法完全言明,总之,这世界是个巨大的草台班子,没什么过不去了,勇敢面对,革故鼎新才是正确,祝你早日走出来。查看图片
点赞 评论 收藏
分享
07-02 22:46
门头沟学院 Java
码农索隆:hr:“管你投没投,先挂了再说”
点赞 评论 收藏
分享
下北澤大天使:你是我见过最美的牛客女孩😍
点赞 评论 收藏
分享
评论
点赞
3
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务