C.Ehab and Path-etic MEXs

题意：给定一n个结点的树，请将0-n-2标在n-1条边上，定义MEX(u,v)为u到v路径没有出现数字的最小值,求一个最优的标号方案满足MEX(u,v)和为最小(n<=1e5).
分析：取一个度数最大的点，将该点所有的边以0开始依次标号，可以证明所有不经过该点的MEX的值为0，经过该点的MEX值可能为0,1,2.

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

typedef long long ll;
const int maxn=1e5+10;

vector<int> p[maxn];

int ans[maxn];

int main()
{
    int n;
    scanf("%d",&n);
    for( int i=1;i<n;i++ )
    {
        int a,b;
        scanf("%d%d",&a,&b);
        p[a].push_back(i);
        p[b].push_back(i);
        ans[i]=-1; 
    }
    pair<int,int> mx(0,0);
    for( int i=1;i<=n;i++ )
    {
        mx=max( mx,make_pair( (int)p[i].size(),i) );
    }
    int cur=0;
    for( int i:p[mx.second] ) ans[i]=cur++;
    for( int i=1;i<n;i++ ) 
    {
        if( ans[i]==-1 ) ans[i]=cur++;
        printf("%d\n",ans[i]);
    }

}

D. Ehab the Xorcist

大致题意:给定u,v,找到一个最短的数组，各元素异或和等于u并且各元素之和等于v。
分析: 我们知道结论 a+b=a^b+2 * (a&b) --- 简单证明可得，那么令u=a^b，v=a+b, x=(a&b)=(u-v)/2 ,显然 [u,x,x]是一个合法数组.所以数组最长长度为3.那么我们考虑能不能再减少长度.当u==v 时[u]显然合法,那么考虑[u^x,x]能否成立的情况,当u&x==0 时，u^x=u+x,即[u^x,x]合法.我们考虑不存在数组的情况.x<0--->u<v 输出-1,并且 u、v必须同奇偶性.否则输出-1
题解代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long u,v;
    scanf("%I64d%I64d",&u,&v);
    if (u%2!=v%2 || u>v)
    {
        printf("-1");
        return 0;
    }
    if (u==v)
    {
        if (!u)
        printf("0");
        else
        printf("1\n%I64d",u);
        return 0;
    }
    long long x=(v-u)/2;
    if (u&x)
    printf("3\n%I64d %I64d %I64d",u,x,x);
    else
    printf("2\n%I64d %I64d",(u^x),x);
}

E.Ehab's REAL Number Theory Problem

题意：给定长度为n的数组a,数组中每个元素满足可整除的除数不超过7个，求从a数组中选择最少的元素满足所有元素乘积为一个完全平方数。(n<=1e5,1<=ai<=1e6)
分析：

考虑每个元素满足可整除的除数不超过7个，将元素进行质因数分解，显然不相同质因数个数不超过2个.(可以证明具有三个质因子个数的数有至少8个不同除数 ).并且如果元素能够整除某个平方数，那么我们先将元素除以该平方数也不会影响答案。
考虑乘积等于某个平方数，将该平方数进行质因数分解每个质因数的个数一定是偶数。那么我们可以将a数组的处理后(除以有平方数因子)元素进行分解因子(每个数最多有2个因子)，将因子作为点，元素作为边的的权值，这样我们就建成了一张图，现在我们求该图的最小环问题，就是求问题的答案。-----------最小环路径上的乘积使得每个质因子个数为偶数.
求最小环问题，该题点数不超过sqr(n)个，可以暴力枚举每个点作为源点，进行bfs找环.

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

const int maxn=1e6+10;
const int inf=0x3f3f3f3f;

int n,ans=inf,lvl[maxn],p[maxn];

vector<int>g[maxn];

void bfs( int v )
{
    if( g[v].empty() ) return;
    memset(lvl,inf,sizeof(lvl));
    queue<int>que;
    lvl[v]=0;
    que.push(v);
    while( !que.empty() )
    {
        v=que.front();que.pop();
        for( auto u:g[v] )
        {
            if( u!=p[v] )
            {
                if( lvl[u]==inf )
                {
                    p[u]=v;
                    lvl[u]=lvl[v]+1;
                    que.push(u);
                }
                else
                {
                    ans=min(ans,lvl[u]+lvl[v]+1);
                }
            }
        }
    }
}

void f( 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 ) ans=1;
    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); 
}

int main()
{
    cin>>n;
    for( int i=1;i<=n;i++ )
    {
        int x;cin>>x;f(x);
    }
    for( int i=1;i*i<maxn;i++ )    bfs(i);
    if( ans==inf ) puts("-1");
    else cout<<ans<<endl;

}

F.Ehab's Last Theorem

题意：给定一个n个点的无向连通图，求长度至少为 $图片说明$ 的环，如果不存在，求长度至少为 $图片说明$ 的独立集.
**分析:
直接上链接理解找最小环.

https://codeforces.ml/blog/entry/68138
找独立集，根据二分图性质找即可.

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

typedef long long ll;

const int maxn=1e5+10;

vector<int> g[maxn],s;
bool marked[maxn];
int sq,dep[maxn];

void dfs( int x )
{
    s.push_back( x );
    dep[x]=s.size();
    for( auto v:g[x] )
    {
        if( !dep[v] ) dfs(v);
        else if( dep[x]-dep[v]+1>=sq )
        {
            puts("2");
            printf("%d\n",dep[x]-dep[v]+1);
            for( int i=dep[v]-1;i<dep[x];i++ )    printf("%d ",s[i]);        
            exit(0);
        }
    }
    if( !marked[x] )
    {
        for( auto v:g[x] ) marked[v]=1;
    }
    s.pop_back();
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    while( sq*sq<n ) sq++;
    while( m-- )
    {
        int a,b;
        scanf("%d%d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }


    dfs(1);
    puts("1");
    for( int i=1;sq;i++ )
    {
        if( !marked[i] )
        {
            printf("%d ",i);
            sq--;
        } 
    }
}

Codeforces Round #628 (Div. 2)

C.Ehab and Path-etic MEXs

D. Ehab the Xorcist

E.Ehab's REAL Number Theory Problem

F.Ehab's Last Theorem