两日总结四

本次总结的时间是2022-7-19~2022-7-20

 这两天主要是打比赛，然后补题，再根据复盘的不足之处去找题目训练。

1.CF一场加补题：

 

 2.航电杯，5小时比赛。

然后就是补题：
对于1003Backpack这个题目比较巧妙。01背包的题意，求得是在V刚好满足的情况下，所有W异或的最大值。一开始就考虑错了，没什么思路。看了题解才知道其实思路是很简单的，就是枚举最后所有异或值的情况，看看是不是能取到刚好的体积。就是我已经给你确定了最后的值，看你能不能把我的体积压到位。能就说明可以否则说明这个异或值取不到，最后去最大的即可。

假设输入v,w; 那么对于这个转移来说 dp[j] = max(dp[j], dp[j^w]) 这里的max就是 |  的意思，将dp[j^w]这个状态全部拿上, j^w 相当于再次异或就是没有拿，还要改变的是dp[j^w]这个状态对应的体积不是这个，而是出去后面大小为v 的空间的状态。（dp[j]里面都是一个1024位的bit,每一位代表空间1）那么出去后面v的空间就是dp[j] <<= v;

因此转移方程：全部移位 g[j] = dp[j];  g[j] <<= v;        之后转移dp[j] |= g[j ^ w];   

#include <bits/stdc++.h>
#define OST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define endl "\n"
using namespace std;
const int N = 1030;
bitset<N> dp[N], g[N];
void solve() {
    int n, m;
    cin >> n >> m;
    for (int j = 0; j < 1024; ++j) { dp[j].reset(); }
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;
        for (int j = 0; j < 1024; j++) {
            g[j] = dp[j];
            g[j] <<= v;
        }
        for (int j = 0; j < 1024; j++) { dp[j] |= g[j ^ w]; }
    }
    int ans = -1;
    for (int i = 0; i < 1024; i++) {
        if (dp[i][m]) { ans = i; }
    }
    cout << ans << endl;
}

signed main() {
    int T = 1;
    cin >> T;   
    while (T--) { solve(); }
    return 0;
}

还有就是另外一道几何题目：

1009, Laser

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
struct node {
    double x, y;
};
node p[N];
int n;
bool ok(node i, node j) {
    if (i.x == j.x || i.y == j.y || abs(i.x - j.x) == abs(i.y - j.y)) return true;
    return false;
}

bool check() {
    cin >> n;
    bool flag = false;
    for (int i = 1; i <= n; i++) { cin >> p[i].x >> p[i].y; }
    node a = p[1], b;
    vector<node> ke;
    for (int i = 2; i <= n; i++) {
        if (ok(a, p[i])) continue;
        b = p[i];
        // 两点不直接满足,枚举两点的交点12个
        if (a.x > b.x) {
            node tmp = a;
            a        = b;
            b        = tmp;
        }
        double ba1 = (a.x + a.y) / 2;
        double ba2 = (a.y - a.x) / 2;
        double bb1 = (b.x + b.y) / 2;
        double bb2 = (b.y - b.x) / 2;
        // a 的水平线交 b的米字4线
        ke.push_back({b.x, a.y});
        ke.push_back({bb1 - a.y, a.y});
        ke.push_back({a.y - bb2, a.y});
        // a的竖直线交 b的米字4线
        ke.push_back({a.x, b.y});
        ke.push_back({a.x, -a.x + bb1});
        ke.push_back({a.x, a.x + bb2});
        // a的斜率为1的直线交b的米字四线
        ke.push_back({b.x, b.x + ba2});
        ke.push_back({b.y - ba2, b.y});
        ke.push_back({(bb1 - ba2) / 2, (ba2 + bb1) / 2});
        // a的斜率为-1的直线交b的米字四线
        ke.push_back({b.x, -b.x + ba1});
        ke.push_back({ba1 - b.y, b.y});
        ke.push_back({(ba1 - bb2) / 2, (ba1 + bb2) / 2});
        break;
    }
    if (ke.size() == 0) {
        flag = true;
    } else {
        for (int i = 0; i < 12; i++) {
            int kk = 1;
            for (int j = 1; j <= n; j++) {
                if (ok(ke[i], p[j])) continue;
                kk = 0;
                break;
            }
            if (kk) {
                flag = true;
                break;
            }
        }
    }
    return flag;
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        if (check())
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
}

3.其他刷题：