头像

AreyouOK




离线:3天前


最近来访(9)
用户头像
xiayutao
用户头像
垫底抽風
用户头像
浩然正气
用户头像
金属
用户头像
油泼面
用户头像
triumph_4


C++ 代码

/*
先不管L, 十进制拆分.
考虑答案统计的形式
例子:51923
0....
1....
2....
3....
4....
50...
510..
511..
...
51923
以50...为例,
设...=a,a的各位之和为y
应统计所有满足以下条件的a的数量:
(50000 + a) % m == 0
其中m = 5 + y
原式变为 a % m == -(50000 % m)
有个小结论:-(a % m) === (-a) % m (mod m)
所以,
a === -50000 (mod m)
此时,满足该条件的正整数a的个数即为所求.
根据上述的关键信息,
记 F[i, y, m, r]为位数为i,模m余数为r, 各个位的数字加起来位y的正整数的个数.
F[i, y, m, r] =
枚举0<=x<=9, 0<=x<=y:
累加: F[i - 1, y - x, m, (r - (-x)*10^(i - 1)) % m]
最终答案为
1~R的月之数 - 1~L-1的月之数

总结:
第一次写数位dp,要注意上下界的问题,如果实在不确定,可以全写成常数
(只不过可能爆0),一定不要随便剪枝。
*/

#include <iostream>
#include <cstdio>
#include <cmath>

#define int long long

namespace io {
    inline int read() {
        char ch = getchar(); int flag = 1, ans = 0;
        while (ch < '0' || ch > '9') { if (ch == '-') flag = -1; ch = getchar(); }
        while (ch >= '0' && ch <= '9') ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
        return flag * ans;
    }
    inline void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace std;
using namespace io;

typedef long long ll;

const int INF = 2147483647;

int L, R;
int f[13][83][83][83];
int fac[13];

int getnum(int x) {
    int res = 0;
    while (x) { 
        res += x % 10;
        x /= 10;
    }
    return res;
}

int query(int X) {
    if (X == 0) return 0;
    int ans = 0, x = 0, n = log10(X);
    for (int i = n; i >= 0; i--) {
        int tmp = X / fac[i];
        int num = getnum(x);
        while (x < tmp) {
            for (int y = num == 0 ? 1 : 0; y <= 9 * i; y++) {
                int m = num + y;
                int r = ((-x) * fac[i] + m * INF) % m;      // 不要漏了这里的*fac[i](并且不是fac[i - 1])
                ans += f[i][y][m][r];
            }
            x++, num++;
        }
        x *= 10;
    }
    if (X % getnum(X) == 0) ans++;      // 还有R本身满足的情况(注意不是无条件的)
    return ans;
}

signed main() {
    L = read(), R = read();
    int n = log10(R);

    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * 10;

    for (int m = 1; m <= 81; m++)                       // 注意这里m的上限不是9*n
        f[0][0][m][0] = 1;

    for (int i = 1; i <= n; i++)
        for (int y = 0; y <= 9 * n; y++)
            for (int m = fmax(1, y); m <= 81; m++)      // 注意这里m的上限不是9*n,因为这个错了很久
                for (int r = 0; r < m; r++)
                    for (int x = 0; x <= 9 && x <= y; x++) {
                        int r_ = (r - x * fac[i - 1] + m * INF) % m;
                        f[i][y][m][r] += f[i - 1][y - x][m][r_];
                    }

    write(query(R) - query(L - 1));

    return 0;
}


活动打卡代码 AcWing 4501. 收集卡牌

AreyouOK
1个月前
/*
其实兑换的次数不会太多, 所以可以大胆遍历计数器.
至多每n次遍历一次, 共m/n次, 每次遍历O(n)
O(m/n * n) = O(m)
*/

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 100010;

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

int main() {
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i++) {
        scanf("%d", &a);
        b[a]++;
        if (b[a] == 1) variety++;
        if (variety == n) {
            variety = 0;
            printf("1");
            for (int j = 1; j <= n; j++) {
                b[j]--;
                if (b[j]) variety++;
            }
        } else
            printf("0");
    }

    return 0;
}


活动打卡代码 AcWing 4500. 三个元素

AreyouOK
1个月前
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 3010;

struct Node {
    int val, id;
    friend bool operator < (Node a, Node b) {
        return a.val < b.val;
    }
} r[N];

int n;
queue<int> q;

int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &r[i].val);
        r[i].id = i;
    }

    sort(r + 1, r + n + 1);

    int last = -1;
    for (int i = 1; i <= n; i++) {
        if (r[i].val != last) q.push(r[i].id);
        last = r[i].val;
        if (q.size() == 3) break;
    }

    if (q.size() < 3)
        for (int i = 1; i <= 3; i++) printf("-1 ");
    else
        while (q.size()) {
            printf("%d ", q.front());
            q.pop();
        }   

    return 0;
}



AreyouOK
2个月前

细节

记得数组开大一点, 防止MLE, 还可以压缩一下.

C++ 代码

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 30010, M = 2010;

int n, m, v[N], w[N], f[M], cnt;

int main() {
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++) {
        int tmp_v, tmp_w, tmp_s;
        scanf("%d%d%d", &tmp_v, &tmp_w, &tmp_s);

        for (int bin = 1; bin <= tmp_s; bin <<= 1) {
            tmp_s -= bin;
            v[++cnt] = tmp_v * bin, w[cnt] = tmp_w * bin;
        }
        if (tmp_s > 0) {
            v[++cnt] = tmp_v * tmp_s, w[cnt] = tmp_w * tmp_s;
        }
    }

    for (int i = 1; i <= cnt; i++) {
        for (int j = m; j >= v[i]; j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    printf("%d", f[m]);

    return 0;
}


活动打卡代码 AcWing 4496. 吃水果

AreyouOK
2个月前
#include <cstdio>

using namespace std;

const int N = 2010, MOD = 998244353;

int n, m, k, f[N][N];

int main() {

    scanf("%d%d%d", &n, &m, &k);

    // 边界条件
    for (int i = 1; i <= n; i++) f[i][0] = m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k && j < i; j++) {
            f[i][j] = (f[i - 1][j] + f[i - 1][j - 1] * (m - 1ll)) % MOD;
        }
    }

    printf("%d", f[n][k]);


    return 0;
}


活动打卡代码 AcWing 4495. 数组操作

AreyouOK
2个月前
#include <cstdio>
#include <algorithm>

using namespace std;

int n, k, a[100010], b[100010];

int main() {

    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }

    sort(a + 1, a + 1 + n);

    int j = 1, s = 0;
    while (k--) {
        printf("%d\n", a[j] - s < 0 ? 0 : a[j] - s);

        s += a[j] - s;

        while (a[j] - s <= 0 && j <= n) j++;
    }


    return 0;
}


活动打卡代码 AcWing 4494. 吃饭

AreyouOK
2个月前
#include <cstdio>

int main() {
    int n, m, k;

    scanf("%d%d%d", &n, &m, &k);

    if (m >= n && k >= n) printf("Yes");
    else printf("No");

    return 0;
}


活动打卡代码 AcWing 4491. 数组操作

AreyouOK
2个月前
#include <iostream>
#include <cstdio>

using namespace std;

int n, s, x, tmp;

int main() {
    scanf("%d", &n);

    while (n--) {
        scanf("%d", &tmp);

        s += tmp;
        if (s < x) x = s;
    }

    printf("%d", s - x);

    return 0;
}



AreyouOK
2个月前
思路

$f[i][j]$表示在前i个小朋友中,有j个与左边不相等的方案数

$a[i]$表示第i位的水果种类
计算$f[i][j]$
考虑第i位,若$a[i] == a[i - 1]$, 那么有$f[i - 1][j]$种.
若$a[i] != a[i - 1]$, 对于每一种前i-1个的方案,第i位有m-1种
填发(当时还在m和m-1间徘徊,感觉自己像个…)
$f[i][j] = f[i - 1][j] + f[i - 1][j - 1] * (m - 1)$

另外,还可以把数组压成一维(我不写啦).
这题可以不开long long,但计算乘法时要强转.

C++ 代码

#include <cstdio>

using namespace std;

const int N = 2010, MOD = 998244353;

int n, m, k, f[N][N];

int main() {

    scanf("%d%d%d", &n, &m, &k);

    // 边界条件
    for (int i = 1; i <= n; i++) f[i][0] = m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k && j < i; j++) {
            f[i][j] = (f[i - 1][j] + f[i - 1][j - 1] * (m - 1ll)) % MOD;
        }
    }

    printf("%d", f[n][k]);


    return 0;
}



AreyouOK
2个月前

方法

没有用差分(不会)
用了一个s来记录累计减去的量.

C++ 代码

#include <cstdio>
#include <algorithm>

using namespace std;

int n, k, a[100010], b[100010];

int main() {

    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }

    sort(a + 1, a + 1 + n);

    int j = 1, s = 0;
    while (k--) {
        printf("%d\n", a[j] - s < 0 ? 0 : a[j] - s);

        s += a[j] - s;

        while (a[j] - s <= 0 && j <= n) j++;
    }


    return 0;
}