微软苏州 2022 Summer Intern SWE-MMD面经 学历：普通本科 软件工程 大三面试官没说有保密协议，看到大家都发了我也来发一下记录一下人生前两次面试（求offer 3/19 官网投简历 3/25收到笔试预告信 3/27笔试 满分 4/8 一面邀请 4/12 一面 ​ 面试官是个小姐姐，进来先自我介绍，竞赛经历，闲聊，然后开始问CV+AI项目（大约5分钟） CV+AI项目 20分钟 ​ 问的特别细，从思路的诞生到实现全部答了一边。 算法题：LIS ​ 面试官只说了个LIS，我问了具体的输入输出，确定了输出最后一次出现的LIS以及LIS...

牛客题霸NC532神奇的数字 思路 ​ 用一个vector保存是偶数的数字，然后扫一遍替换原字符串偶数即可 代码 class Solution { public: /** * * @param number string字符串 * @return string字符串 */ vector<char> v; string change(string number) { // write code here int len=number.size(); for(int...

按照模拟思路，我们每次操作要考虑每一回合哪些n-1个人要进行游戏 。 但是我们不如逆向思维，每一回合我们都只需要一个观察者，那么我们此时最多可以玩多少回合呢？ 要使回合数最多，那么就是让这个人玩够了就去一直当裁判 所以最多回合数就是（当前要玩的回合数-第i个人想要玩的局数） 最后如果这个最多回合数大于等于当前要进行的回合数，就可以保证每一回合都有人当裁判，这个回合数也就可行。 代码 #include<iostream> #include<algorithm> using namespace std; long long n; long long gamers[10000...

算法竞赛进阶指南0x01位运算题解 a^b 背景知识： 1.快速幂 ​ 已知任意数字均可由二进制表示，即为，给定一个十进制整数b，若其在二进制表示下有k位，则其可以被表示为其中为b在二进制表示下的第i位 ​ 根据幂次运算的运算律，同底数幂相乘，底数不变，指数相加，即可得公式 ​ 2.取模运算的分配律 ​ 即为 ​ (a+b) % p = ( a % p + b % p ) % p ​ ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p 结合一下，很简单得到了快速求幂次的快速幂方法 时间复杂度为 即为...

POJ 2018 Best Cow Fences 二分答案,前缀和 题意 给定长度为n的序列，求长度为[m,n]的子序列的最大平均值 思路 简单分析发现本题答案存在单调性，可以采用二分答案的思路 序列中每个值对于平均值的贡献度为 可以到当本序列的时，本平均值avg成立 子序列的长度可以为[m,n-m]的任意数字 我们进行二分时要尽量使 可得前缀和公式 所以序列的的值为 我们在保持最短长度m的前提下，子序列的前端取贡献度最小的值，也就是令取可取的最小值 即为当$$时，当前avg值可行，缩小左区间，否则缩小右区间 注意最后输出卡精度 #include<cstdio> #include...

起床困难综合症 题意 给你N个门，每个门的操作为AND,XOR,OR中的一种，每个门有一个操作数，现在让一个[0,m]的数字x依次通过这n扇门，问最大的结果是多少 思路 位运算没有进位，所以可以每一位单独运算 所以我们让在[0,m]范围的每一位去通过这n道门，查看结果即可 因为x有[0,m]范围的限制，所以我们要尽可能的让x最小 即对于x的第i位当且仅当 x的第i位为0时通过n道门得到的结果不为1 且x的第i位为1时通过n道门得到的结果为1时 x的第i位才为1，否则都是0 最后获得x跑一边n道门就是答案啦 代码 #include<cstdio> #include<utilit...

原题： UvaOJ：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=830&page=show_problem&problem=3666 VJ：https://vjudge.net/problem/UVA-1225 整体思路为将1-N每一次都用sprintf写入到buffer里，然后对其读取，进行计数。 代码如下： #include<stdio.h> #include<string.h> int main(void)...

暂时摆脱了ACM严格的输出要求束缚，现在终于也可以瞎搞了。现在随着课堂实验写一写抽象数据类型了，话不多说上代码。 ps：因为输入输出可以自己瞎鸡儿搞，所以用了很多输出语句显得代码很冗长，但是实际上上全部都是c的基础，请读者耐心观看。 pps：写博客时MarkDown有些卡顿，不知道什么原因导致代码之间有许多空格，实际代码长度为211行。（本人代码风格为松散型） #include<stdio.h> #include<stdlib.h> #define ERROR 0 #define OK 1 typedef int Status; typedef i...

原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=5999 The Third Cup is free Panda and his friends were hiking in the forest. They came across a coffee bar inside a giant tree trunk. Panda decided to treat everyone a cup of coffee and have some rest. Mr. Buck, the bartender greeted Panda and his ani...

本题最大的坑在于： windows环境下的换行符为\r\n，linux环境的换行符为\n. 我们再来看看洛谷的部分OJ判题机数据和机制 常见“我在本地/xxOJ AC了、洛谷却不过”的原因 Linux中换行符是’\n’而Windows中是’\r\n’（多一个字符），有些数据在Windows中生成，而在洛谷评测机Linux环境下评测。这种情况在字符串输入中非常常见。 来源帮助-洛谷 所以我们要用 ch=getchar(); while(ch=='\r'&&ch=='\n') ch=getchar(); 来确保自己读取的不是换行符或者云云。 接下来是其...

Recently Ivan the Fool decided to become smarter and study the probability theory. He thinks that he understands the subject fairly well, and so he began to behave like he already got PhD in that area. To prove his skills, Ivan decided to demonstrate his friends a concept of random picture. A pictu...

01分数规划的裸题，式子可以变形为 ∑ ( a i − x ∗ b i ) \sum(a_i-x*b_i) ∑(ai​−x∗bi​) 之后对x进行二分即可 #include<cstdio> #include<climits> #include<iostream> #include<algorithm> using namespace std; const long double eps = 1e-7; typedef struct ass { long long a; long long b; }ass; bool cmp(lon...

链接：https://ac.nowcoder.com/acm/contest/93/I?&headNav=www 来源：牛客网 时间限制：C/C++ 5秒，其他语言10秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 wyh学长现在手里有n个物品，这n个物品的重量和价值都告诉你，然后现在让你从中选取k个，问你在所有可能选取的方案中，最大的单位价值为多少（单位价值为选取的k个物品的总价值和总重量的比值） 输入描述: 输入第一行一个整数T(1<=T<=10) 接下来有T组测试数据，对于每组测试数据，...

思路 这是一道思维。比赛时候推的错结论WA了十几次。。。。 赛后学习一下Dearmoon的代码，很巧妙 就是从后开始枚举t，看看t的后缀能不能由s串进行多次翻转后得到。。。 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 1003; char s[maxn], t[maxn]; int dp[maxn]; int main(void) { int k; scanf("%d", &am...