比赛链接 / 官方题解链接
A. Johnny and Ancient Computer
Solution
转换成对大的那个数不断做除法。
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
int T;
LL a, b;
int main(){
for(read(T); T; T--){
read(a, b);
int cnt = 0;
while(a != b){
if(a > b) swap(a, b);
if(b % 8 == 0) b /= 8, cnt++;
else if(b % 4 == 0) b /= 4, cnt++;
else if(b % 2 == 0) b /= 2, cnt++;
else break;
if(b * 2 == a) b *= 2;
else if(b * 4 == a) b *= 4;
}
if(a == b) printf("%d\n", cnt);
else puts("-1");
}
return 0;
}
|
B. Johnny and His Hobbies
Solution
枚举 $k$ 验证即可。
Code
>folded1
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<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
int T, n;
set<int> s;
inline bool check(int x){
set<int> t;
for(auto k: s)
t.insert(k ^ x);
return s == t;
}
int main(){
for(read(T); T; T--){
read(n);
bool ok = false;
s.clear();
for(int i = 1; i <= n; i++){
int x; read(x);
s.insert(x);
}
for(int i = 1; i <= 1024; i++){
if(check(i)){
printf("%d\n", i);
ok = true;
break;
}
}
if(!ok) puts("-1");
}
return 0;
}
|
C. Johnny and Another Rating Drop
Solution
一位一位地考虑，第 $i$ 位是连续 $2^i$ 个 $0$，然后连续 $2^i$ 个 $1$，然后再连续 $2^i$ 个 $0$ ……如此反复。每个 $0,1$ 转换的地方对答案有贡献，所以第 $i$ 对答案的贡献就是 $\left\lceil\frac{n+1}{2^i}\right\rceil-1$.
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
int T;
LL n;
int main(){
for(read(T); T; T--){
read(n);
LL ans = 0;
for(int i = 0; i <= 60; i++){
if((1ll << i) > n) break;
ans += (n + 1) / (1ll << i) - 1;
ans += ((n + 1) % (1ll << i) != 0);
}
printf("%lld\n", ans);
}
return 0;
}
|
D. Johnny and Contribution
Solution
如果给定的图合法，那么排序后输出就行了。所以我们只需要判断给定的图是否合法，也就是是否对于每个点，所有小于这个点的值都出现在与之相邻的点中，且不存在与之相等的点。那只需要把小于这个点的值都加起来，看是否等于 $\frac{t_i\cdot(t_i-1)}{2}$.
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 500005;
int n, m;
vi edge[N];
bool b[N];
struct Node{
int t, id;
bool operator < (const Node &A) const{
return t < A.t;
}
}a[N];
int main(){
read(n, m);
for(int i = 1; i <= m; i++){
int u, v; read(u, v);
edge[u].pb(v), edge[v].pb(u);
}
for(int i = 1; i <= n; i++) read(a[i].t), a[i].id = i;
for(int i = 1; i <= n; i++){
LL sum = 0;
for(auto to: edge[i]){
if(a[to].t == a[i].t) return puts("-1"), 0;
if(a[to].t < a[i].t && !b[a[to].t]){
b[a[to].t] = true;
sum += a[to].t;
}
}
if(sum != 1ll * a[i].t * (a[i].t - 1) / 2)
return puts("-1"), 0;
for(auto to: edge[i])
if(a[to].t < a[i].t)
b[a[to].t] = false;
}
sort(a+1, a+n+1);
for(int i = 1; i <= n; i++)
printf("%d ", a[i].id);
return 0;
}
|
E. Johnny and Grandmaster
Solution
从大到小对 $k$ 排序，显然最优策略是：把最大的放进 $A$ 集合，然后不断放 $B$ 集合直到其和与 $A$ 集合相等，然后重复这个过程。由于取模的存在，我们存两集合的差值——放进 $A$ 集合就是加，放进 $B$ 集合就是减，同时为了避免取模后变成 $0$，再选取一个模数，类似双哈希。
P.S. 像 $998244353$ 这个常见的模数被卡了……所以还是用个不常见的质数好了。
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 1000005;
const LL mod1 = 1e9 + 7;
const LL mod2 = 10000019;
int T, n;
LL p, k[N];
LL fpow(LL bs, LL idx, LL MOD){
bs %= MOD;
LL res = 1;
while(idx){
if(idx & 1) (res *= bs) %= MOD;
(bs *= bs) %= MOD;
idx >>= 1;
}
return res;
}
int main(){
for(LL i = 2; i * i <= mod2; i++)
if(mod2 % i == 0)
printf("%lld\n", i);
for(read(T); T; T--){
read(n, p);
for(int i = 1; i <= n; i++) read(k[i]);
sort(k+1, k+n+1), reverse(k+1, k+n+1);
LL ans = 0, diff = 0;
for(int i = 1; i <= n; i++){
if(ans == 0 && diff == 0){
ans += fpow(p, k[i], mod1);
diff += fpow(p, k[i], mod2);
}
else{
(((ans -= fpow(p, k[i], mod1)) %= mod1) += mod1) %= mod1;
(((diff -= fpow(p, k[i], mod2)) %= mod2) += mod2) %= mod2;
}
}
printf("%lld\n", ans);
}
return 0;
}
|
F. Johnny and Megan’s Necklace
Solution
很有趣的一道题！从大到小枚举答案 $k$，那么两个数字能够被“粘合”当且仅当它们的末 $k$ 位相同，所以对于端点值为 $a,b$ 的边，我们在 $a\text{ AND }(2^k-1)$ 和 $b\text{ AND }(2^k-1)$ 之间连一条边，那么从一条边经过一个点走到另一条边，就相当于粘合了两段项链，所以问题转化成了找一条欧拉回路！
找欧拉回路的算法叫做 $Hierholzer$ 算法，基本过程就是 $dfs$，然后用一个栈把欧拉路/回路记录下来。
Code
>folded1
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<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = (1 << 20) + 5;
int n;
struct Node{
int a, b;
}a[N];
vector<pii> edge[N];
bool vis[N];
void dfs(int x){
vis[x] = true;
for(auto &to: edge[x]) if(!vis[to.first]) dfs(to.first);
}
stack<int> sta;
void dfs(int x, int pre){
while(!edge[x].empty()){
pii to = edge[x].back(); edge[x].pop_back();
if(vis[(to.second+1)/2]) continue;
vis[(to.second+1)/2] = true;
dfs(to.first, to.second);
}
if(pre != -1){
sta.push(pre);
if(pre & 1) sta.push(pre + 1);
else sta.push(pre - 1);
}
}
inline bool check(int B){
for(int i = 0; i <= B; i++) edge[i].clear(), vis[i] = false;
for(int i = 1; i <= n; i++){
edge[a[i].a & B].pb(mp(a[i].b & B, 2 * i));
edge[a[i].b & B].pb(mp(a[i].a & B, 2 * i - 1));
}
for(int i = 1; i <= n; i++){
if(edge[a[i].a & B].size() & 1) return false;
if(edge[a[i].b & B].size() & 1) return false;
}
int comps = 0;
for(int i = 0; i <= B; i++)
if(!vis[i] && !edge[i].empty())
dfs(i), comps++;
if(comps != 1) return false;
for(int i = 1; i <= n; i++) vis[i] = false;
for(int i = 0; i <= B; i++)
if(!edge[i].empty())
dfs(i, -1);
return true;
}
int main(){
read(n);
for(int i = 1; i <= n; i++) read(a[i].a, a[i].b);
for(int b = 20; b >= 0; b--){
if(check((1<<b)-1)){
printf("%d\n", b);
break;
}
}
while(!sta.empty()){
printf("%d ", sta.top());
sta.pop();
}
return 0;
}
|