2023/11/20
早上脑子转的不是很快啊
1851F - Lisa and the Martians
看到位运算+贪心+异或：想到字典树，就是一个改编版本的最大异或对
可以证明当ai和aj的某一位2进制位不同是，x在这一位无论怎么取都不行。
所以当遍历到一个ai值时，取字典树里面贪心的查一下和他最大相同的值是多少
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 6e6 + 10;
int son[N][2];
int vis[N];
int a[N];
int n, k;
int tot;
array<int, 4> ans;
void insert(int x, int pos)
{
int p = 0;
for (int i = k - 1; i >= 0; i--)
{
int id = ((x >> i) & 1);
if (son[p][id])
p = son[p][id];
else
{
son[p][id] = ++tot;
p = son[p][id];
}
}
vis[p] = pos;
}
pair<int, int> query(int x)
{
int p = 0, res = 0;
for (int i = k - 1; 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, vis[p]};
}
void solve()
{
for (int i = 0; i <= tot + 1; i++) //想到了如何清空
{
son[i][0] = son[i][1] = 0;
vis[i] = 0;
}
tot = 0;
cin >> n >> k;
int mx = pow(2LL, k) - 1;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
a[i] = x;
pair<int, int> xx = query(x);
if (ans[2] <= (mx ^ xx.first))
{
ans[0] = xx.second;
ans[1] = i;
ans[2] = (mx ^ xx.first);
}
insert(x, i);
}
cout << ans[0] << " " << ans[1] << " " << (mx ^ a[ans[0]]) << endl;
ans[2] = 0;
}
signed main()
{
Acode;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
D - Balanced String
补一下上星期的dp
实质上是在保证1的个数不变的情况下，枚举哪一位填1，重新构造了一个序列，然后和原序列对比，不同的地方就是交换的地方，比如原序列是0，但你这位想填1，那就相当于把原序列中这位的0和某一位的1交换一下，因为保证1的个数不变，所以本质上是一样的。
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 6e6 + 10;
int dp[110][10000];
int dpp[110][10000];
void solve()
{
string s;
cin >> s;
int len = s.size();
s = " " + s;
int cnt1 = 0, cnt0 = 0;
for (int i = 1; i <= len; i++)
{
if (s[i] == '1')
cnt1++;
else
cnt0++;
}
int kk = (len - 1) * len / 2 - (cnt1 - 1) * cnt1 / 2 - (cnt0 - 1) * cnt0 / 2;
int k1 = kk / 2;
kk = k1 + (cnt1 - 1) * cnt1 / 2;
memset(dpp, 0x3f, sizeof dpp);
dpp[0][0] = 0;
for (int i = 1; i <= len; i++)
{
for (int j = 0; j <= cnt1; j++)
{
for (int k = 0; k <= kk; k++)
{
dp[j][k] = dpp[j][k];
if (j >= 1 && k >= i - 1)
dp[j][k] = min(dp[j][k], dpp[j - 1][k - i + 1] + (s[i] != '1'));
}
}
for (int j = 0; j <= cnt1; j++)
{
for (int k = 0; k <= kk; k++)
{
dpp[j][k] = dp[j][k];
}
}
}
cout << dp[cnt1][kk] << endl;
}
signed main()
{
Acode;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
CF1860E Fast Travel Text Editor
这个算是把上星期打的一场edu补完了
非常好的一道图论题，q次询问注定技巧一堆。
首先是建图，常规建图就直接T，常用技巧，建立虚点，进来0，出去1.等价实现。边数降到n级别的
第二是每次询问两个点之间的最短路，每次都跑dij直接g。发现虚点数量很少只有26*26，用虚点都跑一边最短路。记录这个虚点到其他点的最短距离。原来512mb是可以开3e7的long long的。
然后这样，我们依次枚举过某个虚点。这样复杂度可以接受，考虑到边权都是0/1，直接跑0-1bfs O（n）级别非常快
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 5e4 + 700;
int vis[700][N];
vector<pair<int, int>> g[N];
int len;
int get(char i, char j)
{
return (i - 'a') * 26 + j - 'a';
}
void bfs(int x)
{
deque<int> q;
vis[x][x + len] = 0;
q.push_back(x + len);
while (q.size())
{
int u = q.front();
q.pop_front();
for (auto it : g[u])
{
int v = it.first;
int w = it.second;
if (vis[x][v] > vis[x][u] + w)
{
vis[x][v] = vis[x][u] + w;
if (w)
q.push_back(v);
else
q.push_front(v);
}
}
}
}
void solve()
{
string s;
cin >> s;
int n = s.size();
len = s.size() + 5;
s = " " + s;
for (int i = 1; i <= n; i++)
{
if (i != n)
{
g[i].push_back({i + 1, 1});
g[i].push_back({get(s[i], s[i + 1]) + len, 0});
g[get(s[i], s[i + 1]) + len].push_back({i, 1});
}
if (i != 1)
g[i].push_back({i - 1, 1});
}
memset(vis, 0x3f, sizeof vis);
for (int i = 0; i <= 26 * 26; i++)
{
bfs(i);
}
int q;
cin >> q;
while (q--)
{
int s, t;
cin >> s >> t;
int ans = abs(s - t);
for (int i = 0; i <= 26 * 26; i++)
{
ans = min(ans, vis[i][s] + vis[i][t] - 1);
}
cout << ans << endl;
}
}
signed main()
{
Acode;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
CF1845D Rating System
思路：最大前后缀，我们可以判断k应该为某一个前缀值，然后我们保护这个值不会减少，一直等到上升的序列出现。
因为要走完整个数组，所以我们来看最大的后缀是多少
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 2e6 + 700;
int a[N];
int pre[N], suf[N];
int pres[N], sufs[N];
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n + 1; i++)
{
pre[i] = suf[i] = pres[i] = sufs[i] = 0;
}
for (int i = 1; i <= n; i++)
{
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
pres[i] = max(pre[i], pres[i - 1]);
}
for (int i = n; i >= 1; i--)
{
suf[i] = suf[i + 1] + a[i];
sufs[i] = max(suf[i], sufs[i + 1]);
}
int ans = 0;
int id = 0;
for (int i = 1; i <= n; i++)
{
if (pres[i] + sufs[i + 1] > ans)
{
ans = max(ans, pres[i] + sufs[i + 1]);
id = pres[i];
}
}
cout << id << endl;
}
signed main()
{
Acode;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}