题目单, wls, 博客

A - 九进制转十进制

思路

进制转换没什么好说的

代码

#include <iostream>

using namespace std;

int main() {
    int n = 2022;
    int t = 1;
    int ans = 0;
    while (n) {
        ans += (n % 10) * t;
        n /= 10;
        t *= 9;
    }
    cout << ans << endl;
    return 0;
}

B - 顺子日期

思路

手算还是很简单的, 毕竟月和日都是非常小的数
012 算or不算?

20221012
2022012 + 0 … 9

2022123 + 0 … 1
20220123
程序就不写了.. 太麻烦

C - 刷题统计

思路

应该是要数学题, 那么一周就可以做$5 \cdot a + 2 \cdot b$道题目

然后就是剩余题目的计算, 要注意向上整除

代码

#include <iostream>

using namespace std;
typedef long long LL;

int main() {
    LL a, b, c;
    cin >> a >> b >> c;
    LL ans = c / (a * 5 + b * 2) * 7;
    c %= (a * 5 + b * 2);
    if (c <= a * 5) ans += (c + a - 1) / a;
    else {
        ans += 5;
        ans += (c - a * 5 + b - 1) / b;
    }
    cout << ans << endl;
    return 0;
}

D - 修剪灌木

思路

看起来只是一道思维题目, 对于某一个位置x来说, 他的最大值应该出现在以下情况内
+ 爱丽丝从最左边走过来
+ 爱丽丝经过之后走到最右边折返
+ 爱丽丝第二次经过后, 走到最左边折返

所以说我们找一下最大值即可

代码

#include <iostream>

using namespace std;
typedef long long LL;

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) {
        cout << max(i, max((i - 1) * 2, (n - i) * 2)) << endl;
    }
    return 0;
}

E- X 进制减法

思路

贪心没跑了, 那么就是如何贪

.. 看题解把

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long LL;

const int mod = 1e9 + 7;

int n, m1, m2;
vector<int> a, b;

int main() {
    cin >> n;
    cin >> m1;
    for (int i = 0; i < m1; i ++ ) {
        int x;
        cin >> x;
        a.push_back(x);
    }
    cin >> m2;
    for (int i = 0; i < m2; i ++ ) {
        int x;
        cin >> x;
        b.push_back(x);
    }
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    LL ans = 0;
    LL t = 1;
    for (int i = 0; i < m1; i ++ ) {
        int p = max(2, a[i] + 1);
        if (i < m2) p = max(p, b[i] + 1);

        ans = (ans + (a[i] - (i < m2 ? b[i] : 0)) * t) % mod;
        t = t * p % mod;
    }
    cout << ans << endl;
    return 0;
}

F - 统计子矩阵

思路

$n^4$的做法大家应该都能想到: 二维前缀和 + DP
但是$500^4 == 6.25e10$必T

其中很多都是不必要枚举的: 如果一个矩阵的和小于k, 那么该矩阵的所有子矩阵都是满足条件的
枚举方式的话不太好想, 这里直接说了: 我们固定上两个行(两个for), 然后双指针枚举两个列l和r, 直到这两个列中间的值>k时, 记录答案, 对于下一个列l + 1来说, 此时的r也是满足条件的

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 510, mod = 1e9 + 7;

LL n, m, k;
LL a[N][N];

LL get(int x, int y, int p, int q) {
    return a[x][y] - a[x][q - 1] - a[p - 1][y] + a[p - 1][q - 1];
}

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

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

    LL ans = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = i; j <= n; j ++ )
            for (int l = 1, r = 1; l <= m; l ++ ) {
                while (r <= m && get(j, r, i, l) <= k) r ++;
                ans += r - l;
                // cout << i << ' ' << l << ' ' << j << ' ' << r << ' ' << get(i, l, j, r) << endl;
            }
    cout << ans << endl;
    return 0;
}

G - 积木画

思路

图解

代码

#include <iostream>

using namespace std;
typedef long long LL;

const int N = 1e7 + 10, mod = 1e9 + 7;

LL n;
LL dp[N];

int main() {
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 5;
    cin >> n;
    for (int i = 4; i <= n; i ++ )
        dp[i] = (2 * dp[i - 1] + dp[i - 3]) % mod;
    cout << dp[n] << endl;
    return 0;
}

H - 扫雷

思路

对于他们的并查集我不是很理解, 如果对于炸弹A和B, A可以影响B, 但是B不可以影响A呢?

I - 李白打酒加强版

J - 砍竹子