L-China

$\href{https://www.acwing.com/blog/content/30572/}{\huge{\color{gold}{卡塞尔学院}}}$

关注数

粉丝数

阅读量

2.0万

+关注发消息

离线：9小时前

最近来访(572)

辣鸡号航母

._839

江水白

Luli

方攵飛夢想

FJ_EYoungOneC

整个AcWing凑不出一个ikun

源泉

yxc的小迷妹

清风qwq

做事要有遗逝感

04辽宁大丑

Kir

-浪漫主义狗-

Sebastian_7

种花家的市长

流年溢梦

say774

Amaryllis_

candy.

活动打卡代码 AcWing 4802. 金明的假期

L-China
9小时前

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

using namespace std;

const int N = 110;

int n;
int w[N], f[N][3];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> w[i];

    memset(f, -0x3f, sizeof f);
    f[0][2] = 0;
    for (int i = 1; i <= n; i ++) 
        for (int j = 0; j < 3; j ++)
            if (j == 2 || (w[i] >> j & 1))
                for (int k = 0; k < 3; k ++)
                    if (j == 2 || j != k)
                        f[i][j] = max(f[i][j], f[i - 1][k] + (j != 2));

    cout << n - max({f[n][0], f[n][1], f[n][2]});

    return 0;
}

            

活动打卡代码 AcWing 4805. 加减乘

L-China
9小时前

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

using namespace std;
typedef long long ll;

const int N = 1e7 + 10;

int n, x, y;
ll f[N];

int main() {
    cin >> n >> x >> y;
    memset(f, 0x3f, sizeof f);
    f[0] = 0;

    for (int i = 1; i <= n; i ++) 
        if (i % 2)
            f[i] = min(f[(i + 1) / 2] + x + y, f[i - 1] + x);
        else
            f[i] = min(f[i / 2] + y, f[i - 1] + x);

    cout << f[n];
    return 0;
}

            

题解 AcWing 4804. 构造矩阵

L-China
10小时前

C++

$法一：$

思路：

模拟

$1、将a矩阵全部初始化为-1$

$2、先把当b[i][j]为0时的第i行和第j列全部更新为0$

$3、在判断b[i][j]为1时是否满足于第i行和第j列不全为0$

$时间复杂度:O(n^3)$

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

using namespace std;

const int N = 110;

int m, n;
int b[N][N], a[N][N];
bool flag;

int main() {
    cin >> m >> n;
    for (int i = 1; i <= m; i ++)
        for (int j = 1; j <= n; j ++) 
            cin >> b[i][j];

    memset(a, -1, sizeof a); // a 矩阵初始化

    for (int i = 1; i <= m; i ++) // 将 b[i][j]为0时的第i行和第j列全部更新为0
        for (int j = 1; j <= n; j ++) {
            if (b[i][j] == 0) {
                for (int x = 1; x <= n; x ++) // 行
                        a[i][x] = 0;
                for (int y = 1; y <= m; y ++) // 列
                        a[y][j] = 0;
            }
        }

    for (int i = 1; i <= m; i ++) 
        for (int j = 1; j <= n; j ++) {
            if (b[i][j] == 1) { // 判断b[i][j]为1时是否满足于第i行和第j列不全为0
                flag = false;
                for (int x = 1; x <= n; x ++) // 行
                    if (a[i][x] == -1 || a[i][x] == 1) {
                        a[i][x] = 1;
                        flag = true;
                    }
                for (int y = 1; y <= m; y ++) // 列
                    if (a[y][j] == -1 || a[y][j] == 1) {
                        a[y][j] = 1;
                        flag = true;
                    }
                if (flag == false) { // 不满足，直接输出NO
                    cout << "NO";
                    return 0;
                }    
            }
        }    


    cout << "YES" << endl;
    for (int i = 1; i <= m; i ++) {
        for (int j = 1; j <= n; j ++) {
            cout << a[i][j] << ' '; 
        }
        cout << endl;
    }

    return 0;
}

$法二：$

思路：

$1、将a矩阵全部初始化为-1$

$2、把当b[i][j]为0时的第i行和第j列全部更新为0$

$3、通过一个check函数判断b[i][j]为1时是否满足于第i行和第j列不全为0$

$时间复杂度:O(n^3)$

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

using namespace std;

const int N = 110;

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

bool check() {
    for (int i = 1; i <= m; i ++)
        for (int j = 1; j <= n; j ++)
            if (b[i][j]) {
                int cnt = 0;
                for (int x = 1; x <= n; x ++) cnt += a[i][x];
                for (int y = 1; y <= m; y ++) cnt += a[y][j];
                if (!cnt) return false;
            }
    return true;        
}

int main() {
    cin >> m >> n;

    memset(a, -1, sizeof a);
    for (int i = 1; i <= m; i ++) 
        for (int j = 1; j <= n; j ++) {
            cin >> b[i][j];
            if (b[i][j] == 0) {
                for (int x = 1; x <= n; x ++) a[i][x] = 0; // 让第i行全为0
                for (int y = 1; y <= m; y ++) a[y][j] = 0; // 让第j列全为0
            }
        }

    if (check()) {
        cout << "YES" << endl;
        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) 
                cout << !!a[i][j] << ' ';
            cout << endl;    
        }
    }
    else cout << "NO";

    return 0;
}

活动打卡代码 AcWing 4804. 构造矩阵

L-China
10小时前

                法一：
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int m, n;
int b[N][N], a[N][N];
bool flag;

int main() {
    cin >> m >> n;
    for (int i = 1; i <= m; i ++)
        for (int j = 1; j <= n; j ++) 
            cin >> b[i][j];

    memset(a, -1, sizeof a);

    for (int i = 1; i <= m; i ++) 
        for (int j = 1; j <= n; j ++) {
            if (b[i][j] == 0) {
                for (int x = 1; x <= n; x ++) // 行
                        a[i][x] = 0;
                for (int y = 1; y <= m; y ++) // 列
                        a[y][j] = 0;
            }
        }

    for (int i = 1; i <= m; i ++) 
        for (int j = 1; j <= n; j ++) {
            if (b[i][j] == 1) {
                flag = false;
                for (int x = 1; x <= n; x ++) // 行
                    if (a[i][x] == -1 || a[i][x] == 1) {
                        a[i][x] = 1;
                        flag = true;
                    }
                for (int y = 1; y <= m; y ++) // 列
                    if (a[y][j] == -1 || a[y][j] == 1) {
                        a[y][j] = 1;
                        flag = true;
                    }
                if (flag == false) {
                    cout << "NO";
                    return 0;
                }    
            }
        }    


    cout << "YES" << endl;
    for (int i = 1; i <= m; i ++) {
        for (int j = 1; j <= n; j ++) {
            cout << a[i][j] << ' '; 
        }
        cout << endl;
    }

    return 0;
}



法二：
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

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

bool check() {
    for (int i = 1; i <= m; i ++)
        for (int j = 1; j <= n; j ++)
            if (b[i][j]) {
                int cnt = 0;
                for (int x = 1; x <= n; x ++) cnt += a[i][x];
                for (int y = 1; y <= m; y ++) cnt += a[y][j];
                if (!cnt) return false;
            }
    return true;        
}

int main() {
    cin >> m >> n;

    memset(a, -1, sizeof a);
    for (int i = 1; i <= m; i ++) 
        for (int j = 1; j <= n; j ++) {
            cin >> b[i][j];
            if (b[i][j] == 0) {
                for (int x = 1; x <= n; x ++) a[i][x] = 0; // 让第i行全为0
                for (int y = 1; y <= m; y ++) a[y][j] = 0; // 让第j列全为0
            }
        }

    if (check()) {
        cout << "YES" << endl;
        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) 
                cout << !!a[i][j] << ' ';
            cout << endl;    
        }
    }
    else cout << "NO";

    return 0;
}

            

活动打卡代码 AcWing 4801. 强连通图

L-China
14小时前

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

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    string str;
    cin >> str;
    char a = str[0], c = str.back();
    cin >> str;
    char d = str[0], b = str.back();

    if (a == '>' && b == 'v' && c == '<' && d == '^' ||
        a == '<' && b == '^' && c == '>' && d == 'v')
        cout << "YES";
    else
        cout << "NO";

    return 0;
}

            

活动打卡代码 AcWing 4799. 最远距离

L-China
15小时前

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

using namespace std;

const int N = 1e5 + 10, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
int ans;

void add(int a, int b) { // 加边
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u, int fa) {
    int d1 = 0, d2 = 0; // d1:当前点距离叶节点的最大值 d2:当前点距离叶节点的次大值
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; // 当前点的子节点
        if (j == fa) continue; // 如果往上找，跳过
        int d = dfs(j, u) + 1;
        if (d >= d1) d2 = d1, d1 = d; // 更新最大值和次大值
        else if (d > d2) d2 = d;
    }

    ans = max(ans, d1 + d2); // 更新一下答案
    return d1; // 当前点距离叶节点的最大值
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++) {
        int a, b; cin >> a >> b;
        add(a, b), add(b, a);
    }

    dfs(1, -1);
    cout << ans;

    return 0;
}

            

活动打卡代码 AcWing 4798. 打怪兽

L-China
16小时前

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

using namespace std;

const int N = 1e3 + 10;

int n, m;
int w[N], q[N];

bool check(int mid) {
    memcpy(q, w, mid * 4);
    sort(q, q + mid, greater<int>());

    int sum = 0;
    for (int i = 0; i < mid; i += 2) { // 贪心
        sum += q[i];
        if (sum > m) return false;
    }

    return true;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i ++) cin >> w[i];

    int l = 0, r = n;
    while (l < r) { // 二分
        int mid = l + r + 1>> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    cout << r;

    return 0;
}

            

题解 AcWing 3418. 杨辉三角形(蓝桥杯12届（2021）C++ 组)

L-China
1天前

C++

$40分做法：$

思路：

$暴力$

$直接预处理出来前1000行的杨辉三角形，然后暴力枚举，找到x，输出即可$

$code1:$

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

using namespace std;

const int N = 1e3 + 10;

int n = 1000;
int a[N][N];

int main() {
    a[1][1] = 1;
    for (int i = 2; i <= n; i ++) // 预处理
        for (int j = 1; j <= i; j ++)
            a[i][j] = a[i - 1][j] + a[i - 1][j - 1];

    int x; cin >> x;

    int cnt = 0;
    for (int i = 1; i <= n; i ++) // 枚举
        for (int j = 1; j <= i; j ++) {
            cnt ++;
            if (a[i][j] == x) {
                cout << cnt;
                return 0;
            }
        }       
    return 0;
}

$50分做法：$

思路：

$推公式$

屏幕截图_20230203_211656.png

屏幕截图_20230203_195116.png

$code2:$

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

using namespace std;

typedef long long ll; 

int main() {
    ll n;
    cin >> n;
    cout << n * (n + 1) / 2 + 2;
    return 0;
}

$80分做法：$

思路：

$将上面两种方法相结合$

$code3:$

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

using namespace std;

const int N = 1e3 + 10;
typedef long long ll; 

int n = 1000;
int a[N][N];

int main() {
    ll x; cin >> x;
    if (x > 1000 * 999 / 2) {
        cout << x * (x + 1) / 2 + 2;
        return 0;
    }

    a[1][1] = 1;
    for (int i = 2; i <= n; i ++)
        for (int j = 1; j <= i; j ++)
            a[i][j] = a[i - 1][j] + a[i - 1][j - 1];

    ll cnt = 0;
    for (int i = 1; i <= n; i ++) 
        for (int j = 1; j <= i; j ++) {
            cnt ++;
            if (a[i][j] == x) {
                cout << cnt;
                return 0;
            }
        }       
    return 0;
}

$满分（100分）做法：$

思路：

二分

屏幕截图_20230203_205931.png

$code4:$

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

using namespace std;

typedef long long ll; 

int n; 

ll C(int a, int b) { // 求组合数函数 
    ll res = 1;
    for (int i = a, j = 1; j <= b; i --, j ++) {
        res = res * i / j;
        if (res > n) return res;
    }
    return res;
} 

bool check(int k) {
    ll l = k * 2, r = max(n, l);
    while (l < r) {
        ll mid = l + r >> 1;
        if (C(mid, k) >= n) r = mid;
        else l = mid + 1;
    }
    if (C(r, k) != n) return false;

    cout << r * (r + 1) / 2 + k + 1;

    return true;
}

int main() {
    cin >> n;
    for (int k = 16; ; k --)
        if (check(k))
            break;      
    return 0;
}

$ps：以上，皆为在蓝桥杯官网题库测试结果$

活动打卡代码 AcWing 3418. 杨辉三角形

L-China
1天前

C++

$40分做法：$

$code1:$

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

using namespace std;

const int N = 1e3 + 10;

int n = 1000;
int a[N][N];

int main() {
    a[1][1] = 1;
    for (int i = 2; i <= n; i ++) // 预处理
        for (int j = 1; j <= i; j ++)
            a[i][j] = a[i - 1][j] + a[i - 1][j - 1];

    int x; cin >> x;

    int cnt = 0;
    for (int i = 1; i <= n; i ++) // 枚举
        for (int j = 1; j <= i; j ++) {
            cnt ++;
            if (a[i][j] == x) {
                cout << cnt;
                return 0;
            }
        }       
    return 0;
}

$50分做法：$

$code2:$

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

using namespace std;

typedef long long ll; 

int main() {
    ll n;
    cin >> n;
    cout << n * (n + 1) / 2 + 2;
    return 0;
}

$80分做法：$

$code3:$

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

using namespace std;

const int N = 1e3 + 10;
typedef long long ll; 

int n = 1000;
int a[N][N];

int main() {
    ll x; cin >> x;
    if (x > 1000 * 999 / 2) {
        cout << x * (x + 1) / 2 + 2;
        return 0;
    }

    a[1][1] = 1;
    for (int i = 2; i <= n; i ++)
        for (int j = 1; j <= i; j ++)
            a[i][j] = a[i - 1][j] + a[i - 1][j - 1];

    ll cnt = 0;
    for (int i = 1; i <= n; i ++) 
        for (int j = 1; j <= i; j ++) {
            cnt ++;
            if (a[i][j] == x) {
                cout << cnt;
                return 0;
            }
        }       
    return 0;
}

$满分（100分）做法：$

$code4:$

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

using namespace std;

typedef long long ll; 

int n; 

ll C(int a, int b) { // 求组合数函数 
    ll res = 1;
    for (int i = a, j = 1; j <= b; i --, j ++) {
        res = res * i / j;
        if (res > n) return res;
    }
    return res;
} 

bool check(int k) {
    ll l = k * 2, r = max(n, l);
    while (l < r) {
        ll mid = l + r >> 1;
        if (C(mid, k) >= n) r = mid;
        else l = mid + 1;
    }
    if (C(r, k) != n) return false;

    cout << r * (r + 1) / 2 + k + 1;

    return true;
}

int main() {
    cin >> n;
    for (int k = 16; ; k --)
        if (check(k))
            break;      
    return 0;
}

$ps：以上，皆为在蓝桥杯官网题库测试结果$

题解 AcWing 796. 子矩阵的和

L-China
2天前

C++

$\color{#cc33ff}{— > 算法基础课题解}$

思路：

二维前缀和

$\color{blue}{模板}$

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]+ a[i][j]; // 求前缀和
s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);//算子矩阵的和

$求二维前缀和：图解$

屏幕截图_20230202_224250.png

$求子矩阵和：图解$

屏幕截图_20230202_230918.png

$二维前缀和：$

屏幕截图_20230202_224918.png

$时间复杂度：O(nm)$

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

using namespace std;

const int N = 1e3 + 10;

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

int main() {
    cin >> n >> m >> q;

    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] - s[i - 1][j - 1] + a[i][j]; // 前缀和
        }

    while (q --) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x1 -  1][y2] - s[x2][y1 - 1] + s[x1 -1][y1 - 1] << endl; // 子矩阵
    }    

    return 0;
}

0 评论

0 评论

C++

思路：

思路：

0 评论

法一：

法二：

0 评论

0 评论

0 评论

0 评论

C++

思路：

思路：

思路：

思路：

0 评论

C++

0 评论

C++

$\color{#cc33ff}{— > 算法基础课题解}$

思路：

0 评论