CF Round 628

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

CF1325 A ~ F

CF Round 628

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

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

A EhAb AnD gCd

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

1
2
3
4
5
6
7
8
9
10
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$ 次后显然每个不同的数字都能做出贡献,答案就是不同数字个数

1
2
3
4
5
6
7
8
9
10
11
12
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 的边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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}$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 时当前距离不是最小距离!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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$ 。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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();
}
文章作者: yijan
文章链接: https://yijan.co/cf-round-628/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog