A 小d和答案修改

就简单的签到题

#include<iostream>

using namespace std;

int main() {
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] >= 'a' && s[i] <= 'z')s[i] = s[i] - 32;
        else if (s[i] >= 'A' && s[i] <='Z')s[i] = s[i] + 32;
    }
    cout << s << endl;
    return 0;
}

B 小d和图片压缩

这题主要就是使用二维前缀和来做，还卡了一下下，难过

#include<iostream>

using namespace std;

const int N = 1010;

int n, m;
int a[N][N], s[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i][j] - s[i - 1][j - 1];
        }
    }
//     for (int i = 1; i <= n; i++) {
//         for (int j = 1; j <= m; j++) {
//             cout<<s[i][j]<<' ';
//         }
//         cout<<endl;
//     }
    int ans = 0;
    for (int i = 2; i <= n ; i+=2) {
        for (int j = 2; j <= m ; j+=2) {
            ans = s[i][j] - s[i - 2][j] - s[i][j - 2] + s[i - 2][j - 2];
            cout << ans / 4 << ' ';
        }
        cout << endl;
    }
    return 0;
}

C 小d和超级泡泡

Flood fill模型，使用dfs和bfs都行，但建议使用dfs代码更好写，bfs就因为有一点没考虑到wa了两罚，伤心

bfs

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

#define PII pair<int,int>
#define f first
#define s second

using namespace std;

const int N = 1010;

char g[N][N];
bool vis[N][N];
int cnt;
int n, m;
int dx[]{0,1,0,-1};
int dy[]{1,0,-1,0};
PII pos;

int bfs(int x,int y) {
    queue<PII > q;
    q.push({x, y});
    vis[x][y] = true;
    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int xx = t.f + dx[i];
            int yy = t.s + dy[i];
            if (vis[xx][yy])continue;
            if (xx < 1 || xx > n || yy < 1 || yy > m)continue;
            if (g[xx][yy] == '#')continue;
            if (g[xx][yy] == '!') {
                //cout << xx << ' ' << yy << endl;
                cnt++;
                //g[xx][yy]='.';
                vis[xx][yy] = true;
                q.push({xx, yy});
                continue;
            }
            q.push({xx, yy});
            vis[xx][yy] = true;
        }
    }
    return cnt;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
            if (g[i][j] == '@') {
                pos.f = i;
                pos.s = j;
            }
        }
    }
    cout << bfs(pos.f, pos.s) << endl;
    //for (int i = 1; i <= n; i++)cout << g[i] << endl;
    return 0;
}

dfs

#include<iostream>
#include<cstring>
#include<algorithm>

#define int long long
#define IOS ios::sync_with_stdio(false);
#define CC cin.tie(nullptr),cout.tie(nullptr);

using namespace std;

const int N = 1010;

char g[N][N];
bool vis[N][N];
int n, m;
int ans;
int dx[]{0,1,0,-1};
int dy[]{1,0,-1,0};

void dfs(int x,int y) {
    if (vis[x][y])return;
    if (x < 1 || x > n || y < 1 || y > m)return;
    if (g[x][y] == '#')return;
    if (g[x][y] == '!') {
        ans++;
        //cout<<ans<<' '<<x<<' '<<y<<endl;
    }
    vis[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        dfs(xx, yy);
    }
}

int32_t main() {
    IOS;
    CC;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin>> g[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (g[i][j] == '@')
                dfs(i, j);
        }
    }
    cout << ans << endl;
    return 0;
}

D 小d和孤独的区

这个题是一个思维题，最终的规律就是左右两边的零加一在相乘，因为自己和自己也可以构成一个只有一的区间，我是用结构体来存左右两边零的个数

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

#define int long long
#define PII pair<int,int>
#define f first
#define s second

using namespace std;

const int N = 1000010;

int a[N];
PII b[N];
int n;

int32_t main() {
    cin >> n;
    int t = 0;
    for (int i = 1; i <= n; i++)cin >> a[i];
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == 1) {
            t++;
            b[t].f = cnt;
            b[t - 1].s = cnt;
            cnt = 0;
        } else cnt++;
    }
    if (cnt)b[t].s = cnt;
    //for (int i = 1; i <= t; i++)cout << b[i].f << ' ' << b[i].s << endl;
    int ans = 0;
    for (int i = 1; i <= t; i++) {
        ans += (b[i].f + 1) * (b[i].s + 1);
    }
    cout << ans << endl;
    return 0;
}

E 小d的博弈

先学完博弈论再来补

F 小d和送外卖