测试原链接：TJU暑期训练 个人排位赛（四）

题目来源：Atcoder-abc282; Atcoder-abc281;

题目考点：

AT-14 Make Bipartite 2

Problem Statement

题目大意：

给定一个简单图，求有多少种边的添加方法使得其是一个二分图？

题目解析

首先学习什么叫二分图

本题使用的二分图性质是：图上加一个边使得其是二分图的前提是其原本就是个二分图，两个二分图之间随便加一个边将二者链接后形成的新图依旧是一个二分图。（涂色倒转）

众所周知，简单图是没有自环和重边的。但是，谁告诉你简单图必定是连通图了？

这是第一个问题点。

其次，二分图的定义是整个图的 所有边 都能够分成两个不相交的集合

换句话说

只要有一个连通区域不是二分图，那整张图就都不是图，这个题的结果直接就是0。不能说把非连通区域排出后剩下的组成也算二分图，这个图就不完整了，就不是题目给定的图了

这是第二个，也是最致命的一个问题点。

剩下的就好说了。设给定的图有个相互独立的非连通区域，对于某一连通区域,初始有条边,涂色为的点个数为,的为,则内的连边最多可以连上条边，使得该连通区域依旧是一个二分图。而之于其他连通分量的所有点均可以加一条边连通两个连通区域形成一块新的二分连通区域,可以连接条边。

所以答案是

话外提一句，统计一个图的边的数量和点的总数可以在时通过的来计算，这样可以不用再考虑去重问题而将之交给自动处理。相对应的，统计点的时候可以在q.pop()时就做标记统计，这样可以统计不同要求的点的各个数量。本题对于点的统计采用的是后者。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
int n0,m0;
vector<int> connects[200001];
bool visited[200001];
int color[2];
int res[200001];
typedef pair<int, int> p;
set<p>s;
vector<p> ans;
void bfs(int i)
{
    s.clear();
    queue<int> q;
    q.push(i);
    bool tag=0;
    while(!q.empty())
    {
        int top=q.front();
        q.pop();
        if(visited[top])continue;
        visited[top]=true;
        color[res[top]]++;
        for(int i=0;i<connects[top].size();i++)
        {
            int next=connects[top][i];
            if(next<=top)s.insert({next,top});
            else s.insert({top,next});
            if(!visited[next])
            {
                res[next]=(res[top]+1)%2;
                q.push(next);
            }
            else
            {
                if(res[next]==res[top])tag=1,cout<<"0"<<endl,exit(0);
            }
        }
    }
    if(tag)color[0]=color[1]=0;
    else m0+=s.size();
    return;
}
signed main()
{
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++)
    {
        cin >> u >> v;
        connects[u].push_back(v);
        connects[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
    {
        if (visited[i])continue;
        memset(color,0,sizeof(color));
        bfs(i);
        n0+=(color[0]+color[1]);
        ans.push_back({color[0], color[1]});
    }
    int answ=0;
    for(int i=0;i<ans.size();i++)
    {
        answ+=(ans[i].first*ans[i].second)+(ans[i].first+ans[i].second)*(n0-(ans[i].first+ans[i].second));
        n0-=ans[i].first+ans[i].second;
    }
    cout<<answ-m0<<endl;
    system("pause");
    return 0;
}

AT-15 Make Bipartite 2

Problem Statement

题目大意：

一共有个球，每个的价值为,每次随机选取两个球，求出得分，然后吃掉一个，剩下的放回去。求可能的最大得分。

题目解析

着实没想到这竟然是一个生成树的题，果然现在我的脑子已经魔怔了，看见最值和选择就是…………

不过仔细考虑，确实也是挺巧的。

每两个球都确定唯一对应的得分，是一个的点——边权关系；同时，每选一次都会吃掉一个，最后选完的时候会是吃了个球有次得分，还是求得分的最值，这就是生成树的两个确定算法的根源。

而且，这个题没有出现说相互独立的个子问题，对于一个球吃不吃掉这个抉择都会对后面的得分区间产生影响，不符合要求的若干个子问题互不干涉，所以不是.

生成树，不多说了，注意集合合并的时候是father[getfather(p)]=getfather(q),或者写作father[father[p]]=father[q]

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef struct node
{
    pair<int, int> uv;
    int w;
    bool operator<(const node &x) const
    {
        return x.w > w;
    }
} node;
#define maxn int(1e7)
int a[501];
int father[501];
int n, m;
void init()
{
    for (int i = 1; i <= n; i++)
    {
        father[i] = i;
    }
}
int getfather(int x)
{
    if (x == father[x])
        return x;
    else
        return getfather(father[x]);
}
#define mod m
int quickpow(int a, int n)
{
    int e = 1;
    while (n)
    {
        if (n & 1)
            (e *= a) %= mod;
        (a *= a) %= mod;
        n >>= 1;
    }
    return e;
}
int calc(int i, int j)
{
    return (quickpow(a[i], a[j]) % mod + quickpow(a[j], a[i]) % mod) % mod;
}
bool visited[501];
int kruskal(priority_queue<node> q)
{
    int ans = 0;
    while (!q.empty())
    {
        node x = q.top();
        q.pop();
        if(getfather(x.uv.first)!=getfather(x.uv.second))
        {
            father[getfather(x.uv.first)]=getfather(x.uv.second);
            ans+=x.w;
        }
    }
    return ans;
}
signed main()
{
    cin >> n >> m;
    init();
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    priority_queue<node> q;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
        {
            q.push((node{pair<int, int>(i, j), calc(i, j)}));
        }
    cout<<kruskal(q)<<endl;
    system("pause");
    return 0;
}

AT-16 Union of Two Sets

Problem Statement

题目大意：

本题要求在线，根据的提问做出相应的反应。

• 首先，给出一个正整数 （），你需要构造 （） 个区间 ，满足 ，输出 和这 个区间，这些区间的编号按输出顺序依次为 。

• 然后，给出一个正整数 （），表示有 次询问。对于每次询问，给定区间 ，你要找到两个整数 （，可以等于 ），满足在第一步中构造的区间中 与 的并集等于 ，输出 。

题目解析

ST表的原理题

对于本题来说，只需要划分ST区域，因为这样划分可以保证任意两端能组成一个满足要求的并集。划分好之后，对于每一次询问，输出两端的两条线段序号就可以了。

构建时ST不需要存放区间最大或最小值信息，只需要存放线段的编号。

因为单点不成线段，所以不从0开始画。

代码：

#include <bits/stdc++.h>
using namespace std;
int f[4001][21];
int cnt = 0;
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i <= 20; i++)
    {
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
        {
            f[j][i] = ++cnt;
        }
    }
    cout << cnt << endl;
    for (int i = 0; i <= 20; i++)
    {
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
        {
            cout << j << " " << j + (1 << i) - 1 << endl;
        }
    }
    int q;
    cin >> q;
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        int k = log2(r - l + 1);
        cout << f[l][k] << ' ' << f[r - (1 << k) + 1][k] << endl;
    }
}