天哥

V1

2022/08/05阅读:22主题:蓝莹

《进阶指南》0x01 复盘

《进阶指南》0x01 复盘

牛客网

A

(快速幂模板题)

快速幂:计算 a ^ b % p 的值,本题数据量:

思路:

将 b 表示为 (对于 ,有

考虑到 ,余数的可乘性

可以得出如下代码:(注意a与b的更新)

int binpow(int a, int b, int p) {
    int ans = 1 % p;
    while (b) {
        if (b & 1) ans = (long long)ans * a % p;
        a = (long long)a * a % p;
        b >>= 1;
    }
    return ans;
}

B

题目大意:

给定 Z 组数据,对于每组数据:

有 H 组子数据,表示为 ,并给定

求解

思路:

对于每组数据:

考虑余数的可加性及可乘性,分别计算 的值,并将结果求和并取模

C

类比A题,三个参数都改为long long 类型,把用乘号的地方改成加号,加上括号,即可

D

状压DP,将01的状态作为第一维(2进制数),将最后访问的点的编号作为第二维,注意第一维的范围是1到2^n-1,第二维的范围是0到n-1

核心代码:

memset(dp, 0x3fsizeof(dp));
dp[1][0] = 0;
for (int i = 1; i < 1 << n; ++i) {
    for (int j = 0; j < n; ++j) {
        if ((i >> j & 1) == 0continue;
        int last = i ^ 1 << j;
        for (int k = 0; k < n; ++k) {
            if (last >> k & 1) dp[i][j] = min(dp[i][j], dp[last][k] + a[k][j]);
        }
    }
}
printf("%d", dp[(1 << n) - 1][n - 1]);

E

发现三个运算在二进制下的不进位的特点,采用贪心

  • 从高位往低位运算,优先保证高位的结果尽可能是1
  • 如果当前位取0,经过一系列运算后最终结果为1,那么这一位用0
  • 如果当前位取1,最终结果取1,且当前位取1后没有大于限定值,那么这一位取1
  • 否则,这一位取0,结果为0

代码:

#include <stdio.h>
#define MAXN 100005

int n, m, ori, ed;
char op[MAXN];
int t[MAXN];

void read() {
    scanf("%d%d", &n, &m);
    char rd[5];
    for (int i = 1; i <= n; ++i) {
        scanf("%s%d", rd, &t[i]);
        op[i] = rd[0];
    }
}

int cal(int x, int l) {
    for (int i = 1; i <= n; ++i) {
        if (op[i] == 'A') {
            x &= (t[i] >> l) & 1;
        } else if (op[i] == 'O') {
            x |= (t[i] >> l) & 1;
        } else if (op[i] == 'X') {
            x ^= (t[i] >> l) & 1;
        }
    }
    return x;
}

void solve() {
    ori = ed = 0;
    int c0, c1, power;
    for (int i = 30; i >= 0; --i) {
        c0 = cal(0, i), c1 = cal(1, i), power = 1 << i;
        if (c0 == 1) {
            ed += power;
        } else if (c1 == 1 && ori + power <= m) {
            ed += power;
            ori += power;
        }
    }
    printf("%d", ed);
}

int main() {
    read();
    solve();
    return 0;
}

分类:

后端

标签:

C++

作者介绍

天哥
V1