2018/4/15今日头条笔试题解
并没有参加，但是在讨论区看到题了，写写题解吧。
（这题比较不确定，因为我是bfs跑几组数据，然后手推一下猜出来的答案）。
#春招##笔试题目##字节跳动# A：
考虑到问题实际上就是要求最小的k使得a[i] + T = a[i + k - 1]，T = a[k] - a[1];
会发现问题也就是找(a[1] + T,a[2] + T,...a[n - k + 1] + T) == (a[k],a[k + 1],...,a[n])
我们发现在这两组数里面他们的差分序列是相等的。所以可以得出解法
构造一个差分序列c[i] = a[i + 1] - a[i].
问题就相当于求c[1....n - k] == c[k....n - 1]了，这里可以kmp来求
B：
简单的多重背包+0/1背包
dp[i][j]表示前i个物品凑成了面值为j的方案
dp[0][0] = 1;
对于可以无限用的物品来说，最朴素的做法就是
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++)
for(int z = 0; z * a[i] <= j; z++)
dp[i][j] += dp[i - 1][j - z * a[i]];
数据不水的话这东西肯定tle
但是注意到对于dp[i][j]来说实际上它加的是一个前缀和一样的东西..dp[i - 1][j] + dp[i - 1][j - a[i]] + dp[i - 1][j - a[i] * 2]....;
大概你已经发现了都是关于a[i]的这样一个式子，
如果我们在做这个i的dp之前先统计出tmp[j] = tmp[j - a[i]] + dp[i - 1][j];
于是
for(int i = 1; i <= n; i++){
for(int j = 0; j <= m; j++)tmp[j] = (j - a[i] >= 0 ? tmp[j - a[i]] : 0) + dp[i - 1][j];
for(int j = 0; j <= m; j++)dp[i][j] = tmp[j];
}
多重背包的方案做完。
01背包的很简单就不用写了。
这里没写取模。
实际上只要写出朴素dp之后就很容易发现这个优化。
C：
预处理出从起点开始走到i的往四个方向最远的max，然后直接二分答案
D：维护一个优先队列，里面是这样的信息A:分母下标，B当前的分子下标，C分母/分子
重载<号比较C的大小，然后对于i > 1，都把{ A(i),B(i - 1),C( a[i] / a[i - 1 ]) }丢进优先队列，每次取出最小值pop出来，并且加入{ A(A),B(B - 1),C(a[A]/a[B - 1]) }，重复k次就是答案了。
E:
这题并不会证明，猜一发结论，有c % gcd(a,b) == 0时才有答案，并且总是一个瓶子往另一个瓶子倒水，也就是求a * x - b * y == c || b * x - a * y == c 的最小正整数解，然后答案就是2 * (x + y) - 2考虑到问题实际上就是要求最小的k使得a[i] + T = a[i + k - 1]，T = a[k] - a[1];
会发现问题也就是找(a[1] + T,a[2] + T,...a[n - k + 1] + T) == (a[k],a[k + 1],...,a[n])
我们发现在这两组数里面他们的差分序列是相等的。所以可以得出解法
构造一个差分序列c[i] = a[i + 1] - a[i].
问题就相当于求c[1....n - k] == c[k....n - 1]了，这里可以kmp来求
B：
简单的多重背包+0/1背包
dp[i][j]表示前i个物品凑成了面值为j的方案
dp[0][0] = 1;
对于可以无限用的物品来说，最朴素的做法就是
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++)
for(int z = 0; z * a[i] <= j; z++)
dp[i][j] += dp[i - 1][j - z * a[i]];
数据不水的话这东西肯定tle
但是注意到对于dp[i][j]来说实际上它加的是一个前缀和一样的东西..dp[i - 1][j] + dp[i - 1][j - a[i]] + dp[i - 1][j - a[i] * 2]....;
大概你已经发现了都是关于a[i]的这样一个式子，
如果我们在做这个i的dp之前先统计出tmp[j] = tmp[j - a[i]] + dp[i - 1][j];
于是
for(int i = 1; i <= n; i++){
for(int j = 0; j <= m; j++)tmp[j] = (j - a[i] >= 0 ? tmp[j - a[i]] : 0) + dp[i - 1][j];
for(int j = 0; j <= m; j++)dp[i][j] = tmp[j];
}
多重背包的方案做完。
01背包的很简单就不用写了。
这里没写取模。
实际上只要写出朴素dp之后就很容易发现这个优化。
C：
预处理出从起点开始走到i的往四个方向最远的max，然后直接二分答案
D：维护一个优先队列，里面是这样的信息A:分母下标，B当前的分子下标，C分母/分子
重载<号比较C的大小，然后对于i > 1，都把{ A(i),B(i - 1),C( a[i] / a[i - 1 ]) }丢进优先队列，每次取出最小值pop出来，并且加入{ A(A),B(B - 1),C(a[A]/a[B - 1]) }，重复k次就是答案了。
E:
（这题比较不确定，因为我是bfs跑几组数据，然后手推一下猜出来的答案）。
