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;
}