E题

https://codeforces.com/contest/2030/problem/E
题意：数组b的分数为，将b任意划分为k个非空子集后，子集mex和的最大值。
求数组a所有子序列的分数和。

1.考虑求数组b的分数。由于mex值的特性，只需要考虑b中各个元素出现的频率f[i]。从0开始考虑，每个子集只需要有一个0，mex值就会由0变为1，为了让mex和最大，所以我们可以划分f[0]个子集，每个子集安排一个0，这样$score += f[0]$。再考虑1，可以往$min(f[0],f[1])$个子集里加入1使得mex值变为2，这样$score += min(f[0],f[1])$。总之就是贪心，后续以此类推，得到：
$$score(b) = f[0]+min(f[0],f[1])+…min(f[0],f[1],....f[n-1])$$
2.考虑怎么求一个数组a的所有子序列的score和。可能的思路为：由score的计算公式，考虑贡献法。在i位置，如果前面f的最小值为j，则它能贡献j*x(x为考虑选完前面的数，且f的最小值为i的方案数)*后面的数随便选的方案数(后面的数不影响该位置的贡献)。
考虑dp[i][j]：考虑前i个数且，$min(f[0],f[1],…,f[i-1]$)为j的子序列的数量。得到dp[i][j]后，$ans += j*dp[i][j]*2^(f_{i+1}+f_{i+1}+…+f_{n-1})$

dp的状态转移，到这里参考题解，转移方程不难理解

F题

https://codeforces.com/contest/2025/problem/F
给一个序列a，n个元素。初值都为0，
q次查询，每次查询给出两个位置，选择一个位置p，对a[p]加一或者减一，不能使a[i]<0。
如果操作能使得最后数组a元素的和最小。

1.如果一个a[i]是1，要操作它时让它减一，反之如果是0，则让它加一
2.cnt记录查询过程中a数组元素的值，按（1）的方式操作。
3.则只需要确定每次查询，操作的位置即可。假定全部操作x位置，则会有一些位置元素为1，接下来问题转换为：将那几次的操作位置改为y，能消去最多的1。
4.考虑将一次操作x改为y。则x位置元素取反，y位置元素取反。则一次查询两个位置都为0的话，不需要更改。如果都为1的话，修改一次去掉两个1；一个为1一个为0的话，1会从一个位置“跑到”另一个位置。
5.此时问题再转换成，某个位置的1通过每次查询构成的“边”，寻找另一个1来互相“抵消”的过程。于是建图。
6.建图后发现，其实只需要他们的生成森林就可以完成所有操作，于是建一棵生成森林。
7.对其中每一棵树，发现可以把所有的“1”都转换到根节点，即可得到这棵树的最优方案。于是dfs每棵树，如果子节点的元素值为1的话，说明要修改这条边的操作位置。

#include<bits/stdc++.h>
#define LOCAL//delete when submit!!!!!!


using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
const int N = 3e5+10;
string idx="xy",sign="+-";
int n,q;

vector<int> p;
vector<int> siz;
vector<int> cnt;
struct Edge{
    int u,v;
};
vector<Edge> edges;
vector<vector<pii>> tree;
vector<string> ans;

vector<bool> vis;
int find(int x){
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}
void upd(int x,int rt){
    ans[x][0]= ans[x][0]=='x'? 'y':'x';
}


void dfs(int u,int fa){
    vis[u] = true;
    for(auto [v,i]:tree[u]){
        if(v==fa) continue;
        if(vis[v]) continue;

        dfs(v,u);
        if(siz[v]%2){
            upd(i,u);siz[u] = (siz[u]+siz[v])%2;
            siz[v] = 0;
        }
    }
}

void solve(){
    cin>>n>>q;
    tree.resize(n+1);p.resize(n+1);siz.resize(n+1);vis.resize(n+1);ans.resize(q+1);
    cnt.resize(n+1);
    for(int i=1;i<=n;i++){
        p[i] = i;
    }
    for(int i=0;i<q;i++){
        int u,v;cin>>u>>v;
        edges.push_back({u,v});
        siz[u]=(siz[u]+1)%2;
        ans[i]="x+";
    }

    for(int i=0;i<q;i++){
        auto [u,v] = edges[i];
        int ru = find(u),rv=find(v);
        if(ru!=rv){
            tree[u].push_back({v,i});
            tree[v].push_back({u,i});
            p[rv] = ru;
        }
    }
    for(int i=1;i<=n;i++){
        if(!vis[find(i)]) dfs(find(i),-1);
    }

    for(int i=0;i<q;i++){
        if(ans[i][0]=='x'){
            if(cnt[edges[i].u]) ans[i][1]='-',cnt[edges[i].u]++;
            else ans[i][1]='+',cnt[edges[i].u]--;
        }else{
            if(cnt[edges[i].v]) ans[i][1]='-',cnt[edges[i].v]++;
            else ans[i][1]='+',cnt[edges[i].v]--;
        }
        cout<<ans[i]<<endl;
    }
}

int main(){     
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}