2023/11/10
字典树学习.2
最大异或对 (Trie)
找出两个数异或起来的最大值 O(n loga[n]),思路就是贪心的优先把高位置为1，然后在Trie树上查找是否有符合的数
const int N = 1e5 + 10;
const int M = 3e6 + 10;
int n, idx;
int a[N];
int son[M][2];
void insert(int x) //把所有数字先加入Trie里面（建树）
{
int p = 0;
for (int i = 32; i >= 0; i--)
{
int id = ((x >> i) & 1);
if (!son[p][id])
{
son[p][id] = ++idx;
}
p = son[p][id];
}
}
int query(int x)
{
int p = 0, res = 0;
for (int i = 32; i >= 0; i--)
{
int id = ((x >> i) & 1);
if (son[p][!id])
{
res += (1LL << i);
p = son[p][!id];
}
else
p = son[p][id];
}
return res;
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
insert(a[i]);
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
ans = max(ans, query(a[i]));
}
cout << ans << endl;
}
字典树学到最大异或对就可以补昨天的题了
D - XOR Construction
题意：给n-1个数，构造一个n个数的序列，两两异或起来为给定的序列，构造的数是0~n-1的排列。
思路：如果找异或规律的话，只能构造出奇数的情况，所以考虑一般做法。
我们枚举b1,那么通过a的前缀异或和可以知道其他的数，把a的前缀异或和存到字典树中，然后用这棵树对枚举的每个b求最大异或对，若值为n-1（b的上限），意思为b1为这个数的时候，其他的数的最大值为n-1，刚好符合上限，且题目保证一定可以构造出。那么有鸽巢原理，当前的b1就是答案。如果不存在，那么说明b1就是n-1.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 2e5 + 10;
const int M = 3e6 + 10;
int n, idx;
int a[N];
int son[M][2];
int b[N];
void insert(int x)
{
int p = 0;
for (int i = 30; i >= 0; i--)
{
int id = ((x >> i) & 1);
if (!son[p][id])
{
son[p][id] = ++idx;
}
p = son[p][id];
}
}
int query(int x)
{
int res = 0, p = 0;
for (int i = 30; i >= 0; i--)
{
int id = ((x >> i) & 1);
if (son[p][!id])
{
res += (1LL << i);
p = son[p][!id];
}
else
p = son[p][id];
}
return res;
}
void solve()
{
cin >> n;
int res = 0;
for (int i = 1; i <= n - 1; i++)
{
cin >> a[i];
res ^= a[i];
insert(res);
// cerr << res << endl;
}
b[1] = n - 1;
for (int i = 0; i <= n - 1; i++)
{
// cerr << query(i) << endl;
if (query(i) == n - 1)
{
b[1] = i;
break;
}
}
for (int i = 2; i <= n; i++)
{
b[i] = a[i - 1] ^ b[i - 1];
}
for (int i = 1; i <= n; i++)
{
cout << b[i] << " ";
}
}
signed main()
{
Acode;
int T = 1;
while (T--)
{
solve();
}
return 0;
}
CF1864D Matrix Cascade
思维题：如果暴力操作的话复杂度是O（n^3）的，想着降一个n
思路：我们从上到下，从左到右的扫描每一个点，这样可以保证被扫描过的点一定是0.然后对于扫到的点是1的情况，那个我们只考虑他这个点对下一层的影响，就是不把他的贡献走完，而是只走一层。这样的好处是可以累加的处理贡献。所以对于一个点，我们维护三个东西，是否是最左边的点，是否是最右边的点，普通向下的点。这样枚举O（n^2），转移O（1），可以通过本题
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 2e5 + 10;
const int M = 3e6 + 10;
int n, idx;
int mp[3010][3010];
int vis[3010][3010][4];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
char ch;
cin >> ch;
// cin >> mp[i][j];
mp[i][j] = ch - '0';
vis[i][j][1] = vis[i][j][2] = vis[i][j][3] = 0;
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
mp[i][j] += vis[i][j][1] + vis[i][j][2] + vis[i][j][3];
if (mp[i][j] & 1)
{
// cerr << i << " " << j << " " << mp[i][j] << endl;
ans++;
mp[i][j]++;
if (j - 1 >= 1)
vis[i + 1][j - 1][2]++;
if (j + 1 <= n)
vis[i + 1][j + 1][3]++;
vis[i + 1][j][1]++;
}
if (vis[i][j][1])
{
vis[i + 1][j][1] += vis[i][j][1];
}
if (vis[i][j][2])
{
if (j - 1 >= 1)
vis[i + 1][j - 1][2] += vis[i][j][2];
vis[i + 1][j][1] += vis[i][j][2];
}
if (vis[i][j][3])
{
if (j + 1 <= n)
vis[i + 1][j + 1][3] += vis[i][j][3];
vis[i + 1][j][1] += vis[i][j][3];
}
}
}
// for (int i = 1; i <= n; i++)
// {
// for (int j = 1; j <= n; j++)
// {
// cout << mp[i][j] << ' ';
// }
// cout << endl;
// }
cout << ans << endl;
}
signed main()
{
Acode;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
今晚补题补的有点慢的，一个上午就学了字典树和补了一道相关的，下午体育课结束后就写了一题（输）
晚上vp div2 还是3题，D题真的只会暴力，想不到其他的任何做法，还得多练
Codeforces Round 906 (Div. 2) solve(3/7)
https://www.bilibili.com/video/BV1Su4y1t7zm/?vd_source=7b3be65640481106bef731ef741a960f
看了D,E1的题解感觉可补，明天早上早点起来补一补