Codeforces Round #647 (Div. 2)

已给出A,B,C,D,E题解,F待补。（持续补题...）

------------------------------------------------------------------------------------------------------------------

A. Johnny and Ancient Computer

题意：给你两个数a和b，要求将a通过数次合法操作转换为b，输出最小的操作数，若无法转换为b，则输出-1。合法操作有：乘2、4、8，除以2、4、8。（除以操作只在能被整除的情况下执行）

思路：转换是双向的，所以我们认为问题是怎么由较大数转换为较小数。认为a是较大值，b是较小值，我们可以将问题转化为处理a / b的值。

b⋅t1⋅t2…tn=a

t1⋅t2…tn=a/b

　　所以，如果特判a % b != 0必定无法转换，输出-1。然后令k = a / b，用k去试探是否可以被2，4，8整除。由于需要输出最小操作数，所以能被较大数整除就除以较大数。遇到两种情况退出循环：

　　　　1、 k == 1，这时说明已经完成了操作，输出操作数即可。

　　　　2、 k != 1 && k % 2 == 1，这说明无法操作，输出-1。

代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1, M = 1;
 4 typedef long long ll;
 5 typedef unsigned long long ull;
 6 typedef pair<int, int> PII;
 7 #define rep(i, x, y) for(i=x;i<=y;i++)
 8 #define ref(i, x, y) for(i=x;i>=y;i--)
 9 #define MEM(a, x) memset(a, x, sizeof(a))
10 #define Sca(x) scanf("%d", &x)
11 #define Scl(x) scanf("%lld", &x)
12 #define Scf(x) scanf("%f", &x)
13 #define Sclf(x) scanf("%lf", &x)
14 #define pb push_back
15 #define mp make_pair
16 #define fi first
17 #define se second
18 #define lb lower_bound
19 #define ub upper_bound
20 #define endl '
'
21 
22 int T, n;
23 bool vis[N];
24 
25 int main()
26 {
27     ios::sync_with_stdio(false);
28     ull a, b;
29     cin >> T;
30     while (T--) {
31         cin >> a >> b;
32         if (a < b) swap(a, b);
33         if (a % b) {
34             cout << - 1 << endl;
35             continue;
36         }
37         ll k = a / b;
38         ll cnt = 0;
39         while (k) {
40             if (k % 8 == 0) {
41                 k /= 8;
42                 cnt++;
43             }else if (k % 4 == 0) {
44                 k /= 4;
45                 cnt++;
46             }else if (k % 2 == 0) {
47                 k /= 2;
48                 cnt++;
49             }else if (k == 1) {
50                 break;
51             }else {
52                 cnt = -1;
53                 break;
54             }
55         }
56         cout << cnt << endl;
57     }
58     return 0;
59 }

View Code

总结：比赛时写了ios::sync_with_stdio(false);但是还是用了puts导致wa了两次，拖了些时间。下次注意不能再犯傻了。

B. Johnny and His Hobbies

题意：给出一个集合，要求找到一个值k，使得集合中每一个值ai 变为 ai ^ k，仍使新集合等于原集合。

思路：因为所有n的总和不超过1024，所以我们可以从a[1] ^ a[2...n]枚举k的所有值。确定k值后在[2, n]里对每一个a[i]确定它对应的a[i] ^ k，二分查找是否存在这个值。答案取最小值。时间复杂度大概是O(n2logn)。（应该没算错吧）

代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 2048, M = 1;
 4 typedef long long ll;
 5 typedef unsigned long long ull;
 6 typedef pair<int, int> PII;
 7 #define rep(i, x, y) for(i=x;i<=y;i++)
 8 #define ref(i, x, y) for(i=x;i>=y;i--)
 9 #define MEM(a, x) memset(a, x, sizeof(a))
10 #define Sca(x) scanf("%d", &x)
11 #define Scl(x) scanf("%lld", &x)
12 #define Scf(x) scanf("%f", &x)
13 #define Sclf(x) scanf("%lf", &x)
14 #define pb push_back
15 #define mp make_pair
16 #define fi first
17 #define se second
18 #define lb lower_bound
19 #define ub upper_bound
20 #define endl '
'
21 
22 int T, n;
23 ll a[N];
24 bool vis[N];
25 
26 int bsearch(int l, int r, ll x)
27 {
28     while (l < r) {
29         int mid = l + r >> 1;
30         if (a[mid] >= x) r = mid;
31         else l = mid + 1;
32     }
33     return l;
34 }
35 
36 int main()
37 {
38     ios::sync_with_stdio(false);
39     cin >> T;
40     while (T--) {
41         cin >> n;
42         for (int i = 1; i <= n; i++) 
43             cin >> a[i];
44         if (n % 2) {
45             cout << -1 << endl;
46             continue;
47         }
48         int cnt = 0;
49         ll res = 0x3f3f3f3f;
50         sort(a+1, a+1+n);
51         for (int i = 2; i <= n; i++) {
52             ll ans = a[1] ^ a[i];
53             cnt = 2;
54             for (int j = 2; j <= n; j++) {
55                 if (j == i) continue;
56                 ll aim = ans ^ a[j];
57                 int pos = bsearch(1, n, aim);
58                 // cout << "j = " << j << "  pos = " << pos << endl;
59                 if (a[pos] == aim) {
60                     cnt ++;
61                 }else {
62                     break;
63                 }
64             }
65             if (cnt == n) {
66                 res = min(res, ans);
67             }
68         }
69         if (res == 0x3f3f3f3f) res = -1;
70         cout << res << endl;
71     }
72     return 0;
73 }

View Code

总结：拿到题目时就想过枚举k了，不过没敢写，硬是找规律找了好久。。。

C. Johnny and Another Rating Drop

题意：定义了一个不公平值，意味两个数的二进制表示中有多少位不相同。给出一个n，求出0, 1, ... , n中每两个连续的数的不公平值的和。

思路：比赛时我写了前几个值的和，找规律发现答案是2 * n - t，其中t为n和0的不公平值。

　　以下为正解：容易发现第一位，逢1改变一次，所以第一位的总贡献为n；第二位，逢2改变一次，所以第二位总贡献为n/2；第三位，逢4改变一次，第三位总贡献则为n/4......

代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1, M = 1;
 4 typedef long long ll;
 5 typedef unsigned long long ull;
 6 typedef pair<int, int> PII;
 7 #define rep(i, x, y) for(i=x;i<=y;i++)
 8 #define ref(i, x, y) for(i=x;i>=y;i--)
 9 #define MEM(a, x) memset(a, x, sizeof(a))
10 #define Sca(x) scanf("%d", &x)
11 #define Scl(x) scanf("%lld", &x)
12 #define Scf(x) scanf("%f", &x)
13 #define Sclf(x) scanf("%lf", &x)
14 #define pb push_back
15 #define mp make_pair
16 #define fi first
17 #define se second
18 #define lb lower_bound
19 #define ub upper_bound
20 #define endl '
'
21 
22 ull T, n;
23 bool vis[N];
24 
25 void solve1()            //暂未证明
26 {
27     cin >> n;
28     ll temp = n;
29     ll cnt = 0;
30     while (temp) {
31         if (temp & 1) cnt++;
32         temp >>= 1;
33     }
34     cout << 2ll * n - cnt << endl;
35 }
36 
37 void solve2()
38 {
39     cin >> n;
40     ll temp = n;
41     ll ans = 0;
42     ll now = 1;
43     while (temp) {
44         ans += n / now;
45         now *= 2;
46         temp >>= 1;
47     }
48     cout << ans << endl;
49 }
50 
51 int main()
52 {
53     ios::sync_with_stdio(false);
54     cin >> T;
55     while (T--) {
56         // solve1();
57 
58         solve2();
59     }
60     return 0;
61 }

View Code

D. Johnny and Contribution

题意：有n个点，m条边的无向图。每一个点有一个期望值，每次给点赋值的时候，必须赋值为所有与它直接连接的点中的mex值（即未出现过的最小自然数），求一个赋值顺序使得每个点的值是它的期望值。

思路：模拟，从期望点权最小的点开始赋值。维护一个mx数组，使得mx数组里的值是当前点所连的点里的最大值。（其实就是暴力）

代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 5e5+5, M = 1;
 4 typedef long long ll;
 5 typedef unsigned long long ull;
 6 typedef pair<int, int> PII;
 7 #define rep(i, x, y) for(i=x;i<=y;i++)
 8 #define ref(i, x, y) for(i=x;i>=y;i--)
 9 #define MEM(a, x) memset(a, x, sizeof(a))
10 #define Sca(x) scanf("%d", &x)
11 #define Scl(x) scanf("%lld", &x)
12 #define Scf(x) scanf("%f", &x)
13 #define Sclf(x) scanf("%lf", &x)
14 #define pb push_back
15 #define mp make_pair
16 #define fi first
17 #define se second
18 #define lb lower_bound
19 #define ub upper_bound
20 #define endl '
'
21 
22 int T, n, m;
23 bool vis[N];
24 struct node{
25     int id, val;
26 }a[N];
27 vector<int> v[N];
28 int mx[N], ans[N];
29 
30 bool cmp(node a, node b)
31 {
32     if (a.val == b.val) {
33         return a.id < b.id;
34     }else{
35         return a.val < b.val;
36     }
37 }
38 
39 int main()
40 {
41     //ios::sync_with_stdio(false);
42     cin >> n >> m;
43     for (int i = 1; i <= m; i++) {
44         int l, r;
45         Sca(l); Sca(r);
46         v[l].pb(r); v[r].pb(l);
47     }
48     for (int i = 1; i <= n; i++) {
49         int val;
50         Sca(a[i].val);
51         a[i].id = i;
52     }
53     sort(a+1, a+1+n, cmp);
54     for (int i = 1; i <= n; i++) {
55         int x = a[i].id, val = a[i].val;
56         if (mx[x] != val - 1) {
57             puts("-1");
58             return 0;
59         }
60         ans[i] = x;
61         for (auto i : v[x]) {
62             if (mx[i] == val - 1) {
63                 mx[i] = val;
64             }
65         }
66     }
67     for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
68     return 0;
69 }

View Code

总结：比赛时看了半天硬是没有看懂题意，英语果然还是很重要。

E. Johnny and Grandmaster

题意：给出一个序列k，要求将k分为两个集合，求得

思路：有一个前置知识：

　　 所以我们就可以根据贪心策略，先将k降序排序。定义ans为最终答案，每当ans = 0时，让ans加上p的k[i]次；ans != 0时，ans减去p的k[i]次。

　　 这样大值被消化了，最后得到的即为最小值。

　　值得注意的是，过程中处处用到对1e9+7取余，所以ans = 0时并不一定真的是ans = 0，而是ans是1e9+7的倍数。所以我们每次多运算一个值，让它对其他数取余，这样当两个值都等于0时，就是ans真正为0。

代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e6+5, M = 1, MOD = 1e9+7, _MOD = 1e9+5;
 4 typedef long long ll;
 5 typedef unsigned long long ull;
 6 typedef pair<int, int> PII;
 7 #define rep(i, x, y) for(i=x;i<=y;i++)
 8 #define ref(i, x, y) for(i=x;i>=y;i--)
 9 #define MEM(a, x) memset(a, x, sizeof(a))
10 #define Sca(x) scanf("%d", &x)
11 #define Scl(x) scanf("%lld", &x)
12 #define Scf(x) scanf("%f", &x)
13 #define Sclf(x) scanf("%lf", &x)
14 #define pb push_back
15 #define mp make_pair
16 #define fi first
17 #define se second
18 #define lb lower_bound
19 #define ub upper_bound
20 #define endl '
'
21 
22 int T, n, p, k[N];
23 bool vis[N];
24 bool cmp(int a, int b)
25 {return a > b;}
26 
27 ll QuickPow(ll a, ll b, ll mod)
28 {
29     ll ans = 1;
30     while (b) {
31         if (b & 1) ans = (ans * a) % mod;
32         a = (a * a) % mod;
33         b >>= 1;
34     }
35     return ans % mod;
36 }
37 
38 void solve()
39 {
40     scanf("%d%d", &n, &p);
41     for (int i = 1; i <= n; i++) Sca(k[i]);
42     if (p == 1) {
43         cout << n % 2 << endl;
44         return;
45     }
46     sort(k + 1, k + 1 + n, cmp);
47     ll res = 0, ans = 0;
48     for (int i = 1; i <= n; i++) {
49         if (!ans && !res) {
50             ans += QuickPow(p, k[i], MOD);
51             res += QuickPow(p, k[i], _MOD);
52         }else{
53             ans = ((ans - QuickPow(p, k[i], MOD)) + MOD) % MOD;
54             res = ((res - QuickPow(p, k[i], _MOD)) + _MOD) % _MOD;
55         }
56     }
57     cout << ans << endl;
58 }
59 
60 int main()
61 {
62     // ios::sync_with_stdio(false);
63     cin.tie(0); cout.tie(0);
64     cin >> T;
65     while (T--) {
66         solve();
67     }
68     return 0;
69 }

View Code

F. Johnny and Megan's Necklace