[Python知识库]暑假第三周学习笔记

周一

今天的主要精力在学python

感觉一些事情上还是没有达到自己的期望

但大学还是抱着学习的心态去努力汲取知识

做一块海绵 用这宝贵时光努力学习成长

周二

今天早上跑了步，出了很多汗，整个人都舒服很多

坚持锻炼

最近今天有点摸鱼，回归猛肝的状态

搞起

P3522 [POI2011]TEM-Temperature（单调队列）

这道题首先发现要维护之前的一个区间的最大值

而这个区间又是连续的，左右端点只会增加，就用单调队列

注意单调队列里面存的值是区间的部分值，所以更新的时候要注意不一定是队头的来更新

交上去WA了

因为是最大值，所以我就写了一个单调递减的单调队列，以往我都这么写

但是这道题不行，因为相等的时候元素不能删，这道题更新答案的时候和其位置有关，相等的时候并不是等价的

以前更新答案的时候是f(x)的形式，x同f(x)就同，而这题不一样。

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 1e6 + 10;
int dp[N], a[N], b[N], q[N], n;

int main()
{
    scanf("%d", &n);
    _for(i, 1, n) scanf("%d%d", &a[i], &b[i]);

    int l = 1, r = 1, ans = 1, first = 1;
    dp[1] = q[1] = 1;
    _for(i, 2, n)
    {
        while(l <= r && a[q[l]] > b[i])
        {
            l++;
            if(l <= r) first = q[l];
            else first = i;
        }

        dp[i] = i - first + 1;
        ans = max(ans, dp[i]);

        while(l <= r && a[q[r]] < a[i]) r--;
        q[++r] = i;
    }

    printf("%d\n", ans);

    return 0;
}

P4544 [USACO10NOV]Buying Feed G（单调队列优化dp）

很容易想到dp[i][j]表示前i个坐标j吨饲料的最小花费

一开始想枚举之前所有的坐标，来转移，发现这样很慢

直接前i个，枚举前面一个买或不买，买的话买多少。也就是说存在不买的情况。?

可以写出dp[i][j] = min(dp[i-1][j-t] * (x[i] - x[i - 1]) + t * c[i - 1])

0 <= t <= f[i - 1]

这样会超时，考虑单调队列优化

三层循环，i， j， t，显然优化第三层

然后我就卡住了，发现这样很难搞，我就把式子换了一下

dp[i-1][p] + j* j * (x[i] - x[i - 1]) + j * c[i - 1]?-?p?* c[i - 1]

发现j* j * (x[i] - x[i - 1]) + j * c[i - 1]对于当前的dp[i][j]来说是定值

而i定时，dp[i - 1][p] - p * c[i - 1]这个东西是可以用单调队列优化的

因为p有范围，且值只与p本身有关（i定值），与变化的j无关

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

typedef long long ll;
const int N = 500 + 10;
const int M = 1e4 + 10;
struct node { ll x, f, c; };
vector<node> ve;
int q[M], k, e, n;
ll dp[N][M];

bool cmp(node a, node b)
{
    return a.x < b.x;
}

ll val(int i, int p)
{
    return dp[i - 1][p] - p * ve[i - 1].c;
}

int main()
{
    scanf("%d%d%d", &k, &e, &n);
    _for(i, 1, n)
    {
        ll x, f, c;
        scanf("%lld%lld%lld", &x, &f, &c);
        ve.push_back(node{x, f, c});
    }
    ve.push_back(node{e, 0, 0});
    sort(ve.begin(), ve.end(), cmp);

     _for(j, 1, k) dp[0][j] = 1e18;
    rep(i, 1, ve.size())
    {
        _for(j, 0, k) dp[i][j] = 1e18;

        int l = 1, r = 0;
        _for(j, 0, k)
        {
            while(l <= r && val(i, q[r]) >= val(i, j)) r--;
            q[++r] = j;

            while(l <= r && j - ve[i - 1].f > q[l]) l++;
            dp[i][j] = min(dp[i][j], j * j * (ve[i].x - ve[i - 1].x) + j * ve[i - 1].c + val(i, q[l]));
        }
    }
    printf("%lld\n", dp[ve.size() - 1][k]);

    return 0;
}

P3572 [POI2014]PTA-Little Bird（单调队列）

逐渐进入状态

这题依然是单调队列

因为取最小的是dp值，所以按照dp值的大小来构造单调队列

这里的高度要注意

首先dp值小但高度更低也没有关系，这样结果至少不会更差

做单调队列的题目时要考虑是否可以相等的问题

这道题相等的时候要格外考虑，dp值相同时就按照高度

如果dp值相同，高度小，又在更左边，那就出队

此外，写单调队列先初始化，先把第一个点入队，再弄

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 1e6 + 10;
int h[N], dp[N], q[N], n, m, k;

int main()
{
    scanf("%d", &n);
    _for(i, 1, n) scanf("%d", &h[i]);

    scanf("%d", &m);
    while(m--)
    {
        scanf("%d", &k);

        int l = 1, r = 1;
        q[1] = 1; dp[1] = 0;
        _for(i, 2, n)
        {
            while(l <= r && q[l] < i - k) l++;
            dp[i] = dp[q[l]] + (h[q[l]] <= h[i]);

            while(l <= r && (dp[q[r]] > dp[i] || dp[q[r]] == dp[i] && h[q[r]] < h[i])) r--;
            q[++r] = i;
        }
        printf("%d\n", dp[n]);
    }

    return 0;
}

P3089 [USACO13NOV]Pogo-Cow S（状态设计与枚举顺序）

这题是看题解的

首先这个状态设计我就没想到，dp[j][i]表示从j跳到i的最大值

感觉就挺突然的………………还是太菜了

转移方程很好写 dp[j][i] = max(p[i] + dp[k][j]) = p[i] + max(dp[k][j])
考虑怎么优化，一开始想单调队列优化k，发现不行

因为在j移动的时候，dp[k][j]和j有关。这个值应该和移动j无关才行

然后我就卡住了

看了题解，真的妙，按照常规思维是先枚举i后枚举j

这里改成先枚举j后枚举i，这样子dp[k][j]的时候，就与移动i无关了

可以发现，固定j的时候，i逐渐增大，可以用来转移的dp[k][j]只会增加不会减少

因此就用一个变量来维护就行了

这题还要换个方向，这时其实很容易，把整个数组翻转一下再做一次就行了

#include <bits/stdc++.h>
#define x first
#define p second
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 1e3 + 10;
int dp[N][N], ans, n;
pair<int, int> a[N];

void solve()
{
    _for(j, 1, n)
    {
        dp[j][j] = a[j].p;
        int mx = dp[j][j], k = j;
        _for(i, j + 1, n)
        {
            while(k - 1 >= 1 && abs(a[k - 1].x - a[j].x) <= abs(a[i].x - a[j].x)) mx = max(mx, dp[--k][j]);
            dp[j][i] = a[i].p + mx;
        }
    }

    _for(j, 1, n)
        _for(i, j, n)
            ans = max(ans, dp[j][i]);
}

int main()
{
    scanf("%d", &n);
    _for(i, 1, n) scanf("%d%d", &a[i].x, &a[i].p);
    sort(a + 1, a + n + 1);

    solve();
    reverse(a + 1, a + n + 1);
    solve();
    printf("%d\n", ans);

    return 0;
}

?D - Meaningless Sequence（数位dp）

接下来刷几道数位dp

数位dp无非是问一个区间内有多少个符合题目条件的数

每个数都有个值，如果问个数则值为1，问其他的看题目

这道题可以发现每个数的值就是c^（1的个数）

数位dp套模板就行

模板还是要深刻理解比较好。无非是lead 和 limit 记忆化搜索

这道题前导0，是否为第一位等无所谓

所以不需要lead

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

typedef long long ll;
const int N = 3000 + 10;
const int mod = 1e9 + 7;
ll dp[N][N], c;
int len;
string a;

int add(int a, int b) { return (a + b) % mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }

int binpow(int a, int b)
{
    int res = 1;
    for(; b; b >>= 1)
    {
        if(b & 1) res = mul(res, a);
        a = mul(a, a);
    }
    return res;
}

int dfs(int pos, int sum, int limit)
{
    if(pos >= len) return binpow(c, sum);
    if(!limit && dp[pos][sum] != -1) return dp[pos][sum];
    ll res = 0, mx = limit ? (a[pos] - '0') : 1;
    _for(i, 0, mx) res = add(res, dfs(pos + 1, sum + i, i == mx && limit));
    if(!limit) dp[pos][sum] = res;
    return res;
}

int main()
{
    cin >> a >> c;
    len = a.size();
    memset(dp, -1, sizeof dp);
    printf("%d\n", dfs(0, 0, 1));
    return 0;
}

P4999 烦人的数学作业（数位dp）

挺水的。这道题的值是每个数字之和

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

typedef long long ll;
const int mod = 1e9 + 7;
int dp[25][200], a[25], len;

int add(int a, int b) { return (a + b) % mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }

int dfs(int pos, int sum, int limit)
{
    if(pos > len) return sum;
    if(!limit && dp[pos][sum] != -1) return dp[pos][sum];
    int res = 0, mx = limit ? a[len - pos + 1] : 9;
    _for(i, 0, mx) res = add(res, dfs(pos + 1, sum + i, i == mx && limit));
    if(!limit) dp[pos][sum] = res;
    return res;
}

int solve(ll x)
{
    len = 0;
    while(x) a[++len] = x % 10, x /= 10;
    memset(dp, -1, sizeof dp);
    return dfs(1, 0, 1);
}

int main()
{
    int T; scanf("%d", &T);
    while(T--)
    {
        ll l, r;
        scanf("%lld%lld", &l, &r);
        printf("%d\n", (solve(r) - solve(l - 1) + mod) % mod);
    }
    return 0;
}

P4124 [CQOI2016]手机号码（数位dp）

一样套模板，只是复杂了一点

注意要特判一下

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

typedef long long ll;
ll dp[25][15][15][2][2][2], a[25], len;

ll dfs(int pos, int pre1, int pre2, int have4, int have8, int ans, int lead, int limit)
{
    if(pos > len) return ans;
    if(!limit && !lead && dp[pos][pre1][pre2][have4][have8][ans] != -1) return dp[pos][pre1][pre2][have4][have8][ans];
    ll res = 0, mx = limit ? a[len - pos + 1] : 9;
    _for(i, 0, mx)
    {
        if(!i && lead || i == 4 && have8 || i == 8 && have4) continue;
        res += dfs(pos + 1, i, pre1, have4 | i == 4, have8 | i == 8, ans | (i == pre1 && pre1 == pre2), 0, i == mx && limit);
    }
    if(!limit && !lead) dp[pos][pre1][pre2][have4][have8][ans] = res;
    return res;
}

ll solve(ll x)
{
    len = 0;
    while(x) a[++len] = x % 10, x /= 10;
    memset(dp, -1, sizeof dp);
    return dfs(1, 10, 10, 0, 0, 0, 1, 1);
}

int main()
{
    ll l, r;
    scanf("%lld%lld", &l, &r);
    if(l == 1e10) printf("%lld\n", solve(r));
    else printf("%lld\n", solve(r) - solve(l - 1));
    return 0;
}

P2606 [ZJOI2010]排列计数（dp统计方案数）

首先把这道题转化到图上

有多少种小根堆的方案

用dp[u]表示以u为根节点的子树有多少种方案

这时我们把最小的数放在u

左子树放一部分，数目是左子树的节点数，剩下的放右子树

这样dp[u] = C(size[u] - 1, size[l]) * dp[l] * dp[r]

用dfs遍历就行 注意边界条件是当这个点为叶子的时候返回1

这里有坑，就是模数可能比较小,可能求组合数的时候n n - m是模数的倍数

这样就不能用费马小定理。解决方法是Lucas 定理

不用考虑具体怎么放，总之就是当前数最小的放在根，然后递归下去

#include <bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 1e6 + 10;
int fac[N], siz[N], n, mod;

int add(int a, int b) { return (a + b) % mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }

int binpow(int a, int b)
{
    int res = 1;
    for(; b; b >>= 1)
    {
        if(b & 1) res = mul(res, a);
        a = mul(a, a);
    }
    return res;
}

int inv(int x) { return binpow(x, mod - 2); }

void init(int u)
{
    siz[u] = 1;
    if(l(u) <= n) init(l(u)), siz[u] += siz[l(u)];
    if(r(u) <= n) init(r(u)), siz[u] += siz[r(u)];
}

int cal(int n, int m)
{
    if(m > n) return 0;
    return mul(fac[n], mul(inv(fac[m]), inv(fac[n - m])));
}

int C(int n, int m)
{
    if(m == 0) return 1;
    return mul(cal(n % mod, m % mod), C(n / mod, m / mod));
}

int dfs(int u)
{
    if(l(u) > n) return 1;
    return mul(mul(C(siz[u] - 1, siz[l(u)]), dfs(l(u))), dfs(r(u)));
}

int main()
{
    scanf("%d%d", &n, &mod);
    fac[0] = 1; _for(i, 1, n) fac[i] = mul(fac[i - 1], i);
    init(1);
    printf("%d\n", dfs(1));
    return 0;
}