蚂蚁算法实习2024.3.26笔试

不小心做了实习笔试，记录一下。选择题一直不太会，略过。
第一题题意：数字符串(长度n<20)只包含一些特定字符的回文子串。
做法：根据数据范围，直接二进制枚举。时间复杂度O(n * 2^n)。

第二题题意：。。模拟某个机器学习数据处理。。
做法：输入对写c++的不太友好，py3模拟一下。

第三题题意：给定一个01字符串（长度n<1e5），开始和结束位置为1，第一问，求从开始到结束位置最少跳几次，跳跃规则只能跳在1上，若上一次跳了x步，当前可以向前跳2x步或者1步，否则只能跳1步。第二问，当没有策略从起始位置跳到最后位置时，问最少把多少个0改为1能够使得第一问满足。
做法：常规动态规划。注意到数据范围n<1e5，对于2的幂次小于19。
所以对于第一问，记dp[i][j]表示当前位置i，表示能够向前跳2^i的跳到当前位置的最小跳跃次数，转移方式特判一下j为0的时候，dp[i][0] = min{dp[i-(1<对于第二问，记dp[i][j]表示当前位置i，表示能够向前跳2^i的最小次数跳到当前位置最小需要填几次0。转移方程对于当前为1或者0分开考虑，也要特判j为0的情况。对于s[i] == 1时候，dp[i][0] = min{dp[i-(1<