526互联

AtCoder Beginner Contest 147

发布时间 2023-03-27 21:49:08作者: Sakana~

AtCoder Beginner Contest 147

https://atcoder.jp/contests/abc147

C - HonestOrUnkind2

推理题，爆搜。好那好难，一直不知道怎么下手

#include <bits/stdc++.h>

using namespace std;
const int N = 25;
int ans, n, a[N][N], b[N][N], tmp[N]; //

int check () {
    for (int i = 1; i <= n; i++) {
        if (!tmp[i])    continue; //只check说真话的的人
        for (int j = 1; j <= n; j++) {
            if (tmp[a[i][j]] != b[i][j])    return 0;
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++)    cnt += (tmp[i] == 1);
    return cnt;
}

void dfs (int x) {
    if (x > n) {
        ans = max (ans, check ());
        return ;
    }
    tmp[x] = 0, dfs (x + 1);
    tmp[x] = 1, dfs (x + 1);
}

int main () {
    cin >> n;
    memset (a, -1, sizeof a);
    for (int i = 1; i <= n; i++) {
        int m;
        cin >> m;
        for (int j = 1; j <= m; j++)    cin >> a[i][j] >> b[i][j];
    }
    dfs (1);
    cout << ans;
}

D - Xor Sum 4

有两种方法，直接 or 间接，前面疯狂WA主要是因为乘法没有随时取模导致爆longlong了

间接法

也是我最初的想法
根据a^b = a+b - 2(a&b)得，所求为：

\[\sum_{i=1}^{n-1}\sum_{j=i+1}^n(a_i\,xor\,a_j) =\sum_{i=1}^{n-1}\sum_{j=i+1}^n(a_i+a_j)-2\sum_{i=1}^{n-1}\sum_{j=i+1}^n (a_i\&a_j)\\ =(n-1)\sum_{i=1}^n a_i-2\sum_{i=1}^{n-1}\sum_{j=i+1}^n (a_i\&a_j) \]

而 \(a_i\&a_j\) 是比较好求的，只需按位 \(a_1\) 到 \(a_n\) 中统计当前位 \(j\) 为 \(1\) 的数有多少个，记个数为 \(cnt_j\)，对总和的贡献就是：

\[2\sum_{i=1}^{n-1}\sum_{j=i+1}^n (a_i\&a_j)=2\sum_{j=0}^{60} （\frac{cnt_j\times(cnt_j-1)}2\times 2^j) \]

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 3e5 + 5, mod = 1e9 + 7;
ll a[N], sum;
int n;

int main () {
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i], (sum += a[i]) %= mod;
    (sum *= (n - 1)) %= mod;

    for (int j = 59; j >= 0; j--) {
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if ((a[i] >> j & 1))    cnt ++;
        }     
        if (!cnt)   continue;
        ll dx = (1ll << j) % mod * cnt % mod * (cnt - 1) % mod;
        // cout << dx << ' ';
        sum = (sum - dx  + mod) % mod;
    }

    cout << sum << endl;
}

//a^b = a+b - 2(a&b)
//a&b就是看有多少位是全1

直接法

直接求异或和。
按位 \(a_1\) 到 \(a_n\) 中统计当前位 \(j\) 为 \(1\) 的数有多少个，记个数为 \(cnt_j\)，对总和的贡献就是

\[\sum_{i=1}^{n-1}\sum_{j=i+1}^n (a_i\,xor\,a_j)=\sum_{j=0}^{60} （{cnt_j\times(n-cnt_j)}\times 2^j) \]

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 3e5 + 5, mod = 1e9 + 7;
ll a[N], sum;
int n;

int main () {
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    for (int j = 60; j >= 0; j--) {
        ll cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] >> j & 1)  cnt ++;
        }
        if (!cnt)   continue;
        sum = (sum + (1ll << j) % mod * cnt % mod * (n - cnt) % mod) % mod;
        // cout << cnt << ' ';
    }
    cout << sum;
}

//a^b = a+b - 2(a&b)
//a&b就是看有多少位是全1

E - Balanced Path

简单线性dp。
然鹅我又想错柿子了，状态总是设不对，就算设对了，也不会转移，就算侥幸转移对了，边界也没设置好呜呜呜呜呜
这题主要是学一个Bitset优化小技巧。
朴素版：

#include <bits/stdc++.h>

using namespace std;
const int N = 85, M = (80 + 80) * 80;
bool f[N][N][M * 2 + 5]; //f[i][j][k]: 差值为 k 的可行性
int n, m, a[N][N], b[N][N];

bool Range (int x, int y) {
    if (x < 1 || x > n || y < 1 || y > m)   return false;
    return true;
}

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> b[i][j];
            a[i][j] -= b[i][j];
        }
    }

    //f[0][0][0] = 1;
    f[1][1][a[1][1] + M] = f[1][1][M - a[1][1]] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1)   continue;
            for (int k = -M; k <= M; k++) {
                f[i][j][k+M] |= (f[i-1][j][k-a[i][j]+M] | f[i-1][j][k+a[i][j]+M]);
                f[i][j][k+M] |= (f[i][j-1][k-a[i][j]+M] | f[i][j-1][k+a[i][j]+M]);
            }
        }
    }
    
    for (int i = 0; i <= M; i++) {
        if (f[n][m][i + M] || f[n][m][M - i]) {
            cout << i << endl;
            break;
        }
    }
}

//差值范围:[-M, M]
//暂定为 red-blue
//很不爽，但是还是要交

bitset优化版：

#include <bits/stdc++.h>

using namespace std;
const int N = 85, M = (80 + 80) * 80;
bitset<2*M+5>f[N][N];
int n, m, a[N][N], b[N][N];

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> b[i][j];
            a[i][j] -= b[i][j];
        }
    }

    //f[0][0][0] = 1;
    f[1][1][a[1][1] + M] = f[1][1][M - a[1][1]] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int k = abs (a[i][j]);
            f[i][j] |= ((f[i-1][j] << k) | (f[i-1][j] >> k));
            f[i][j] |= ((f[i][j-1] << k) | (f[i][j-1] >> k));
        }
    }
    
    for (int i = 0; i <= M; i++) {
        if (f[n][m][i + M] || f[n][m][M - i]) {
            cout << i << endl;
            break;
        }
    }
}

//差值范围:[-M, M]
//暂定为 red-blue
//bitset优化

F - Sum Difference

蛮有意思的一道数论小题。

题意

给你一个首项为 \(x\)，公差为 \(d\) 的 \(n\) 项等差序列，从中任选 \(k\) 个数放入集合 \(S\)，剩余数放入集合 \(T\)，问 \(k\) 从 \(0\) 到 \(n\)，\(S-T\) 共有多少种取值可能。

分析

先进行一个转化：\(S-T=S-(sum-S)=2S-sum\), 其中 \(sum\) 为所有数之和。 \(sum\) 是固定的，所求转化为 \(S\) 有多少种不同的取值。

首先特判掉 \(d=0\) 的情况，即所有数都等于 \(x\)，故 \(x=0\)，输出 \(0\)；否则输出\(n-1\)

\(d<0\)可以把他对称过来，即 \(x,d\) 分别取反之后转化为 \(d>0\) 的情况。

考虑 \(d>0\)，则有 \(S=dv+kx\)，\(v\) 为选取的 \(k\) 个数的 \(d\) 的系数之和。

则 \(0+1+2+...+k-1\leq v\leq (n-k)+(n-k+1)+...+(n-1)\)

即 \(v\in [\frac{k(k-1)}2,\frac{k(2n-k-1)}2]\)

\(k=0,1,...,k\) 时对应的 \(S\) 的图像形如下图，是一个个一次函数：

函数上的点对应在 \(y\) 轴上的值就是 \(S\)，所求即为每个一次函数在定义域为 \(v\in[L,R]\) 范围内的所有取值。观察上图，发现条直线上的点的加纵坐标间距是固定的，如蓝色那条线上，对应 \(y\) 轴上的所有点的距离都是 \(d\)，绿线相邻点之间的距离是\(2d\) ,红线是 \(3d\)，都是 \(d\) 的倍数。那么每条线投影在 \(y\) 轴上的点坐标都是间隔固定距离的点集，因为不同线之间的点集可能会重合，所以我们考虑如何去重。

这里就涉及到了本题最精华的部分，将离散的点转化为连续的线段。因距离和 \(d\) 有关，不妨令 \(S/d=dv/d+kx/d=v+kx/d\)，\(v\) 是连续的，分布在 \([L,R]\) 范围内的数，即长度为 \(R-L+1\) 的线段，问题得以解决。可以理解为，此时 \(S\) 转化为 \(kx\) 模 \(d\) 意义下的一段线段。

Code

#include <bits/stdc++.h>
#define ll long long

using namespace std;
typedef pair<ll, ll> pii;
const int N = 2e5 + 5;
ll n, x, d, sum;
map<int, vector<pii>> v;

int main () {
    cin >> n >> x >> d;
    if (d == 0) {
        if (x == 0)     cout << 1; //0
        else    cout << n + 1;
        return 0;
    }
    if (d < 0)  x = -x, d = -d;
    for (ll k = 0; k <= n; k++) { //别忘了k=0!!!
        ll L = k * (k - 1) / 2, R = k * (2 * n - k - 1) / 2;
        ll t = k * x; //离散的点连续化
        L += t / d, R += t / d;
        v[t % d].push_back ({L, R}); //%d意义下同运算
    }
    
    for (auto vi : v) { //区间合并
        ll t = vi.first;
        auto tt = vi.second;
        sort (tt.begin (), tt.end ());
        ll l = tt[0].first, r = tt[0].second;
        for (int i = 1; i < tt.size (); i++) {
            if (tt[i].first <= r)   r = max (r, tt[i].second); //区间有重叠，合并为大区间
            else    sum += r - l + 1, l = tt[i].first, r = tt[i].second; 
        }
        sum += r - l + 1;
    }
    cout << sum << endl;
}

//s=kx+vd