2023大厂真题提交网址(含题解):

www.CodeFun2000.com（http://101.43.147.120/）

最近我们一直在将收集到的机试真题制作数据并搬运到自己的OJ上，供大家免费练习,体会真题难度。现在OJ已录入50+道2023年最新大厂真题，同时在不断的更新。同时，可以关注"塔子哥学算法"公众号获得每道题的题解。

题目链接

题目思路:

题目条件比较繁杂，一步一步分析.

1.要求同时满足$m$个条件，那么递归出口就不是$O(1)$的判断，而是$O(m)$循环判断.

2.需要让我们判断的等式为 f ( x + i ) ≡ a i ( m o d 2 ) f(x+i) \equiv a_i \ \ (mod \ \ 2) f(x+i)≡ai​  (mod  2)

2.1这个式子涉及到了加法，就可能有进位，比较难处理。但是发现$i$比较小，即只会对数$L$的低六位产生影响。所以可以暴力枚举低六位的情况。

2.2考虑来自低六位的进位会对【二进制中1】的个数的影响：
记录一个从第七位开始的连续的1的个数为$one$.那么$one\to 1$

所以若进位：$f(x+i)\equiv sum-one+f((x+i)\&(1<<8))(mod2)$

不进位时：$f(x+i)\equiv sum+f((x+i)\&(1<<7))(mod2)$

然后我们知道二进制下加法减法都是异或。所以统一按异或处理即可.

所以总体上$dp(前缀长度,数位和的奇偶,当前连续1的个数的奇偶,顶到上界)$

然后$dfs$到后六位时直接暴力统计即可.

注意点:

1.暴力统计的时候注意，若顶到上界，那么上界就应该是$L\%128$,否则是 2 7 − 1 2^7-1 27−1

2.还有记忆化搜索的时候注意由于递归出口不再是$O(1)$的复杂度，而是 O ( 2 7 ∗ m ) O(2^7*m) O(27∗m)，所以得优先记忆化返回，而不是递归出口在前。

时间复杂度:

复杂度分为两个部分，一个部分是记忆化搜索填表,$O(dp数组大小\ast 转移)=O(16\ast logL)$

一部分是后六位的暴力计算$cal函数$，根据状态个数，它最多被调用$8$次.每次复杂度为: O ( 2 7 ∗ m ) O(2^7*m) O(27∗m).总复杂度为: O ( 2 10 ∗ m ) O(2^{10}*m) O(210∗m)

整个算法总复杂度为: O ( T ( 16 ∗ l o g L + 2 10 ∗ m ) ) O(T(16*logL+2^{10}*m)) O(T(16∗logL+210∗m))

最差计算次数跑到$1e8$次左右，但是实际运行$15ms$。

#include
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
const int maxn = 100 + 5;
const int mod = 1e9 + 7;
int a[maxn] , m , dig[maxn] , cnt;
ll dp[65][2][2][2] , L;
int f[500];
ll cal (int sum , int one , int li)
{int s = (li ? L % 128 : 127);int ans = 0;for (int i = 0 ; i <= s ; i++){bool ok = true;for (int j = 0 ; j < m && ok ; j++){if (i + j < 128) ok = ((f[i + j] ^ sum) == a[j]);else ok = ((f[i + j] ^ one ^ sum) == a[j]);}ans += ok;}return ans;
}
ll dfs (int step , int sum , int one , int li) {ll &x = dp[step][sum][one][li];if (~x) return x;if (step <= 6){x = cal(sum , one , li);return x;}int up = (li ? dig[step] : 1);ll ans = 0;for (int i = 0 ; i <= up ; i++){int no = one;if (i) no ^= 1;else no = 0;ans += dfs(step - 1 , sum ^ i , no , li && i == up);}return x = ans;
}
ll solve (ll x)
{memset(dp , -1 , sizeof dp);cnt = 0;int len = 0;for (int i = 63 ; i >= 0 ; i--){dig[i] = (x >> i) & 1;if (dig[i]) len = max(len , i);}return dfs(len , 0 , 0 , 1);
}
int main()
{ios::sync_with_stdio(false);int t; cin >> t;for (int i = 1 ; i < 500 ; i++)f[i] = (f[i >> 1] + (i & 1))%2;while (t--){cin >> m; cin >> L;for (int i = 0 ; i < m ; i++) cin >> a[i];cout << solve (L) << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！