头像

我只负责签到zzz




离线:13天前


活动打卡代码 AcWing 90. 64位整数乘法

#include <iostream>

using namespace std;

typedef long long ll;

ll qk_mul(ll a, ll b, ll m) {
    if(m == 1) return 0; // 如果mod为1,自然答案为0
    ll res = 0;
    while (b) {
        if (b & 1) res = (res + a) % m;
        a = (a + a) % m;
        b >>= 1;
    }
    return res;
}

int main() {
    ll a, b, m; cin >> a >> b >> m;
    cout << qk_mul(a, b, m);
}


活动打卡代码 AcWing 89. a^b

#include <iostream>

using namespace std;

typedef long long ll;

ll qk_pow(ll a, ll b, ll m) {
    if(!a || m == 1) return 0; // 如果a为0,mod为1,自然答案为0
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

int main() {
    ll a, b, m; cin >> a >> b >> m;
    cout << qk_pow(a, b, m);
}



题目链接 372. 棋盘覆盖

思路:
题目要求在允许的格子用1*2的骨牌填充且不重叠,那我认为可以在这些允许的格子(也是就每一个允许范围连通块)内用dfs交替填充黑白两色,然后累加每次dfs中填充黑色和白色较少的次数,最后累加的结果就是答案。因为黑白都是交替的,所以较少的那个颜色就一定有另外一个与之相邻且相反颜色的格子与它对应,也就组成了一个骨牌。

例如:
4*4的棋盘: (1代表禁止放置,0代表可以放置,b代表黑色,w代表白色)
开始:
0 0 1 0
1 0 0 1
0 1 0 0
0 0 1 0
填充后:(或者b和w互换也是一样的)
b w 1 b
1 b w 1
b 1 b w
w b 1 b
可以看出每个连通块较小颜色数目的总和为3 + 0 + 1 = 4, 所以最后答案为4

我的代码:

#include <iostream>
#include <algorithm>

using namespace std;

int g[105][105], mv[4][2] = { 1, 0, 0, 1, -1, 0, 0, -1 }, n, t, ans, c1, c2; // c1, c2记录的是黑、白方格的数目

void dfs(int x, int y, int color) { 
    if (color) c1++;
    else c2++;
    g[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int xx = x + mv[i][0];
        int yy = y + mv[i][1];
        if (xx < 1 || xx > n || yy < 1 || yy > n) continue;
        if (!g[xx][yy]) dfs(xx, yy, color ^ 1);
    }
}

int main() {
    cin >> n >> t;
    while (t--) {
        int x, y; cin >> x >> y;
        g[x][y] = 1;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (!g[i][j]) {  // 每次对一个没访问过的连通块进行搜索
                c1 = 0, c2 = 0;
                dfs(i, j, 0);
                ans += min(c1, c2);
            }

    cout << ans;
}