CF Round 628

终于写了一次 A ~ F 的全部题解。

CF1325 A ~ F

一晚上补完了。。好累。。

以后代码头文件和宏定义太长的就不写上了，专门开个帖子放头文件吧。

A EhAb AnD gCd

输出 $1 , n - 1$ 显然正确。

int n , k , P;
 
void solve() {
    cin >> n;
    cout << 1 << ' ' << n - 1 << endl;
}
int main() {
    int T;cin >> T;
    while( T-- ) solve();
}

B CopyCopyCopyCopyCopy

考虑复制 $n$ 次后显然每个不同的数字都能做出贡献，答案就是不同数字个数

int n , k , P;
int A[MAXN];
void solve() {
    cin >> n;
    for( int i = 1 ; i <= n ; ++ i ) scanf("%d",&A[i]);
    sort( A + 1 , A + 1 + n );
    cout << unique( A + 1 , A + 1 + n ) - A - 1 << endl;
}
int main() {
    int T;cin >> T;
    while( T-- ) solve();
}

C Ehab and Path-etic MEXs

我们拖出所有的叶子。首先如果叶子只有两个意味着是一条链，显然不管怎么放答案都一样。。

否则，至少有三个叶子，直接把叶子向父亲的连边放 0,1,2 ，剩下的随意放就好了。

为啥这样是对的呢，我们知道肯定 mex 的最大值不会少于 2 ，因为不管怎么说从 0 的边都可以走到 1 的边。但是如果三个都是叶子，显然没办法走到 2 的边。

int n , k , P;
int A[MAXN];
vector<int> G[MAXN], o;
int deg[MAXN] , ans[MAXN];
void solve() {
    cin >> n;
    for( int i = 1 , u , v ; i < n ; ++ i ) {
        scanf("%d%d",&u,&v) , G[u].push_back( i ) , G[v].push_back( i );
        deg[u] ++ , deg[v] ++;
    }
    for( int i = 1 ; i <= n ; ++ i ) if( deg[i] == 1 ) o.push_back( i );
    memset( ans , -1 , sizeof ans );
    if( o.size() <= 2 ) {
        for( int i = 0 ; i < n - 1 ; ++ i ) printf("%d\n",i);
    } else {
        int cur = 0;
        for( int x : o ) {
            for( int v : G[x] ) ans[v] = cur;
            ++ cur;
            if( cur >= 3 ) break;
        }
        cur = 2;
        for( int i = 1 ; i < n ; ++ i ) {
            if( ans[i] == -1 ) printf("%d\n",++ cur);
            else printf("%d\n",ans[i]);
        }
    }
}
int main() {
    solve();
}

D Ehab the Xorcist

首先，两个数的 xor 和和必然奇偶性相同。如果不相同肯定是 No Solution。

然后考虑，我们知道 $a+b = a\ \text{xor}\ b + 2(a\ \text{and}\ b)$ 。因为 xor 实际上是不进位加法，可以通过 and 来进位。

所以有 $u \le v$ 否则又 No Solution。

然后考虑，如果我们有三个位置，必然可以构造出答案。因为可以放一样的数，可以直接放 $u$ 和两个 $\frac{v-u}{2}$ 。这个构造也是蛮神仙的。。

然后什么时候可以用两个位置构造出答案？显然我们有 $\frac{v-u}{2}$ 就必须是 $a\ \text{and}\ b$ ，而 $u$ 是 $a\ \text{xor}\ b$ ，如果它们之间有交，也就是说某些位置既都是 1 ，又两个位置不同，这显然矛盾了啊。所以如果没有交，可以构造出 $u\ \text{or}\ \frac{v-u}{2},\frac{v-u}{2}$ 。

ll u , v , k;
void solve( ) {
    cin >> u >> v;
    if( !u && !v ) return puts("0") , void();
    if( u + v & 1 ) return puts("-1") , void();
    if( u > v ) return puts("-1") , void();
    if( u == v ) return printf("1\n%lld\n",u),void();
    ll t = ( v - u ) / 2;
    if( t & u ) {
        printf("3\n%lld %lld %lld\n",u , v - u >> 1 , v - u >> 1);
    } else {
        printf("2\n%lld %lld\n",u|t,t);
    }
}
signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

E Ehab’s REAL Number Theory Problem

个人感觉很好的一个题。

发现所有数字约数个数不超过 7 ，这就告诉我们它不能有三个素因子。如果它有两个素因子，也只能是 $pq$ 或 $pq^2$ 这两种形式。但是由于最后要凑出平方数，所以显然 $pq^2$ 可以看成是 $p$ 。如果是质数的次幂，我们也可以直接把次幂模 2 来做就好了。

所以，最后每个数字都是 $p,pq$ 的形式。

最后既然要找一些数字乘起来是个完全平方，肯定不会超过两个数字含有同一个质数（感性理解一下很容易发现。。）。所以我们可以把每个数字看成一条边，如果是 $pq$ 就看成 $p \to q$ ，否则就看成 $1 \to p$ （当然是双向边）。

然后现在问题就是找最小的环了。。最小环的问题是 $O(n^2)$ 的。但是我们可以发现一个性质，如果一个路径从大于 $\sqrt{\max A}$ 的点出发，就必然会前往一个小于 $\sqrt {\max A}$ 的点。所以每个路径必然包含至少一个小于 $\sqrt{\max A}$ 的点。所以我们从所有小于根号的点开始跑 bfs 就好了。

这东西开始写 dfs ，，后来发现 dfs 找最小环是错的！因为 dfs 时当前距离不是最小距离！

int n , m , k;
int A[MAXN];
int occ[MAXN];
vector<int> G[MAXN];
int dis[MAXN];
int s , re = 0x3f3f3f3f;
queue<int> Q;
int par[MAXN];
int bfs( int S ) {
    memset( dis , 0x3f , sizeof dis );
    re = 0x3f3f3f3f , Q.push( S );
    dis[S] = 0;
    while( !Q.empty() ) {
        int u = Q.front(); Q.pop();
        for( int v : G[u] ) {
            if( dis[v] == 0x3f3f3f3f ) par[v] = u , dis[v] = dis[u] + 1 , Q.push( v );
            else if( par[u] != v ) re = min( re , dis[v] + dis[u] + 1 );
        }
    }
    return re;
}
void solve( ) {
    vector<int> a;
    cin >> n;
    int ans = 0x3f3f3f3f;
    set<int> S;
    rep( i , 1 , n ) {
        scanf("%d",A + i);
        for( int t = 2 ; t * t <= A[i] ; ++ t ) if( A[i] % t == 0 ) {
            int r = A[i] / t;
            if( r % t == 0 ) {
                while( A[i] % t == 0 && ( A[i] / t ) % t == 0 ) A[i] /= t , A[i] /= t;
            }
            else if( fabs( sqrt( 1.0 * r ) - floor( sqrt( 1.0 * r ) ) ) <= 1e-7 ) { A[i] = t; }
            break;
        }
        if( A[i] == 1 ) return void( puts("1") );
        int p = 0 , q = 0;
        for( int t = 2 ; t * t <= A[i] ; ++ t ) if( A[i] % t == 0 ) { p = t; q = A[i] / t; };
        if( p ) G[p].push_back( q ) , G[q].push_back( p );
        else G[1].push_back( A[i] ) , G[A[i]].push_back( 1 );
        if( occ[A[i]] ) ans = 2;
        occ[A[i]] = 1;
    }
    if( ans <= 2 ) return void( printf("%d\n",ans) );
    for( int i = 1 ; i <= 1000 ; ++ i ) ans = min( ans , bfs( i ) );
    if( ans == 0x3f3f3f3f ) puts("-1");
    else cout << ans << endl;
}
signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

F Ehab’s Last Theorem

为了方便一点，设 $d = \lceil \sqrt n \rceil$。。不然估计要写死。。

我们考虑把 dfs 树建出来，然后环就对应 dfs 树上的返祖边。如果我们已经找到了一个 $\ge d$ 的环，直接输出就好了。

否则，我们所有的返祖边都是 $\le d-1$ 的。所以我们可以按照深度模 $d-1$ 进行分类。画图不难发现，这样最长的边的端点的深度都不会相差到 $d-1$ 。如果深度相差 $d-1$ 就说明这里有一个长度为 $d$ 的环了。

所以，直接拿深度模 $d-1$ 分类后的每一类来看看。根据抽屉原理，这样必然有一类有大于等于 $d$ 个点。

记住输出的时候输出 exactly $d$ 。。

ll n , m;
vector<int> G[MAXN];
int vis[MAXN] , dep[MAXN] , d , fa[MAXN];
void dfs( int u ) {
    vis[u] = 1;
    for( int v : G[u] ) {
        if( vis[v] && ( dep[u] - dep[v] + 1 ) >= d ) {
            vector<int> cyc;
            int x = u;
            while( x != v ) cyc.push_back( x ) , x = fa[x];
            cyc.push_back( v );
            puts("2");
            printf("%d\n",cyc.size());
            for( int t : cyc ) printf("%d ",t);
            exit( 0 );
        } else if( !vis[v] ) {
            fa[v] = u , dep[v] = dep[u] + 1;
            dfs( v );
        }
    }
}
int cn[MAXN];
void solve( ) {
    cin >> n >> m;
    int u , v;
    rep( i , 1 , m ) {
        scanf("%d%d",&u,&v);
        G[u].pb( v ) , G[v].pb( u );
    }
    d = sqrt( n ) - 1;
    while( d * d < n ) ++ d;
    dfs( 1 );
    int t = d - 1;
    for( int i = 1 ; i <= n ; ++ i )
        cn[dep[i] % t] ++;
    int ps = max_element( cn , cn + t ) - cn;
    puts("1");
    vi ans;
    for( int i = 1 ; i <= n ; ++ i ) if( dep[i] % t == ps ) ans.pb( i );
    ans.resize( d );
    for( int x : ans ) printf("%d ",x);
}
signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}