Random

题目描述：
N个数字，随机生成[0，1]之间的数
做M次操作，1/2概率删除最大值，1/2概率删除最小值
计算期望值总和，结果对10^9+7取模

想法：
从题目上来看N个数可以看做都是0.5，每进行一次操作就可以减少0.5，所以最终答案就是(n-m)/2%(mod)
但是需要注意的是这里使用除法逆元去计算结果，否则就会出问题，比赛时就是因为这个没通过。

知识点：除法逆元

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

const ll p = 1e9 + 7;

ll fast_pow(ll a, ll b, ll p) {
    ll ans = 1;
    a %= p;
    while (b != 0) {
        if (b & 1) {
            ans = (ans * a) % p;
        }
        a = (a * a) % p;
        b >>= 1;
    }
    return ans;
}

int main() {
    int times;
    cin >> times;
    while (times--) {
        int n, m;
        cin >> n >> m;
        cout << (n - m) * fast_pow(2, p - 2, p) % p << endl;
    }
}

Alice and Bob

题目描述：
有m个写在黑板上的数字，所有这些都是介于0和n.
如果黑板上还有数字，并且没有带值的数字0在黑板上，爱丽丝可以将黑板上剩余的数字分成两组。
Bob 选择其中一组并擦除该集中的所有数字。然后将所有剩余的数字减去一。
在任何时候，如果有一个值为0在黑板上，爱丽丝获胜;否则，如果黑板上的所有数字都被擦除，则鲍勃获胜。
请确定如果爱丽丝和鲍勃都以最佳方式玩游戏，谁将赢得游戏。

想法：
如果至少有两个1，将它们分开，无论Bob做什么选择，Alice都可以获胜
如果至少有一个1，至少有两个2，可以得到至少两个1
如果至少有4个2，将它们分开，可以得到至少两个1
由此可以得到两个i+1可以等价为一个i

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;


ll a[1000009];

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 0; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = n; i >= 1; i--) {
            a[i - 1] += a[i] / 2;
        }
        if (a[0] >= 1) {
            cout << "Alice" << endl;
        } else {
            cout << "Bob" << endl;
        }
    }
    return 0;
}

Laser

题目描述：
在平面上有很多点，是否能够用一个“米”字使得所有的点都在这四条线上。

想法：
我们先从第一个点出发，依次枚举四个方向abcd，如果发现某个点不在枚举的方向上，例如a，那么从那个点出发枚举bcd方向，我们就可以得到与a方向的三个交点，再从这三个交点入手暴力枚举四个方向，就能得到结果

#include<iostream>

using namespace std;


const int N = 5e5 + 10;
int x[N], y[N], n;


int check1() {
    for (int i = 1; i <= n; i++) {
        if (y[i] != y[1]) {
            return i;
        }
    }
    return 0;
}

int check2() {
    for (int i = 1; i <= n; i++) {
        if (x[i] != x[1]) {
            return i;
        }
    }
    return 0;
}

int check3() {//右
    for (int i = 1; i <= n; i++) {
        if ((x[i] - x[1]) != (y[i] - y[1])) {
            return i;
        }
    }
    return 0;
}

int check4() {//左
    for (int i = 1; i <= n; i++) {
        if ((x[i] - x[1]) != (-(y[i] - y[1]))) {
            return i;
        }
    }
    return 0;
}

bool isCenter(int a, int b) {
    for (int i = 1; i <= n; i++) {
        if (x[i] == a || y[i] == b || abs(a - x[i]) == abs(b - y[i])) {
            continue;
        }
        return false;
    }
    return true;
}

bool solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }
    int i;
    i = check4();
    if (i) {
        if (isCenter(x[i], -x[i] + y[1] + x[1]) || isCenter(y[1] + x[1] - y[i], y[i]) ||
            isCenter((y[1] + x[1] - y[i] + x[i]) >> 1, (-x[i] + y[1] + x[1] + y[i]) >> 1))
            return true;
    } else {
        return true;
    }
    i = check3();
    if (i) {
        if (isCenter(x[i], x[i] + y[1] - x[1]) || isCenter(y[i] - y[1] + x[1], y[i]) ||
            isCenter((y[i] - y[1] + x[1] + x[i]) >> 1, (x[i] + y[1] - x[1] + y[i]) >> 1))
            return true;
    } else {
        return true;
    }
    i = check2();
    if (i) {
        if (isCenter(x[1], y[i]) || isCenter(x[1], y[i] - x[i] + x[1]) || isCenter(x[1], y[i] + x[i] - x[1]))
            return true;
    } else {
        return true;
    }
    i = check1();//找到不与第一个点同处于水平线上的i点
    if (i) {
        if (isCenter(x[i], y[1]) || isCenter(x[i] + y[1] - y[i], y[1]) || isCenter(x[i] - y[1] + y[i], y[1]))
            return true;
    } else {
        return true;
    }
    return false;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        if (solve()) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }

    }
}

Backpack

题目大意：
背包容量为m
有n个物品，每个物品都有volume和weight
求在背包装满的条件下最大的价值为多少

官方解释：

个人理解：
对于那个转移方程，
如果f(i-1,j,k)=1，表示不拿i位置的值我们也可以做到前i个物品异或和为j并且体积为k，
如果f(i-1,j^v,k-w)=1,表示的是拿上i位置的值我们可以做到前i个物品异或和为j并且体积为k，
只要两种情况有一种成立就f(i,j,k)就存在，所以f(i,j,k)=f(i-1,j,k)|f(i-1,j^v,k-w)。(j^v ^v = j,k-w +w = k)
由于所有的状态都是0或者1，我们可以使用bitset进行操作。

#include<iostream>

using namespace std;

#include<bitset>


int n, m;
bitset<1025> f[1025], g[1025];


void solve() {
    for (int i = 0; i < 1024; i++) {
        f[i].reset();
        f[i].reset();
    }
    f[0][0] = 1; //异或和为0并且体积为0的情况存在
    cin >> n >> m;
    int v, w;
    for (int i = 1; i <= n; i++) {
        cin >> v >> w;
        for (int i = 0; i < 1024; i++) {
            g[i] = f[i];
            g[i] <<= v;//由于数组是从左往右开始，bitset是从右往左开始，所以左移代表着减去当前的体积。
        }
        for (int i = 0; i < 1024; i++) {
            f[i] |= g[i ^ w];
        }
    }
    int ans = -1;
    for (int i = 0; i < 1024; i++) {
        if (f[i][m]) {
            ans = i;
        }
    }
    cout << ans << endl;

}


int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}