A.Johnny and Ancient Computer

题意：

给出和，每次只能进行
选一个操作，求变成的最小操作次数。

题解：

因为乘除等价，直接贪心判断即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
const int INF = 0x3f3f3f3f;
void solve()
{
    ll x, y;
    scanf("%lld%lld", &x, &y);
    if(x > y) swap(x, y);
    int ans = 0;
    while(x<y)
    {
        if(8 * x <= y)
            x *= 8, ans++;
        else if(4 * x <= y)
            x *= 4, ans++;
        else if(2 * x <= y)
            x *= 2, ans++;
        else break;
    }
    printf("%d\n",x == y ? ans : -1);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
    return 0;
}

B.Johnny and His Hobbies

题意：

问最小的数字使得初始集合的每个数都异或后集合不变。

题解：

因为,因此,所以只需要贪心从小到大遍历中满足条件的值输出最小的即可，否则输出

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int n;
    scanf("%d", &n);
    set<int> s;
    for (int i = 0, x; i < n; i++)
        scanf("%d", &x), s.insert(x);
    for (int i = 1; i <= 1024; i++)
    {
        set<int> t;
        for (auto j : s)
            t.insert(j ^ i);
        if (s == t)
        {
            printf("%d\n", i);
            return;
        }
    }
    puts("-1");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Johnny and Another Rating Drop

题意：

给定一个数，定义两个数的差值是二进制下不同的位数。求到相邻数字的差值之和。

题解：

观察样例可以发现答案就是每位上的个数之和
图片说明 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    ll n;
    scanf("%lld", &n);
    ll ans = 0;
    while (n)
    {
        ans += n;
        n /= 2;
    }
    printf("%lld\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Johnny and Contribution

题意：

给定一张图，每一个节点都是一篇博客，每个点的主题数是除周围博客主题数之外数的最小值。询问是否存在一种符合期望的主题数的访问顺序。

题解：

根据每个顶点的属性从小到大进行排序。然后依次安排，对每个节点判断一下相邻结点的期望颜色是否也为与颜色相同，如果是,则的期望颜色加一.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 5;
int num[maxn];
vector<int> G[maxn], col[maxn], ans;
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1, x; i <= n; i++)
    {
        scanf("%d", &x);
        col[x].push_back(i);
        num[i] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        for (auto u : col[i])
        {
            if (num[u] != i)
            {
                puts("-1");
                return 0;
            }
            for (auto v : G[u])
                if (num[v] == i)
                    num[v]++;
            ans.push_back(u);
        }
    }
    for (auto i : ans)
        printf("%d ", i);
    puts("");
    return 0;
}

E.Johnny and Grandmaster

题意：

给定个数和底数，可以获得个贡献 ，把这个贡献分成两份，询问两份的最小差值的绝对值是多少？

题解：

把这个数从大到小进行排序，对于每个数，如果把这个数分配给一个集合，那么另外一个集合就要想办法凑出这个数。此时有两种情况：

  1. 剩下所有数拿完，还不能大于第一堆，那答案就是他们的差值。
  2. 剩下所有数的和大于第一堆那个数，如果是这个情况那么我们必定能拿到一些数，使得他们的和要等于第一堆那个数，然后两者抵消，再判断剩下那些数就行。

要注意的是差值为的时候 不能光用来判断,得再搞一个模数来保证差值为,因为当差值为的倍数时，结果也同样为,但实际不为

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
const ll mod1 = 1e9 + 7;
const ll mod2 = 983231753;
ll k[maxn];
ll ksm(ll a, ll b, ll mod)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
void solve()
{
    ll n, p;
    scanf("%lld%lld", &n, &p);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &k[i]);
    ll ans1 = 0, ans2 = 0;
    sort(k + 1, k + n + 1, greater<ll>());
    for (ll i = 1; i <= n; i++)
    {
        ll t1 = ksm(p, k[i], mod1);
        ll t2 = ksm(p, k[i], mod2);
        if (ans1 == 0 && ans2 == 0)
            ans1 = t1, ans2 = t2;
        else
            ans1 = (ans1 - t1 + mod1) % mod1, ans2 = (ans2 - t2 + mod2) % mod2;
    }
    printf("%lld\n", ans1);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}