Codeforces Round #628 (Div. 2)【ABCDEF】（题解）

目录
[toc]

涵盖知识点：思维、构造、图论。

比赛链接：传送门

E题脑抽。。。写的很垃圾，极限卡过。

A - EhAb AnD gCd

题意： 给一个(n)，找一对数((x,y))使得(gcd(x,y)+lcm(x,y)=n)
题解： (x=1,y=n-1)
Accept Code：

#include <bits/stdc++.h>
using namespace std;

int main(){
    int t;
    cin>>t;
    while(t--){
        int x;
        cin>>x;
        cout<<1<<" "<<x-1<<"
";
    }
    return 0;
}

B - CopyCopyCopyCopyCopy

题意： 无限拼接给定序列，找最长严格递增长度。
题解： 给定序列有多少不同元素就有多长。
Accept Code：

#include <bits/stdc++.h>
using namespace std;
set<int> s;
int main(){
    int t;
    cin>>t;
    while(t--){
        s.clear();
        int n;
        cin>>n;
        while(n--){
            int x;
            cin>>x;
            s.insert(x);
        }
        cout<<s.size()<<"
";
    }
    return 0;
}

C - Ehab and Path-etic MEXs

题意： 给一棵(n)顶点树的边从(0)到(n-2)编号,使得任意两点之间路径的(MEX)值最小。
题解：

如果树是一条链，随便排。全链路径的(MEX)一定为(n-1)。
如果存在某一个节点度数大于等于3，选择其中三条边编号0，1，2。这样其他的路径一定不会同时经过0，1，2。而无论怎么排列，一定无法避免其中会有一条路径同时经过0，1。所以所有路径的(MEX)的最小值一定为2。其他的随便排就可以了。

Accept Code：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef pair<int,int> pii;
vector<pii> edg[maxn];
int ans[maxn];
int main(){
    int n;
    cin>>n;
    for(int i=1,u,v;i<=n-1;i++){
        cin>>u>>v;
        edg[u].emplace_back(v,i);
        edg[v].emplace_back(u,i);
        ans[i]=-1;
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(edg[i].size()>=3){
            for(auto j:edg[i]){
                ans[j.second]=cnt++;
            }
            for(int j=1;j<=n;j++){
                if(ans[j]==-1)
                    ans[j]=cnt++;
            }
            for(int j=1;j<n;j++){
                cout<<ans[j]<<"
";
            }
            return 0;
        }
    }
    for(int i=1;i<n;i++)cout<<i-1<<"
";
    return 0;
}

D - Ehab the Xorcist

题意： 找最短序列，使得全序列异或值等于(u),全序列的和等于(v)。
题解： 先讲特判。

(u>v)：不存在。
(u,v)奇偶性不同：不存在。
(u=v=0)：根据样例应该是0.
(u=v e0)：一个元素等于(u)即可。

对于一般情况，先给出两条规律：

(xoplus x=0)
(xoplus0=x)

所以我们可以构造一个长度为3的序列({u,x,x}),一定满足异或值为(u)，解得(x=frac{v-u}{2})。
注意到样例中存在长度为2的序列。那么继续操作。
若满足(uoplus x=u+x),则((uoplus x)oplus x=(u+x)oplus x),那么长度为2的序列也被我们构造出来了。
对其余情况长度一定不可能为2的证明： 根据(a+b=aoplus b+2 imes(a&b)),则(a&b=x)。那么除了上述情况不存在其他情况长度为2。
Accept Code：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef long long ll;

int main(){
    ll u,v;
    cin>>u>>v;
    if(u==0&&v==0){
        puts("0");
        return 0;
    }
    if(u>v||((u&1)!=(v&1))){
        puts("-1");
        return 0;
    }
    if(u==v){
        puts("1");
        cout<<u<<"
";
        return 0;
    }
    ll x=u,y=(v-u)>>1;
    if((x^y)==(x+y)){
        puts("2");
        cout<<x+y<<" "<<y<<"
";
    }else{
        puts("3");
        cout<<x<<" "<<y<<" "<<y<<"
";
    }
    return 0;
}

E - Ehab's REAL Number Theory Problem

题意： 给一个数组，每个元素因子数不超过7，求最短序列使积为完全平方数。
题解： 因子数不超过7，则只能有两个素因子。抽象建图bfs找最短环。
Accept Code：（好像有别的更好写法。。。这种自己写出来总感觉怪怪的，而且跑起来巨慢QAQ，求教）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int maxn=1e6+5;
vector<int> edg[maxn];
int dis[maxn];
int bfs(int s){
    vector<int> E;
    queue<int> q;
    vector<int> par(maxn);
    par[s]=0;
    dis[s]=0;
    E.push_back(s);
    q.push(s);
    int ans=inf;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i:edg[x]){
            if(dis[i]==-1){
                par[i]=x;
                dis[i]=dis[x]+1;
                E.push_back(i);
                q.push(i);
            }else if(par[x]!=i) ans=min(ans,dis[x]+dis[i]+1);
        }
    }
    for(auto it:E) dis[it]=-1;
    return ans;
}
int main() {
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        vector<pii> pf;
        for(ll f=2;f*f<=x;f++){
            if(x%f==0){
                pf.emplace_back(f,0);
                while(x%f==0){
                    pf.back().second++;
                    x/=f;
                }
            }
        }
        if(x>1) pf.emplace_back(x,1);
        for(int j=pf.size()-1;j>=0;j--)
            if(pf[j].second%2==0)
                pf.erase(pf.begin()+j);
        if(pf.empty()) return cout<<1,0;
        while(pf.size()<2) pf.emplace_back(1,0);
        edg[pf[0].first].push_back(pf[1].first);
        edg[pf[1].first].push_back(pf[0].first);
    }
    int ans=inf;
    memset(dis,-1,sizeof dis);
    for(int i=1;i<=1000;i++) ans=min(ans,bfs(i));
    cout<<(ans==inf?-1:ans);
    return 0;
}

队友写的靠谱一点：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int n, ans = INF, dep[maxn], fa[maxn];
vector<int> G[maxn];
void div(int x)
{
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            while (x % (i * i) == 0)
                x /= i * i;
    if (x == 1)
        puts("1"), exit(0);
    int p1 = x, p2 = 1;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            p1 = x / i, p2 = i;
    G[p1].push_back(p2);
    G[p2].push_back(p1);
}
void bfs(int x)
{
    memset(dep, INF, sizeof(dep));
    queue<int> q;
    dep[x] = 0;
    q.push(x);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto v : G[u])
        {
            if (v == fa[u])
                continue;
            if (dep[v] == INF)
            {
                fa[v] = u;
                dep[v] = dep[u] + 1;
                q.push(v);
            }
            else
                ans = min(ans, dep[u] + dep[v] + 1);
        }
    }
}
int main()
{
 
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++)
    {
        scanf("%d", &x);
        div(x);
    }
    for (int i = 1; i <= 1000; i++)
        bfs(i);
    if (ans == INF)
        puts("-1");
    else
        printf("%d
", ans);
    return 0;
}

F - Ehab's Last Theorem

题意： 给定一个(n)个点(m)条边的无向图。要求找出一个点数恰好为(lceilsqrt{n} ceil)的独立点集或者找出一个点数至少为(lceilsqrt{n} ceil)的环
题解： 首先，找环是很容易的，直接在 dfs 树上找返祖边（回边）即可，如果存在点数大于等于(lceilsqrt{n} ceil)的环就直接输出，类似于tarjan找环。然后再考虑独立集的构造，我们用(lceilsqrt{n} ceil-1)种颜色给给dfs树上的节点按照(dep_i mod (lceilsqrt{n} ceil-1))的规则染色,那么在模下相同深度的节点构成的肯定是一个独立点集，而在模意义下相同的任意两个不同深度节点之间，如果存在直连边就说明存在一个节点数大于等于(lceilsqrt{n} ceil)的环。于是只要找一个大于等于(lceilsqrt{n} ceil)的集合输出(lceilsqrt{n} ceil)个点即可.
Accept Code：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int n, m, lim;
int dep[maxn], fa[maxn], num[maxn];
vector<int> edg[maxn];
void dfs(int u){
    num[dep[u] % (lim - 1)]++;
    for (auto v : edg[u]){
        if (v == fa[u])
            continue;
        if (dep[v] == -1){
            dep[v] = dep[u] + 1;
            fa[v] = u;
            dfs(v);
        }
        else if (dep[u] - dep[v] + 1 >= lim){
            puts("2");
            printf("%d
", dep[u] - dep[v] + 1);
            for (int i = u; i != fa[v]; i = fa[i])
                printf("%d ", i);
            exit(0);
        }
    }
}
int main(){
    cin>>n>>m;
    memset(dep,-1,sizeof dep);
    dep[1] = 0;
    lim = ceil(sqrt(1.0 * n));
    for (int i = 1,x,y; i <= m; i++){
        cin>>x>>y;
        edg[x].push_back(y);
        edg[y].push_back(x);
    }
    dfs(1);
    puts("1");
    for (int i = 0; i < lim - 1; i++){
        if (num[i] < lim)
            continue;
        int tot = lim;
        for (int j = 1; j <= n; j++){
            if (dep[j] % (lim - 1) == i){
                if (tot-- != lim)
                    printf(" ");
                printf("%d", j);
                if (tot == 0)
                    return 0;
            }
        }
    }
}