B

题目大意

  给你两张扫雷图A和B，你最多对B修改\(\lfloor \frac{MN}{2} \rfloor\)次，问是否能让B中的数字之和等于A。

解题思路

  扫雷图中的数字等价于相邻的非雷格子与空白格子的对数，相当于一张黑白色的图，很明显，黑白颜色是相对的，即是交换颜色，相邻的黑白颜色的对数也不会改变(就像把黑白对改成白黑对那样)。所以对比两个图中不同的块的个数，如果小于\(\lfloor \frac{MN}{2} \rfloor\)就直接输出A，否则输出A格子翻转之后的图。

代码

const int maxn = 1e3+10;
int n, m;
char g1[maxn][maxn], g2[maxn][maxn], g3[maxn][maxn];
int solve(char ga[maxn][maxn], char gb[maxn][maxn]) {
    int cnt = 0;
    for (int i = 1; i<=n; ++i)
        for (int j = 1; j<=m; ++j)
            if (ga[i][j]!=gb[i][j]) ++cnt;
    return cnt;
}
int main() {
    IOS;
    cin >> n >>m;
    for (int i = 1; i<=n; ++i) cin >> g1[i]+1;
    for (int i = 1; i<=n; ++i) cin >> g2[i]+1;
    for (int i = 1; i<=n; ++i)
        for (int j = 1; j<=m; ++j) {
            if (g1[i][j]=='.') g3[i][j] = 'X';
            else g3[i][j] = '.';
        }
    if (solve(g1, g2)<=n*m/2) {
        for (int i = 1; i<=n; ++i) cout << g1[i]+1 << endl;
    }
    else if (solve(g3, g2)<=n*m/2) {
        for (int i = 1; i<=n; ++i) cout << g3[i]+1 << endl;
    }
    return 0;
}

C

题目大意

  给你两个数X和Y，求下面式子

解题思路

  可以考虑数位dp按位填数，\(i \& j = 0\)说明同一位不同1，而后面的取log相当于求i和j中最高的那个二进制位位数。这样就转换成了一个比较板子的数位dp了，细节可以看注释。

代码

int a[33], b[33];
ll dp[33][2][2][2];
ll solve(int len, int lim1, int lim2, int tp) {
    //tp 0:前面有1 1:前面没有1
	if (len==-1) return 1;
	if (dp[len][lim1][lim2][tp]!=-1) return dp[len][lim1][lim2][tp];
	int up1 = lim1 ? a[len]:1; 
    //如果前面到上限了，只能取当前上限，否则填0和1都可，即当前上限是1
	int up2 = lim2 ? b[len]:1;
	ll res = 0;
	for (int i = 0; i<=up1; ++i)
		for (int j = 0; j<=up2; ++j) {
			if (i&j) continue;
			ll t;
			if (tp&&(i||j)) t = len+1; 
            //如果前面没有1，当前有1，说明当前是最高位，计算log
			else t = 1;
			res = (res+solve(len-1, lim1&&i==up1, lim2&&j==up2, tp&&!i&&!j)*t%MOD)%MOD;
            //lim&&i==up1，如果前面取到上限，并且当前也是上限，对于下一个来说才受限制，否则随便取
		}
	return dp[len][lim1][lim2][tp] = res;
}
int main() { 
	IOS;
	int __; cin >> __;
	while(__--) {
		int x, y; cin >> x >> y;
		int len = 0;
		while(x||y) {
			a[len] = x&1;
			b[len] = y&1;
			x >>= 1;
			y >>= 1;
			++len;
		}
		clr(dp, 0xff);
		cout << ((solve(len-1, 1, 1, 1)-1)%MOD+MOD)%MOD << endl;
        //减1即减去0 0的情况
	}
	return 0;
}