CF Round 628

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

CF1325 A ~ F

CF Round 628

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

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

A EhAb AnD gCd

输出 1,n11 , 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

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

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 xor b+2(a and b)a+b = a\ \text{xor}\ b + 2(a\ \text{and}\ b) 。因为 xor 实际上是不进位加法,可以通过 and 来进位。

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

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

然后什么时候可以用两个位置构造出答案?显然我们有 vu2\frac{v-u}{2} 就必须是 a and ba\ \text{and}\ b ,而 uua xor ba\ \text{xor}\ b ,如果它们之间有交,也就是说某些位置既都是 1 ,又两个位置不同,这显然矛盾了啊。所以如果没有交,可以构造出 u or vu2,vu2u\ \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 ,这就告诉我们它不能有三个素因子。如果它有两个素因子,也只能是 pqpqpq2pq^2 这两种形式。但是由于最后要凑出平方数,所以显然 pq2pq^2 可以看成是 pp 。如果是质数的次幂,我们也可以直接把次幂 模 2 来做就好了。

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

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

然后现在问题就是找最小的环了。。最小环的问题是 O(n2)O(n^2) 的。但是我们可以发现一个性质,如果一个路径从大于 maxA\sqrt{\max A} 的点出发,就必然会前往一个小于 maxA\sqrt {\max A} 的点。所以每个路径必然包含至少一个小于 maxA\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=nd = \lceil \sqrt n \rceil。。不然估计要写死。。

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

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

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

记住输出的时候输出 exactly dd 。。

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();
}
\