A 简单数学

题意：给一个正整数 $n$ ，问n是否存在 $x, x>1$ ，使得 $x$ 能整除 $n$ ，并且 $x$ 是奇数？
签到题，多琢磨一下就能知道做法：判定 $n$ 是否是2的幂次，不是则有解
这里是正经的推导：
- 设 $\alpha_i$ 为正整数， $p_i$ 为质数，则由唯一分解定理： $n = \prod_{i = 1} ^ k p_i^{\alpha_i}$
- 我们知道，除2之外，所有的质数都是奇数。也就是说，要想在 $n$ 中找到奇数因子，只需要有除2之外的质数即可
- 所以直接判定 $n$ 是否为2的幂次即可
- 判定2的幂次可使用 $n \& (n-1)$ 判定，若结果为0，则为2的幂次

#include <bits/stdc++.h>
using namespace std;
signed main() {
    long long n;
    while(cin >> n) {
        puts(n & (n-1) ? "YES" : "NO");
    }
    return 0;
}

B 硬币游戏

题意：进行 $n-1$ 次比赛，每次比赛选取2人，硬币多的获胜，相同则随机。获胜者获得败者所有硬币，求最后可能的冠军编号
首先，这 $n$ 个人当中硬币数最多的必可以为冠军，这是显而易见的。然后我们考虑次大的，如果它和比它硬币数少的人的硬币总和，比最大的大，那么这个人也可以为冠军，同理类推
所以我们需要对整个序列排序并记下该对象的编号，然后对硬币求前缀和，然后推导能成为冠军的即可。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = 1e6 + 7;
int n, tot;
ll prefix[N];
pair<ll, ll> arr[N];
ll ans[N];
signed main() {
    while(~scanf("%d", &n)) {
        tot = 0;

        for(int i = 1; i <= n; ++i) {
            scanf("%lld", &arr[i].first);
            arr[i].second = i;//fi为硬币数，se为编号
        }sort(arr + 1, arr + 1 + n);
        for(int i = 1; i <= n; ++i) {
            prefix[i] = prefix[i-1] + arr[i].first;
        }ans[++tot] = arr[n].second;//最大的一定可以为冠军
        for(int i = n; i >= 2; --i) {
            if(prefix[i-1] >= arr[i].first) //前i-1个的和不小于i的，可以赢
                ans[++tot] = arr[i-1].second;
        }
        sort(ans + 1, ans + 1 + tot);//序号从小到大输出
        printf("%d\n", tot);
        for(int i = 1; i <= tot; ++i) printf("%lld%c", ans[i], i == tot ? '\n' : ' ');
    }
    return 0;
}

C 包裹

题意：给定 $n$ 个包裹的重量，顺序装载，能在 $D$ 天能运完的最小装载量为多少？
明显的二分板子题，装载量满足单调性（小的能装，大的也能），而且给定装载量还容易验证是否可行

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = 1e5 + 7;
ll n, d;
int arr[N];

bool check(int tmp) {
    int index = 1, cnt = 0;//标记当前选取位置、天数
    while(index <= n) {
        ++cnt;
        int tot = 0;
        while(tot + arr[index] <= tmp) {
            tot += arr[index];
            ++index;
            if(index > n) break;
        }
        if(cnt > d) return false;
    }return true;
}

signed main() {
    while(~scanf("%lld%lld", &n, &d)) {
        for(int i = 1; i <= n; ++i) scanf("%d", &arr[i]);
        ll ans = 1, l = 1, r = 0x3f3f3f3f;//[1,INF]中
        while(l <= r) {
            int mid = l + r >> 1;
            if(check(mid)) r = mid - 1, ans = mid;
            else l = mid + 1;
        }printf("%lld\n", ans);
    }
    return 0;
}

D 飞神Ⅱ

题意：给定 $n$ 和7个档位，每个档位第一次有额外奖励，求可获取的最大奖励
首先要注意到每个档位给的基础奖励都是 $1:10$ 的，所以问题就被大大简化了，只需要注意每个档位的第一次额外奖励是否能拿到即可
判定7个档位中选取若干档位，使得获得的额外奖励最多，可以01背包，也可以二进制枚举，这里就直接枚举了

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 7;
int t, n;
int a[] = {0, 8, 18, 28, 58, 128, 198, 388};//额外奖励
int b[] = {0, 1, 6, 28, 88, 198, 328, 648};//所需代价
signed main() {
    cin >> t;
    while(t--) {
        cin >> n;
        int ans = 0;
        for(int i = 0; i < (1 << 7); ++i) {//2进制枚举，由高位到低位对应7至1档
            int tmp = i;
            int cost = 0, value = 0;
            for(int j = 1; j <= 7; ++j) {
                if(tmp & 1) {
                    cost += b[j];
                    value += a[j];
                }tmp >>= 1;
            }if(cost <= n) ans = max(ans, value + 10 * n);//取最大值
        }cout << ans << endl;
    }
    return 0;
}

F 简单分解

题意：给定 $n$ ，求由 $n = \sum_{i=1} ^k a_i$ ，并且其中 $a_i \ne a_j$ 其中 $1\le i, j\le k, i\ne j$ 确定的 $(\prod_{i = 1}^ka_i)_{max}$
首先能够比较快想到的是将 $n$ 从 $2$ 开始拆，然后继续拆 $3,4\dots$ ，我们设拆完还剩余的量为 $x$ ，能拆到的最后一个数为 $k$
- $x = 0$ ，皆大欢喜，结果就是从 $2$ 乘到 $k$ ，期间取模
- ，我们就要考虑剩下的放哪些数上更好了，并且还要使得不重复
  - 我们先考虑这个数仅有两项组成： $(k-1)k$
  - 首先我们比较容易想到的是将 $x$ 直接放到 $k$ 上，很容易就能使得 $a_i$ 不重复。此时结果为 $(k-1)(k+x)$
  - 然后我们再考虑将 $x$ 拆成两部分 $i,j$ ， $i+j = x$ ，分别放到两项中，此时结果为 $(k-1+i)(k+j)$
  - 展开一下，我们就要比较 $k^2+kx-(k+x)$ 和 $k^2+(i+j)k-(k+j-ij)$ 的大小，因为 $i+j = k$ ，所以我们只需要比较常数项的大小即可，也就是： $k + x$ 和 $k +j -ij$ ，显然，前者比后者更大。又因为常数项前的负号，可知：将 $k$ 拆开放更能得到较大的数
  - 所以得到第一个结论：拆开放比放一起更好。但是我们还需要去找拆开放多少更好，这里可以直接猜每项加 $1$ ，猜不到没关系，我们去打表看
  - 我们取 $n = 2 + 3 + 4 + 5 + k$ ， $k \le 5，14\le n\le19$ ，一共只需要四项。打表代码如下：

#include <bits/stdc++.h>
using namespace std;
signed main() {
    for(int n = 14; n <= 19; ++n) {
        int ans = 0, ta,tb,tc,td;//记录结果，中间项
        for(int a = 2; a <= n; ++a) {
            for(int b = 2; b <= n - a; ++b) {
                if(a == b) continue;//去重
                for(int c = 2; c <= n - a - b; ++c) {
                    if(a == c || b == c) continue;
                    for(int d = 2; d <= n - a - b - c; ++d) {
                        if(a == d || b == d || c == d) continue;
                        if(a * b * c * d > ans) {
                            ans = a * b * c * d;
                            ta = a, tb = b, tc = c, td = d;
                        }
                    }
                }
            }
        }cout << ans << ' ' << ta << ' ' << tb << ' ' << tc << ' ' << td << endl;
    }
    return 0;
}
//结果为：
// 120 2 3 4 5
// 144 2 3 4 6
// 180 2 3 5 6
// 240 2 4 5 6
// 360 3 4 5 6
// 420 3 4 5 7

很明显，从最后一个数开始加1，并且可以循环。那么结果就出来了：从 $2$ 开始拆自然数，然后将余项分别加入每一项中。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e3 + 7, mod = 1e9 + 7;
int n, tot = 0;
int arr[N];//arr[i] = i + 1
signed main() {
    while(~scanf("%d", &n)) {
        if(n <= 4) printf("%d\n", n);
        else {
            tot = 0;
            ll tmp = n, ans = 1;
            int goal = 2;
            while(n - goal >= 0) {
                arr[++tot] = goal;
                n -= goal;
                ++goal;
            }//拆自然数，存入arr中
            for(int i = tot; i >= 1 && n; --i) {
                arr[i] += 1;
                n -= 1;
                if(i == 1) i = tot + 1;//重置循环到最末尾
            }
            for(int i = 1; i <= tot; ++i) ans = arr[i] * ans % mod;
            printf("%lld\n", ans);
        }
    }
    return 0;
}

G 朋友的朋友的朋友？

题意：给定 $n$ 个点，每一个点有权值 $a_i$ ，有 $m$ 条边，权值为 $a_i \ xor \ a_j$ ，求联通 $n$ 个点的最小花费
最小生成树板子，多组输入记得初始化（：

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 7, M = 1e6 + 7;//点数，边数

ll n, m, tot = 0 ,cost = 0, fa[N];
int arr[N];

struct G{int from, to , w;}edge[M << 1];//存图
bool cmp(G a, G b) {return a.w < b.w;}

void init(int n) {
    for(int i = 1; i <= n; ++i) {
        fa[i] = i;
    }tot = cost = 0;//注意初始化(:
}

inline ll Find(ll x) {return x == fa[x] ? x : fa[x] = Find(fa[x]);}

void Union(ll x, ll y) {
    x = Find(x), y = Find(y);
    if(x != y) fa[x] = y;
}

bool Kruskal(ll & cost) {//排序的时候记得是排边的数目
    ll cnt = 0;//统计边个数
    cost = 0;
    for(int i = 1; i <= tot; ++i) {
        int u = edge[i].from, v = edge[i].to, w = edge[i].w;
        if(Find(u) != Find(v)) {
            Union(u, v);
            ++cnt;
            cost += w;
            if(cnt >= n-1) break;
        }
    }return (cnt == n - 1);
}

inline ll read() {
    ll s = 0, f = 1;
    char ch;
    do {
        ch = getchar();
        if (ch == '-') f = -1;
    } while (ch < 48 || ch > 57);
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * f;
}

signed main() {
    while(~scanf("%lld%lld", &n, &m)) {
        init(n);
        for(int i = 1; i <= n; ++i) arr[i] = read();
        for(int i = 1; i <= m; ++i) {
            int from = read(), to = read();
            edge[++tot].from = from, edge[tot].to = to, edge[tot].w = arr[from] ^ arr[to];
            edge[++tot].from = to, edge[tot].to = from, edge[tot].w = arr[from] ^ arr[to];
        }sort(edge + 1, edge + 1 + tot, cmp);
        Kruskal(cost);
        printf("%lld\n", cost);
    }
    return 0;
}

E H

摸了，等明天有时间补

JXNU第一届图灵杯个人题解

A 简单数学

B 硬币游戏

C 包裹

D 飞神Ⅱ

F 简单分解

G 朋友的朋友的朋友？

E H