= Vain学习(C/C++ acm算法 python Linux Golang)的个人网站 =

Home

Codeforces Round #628 (Div. 2)

Posted on

$A - Eh$ $Ab$ $An$ $D$ $gCd$

思路：
显然$1$与任何数的$gcd$为$1$,与任何数的$lcm$都是两数中最大的，呢么直接构造$1,x-1$便是答案。

参考代码：

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
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <math.h>
using namespace std;
//typedef long long ll;
#define int long long
const int N = 1e3 + 5;
const int maxn = 2e6 + 20;
const int mod = 1e9 + 7;
int inv[maxn], dp[maxn], vis[maxn], dis[maxn];
int fac[maxn];
vector<int> vec;
typedef pair<int, int> p;
int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
void init()
{
    fac[0] = 1;
    for (int i = 1; i <= 20; i++)
        fac[i] = fac[i - 1] * i;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q, u, v, w, k, t;
    cin>>t;
    while(t--)
    {
        int a,b;
        cin>>a;
        cout<<1ll<<' '<<a-1ll<<endl;
    }
}

$B-CopyCopyCopyCopyCopy$

思路：
最大长度就是序列中有多少不同的数。

参考代码：

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
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <math.h>
using namespace std;
//typedef long long ll;
#define int long long
const int N = 1e3 + 5;
const int maxn = 2e6 + 20;
const int mod = 1e9 + 7;
int inv[maxn], dp[maxn], vis[maxn], dis[maxn];
int fac[maxn];
vector<int> vec;
typedef pair<int, int> p;
int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
void init()
{
    fac[0] = 1;
    for (int i = 1; i <= 20; i++)
        fac[i] = fac[i - 1] * i;
}
map<int, int> mp;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q, u, v, w, k, t;
    cin >> t;
    while (t--)
    {
        mp.clear();
        int n, ans = 0;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> v;
            if (!mp[v])
                ans++, mp[v] = 1;
        }
        cout << ans << endl;
    }
}

$C - Ehab$ $and$ $Path-etic$ $MEXs$

题意：
让$mexs(u,v)$答案尽可能的小，我们如何构造树？

  • $mexs(u,v)$第一个不存在的非负整数
    思路：
    说实话这题很简单，就是感觉题意太难搞了，其实对于树，我们想让任意一条链上的值尽可能的小，若树不会退化成链，呢么只要使$0，1，2$，不在一条链上就行,也就是说在叶子节点上的边即可，而叶子节点有一个特点就是出度为$0$，或者度为$1$,我们只要找到3个叶子节点，将3个叶子节点的值赋值为$0，1，2$，其他随意构造就好了，这时这颗树上$mexs(u,v)$最大为$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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <math.h>
using namespace std;
//typedef long long ll;
#define int long long
const int N = 1e3 + 5;
const int maxn = 2e6 + 20;
const int mod = 1e9 + 7;
int inv[maxn], dp[maxn], vis[maxn], dis[maxn];
int fac[maxn];
vector<int> vec;
typedef pair<int, int> p;
int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
void init()
{
    fac[0] = 1;
    for (int i = 1; i <= 20; i++)
        fac[i] = fac[i - 1] * i;
}
map<int, int> mp;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q, u, v, w, k, t;
    // cin >> t;
    // while (t--)
    // {
    int n;
    q = 0;
    cin >> n;

    vector<int> a(n + 1, 0);
    vector<int> pb(n + 1, 0);
    vector<int> ans(n + 1, 0);
    for (int i = 0; i <= n - 2; i++)
        cin >> u >> v, a[u]++, a[v]++, pb[v] = pb[u]=i;
    if (n == 2)
    {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 1; i <= n; i++)
    {

        if (a[i] == 1)
            ans[pb[i]] = ++q;
        if (q == 3)
            break;
    }
    for (int i = 0; i < n - 1; i++)
    {
        if (ans[i])
            cout << ans[i] - 1 << endl;
        else
            cout << (++q - 1) << endl;
    }

    //}
}

$D - Ehab$ $the$ $Xorcist$

思路：
分几种情况：
1.首先当 $u>v$，显然是没有答案的，因为就算可以异或出$u$，异或出$u$的两个值的和肯定大于$v$。
2.当 $(v-u)$ %$2$$==0$，此时我们可以构造长度$3$的答案，答案为 $u$ ^ $x$ ^ $x$，
$x=(v-u)/2$。
3：这里我们需要讨论构造长度为$2$的情况，不分奇偶，为什么把这个放到第三条说，因为他是以第二条为条件引入的。

如果 $x$^$y==u$，且$x+y==v$且$(x>y)$，显然我们可以将$x$化成一个二进制串，将$y$从$x$
上给异或掉，呢么我们可以构造 $y=(v-u)/2,x=(v+u)/2$，如果这个不满足，则不满足长度为$2$的情况。
4：判断$u==v$，若相等且 $u!=0$则输出$1$，$u$，反则输出$0$。

参考代码：

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <math.h>
using namespace std;
//typedef long long ll;
#define int long long
const int N = 1e3 + 5;
const int maxn = 2e6 + 20;
const int mod = 1e9 + 7;
int inv[maxn], dp[maxn], vis[maxn], dis[maxn];
int fac[maxn];
vector<int> vec;
typedef pair<int, int> p;
int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
int ksm(int a, int b)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
            ans *= a;
        a *= a;
        b >>= 1;
    }
    return ans;
}
map<int, int> mp;
int a[66], b[66];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q, u, v, w, k, t;
    // cin >> t;
    // while (t--)
    // {
    cin >> u >> v;
    if (u > v)
    {
        cout << -1 << endl;
        return 0;
    }
    if (u == v)
    {
        if (u != 0)
        {
            cout << 1 << endl;
            cout << u << endl;
        }
        else
            cout << 0 << endl;
        return 0;
    }
    int x = (v - u) / 2, y = (v + u) / 2;
    if ((x ^ y) == u && (x + y == v))
    {
        cout << 2 << endl;
        cout << x << ' ' << y << endl;
    }
    else
    {
        if ((v - u) % 2 == 0)
        {
            cout << 3 << endl;
            cout << u << ' ' << (v - u) / 2 << ' ' << (v - u) / 2 << endl;
        }
        else
            cout << -1 << endl;
    }
    //}
}