AtCoder Beginner Contest 172

比赛链接

C Tsundoku

题目链接

Solution

不论如何选取，选取的一定是 A 与 B 数组从头开始的一段。先预处理出前缀和，然后枚举在 A 数组中选取的位置 $i$，其前缀和为 $sumA_i$, 接下来找到 B 数组中前缀和不超过 $k-sumA_i$ 的最后一个位置 $j$，那么此时能选取书的总数为 $i+j$。答案即为所有 $i+j$ 的最大值

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 200005;
ll sumA[maxn], sumB[maxn];
int ans,n, m, k, x;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> x, sumA[i] = sumA[i - 1] + x;
    for (int i = 1; i <= m; i++) cin >> x, sumB[i] = sumB[i - 1] + x;
    for (int i = 0; i <= n && sumA[i] <= k; i++) {
        int rem = k - sumA[i];
        int Index = upper_bound(sumB, sumB + m + 1, rem) - sumB;
        ans = max(ans, i + Index - 1);
    }
    cout << ans;
    return 0;
}

D Sum of Divisors

题目链接

Solution

根据题意，求解过程可以用如下伪代码表示：

ans = 0
for i = 1, ..., N:
    for j = 1, ..., N:
	if i % j == 0 then ans += i
print ans

由于所有二元组都被枚举到，所以两层循环可交换顺序：

ans = 0
for j = 1, ..., N:
    for i = 1, ..., N:
        if i % j == 0 then ans += i
print ans

令 $g(j)$ 表示 $j$ 的所有不超过 $N$ 的倍数的和，那么答案可以表示为 $\sum\limits_{j=1}^Ng(j)$。
对于任意 $X(1<=X<=N)$，令 $Y$ = $\lfloor N/X \rfloor$，那么 $g(X)$ = $X+2X+...YX$ = $(1+Y)YX/2$。这样在 $O(N)$ 时间内即可求得答案。

Code

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ll;
ll n, ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        ll j = n / i;
        ans += i * j * (j + 1) / 2;
    }
    cout << ans;
    return 0;
}

E NEQ

题目链接

Solution

先不考虑 $\forall i \in[1,N], A_i \neq B_i$ 这一条件，那么总共的方案数为 $(A_M^N)^2$。

接下来只需要去除使 $A,B$ 数组中某几位相同的方案。设 $P_i$ 表示事件: $A_i = B_i$。那么不合法的方案构成的集合为 $P_1\cup P_2 \cup ...\cup P_n$。由容斥原理有 $|P_1\cup P_2 \cup ...\cup P_n|=\sum\limits_{1<=i<=n}|P_i|-\sum\limits_{1<=i<j<=n}|P_i\cap P_j|$
$+\sum\limits_{1<=i<j<k<=n}|P_i\cap P_j\cap P_k|-...+(-1)^{n-1}|P_1\cap P_2 \cap ...\cap P_n|$。

设一下标集合 $S$，集合大小为 $|S|$，则它对应的满足 $\forall i \in S, A_i = B_i$的 $A,B$数组 有$A_M^{|S|}(A_{M-|S|}^{N-|S|})^2$ 对 ($|S|$位相同对应$A_M^{|S|}$，剩下$N-|S|$位从剩下$M-|S|$个数中任取)。
根据容斥原理,这一集合对不合法方案的贡献为 $(-1)^{|S|-1}A_M^{|S|}(A_{M-|S|}^{N-|S|})^2$。显然，这样的集合有$C_N^{|S|}$个。于是所有大小为 $|S|$ 的集合的贡献为
$C_N^{|S|}(-1)^{|S|-1}A_M^{|S|}(A_{M-|S|}^{N-|S|})^2$。将所有大小的集合的贡献累加即可得到不合法的方案数, 把它从总的方案数中减去即可。

Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int maxn = 5e5 + 5;
int n, m;
ll inv[maxn], fac[maxn], ans;

ll qpow(ll a, ll b) {
    ll ans = 1, base = a;
    while (b) {
        if (b & 1) ans = ans * base % MOD;
        b >>= 1, base = base * base % MOD;
    }
    return ans;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i <= m; i++) fac[i] = fac[i - 1] * i % MOD;
    for (int i = 0; i <= m; i++) inv[i] = qpow(fac[i], MOD - 2);
}

ll A(ll a, ll b) { return fac[a] * inv[a - b] % MOD; }

ll C(ll a, ll b) { return fac[a] * inv[b] % MOD * inv[a - b] % MOD; }

int main() {
    cin >> n >> m;
    init();
    ans = qpow(A(m, n), 2);
    for (int s = 1; s <= n; s++) {
        ans -= (s & 1 ? 1 : -1) * C(n, s) * A(m, s) % MOD *
               qpow(A(m - s, n - s), 2) % MOD;
        ans %= MOD;
    }
    cout << (ans + MOD) % MOD;
    return 0;
}

F Unfair Nim

题目链接

Solution

要做本题首先要直到这个结论：后出手的人有必胜策略当且仅当 $A_1⊕A_2⊕...⊕A_N=0$

设从第一堆移动石子数为 $x(0<=x<A_1)$，令 $a=A_1-x,b=A_2+x$，其中$1<=a<=A_1$，那么有 $a+b=A_1+A_2 =S,a⊕b=A_3⊕A_4⊕...⊕A_N=X$。题目要求最小的 $x$，即求最大的 $a$，使前面两个式子成立。

由于 $a+b=a⊕b+2*(a\&b)$ ($a⊕b$ 可视为不进位的加法，加上 $(a \& b)<<1$ 即将进位加上)，可以得出 $(a\&b)=(S-X)/2=D$。如果 $S-X$ 不是偶数，$D$ 小于0，或者 $D$ 与 $X$ 在二进制下某一位同为 1 ($a\&b$ 在某一位为 1 仅当 $a,b$ 在这一位同为 1，而此时$a⊕b$ 在这一位的结果应为 0)，本题无解。

将 $X$ 在二进制下拆分成两个数 $Y,Z$，满足$Y\&Z=0,Y⊕Z=X$,即 $X$ 某一位为 1 时，$Y,Z$ 在这一位不同时为1。可以解出 $a=D⊕Y,b=D⊕Z$,可以证明无其它形式的解。根据前面的结论，$D$ 与 $Y$ 不存在某一位同为 1 的情况，所以 $D⊕Y\ge D$，因此 $a$ 的最小值为 $D$。如果 $D > A_1$ 则本题无解。接下来从高位到低位考察 $X$ 二进制下的每一位，如果这一位为 1，尝试将这一位加到 $a$ 中，看得到的结果是否大于 $A_1$, 如果大于则不能加上这一位。最后，若 $a=0$，即$x=A_1$，本题无解。否则，输出 $A_1-a$ 即为移动石子的最小数量。

Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int N;
ll A1, A2, A, ans, X;

bool check(ll a, ll b) {
    for (int i = 41; ~i; i--) {
        int ai = (a >> i) & 1;
        int bi = (b >> i) & 1;
        if (ai == 1 && bi == 1) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> N;
    cin >> A1 >> A2;
    ll S = A1 + A2;
    for (int i = 3; i <= N; i++) cin >> A, X ^= A;
    ll D = (S - X) >> 1;
    if (((S - X) & 1) || D < 0 || D > A1 || !check(D, X)) cout << -1, exit(0);
    ans = D;
    for (int i = 41; ~i; i--) {
        bool Xi = (X >> i) & 1;
        if (Xi && ((ans | (1ll << i)) <= A1)) ans |= 1ll << i;
    }
    cout << (ans ? A1 - ans : -1);
    return 0;
}