Codeforces Round 770 div.2 EF

E. Fair Share

题意：有 \(n\) 组物品，第 \(i\) 组有 \(m_i\) 个，每个物品有一个编号，保证每种物品出现偶数次，每组物品有偶数个，要求将所有物品划分为两组，使得一组中有每种物品各一半，每组物品各一半。

首先将问题抽象出来，组别和物品类别其实没有什么区别，都是物品的属性；

建图：左边点表示组别，右边点表示类别，\(i\) 组中包含物品 \(j\)，则连边 \(i,j\)

因为保证了物品出现偶数次，一组也有偶数个物品，那么这张图必然存在若干条欧拉回路

寻找欧拉回路，对于每条欧拉回路，如果一条边是由左到右遍历，则分至 \(L\) 组，否则分至 \(R\) 组，由于欧拉回路的性质（一个点的入次数和出次数相等，这样一定能保证恰好均分）

然后我发现我好像从来没写过欧拉回路，想当然的写了一波TLE了一页（

关键在于，欧拉回路标记vis的是边而不是点，一个点可能遍历多次，如果还是每遍历到一个点就去遍历它的所有连边，即使有vis标记忽略已经走过的边，还是会变成 \(n^2\)

需要记录每个店最后一次遍历的边是哪条，下次再跑直接从这开始即可。

int n, m;
struct Edge{
    int x, y, pj, vis;
}e[maxn];
int ecnt = 0;
vector<int> vp[maxn];
int lst[maxn];
string ans[maxn];
 
void dfs(int p){
    for(int j=lst[p];j<vp[p].size();j=lst[p]){
        int i = vp[p][j];
        lst[p] = j+1;
        if(e[i].vis) continue;
        e[i].vis = 1;
        if(p <= n){
            ans[e[i].x][e[i].pj] = 'L';
            dfs(e[i].y);
        }else{
            ans[e[i].x][e[i].pj] = 'R';
            dfs(e[i].x);
        }
    }
}
 
void solve(){
    cin >> n;
    map<int, int> lsh;
    int tot = n;
    for(int i=1;i<=n;i++){
        cin >> m;
        ans[i] = string(m, '\0');
        for(int j=0;j<m;j++){
            int x; cin >> x;
            if(!lsh[x]) lsh[x] = ++tot;
            e[++ecnt] = {i, lsh[x], j, 0};
            vp[lsh[x]].push_back(ecnt);
            vp[i].push_back(ecnt);
        }
    };
    for(int i=1;i<=tot;i++){
        if(vp[i].size() % 2 != 0){
            cout << "NO\n";
            return;
        }
    }
    for(int i=1;i<=tot;i++) if(lst[i] < vp[i].size()) dfs(i);
    cout << "YES\n";
    for(int i=1;i<=n;i++) cout << ans[i] << '\n';
}

F. Fibonacci Additions

一道差分好题

题意：有长度为 \(n\) 的 \(a\) 数组和 \(b\) 数组，接下来有若干次修改：使 \(a\) 或者 \(b\) 数组的 \([l,r]\) 段依次加上斐波那契数列，即 \(a_l+1\)，\(a_{l+1}+1\)，\(a_{l+3}+2\)...

每次修改完成后，要求输出 \(a\) 与 \(b\) 是否完全相等。

首先需要利用斐波那契数列的性质：\(f_i=f_{i-1}+f_{i-2}\)

在空数组上随便修改几段试一下就会发现，不论怎么修改，在修改量上，永远有 \(d_i=d_{i-1}+d_{i-2}\)

既然如此，可以考虑对修改量差分（前缀和的形式改为斐波那契形式）

写个例子理解一下，比如要对3-6这段区间加斐波那契数列：

修改量：0 0 f1 f2 f3 f4 0 0 0

差分d： 0 0 f1 0 0 0 -f5 -f4 0

如果我们对差分数组这样修改，那么它的斐波那契前缀和即为修改量；

这样就简单啦，显然任意一组修改量和它的差分数组是一一对应的，我们直接把初始情况转化为差分数组，然后每次在差分数组上进行3次单点修改，就可以很方便的判断是否一样了。

ll n, q, mod, a[maxn], tot = 0;
ll f[maxn];
 
void modify(ll x, ll ad){
    if(x > n) return;
    if(a[x] == 0) tot--;
    a[x] = (a[x] + ad + mod) % mod;
    if(a[x] == 0) tot++;
}
 
void solve(){
    cin >> n >> q >> mod;
    f[1] = f[2] = 1;
    for(ll i=3;i<=n;i++) f[i] = (f[i-1] + f[i-2]) % mod;
    for(ll i=1;i<=n;i++) cin >> a[i];
    for(ll i=1;i<=n;i++){
        ll x; cin >> x;
        a[i] -= x;
        a[i] = (a[i] % mod + mod) % mod;
    }
    for(ll i=n;i>=2;i--) a[i] -= a[i-1] + a[i-2], a[i] = (a[i] % mod + mod) % mod;
    for(ll i=1;i<=n;i++) tot += !a[i];
 
    for(ll i=1;i<=q;i++){
        char c; ll x, y;
        cin >> c >> x >> y;
        if(c == 'A'){
            modify(x, 1);
            modify(y+2, -f[y-x+1]);
            modify(y+1, -f[y-x+2]);
        }else{
            modify(x, -1);
            modify(y+2, f[y-x+1]);
            modify(y+1, f[y-x+2]);
        }
        cout << vector<string>{"NO", "YES"}[tot == n] << '\n';
    }
}