Educational Codeforces Round 134 (Rated for Div. 2)
D. Maximum AND
题目大意
给出序列a,b
,b
可以任意排列,序列c有\(c_i=a_i\bigoplus b_i\)。c序列的价值为c1&c2&c33...&cn
分析
不难想到,从高到底考虑,每一个\(a_i\)与\(b_i\)对应二进制位。假设考虑的是其中bit
位,则需要所有的\(a_i\)与\(b_i\)的bit
位中,每一个匹配的都两两不同,即\(a_i\)的bit
位中1的数量等于b_i
中0的数量,反之亦然。这样最后c
的价值就可以在当前位取到1
。
则,很明显我们要进行分组操作,高位选择后,会将当前b
的分组再次拆分。
分组操作是蛮经典的操作,可以考虑进行积累。我会在代码中加上注释,可以直接看代码。
Ac_code
#include <bits/stdc++.h>
#define fi first
#define se second
#define endl '\n'
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e5 + 10,M = N*2;
void solve()
{
int n;cin>>n;
vector<int> a(n),b(n);
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
vector<vector<int>> bb(1),aa(1);
for(int i=0;i<n;i++) bb[0].push_back(b[i]),aa[0].push_back(a[i]);
int ans = 0;
for(int i=29;i>=0;i--)
{
bool f = 1;
for(int j=0;j<bb.size();j++)//首先看这一位是否能完成匹配
{
int cnt[2] = {0};
for(auto x:bb[j]) cnt[x>>i&1]++;
for(auto x:aa[j]) cnt[(x>>i&1)^1]--;
if(cnt[0]||cnt[1])
{
f = 0;
break;
}
}
if(!f) continue;//若不能完成匹配,则对分组无影响,则直接继续。
ans|=1<<i;
vector<vector<int>> nb,na;//将新的分组求出来
for(int j=0;j<bb.size();j++)
{
vector<int> v1[2],v2[2];//对于当前组,将其按照当前位拆分为更细的1,0组
for(auto x:bb[j]) v1[x>>i&1].push_back(x);
for(auto x:aa[j]) v2[(x>>i&1)^1].push_back(x);//a中当前位是1,则需要存到相反的0组,是0的存到1组。因为匹配的时候是与相反的位匹配。
for(int k=0;k<2;k++)
if(v1[k].size())
{
nb.push_back(v1[k]);
na.push_back(v2[k]);
}
}
bb.swap(nb),aa.swap(na);
}
cout<<ans<<'\n';
}
int main()
{
ios;
int T=1;
cin>>T;
while(T -- ) {
solve();
}
return 0;
}
E. Prefix Function Queries
题目大意
给出一个初始字符串,每次加入长度不超过10的串,要求增加部分的ne
数组,每次求完之后把新加入的字符删除。
分析
首先每次加入,我们都求一个kmp
是不太合理的。因此考虑可持久化kmp
。然后,就差不多了。
#include <bits/stdc++.h>
#define fi first
#define se second
#define endl '\n'
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
typedef long long LL;
using namespace std;
const int N = 2e6 + 10,M = N*2;
int ne[N],pre[N],last;
char s[N],t[N];
void add(char x)
{
int j = last;
while (j && s[ne[j] + 1] != x) j = pre[j];
s[++last] = x, j = ne[j] + 1;
if (last == 1) ne[1] = pre[1] = 0;
else if (s[j] == x) {
ne[last] = j;
if (s[ne[j] + 1] == s[j + 1]) pre[last] = pre[j];
else pre[last] = j;
}
else ne[last] = pre[last] = 0;
}
void solve()
{
cin>>t;int len = strlen(t);
// cout<<t<<endl;
for(int i=0;i<len;i++) add(t[i]);
int q;cin>>q;
while(q--)
{
cin>>t;
len = strlen(t);
for(int i=0;i<len;i++) add(t[i]),cout<<ne[last]<<' ';
cout<<"\n";
last-=len;
}
}
int main()
{
ios;
int T=1;
// cin>>T;
while(T -- ) {
solve();
}
return 0;
}
标签:pre,Educational,Rated,last,int,Codeforces,ne,--,define
From: https://www.cnblogs.com/aitejiu/p/16632372.html