2022杭电多校第一场（K/L/B/C）

K. Random

可以粗略的看作每个数的概率都是1/2
这种取模方法需要注意 ： ll te = (mod + 1) / 2; 1ll * (n - m) * te % mod;

	int t;
    cin >> t;
    ll te = (mod + 1) / 2;
    while(t--){
    
        ll n, m;
        cin >> n >> m;
        cout << 1ll * (n - m) * te % mod << endl;
    }

或者更好理解的：

ll qpow(ll a, ll b) {
    
  int ans = 1;
  a = (a % p + p) % p;
  for (; b; b >>= 1) {
    
    if (b & 1) ans = (a * ans) % p;
    a = (a * a) % p;
  }
  return ans;
}
int main() {
    
    ll mm = qpow(2, p - 2);
    int t;
    cin >> t;
    while(t--){
    
        ll n, m;
        cin >> n >> m;
        cout << (n - m) * mm % p << endl;
    }
    return 0;
}

L. Alice and Bob

博弈论

总结：

• 从更明显，更好入手的地方考虑；例如：Alice只需要有0就可以赢，问题就转化成了：如何将数转化成含0的
• 转化必胜态，由基础必胜到更大范围
• （也许能从很怪的地方入手，例如：0 2-Alice赢）
  
  来自知乎 - 每日一棵splay - https://zhuanlan.zhihu.com/p/543760351

关键在于构造出0

	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 > 0; i--){
    
            a[i - 1] += a[i] / 2;
        }
        if (a[0])
            cout << "Alice" << endl;
        else
            cout << "Bob" << endl;
    }

B. Dragon slayer

dij写到一半发现不对…
总结：

• 不限定方向随便走：只用限定上下左右四个方向就行
• 感觉31以内都可以二进制枚举

二进制枚举选择删去哪些墙

int n, m, k;
int xs, ys, xt, yt;

int dx[] = {
    0, 0, 1, -1};
int dy[] = {
    1, -1, 0, 0};

bool g[35][35];
bool vis[35][35];

struct node
{
    
    int x1, y1, x2, y2;
}wall[35];

int lowbit(int x){
    
    return x & (-x);
}

void add(int k){
    
    if(wall[k].x1 > wall[k].x2)
        swap(wall[k].x1, wall[k].x2);
    if(wall[k].y1 > wall[k].y2)
        swap(wall[k].y1, wall[k].y2);
    for (int i = wall[k].x1; i <= wall[k].x2; ++i){
    
        for (int j = wall[k].y1; j <= wall[k].y2; ++j){
    
            g[i][j] = true;
        }
    }
}

void del(int k){
    
    if(wall[k].x1 > wall[k].x2)
        swap(wall[k].x1, wall[k].x2);
    if(wall[k].y1 > wall[k].y2)
        swap(wall[k].y1, wall[k].y2);
    for (int i = wall[k].x1; i <= wall[k].x2; ++i){
    
        for (int j = wall[k].y1; j <= wall[k].y2; ++j){
    
            g[i][j] = false;
        }
    }
}

bool bfs(){
    
    queue<PII> q;
    q.push({
    xs, ys});
    re(vis);
    vis[xs][ys] = true;
    while(!q.empty()){
    
        int x = q.front().first, y = q.front().second;
        q.pop();
        if(x == xt && y == yt)
            return true;
        for (int i = 0; i < 4; ++i){
    
            int xx = x + dx[i], yy = y + dy[i];
            if(xx >= 0 && xx < n && yy >= 0 && yy < m && !vis[xx][yy] && !g[xx][yy]){
    
                q.push({
    xx, yy});
                vis[xx][yy] = true;
            }
        }
    }
    return false;
}

int main()
{
    
    int t;
    cin >> t;
    while (t--){
    
        cin >> n >> m >> k;
        n *= 2, m *= 2;
        cin >> xs >> ys >> xt >> yt;
        xs = xs * 2 + 1, ys = ys * 2 + 1, xt = xt * 2 + 1, yt =  yt * 2 + 1;
        for (int i = 0; i <= n; ++i){
    
            for (int j = 0; j <= m; ++j){
    
                g[i][j] = false;
            }
        }
        for (int i = 0; i < k; ++i){
    
                int x1, x2, y1, y2;
                cin >> x1 >> y1 >> x2 >> y2;
                wall[i] = {
    x1 * 2, y1 * 2, x2 * 2, y2 * 2};
        }
        int ans = 0;
        for (int i = 0; i < (1 << k); ++i){
    
            int cnt = 0;
            for (int j = i; j; j -= lowbit(j))
                ++cnt;
            if(cnt <= ans)
                continue;
            for (int j = 0; j < k; ++j){
    
                if(i >> j & 1)
                    add(j);
            }
            if(bfs())
                ans = cnt;
            for (int j = 0; j < k; ++j){
    
                if(i >> j & 1)
                    del(j);
            }
        }
        cout << k - ans << endl;
    }
    return 0;
}

C. Backpack

总结：(点击跳转至原链接)

• 不能把异或值当作结果来进行动态规划，因为异或值本身不具有最优子结构
  
• 内存限制，三维开不下，要的只是0,1，bitset压位优化
  
  来源：菜鸟教程

bitset<1030>f[2][1030];//f[i][j]前i个物品得到异或值位j的所有的体积状态 不要开太大了，会超时
int main() {
    
	IOS;
    int t;
    scanf("%d", &t);
    while(t--){
    
        int n, m;
        scanf("%d %d", &n, &m);
        for (int i = 0; i < 1024; ++i)
            f[0][i].reset();
        f[0][0].set(0);
        for (int i = 1; i <= n; ++i){
    
            int v, w;
            scanf("%d %d", &v, &w);
            for (int j = 0; j < 1024; ++j){
    
                f[i & 1][j] = f[(i & 1) ^ 1][j] | (f[(i & 1) ^ 1][j ^ w] << v);//左移v == 减v
                //相当于滚动数组
                /* bitset<N> f[N],g[N]; f[0][0] = 1; for(int j=0;j<=1023;j++) g[j]=f[j];赋值上一维 for(int j=1023;j>=0;j--) { f[j]|=g[j^w]<<v; } cout << f[i][m] */
            }
        }
        bool flag = true;
        for (int i = 1023; i >= 0; --i){
    
            if(f[n & 1][i][m]) {
    
                printf("%d\n", i);
                flag = false;
                break;
            }
        }
        if(flag)
            printf("-1\n");
    }
    return 0;
}