滴滴编程第一题 9.10 c++ ac代码
#include<iostream>
#include<vector>
#include<set>
using namespace std;
int CalcNum(vector<int>&data)
{
int num = data.size();
vector<int>result(num,0);
set<int>temp;
vector<set<int>>dp(num,temp); //存储以下标i结尾的区间的异或值
if (data[0] == 0)
{
result[0] = 1;
}
else
{
dp[0].insert(data[0]);
}
for (int i = 1; i < num; i++)
{
if (data[i] == 0)
{
result[i] = result[i - 1] + 1;
continue;
}
if (dp[i - 1].find(data[i]) != dp[i - 1].end())
{
result[i] = result[i - 1] + 1;
continue;
}
result[i] = result[i - 1];
set<int>::iterator it = dp[i - 1].begin();
while (it!=dp[i-1].end())
{
int cur = data[i]^(*it);
dp[i].insert(cur);
it++;
}
dp[i].insert(data[i]);
}
return result[num - 1];
}
int main()
{
int n;
cin >>n;
vector<int>data(n,0);
for (int i = 0; i <n; i++)
{
cin >> data[i];
}
int result = CalcNum(data);
cout << result;
return 0;
}
#滴滴##C++工程师#
海康威视公司福利 1311人发布