周六上午是头条春招研发岗笔试，共2小时，5到题目，OI赛制（有部分分）。难度较大。
题目1
C语言有两种注释，单行注释//和多行注释/* */。请编写程序，统计注释数量。注意引号中的不要统计，以及引号中间可能出现的转义字符影响。
输入描述：
C语言源程序
输出描述：
两种注释加起来的总数量
样例1
输入：
// line comment
// line comment2
int main() {
return 0;
}
输出：
2
样例2
输入：
// line comment //
/* block comment */ /* block comment 2 */
int main() {
char[] s = "/* string */";
return 0;
}
输出：
3
说明：
输入有一个单行注释和两个多行注释，
共3条注释；注意引号中的不是注释
数据范围：
对于 $50\%$ 的数据，$0 \lt 输入行数 \lt 20$
对于 $100\%$ 的数据，$0 \lt 输入行数 \lt 1000$
算法
(模拟，字符串处理) $O(n)$
遍历整个字符串，遍历时记录三个状态 c1, c2, qs，分别记录当前字符是否在单行注释中、是否在多行注释中、是否在字符串内部。
- 如果在单行注释中，则
- 如果遇到换行符，则退出单行注释状态
- 如遇其他字符，则直接跳过
- 如果在多行注释中，则
- 如果遇到
*/，则退出多行注释状态 - 如遇其他字符，则直接跳过
- 如果遇到
- 如果在字符串内部，则
- 如果如果遇到
'"'，则需判断该引号是否被转义（判断它前面共有多少个相邻的'\'，如果有奇数个，说明这个引号是转义字符，否则不是）。如果引号未被转义，则退出引号状态 - 如遇其他字符，则直接跳过
- 如果如果遇到
- 如果遇到
"、\\、\*，则分别进入引号状态、单行注释状态、多行注释状态，如果进入注释状态，则将答案加1. - 如果遇到单引号，则为了避免出现
'"'的情况，需要直接跳过单引号的内容 - 其他情况直接跳过
时间复杂度分析：整个字符串仅被遍历1遍，所以时间复杂度是 $O(n)$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int main()
{
cout << '\q' << endl;
int res = 0;
char c;
string code;
while ((c = getchar()), c != -1) code += c;
int c1 = 0, c2 = 0, qs = 0;
for (int i = 0; i < code.size(); i++)
{
if (code[i] == '\n')
{
c1 = 0;
}
else if (c1)
{
}
else if (c2)
{
if (i + 1 < code.size() && code[i] == '*'
&& code[i + 1] == '/')
{
c2 = 0;
i++;
}
}
else if (qs)
{
if (code[i] == '"')
{
int t = 0;
for (int j = i - 1; j >= 0; j--)
if (code[j] == '\\')
{
t++;
}
else
{
break;
}
if (t % 2 == 0) qs = 0;
}
}
else if (code[i] == '"')
{
qs = 1;
}
else if (i + 1 < code.size() && code[i] == '/'
&& code[i + 1] == '/')
{
c1 = 1;
res++;
i++;
}
else if (i + 1 < code.size() && code[i] == '/'
&& code[i + 1] == '*')
{
c2 = 1;
res++;
i++;
}
else if (code[i] == '\'')
{
if (code[i + 1] == '\\') i += 3;
else i += 2;
}
}
cout << res << endl;
return 0;
}
题目2
场景描述：在规则匹配系统中存在如下场景：有若干前缀字符串库，(每个库100万左右字符串，保存的是UTF8编码的字符串，包括汉字），需要判断该库中是否存在某个字符串是给定字符串的前缀。
简化描述：给出一个有m个字符串的有序数组（字典序排序），在S中寻找给定字符串a的前缀，存在返回1，不存在返回-1。
输入描述：
第一行，空格分开的两个数字，第一个数字为m，表示组成前缀字符串元素的个数；第二个数字为n，表示需要进行前缀查找的元素个数。
接下来是m个字符串组成前缀字符串库。
接下来是n个字符串标识进行前缀查找的元素。
m和n个字符串中间有一个空行分隔。
输出描述：
n行结果，每个结果均为1或者-1，两种结果之间有一个空行分隔。
样例
输入：
6 3
a
bc
d
eba
ebc
f
yuklx
bcc
ff
7 3
a
bc
d
eba
ebc
f
你好
ebcc
你好吗
ebd
输出：
-1
1
1
1
1
-1
数据范围：
对于 $40\%$ 的数据，$0 \lt m, n \lt 20$
对于 $100%$ 的数据，$0 \lt m, n \lt 200万$
字符串为UTF8编码，包括汉字等各种字符，不仅限于ASCII码
算法
（二分）$O(nlogm * L)$
有序字符串数组有个很重要的性质：
拥有相同前缀的字符串会排在一起
对于每个要进行查找的字符串 $s$，在字符串库中二分查找出小于等于它的最大的一个字符串 $t$，则如果字符串库中包含 $s$ 的前缀，那么 $t$ 一定就是 $s$ 的最长前缀。
时间复杂度分析：对每个要查找的字符串，二分查找的时间复杂度是 $O(logm * L)$，其中 $L$ 是字符串的最大长度。所以总时间复杂度是 $O(nlogm * L)$。
C++ 代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int main()
{
int m, n;
vector<string> S;
while (cin >> m >> n)
{
S.clear();
string str;
for (int i = 0; i < m; i++)
{
cin >> str;
S.push_back(str);
}
for (int i = 0; i < n; i++)
{
cin >> str;
int l = 0, r = m - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (str >= S[mid]) l = mid;
else r = mid - 1;
}
if (str.find(S[r]) == 0)
cout << 1 << endl;
else cout << -1 << endl;
}
}
return 0;
}
题目3
某公司招聘，有n个人入围，HR在黑板上依次写下m个正整数 $A_1, A_2, … A_m$，然后这n个人围成一个圈，并按照顺时针顺序为他们编号 $0, 1, 2, … n-1$。录取规则是：
第一轮从0号的人开始，取用黑板上的第1个数字，也就是 $A_1$，黑板上的数字按次序循环使用，即如果某轮用了第 $k$ 个，则下一轮需要用第 $k+1$ 个($k \lt m$)，每一轮按照黑板上的次序取用到一个数字 $A_x$，淘汰掉从当前轮到的人开始按照顺时针顺序数到的第 $A_x$ 个人，下一轮开始时轮到的人即为被淘汰掉的人的顺时针顺序下一个人，被淘汰的人直接回家，所以不会被后续轮次计数时数到，经过n-1轮后，剩下的最后1人被录取，所以最后被录取的人的编号与 $(n, m, A_1, A_2, … A_m)$ 相关。
输入描述：
第一行是一个正整数N，表示有N组参数。
从第二行开始，每行有若干个正整数，依次存放 $n, m, A_1, A_2, … A_m$，共有N行，也就是上面的N组参数。
输出描述：
输出有N行，每行对应相应的那组参数确定的录取之人的编号。
样例
输入：
1
4 2 3 1
输出：
1
说明：
样本里只有1组测试数据，说的是有4人入围（编号0-3）。
黑板上依次写下2个数字：3、1，那么：
第一轮：当前轮到0号，数到数字3，顺时针数第3个人是2号，
所以淘汰2号，下一轮从3号开始，目前剩余：0、1、3；
第二轮：当前数到3号，取到数字1，顺时针数第1个人是3号，
所以淘汰3号，下一轮从0号开始，目前剩余：0、1；
第三轮：当前轮到0号，循环取到数字3，顺时针数第3个人是0号，
所以淘汰0号，最后只剩下1号，所以录取1号，输出1；
数据范围：
$N: 0 \lt N \lt 10$
$m: 0 \lt m \lt 10^3$
$A_x: 0 \lt A_x \lt 10^3$
$n:$
$0 \lt n \lt 10^3 (50\%)$
$0 \lt n \lt 10^5 (30\%)$
$0 \lt n \lt 10^7 (20\%)$
算法
(约瑟夫问题) $O(n)$
经典约瑟夫问题的变种，可以用动态规划来做。
令$f[n][k]$表示共有 $n$ 个人，从编号是0的人开始数，从第 $k$ 个数 $A_k$ 开始用，最终剩下的人的编号是多少。
则第一次我们会去掉编号是 $A_k - 1$ 的人，然后对剩下的人重新编号：
$A_k => 0$,
$A_k + 1 => 1$,
…
$x => (x - A_k) \% n$,
则此时问题变成了共有 $n - 1$ 个人，从编号是0的人开始数，从第 $k + 1$ 个数 $A_{k+1}$开始用。则最终剩下的人的编号是 $f[n-1][k+1]$。
最后我们再将编号转化回来，所以 $f[n][k] = (f[n-1][k+1] + A_k) \% n$。
注意：在C++中，取模运算非常耗时，所以要尽可能用 if 语句和减法替换掉。
时间复杂度分析：虽然状态表示有两维，但对于每一个 $n$，仅有一个与之对应的 $k$ 被用到，所以总共用到的状态数是 $n$。状态转移的复杂度是 $O(1)$，所以总共的时间复杂度是 $O(n)$。
C++代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const int N = 1010;
int n, m;
int a[N];
int main()
{
int T;
cin >> T;
while (T--)
{
cin >> n >> m;
for (int i = 0; i < m; i++) cin >> a[i];
int start = (n - 2) % m, f = 0;
for (int i = 0; i < n - 1; i ++ )
{
f += a[start];
if (f >= i + 2) f %= (i + 2);
start--;
if (start < 0) start = m - 1;
}
cout << f << endl;
}
return 0;
}
题目4
ElasticSearch(下称ES)有一个经典问题，计算一个query与文档的匹配度，简化描述如下：
ES会对用户query进行切词操作，query会被切割成多个关键字a、b、c；然后ES会在倒排索引中寻找a、b、c，并回溯关键字在文档中的位置，从而计算匹配度；
现模拟ES计算query匹配度的方法，给出如下问题的解：
输入：“mbh”切词后分别为”m”、”b”、”h”（模拟切词后的3个关键字），”amhbgyhdc” （模拟ES的一个文档）。
关键字m出现在第2个位置；
关键字b出现在第4个位置；
关键字h出现在第3、7个位置，但第3个位置与query关键字逆序，为简化流程，可以排除掉；
如果没有匹配到所有关键词，打分为0分；
如果匹配到所有关键词，打分为100分，但要区分出相似度，
m-b隔了一个词，100-1 = 99；
b-h隔了2个词，99-2 = 97；
最后这个例子的得分为97分；
请实现一个简单的模拟算法，计算匹配度问题（有多个匹配时需要找出得分最高的匹配）。
输入描述：
输入为2行，
第一行是多个关键字，用a-z的小写字母代表；
第二行是一篇文档，同样用a-z的小写字母代表；
输出描述：
输出是匹配度的值；
没有匹配到所有关键字，为0分；
匹配到所有关键字，并计算匹配度，<= 100分；（有可能为负分）
样例
输入：
mbh
amhbgyhdc
输入出：
97
数据范围
第一行：小写英文字母组成，$1 \le 长度 \le 10$;
第二行：小写英文字母组成，$1 \le 长度 \le 1024$;
算法
(动态规划) $O(nm)$
匹配度仅和第一个关键字的位置 $pos_0$ 和最后一个关键字的位置 $pos_{m-1}$ 有关，
$匹配度 = 100 - (pos_{m-1} - pos_0 - m + 1)$，所以我们为了使匹配度尽可能高，我们需要让 $pos_{m-1} - pos_0$ 尽可能小。
状态表示：$f[i][j]$ 表示枚举到文档的第 $i$ 个字符，匹配到第 $j$ 个关键字时，第0个关键字匹配的下标最大是多少。
状态转移：分两种情况考虑：
- 如果 $doc[i]$ 和 $key[j]$ 不匹配，则 $f[i][j] = f[i - 1][j]$；
- 如果 $doc[i]$ 和 $key[j]$ 匹配，则 $f[i][j] = f[i - 1][j - 1]$；
两种情况取较大值。
最后我们枚举 $pos_{m-1}$ 的所有位置，分别计算匹配度，取匹配度的最大值即可。
时间复杂度分析：假设 $n$ 表示文档长度，$m$ 表示关键字长度。那么状态总共有 $n*m$ 个，状态转移复杂度 $O(1)$，所以总时间复杂度是 $O(nm)$。
C++ 代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const int N = 1030, M = 15;
int n, m;
int f[N][M];
int main()
{
string key, doc;
cin >> key >> doc;
n = doc.size(), m = key.size();
memset(f, -1, sizeof f);
for (int i = 1; i <= n; i++)
{
if (key[0] == doc[i - 1])
{
f[i][1] = i - 1;
}
else f[i][1] = f[i - 1][1];
}
for (int i = 1; i <= n; i ++ )
for (int j = 2; j <= m; j++)
{
f[i][j] = f[i - 1][j];
if (key[j - 1] == doc[i - 1])
f[i][j] = max(f[i][j], f[i - 1][j - 1]);
}
int res = -1000000;
for (int i = 1; i <= n; i++)
if (f[i][m] != -1)
res = max(res, 100 - (i - f[i][m] - m + 1));
if (res == -1000000) res = 0;
cout << res << endl;
system("pause");
return 0;
}
题目5
小Q最近迷上了一款叫“贪吃蛇蛇”的小游戏。平面上有个数字矩阵，每个单元都是一个整数，有正有负，最开始的时候小Q操纵一条长度为0的蛇蛇从矩阵最左侧人选一个单元进入地图，蛇每次只能够到达当前位置的右上相邻、右侧相邻和右下相邻的单元格。蛇蛇到达一个单元格后，自身的长度会瞬间加上该单元格的数值，任何情况下长度为负则游戏结束。小Q是个天才，他拥有一个超能力，可以在游戏开始的时候把地图中的某一个节点的值变为其相反数（注：最多只能改变一个节点）。问在小Q游戏过程中，他的蛇蛇最长长度可以到多少？
输入描述：
第一行两个整数n，m，表示地图有n行m列；
接下来n行，每行m个整数T(i, j)表示地图中每个单元的值
输出描述：
一个整数，表示蛇最长的长度。
样例
输入
4 3
1 -4 10
3 -2 -1
2 -1 0
0 5 -2
输出
17
说明
将第一行第二列的-4改成4，然后从第二行的第一列进入地图，
路线是3 -> 4（原-4）-> 10
数据范围
对于 $40\%$ 的数据，$1 \le n, m \le 20$
对于 $100\%$ 的数据，$1 \le n, m\le 1000$, $-1000 \le T(i, j) \le 1000$
算法
（动态规划） $O(nm)$
令 $f[i][j]$ 表示走到格子 $(i, j)$ ，不使用技能得到的最大长度；$g[i][j]$ 表示走到格子 $(i, j)$，使用技能得到的最大长度。
则$f[i][j]$ 仅能从未使用技能的状态转移：$f[i][j] = max(f[i-1][j-1]$ $, f[i][j-1],$ $ f[i+1][j-1])$ $ + T[i][j]$;
$g[i][j]$ 分两种情况考虑：
- 从未使用技能的状态转移，则在当前格子 $(i, j)$ 使用技能，转移方程是：$max(f[i-1][j-1], $ $f[i][j-1], $ $f[i+1][j-1])$ $ + (-T[i][j])$;
- 从使用过技能的状态转移，转移方程是：$max(g[i-1][j-1], $ $g[i][j-1], $ $g[i+1][j-1])$ $ + T[i][j]$;
两种情况取较大值即可。
由于题目中要求：任何情况下蛇的长度为负数，则游戏结束。所以我们只能从非负状态转移。
计算完所有状态后，答案就是所有状态的最大值。
时间复杂度分析：状态总数是 $2mn$，状态转移复杂度是 $O(1)$，所以总时间复杂度是 $O(mn)$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const int N = 1010, INF = 1000000;
int n, m;
int d[N][N], f[N][N], g[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> d[i][j];
for (int i = 0; i <= n + 1; i++)
for (int j = 1; j <= m; j++)
f[i][j] = g[i][j] = -INF;
int res = 0;
for (int j = 1; j <= m; j++)
for (int i = 1; i <= n; i++)
{
for (int k = i - 1; k <= i + 1; k++)
{
if (f[k][j - 1] >= 0)
{
f[i][j] = max(f[i][j],
f[k][j - 1] + d[i][j]);
g[i][j] = max(g[i][j],
f[k][j - 1] - d[i][j]);
}
if (g[k][j - 1] >= 0)
g[i][j] = max(g[i][j],
g[k][j - 1] + d[i][j]);
}
res = max(res, f[i][j]);
res = max(res, g[i][j]);
}
cout << res << endl;
return 0;
}
yls，第四题的25行和40行处枚举的下标好像不一致，应该都从0开始或者都从1开始吧
f[i][j]下标是从1开始的，doc[]下标是从0开始的。牛啊
谢谢hh
代码是完整的吗？
是滴