Running-Turtle

My blogs

0%

发表于 更新于 分类于

AOT 与 JIT

JIT AOT
Just-in-Time, 实时编译 Ahead-of-Time，预编译或提前编译
Java跨平台的基础 无法跨平台

AOT的优点

  • 启动和运行的速度快（传统SpringBoot空项目启动时间大概是2秒，AOT的启动时间大概是100毫秒）

  • 打包体积小

AOT的缺点

  • 编译后的程序不支持跨平台

  • 不支持动态功能，如 AOP（面向切面编程，Aspect Oriented Programming)

JIT在高并发中的生产问题现象

现象： 热点应用重启后，出现业务超时，几分钟后恢复正常

解决方法：

  • 预热： 初始让程序自动运行热点代码几百次

  • 流量控制： 启动时小流量，运行几分钟后逐步放到正常流量

GraalVM代替JDK实现AOT

GraralVM 同样出自于 Oracle。它是一个跨语言的通用虚拟机，不仅支持了 Java、Scala、Groovy、Kotlin等基于 JVM 的语言，以及 C、C++等基于 LLVM 的语言，还支持其他像 JavaScipt、Ruby、Rust、Python 和 R 语言等。

发表于 分类于

Codeforces Round 997 (Div. 2)

A

求的是 perimeter, 看成 area 了。

一道 A 卡了 26 min

B

思路跟答案完全不一样。

C

用样例构造答案过了。没看正解

D

做了很久，推了个式子最后发现不能用。

正难则反，考虑用 $\frac {n*(n+1)} 2$ 来减掉不合法的方案数。

假设一个连续子数组中 $\leq x$ 的数为 $-1$ , $>x$ 的数为 $1$ 。

那么如果这个连续子数组的和为 0，这个数组就是一个不合法数组。

首先这么构造一定排除了奇数。对于偶数来讲，会把 $x$ 正好卡到 $\frac {len} 2$ 的位置，且 $\frac{len} 2 + 1$ 正好是 $>x$ 的数。

然后枚举 $x$ ，维护前缀和快速求 $s_{j\sim i}=0$ 的数量。

注意对于 [1, 2, 6, 6] 这个不合法数组会在 $2\leq x\leq 6$ 时各被算一遍答案。

我们考虑只在遇到 $a_i=x$ 时再添加前缀和。

这样枚举到区间和为 0 的，一定就包含了 $x$ ，且 $x$ 是 -1 中的最大元素，就一定保证这个数是被按照 $x$ 来计数的。

参考题解 : Codeforces Round 997 (Div. 2) - maburb - 博客园 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void solve(){
    int n;
    cin >> n;

    vector<int> a(n + 1);
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
    }

    int ans = n * (n + 1) / 2;
    for(int x = 1; x <= 10; x ++) {
        vector<int> sum(n + 1);
        for(int i = 1; i <= n; i ++) {
            sum[i] = sum[i - 1] + (a[i] <= x ? -1 : 1);
        }

        vector<int> cnt(2 * n + 1);
        for(int i = 1, j = 0; i <= n; i ++) {
            if(a[i] == x) {
                while(j < i) {
                    cnt[sum[j] + n] ++;
                    j ++;
                }
            }
            ans -= cnt[sum[i] + n];
        }
    }

    cout << ans << '\n';
}

2025-01-17 22-33-03 div2_哔哩哔哩_bilibili

发表于 分类于

没有必要顺着做，讲完树形DP的几道题目就可以讲树上背包的内容然后做树上背包的题，最后尽量做这个题单就可以，如果没做完题单把剩的题标记一下，如果有补充的新题也可以记录一下发我，尽量让学生自己想出来正确的状态和转移，或者给他们指出来为什么他们想的是错的。

10:30–12:15

下午1:30–5:15

树形背包、树形DP是什么，以及树上背包题单

树形DP 树上背包 DAG上的DP

P1352 没有上司的舞会 树形DP √

https://www.luogu.com.cn/problem/P1352

状态表示

  • f[u][1] 表示以 u 为根节点的子树并且包括 u 的总快乐指数

  • f[u][0] 表示以 u 为根节点的子树并且不包括 u 的总快乐指数

状态计算

  • 选 u , $f[u][1]+=\sum f[son][0]$

  • 不选 u , $f[u][0]+=\sum max(f[son][1],;f[son][0])$

1
2
3
4
5
6
7
8
9
void dfs(int u){
    f[u][1]=r[u];
    for(int i=h[u]; i!=-1; i=ne[i]){
        int v=e[i];
        dfs(v);
        f[u][0]+=max(f[v][1], f[v][0]);
        f[u][1]+=f[v][0];
    }
}

通过 DFS，在返回上一层时更新当前结点的最优解。

、、树形DP经典题目。

、、$dp_{u,0/1}$ 代表是否选节点 u，以节点 u 为根的子树能得到的最大快乐值。

P4084 USACO17DEC] Barn Painting G 树形 DP √

https://www.luogu.com.cn/problem/P4084

n 个结点的树，k 个结点染色了，剩下的结点每个可以染色 3 种，求最终方案数 ？

设 $dp_{u,0/1/2}$ 表示以 u 为根的子树，染色为 0/1/2 的方案数。

$dp_{u,c}*=dp_{v,1/2/3}$ ，注意染色不能相同，注意初始化问题

P2016 战略游戏 树形DP√

最少点覆盖所有边问题

$dp_{u,0/1}$ 表示以 u 为根的子树，是否选择在 u 点布置士兵，覆盖子树所有边的最小方案数。

P1122 最大子树和 树形DP √

求最大子树和

设 $dp_u$ 是以 u 为根的最大子树，那么答案一定是 $\max dp_i$

注意这里答案不一定是 $dp_1$ 。

对于以根 r 为根的树来说，答案的联通块一定是以其中某一个点作为根节点的包括一部分点的子树、所以可以枚举 $dp_i$ 。

P3478 换根DP例题 √

换根DP入门文章

https://zhuanlan.zhihu.com/p/2084665478 有详细讲换根DP。

P2986 换根DP应用 √

先考虑 f, $cow_u$ 表示 $T_1$ 中以 u 为根的奶牛的数量之和。

$f_u=\sum(f_v + w\times cow_v)$

$g_v=g_u-cow_v\times w + (sumCow-cow_v)\times w$

CF1689C 思维 + 树形DP √

acyclic 无环的

Problem - 1689C - Codeforces

可以发现题目给定的是一个二叉树。

设 $dp_u$ 表示以 u 为根的子树，u 感染了，最多 save 几个。

若 $out_u=1$ , 拯救 $son_u-2$ 个（删儿子）

若 $out_u=0$ , 0 个

若 $out_u=2$ ，删左儿子或者右儿子

CF1092F 换根DP , 基础换根的式子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs1(int u, int fa) {
    sa[u] = a[u];
    for(int v : e[u]) {
        if(v == fa) continue ;
        dfs1(v, u);
        sa[u] += sa[v];
        f[u] += f[v] + sa[v];
    }
}

void dfs2(int u, int fa) {
    for(int v : e[u]) {
        if(v == fa) continue ;
        g[v] = g[u] + suma - 2 * sa[v];
        dfs2(v, u);
    }
}

CF1693B

P2052 道路修建 树形DP √

设 $son_u$ 表示以 $u$ 为根的子树有多少个点。

对于道路 $(u,v,w)$ ，u 为父节点，费用是 $w*|(n-son_v)-son_v|$ 。

CF120F

P2015 树形背包例题二 √

读题。以 1 为根的子树。

对于 (u,v), 选择 v，就得选择 u，所以树形背包，就是有依赖的一种树形DP。

设 $f_{u,x}$ 表示以 u 为根的苹果树，保留 x 个枝条的最大苹果树。

先枚举 x，对于每个 v 点，类似于 01 背包，枚举每个点的决策-即每个点选多少个体积来用，

所以 $f_{u,x}=max(f_{v,s}+f_{u,x-s},f_{u,x})$ ，这是一般的树形背包的形式，本题保留的树枝，想让 u 跟 v 连接，至少保留一根树枝。

$f_{u,x}=\max(f_{u,x},f_{v,s}+f_{u,x-s})$ 。

CF212E

AT_abc287_f

AT_abc207_f

CF815C

P1272 树形背包题目 √

https://blog.csdn.net/weixin_72060925/article/details/129442749

设 $f_{u,x}$ 表示保留以 u 为根的子树的 x 个点，最少删多少条边。

$f_{u,1}=e_u.size()$ ，即删除该点的所有出边以及其与父节点的边。

$f_{u,i}=\min (f_{u,i},(f_{v,j}-1)+(f_{u,i-j}-1))$ 。

为什么 -1，$f_{v,j}$ 表示删边的时候，默认删除了 $(u,v)$ ，对于 $f_{u,i-j}$ 同理。即它们的值都多算了 1，所以需要减一。

$\text{res}=\min_i f_{i,P}$

在这里插入图片描述 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * f[u][i] 表示以 u 为根的子树, 保留 i 个点, 最少删除多少条边 ?
 */

void dfs(int u, int fa) {
    son[u] = 1;
    f[u][1] = (int)(e[u].size()); // 只保留 u, 需要删多少边
    for(int v : e[u]) {
        if(v == fa) continue ;
        dfs(v, u);
        son[u] += son[v];
        for(int i = son[u]; i >= 1; i --) {
            for(int j = 1; j <= son[v] && j < i; j ++){
                f[u][i] = min(f[u][i], (f[u][i - j] - 1) + (f[v][j] - 1));
            }
        }
    }
}

void solve(){
    cin >> n >> P;
    for(int i = 1; i < n; i ++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= n; j ++) {
            f[i][j] = 1E9;
        }
    }

    dfs(1, 0);

    int res = 2E9;
    for(int i = 1; i <= n; i ++){
        res = min(res, f[i][P]);
    }
    cout << res;
}

补充题目

有依赖的背包问题 树形背包例题引入√

10. 有依赖的背包问题 - AcWing题库

作为树上背包的模板例题引入。

发表于 分类于 ，

单调栈

模板

单调栈，可以用来求 左边/右边 第一个 大于/小于/大于等于/小于等于 当前元素的下标的位置。

模板说明 ：

1，求左边 ：从左往右遍历 ；求右边 ：从右往左遍历

2，求 < a[i] 的元素 ：维护严格递增的单调栈,   a[i] <= top 作为出栈条件

求 <= a[i] 的元素 : 维护非严格递增的单调栈, a[i] <  top 作为出栈条件

求 > a[i]  的元素 : 维护严格递减的单调栈,   a[i] >= top 作为出栈条件

求 >= a[i] 的元素 : 维护非严格递减的单调栈, a[i] >  top 作为出栈条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 左边第一个 < a[i] 的下标
vector<int> LeftAndStrictlyLess(int* a, int n) {
    vector<int> lf(n + 1);
    stack<int> stk;
    for(int i = 1; i <= n; i ++) {
        while(stk.size() && a[i] <= a[stk.top()]) {
            stk.pop();
        }
        lf[i] = (stk.size() ? stk.top() : -1);
        stk.push(i);
    }
    return lf;
}

// 右边第一个 < a[i] 的下标
vector<int> RightAndStrictlyGreater(int *a, int n) {
    vector<int> rt(n + 1);
    stack<int> stk;
    for(int i = n; i >= 1; i --) {
        while(stk.size() && a[i] <= a[stk.top()]) {
            stk.pop();
        }
        rt[i] = (stk.size() ? stk.top() : -1);
        stk.push(i);
    }
    return rt;
}

单调栈与DP结合

例题一 ：907. 子数组的最小值之和 - 力扣（LeetCode）

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7 。

因为是连续子数组，考虑每个点作为右端点的所有连续子数组的 min(b) 的总和，设为 $f(x)$ 。

发现对于位置 $i$ 的元素 $a_i$ 来说，设 $lf(i)$ 表示 $a_i$ 左边第一个 $<a_i$ 的元素的位置。那么 $[lf(i)+1,i]$ 作为左端点时，min(b) 都是 $a_i$ ，因为 $a_i$ 大于等于这些元素。对于 $lf(i)$ 及其左边的位置，发现答案就是 $f(lf(i))$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    const int MOD = 1E9 + 7;
    vector<int> RightAndStrictlyGreater(vector<int> a, int n) {
        vector<int> rt(n);
        stack<int> stk;
        for(int i = 0; i < n; i ++) {
            while(stk.size() && a[i] <= a[stk.top()]) {
                stk.pop();
            }
            rt[i] = (stk.size() ? stk.top() : -1);
            stk.push(i);
        }
        return rt;
    }

    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        vector<int> f(n, 0);
        vector<int> lf = RightAndStrictlyGreater(arr, n);
        for(int i = 0; i < n; i ++) {
            if(lf[i] != -1) f[i] += f[lf[i]];
            (f[i] += (i - lf[i]) * arr[i]) %= MOD;
        }
        int res = 0;
        for(int i = 0; i < n; i ++) {
            // cout << i << ' ' << lf[i] << ' ' << f[i] << '\n';
            (res += f[i]) %= MOD;
        }
        return res;
    }
};

经典 Trick 悬线法

例题一 : 84. 柱状图中最大的矩形 - 力扣（LeetCode）

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

这个问题比较显然，作为例题二的引入。

显然对于答案的矩形来说，它的高一定是其中一个柱子的高，因为如果比所有柱子都矮，答案还可以加一。

那么对于每个柱子 $h_i$ ，我们维护每个柱子左边第一个 $<h_i$ 的位置 $lf(i)$ ，右边第一个 $>h_i$ 的位置 $rt(i)$ 。

那么对于柱子 $i$ ，他就可以跟 $[lf(i)+1,rt(i)-1]$ 的这些位置的柱子结合为一个矩形，高度为 $h_i$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> lf(n), rt(n);
        stack<int> stk;
        for(int i = 0; i < n; i ++) {
            while(stk.size() && heights[i] <= heights[stk.top()]) {
                stk.pop();
            }
            lf[i] = (stk.size() ? stk.top() : -1);
            stk.push(i);
        }
        while(stk.size()) stk.pop();
        for(int i = n - 1; i >= 0; i --) {
            while(stk.size() && heights[i] <= heights[stk.top()]) {
                stk.pop();
            }
            rt[i] = (stk.size() ? stk.top() : n);
            stk.push(i);
        }
        while(stk.size()) stk.pop();
        int maxArea = 0;
        for(int i = 0; i < n; i ++) {
            maxArea = max(maxArea, heights[i] * (rt[i] - lf[i] - 1));
        }
        return maxArea;
    }
};

例题二 : 85. 最大矩形 - 力扣（LeetCode）

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

考虑到答案矩阵一定包含一条完整的竖线。

考虑经典的技巧，悬线法。

设 $h(i,j)$ 表示从下标 $(i,j)$ 向上延伸的最大长度，要求这条竖线全部是 1 。

那么我们枚举行，对于每一行的列，假设来到了 $(x,y)$ 这个点，对于 $x$ 这一列，用单调栈维护 $h(x,y)$ 向两侧延伸的最大矩形长度，一定能枚举到答案矩形。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    int n, m, res = 0;
    vector<vector<int> > hangLine;

    void work(int row) {
        vector<int> lf(m), rt(m);
        stack<int> stk;
        for(int j = 0; j < m; j ++) {
            while(stk.size() && hangLine[row][j] <= hangLine[row][stk.top()]) {
                stk.pop();
            }
            lf[j] = (stk.size() ? stk.top() : -1);
            stk.push(j);
        }
        while(stk.size()) {
            stk.pop();
        }
        for(int j = m - 1; j >= 0; j --) {
            while(stk.size() && hangLine[row][j] <= hangLine[row][stk.top()]) {
                stk.pop();
            }
            rt[j] = (stk.size() ? stk.top() : m);
            stk.push(j);
        }
        while(stk.size()) {
            stk.pop();
        }
        for(int j = 0; j < m; j ++) {
            res = max(res, hangLine[row][j] * (rt[j] - lf[j] - 1));
        }
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        n = matrix.size(), m = matrix[0].size(); 
        hangLine.resize(n);
        for(int i = 0; i < n; i ++) {
            hangLine[i].resize(m);
        } 
        for(int i = 0; i < n; i ++) {
            for(int j = 0; j < m; j ++) {
                if(matrix[i][j] == '1') {
                    hangLine[i][j] = (i ? hangLine[i - 1][j] + 1 : 1);
                }
            }
        }
        for(int i = 0; i < n; i ++) {
            work(i);
        }
        return res;
    }
};

双倍经验 ：P4147 玉蟾宫

练习题

例题一 : P6510 奶牛排队

奶牛在熊大妈的带领下排成了一条直队。

显然，不同的奶牛身高不一定相同……

现在，奶牛们想知道，如果找出一些连续的奶牛，要求最左边的奶牛 $A$ 是最矮的，最右边的 $B$ 是最高的，且 $B$ 高于 $A$ 奶牛。中间如果存在奶牛，则身高不能和 $A,B$ 奶牛相同。问这样的奶牛最多会有多少头？

从左到右给出奶牛的身高，请告诉它们符合条件的最多的奶牛数（答案可能是 $0,2$，但不会是 $1$）。

枚举右端点 $i$ ，即 $a_i=B$ ，设第一个 $\geq B$ 的位置为 $lf(i)$ ，那么 $[lf(i)+1,i-1]$ 这些位置是左端点的备选位置。

我们可以枚举这些点，设第一个 $\leq a_i$ 的位置为 $rt(i)$ ，那么只要 $rt(i)>i$ ，这个位置就是合法的。这样就得到了解法一，显然这种时间复杂度是难以解释的，虽然可以通过题目，但是我们还是希望得到拥有明确时间复杂度的解法。

考虑到 $[lf(i)+1,i-1]$ 这些位置里面，取一个最靠左的位置，满足这个位置到右端点之间，该位置的数是唯一最小值。

不动脑的想，可以维护 ST 表求最小值，最小值最靠右的位置可以用线段树求区间值域最靠右位置，这里的值域当然就是一个点了。

但是这种数据结构太大了，大过题目本身。其实就是求最靠左的最小值，而且这个最小值是最靠右最小值。我们维护一个单调严格递增栈即可，这样对栈的下标二分，分出来最左边的位置，因为是严格递增，该位置一定是最靠右的值。

  • 解法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
constexpr int N = 1e5 + 10;
stack<int> stk1, stk2;
int n, ls[N], rs[N], a[N], ans = 0;

void solve() {
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
    }

    // l[i] 维护左边第一个 >= 的
    for(int i = 1; i <= n; i ++) {
        while(stk1.size() && a[i] > a[stk1.top()]) {
            stk1.pop();
        }
        ls[i] = (stk1.size() ? stk1.top() : 0);
        stk1.push(i);
    }

    // r[i] 维护右边第一个 <= 的
    for(int i = n; i >= 1; i --) {
        while(stk2.size() && a[i] < a[stk2.top()]) {
            stk2.pop();
        }
        rs[i] = (stk2.size() ? stk2.top() : n + 1);
        stk2.push(i);
    }

    for(int i = 1; i <= n; i ++) {
        for(int j = ls[i] + 1; j < i; j ++) {
            if(ans >= i - j + 1) break;
            if(rs[j] > i) {
                ans = i - j + 1;
            }
        }
    }
    cout << ans << '\n';
}
  • 解法二 $O(n\log n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
const int N = 1E5 + 10;;

int n, ans, tx, tn;
int a[N], sx[N], sn[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (int i = 1; i <= n; ++i) {
        while (tn && a[i] <= a[sn[tn]]) -- tn;    // 严格递增单调栈 : 栈顶元素是 <    a[i] 的离 i 最近的左边的元素的下标
        while (tx && a[i] > a[sx[tx]]) -- tx;    // 递减单调栈 : 栈顶元素是 >= a[i] 的离 i 最近的左边的元素的下标
        int k = upper_bound(sn + 1, sn + 1 + tn, sx[tx]) - sn; 
        if (k != (tn + 1)) {
            ans = max(ans, i - sn[k] + 1);
        }
        sn[++ tn] = i;
        sx[++ tx] = i;
    }
    printf("%d\n", ans);
    return 0;
}

发表于 分类于

题目链接 ：C - Snake Numbers

Snake Numbers，蛇数，是指最高位大于其余所有位的数，给定 $10\leq L,R\leq 10^{18}$ ，求 $[L,R]$ 有多少蛇数 ？

1、设 $f(x)$ 表示 $10 \sim x$ 有多少蛇数，答案就是 $f(R)-f(L-1)$ 。

2、假设 $x$ 的位数为 $n$ ，分三种情况讨论 ：

  • 假设 $x$ 的位数 $<n$

  • 假设 $x$ 的位数 $=n$ ，开头元素 $<S_0$

  • 假设 $x$ 的位数 $=n$ ，开头元素 $=S_0$ （Trick ：按照前缀相同的位数枚举）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
using namespace std;
#define int long long

/**
 * Snake Numbers :
 * 蛇数，是指最高位的值大于其余所有位的值的一种数, 给你 x , y (10 <= x <= y), 求 x ~ y 一共有多少蛇数 ?
 * 1、f(x) 表示 10 ~ x 有多少蛇数, 那么答案 = f(y) - f(x - 1)
 * 2、假设 x 的位数为 n, 
 *      2.1、首先考虑所有位数 < n 的数, 
 */

/**
 * 举例 
 * 56126
 * 1、先考虑 < n 位的 :
 * 对于 2 位数 : 10 ; 20 21 ; 30 31 32 ; 40 41 42 43 统一 : 1 + 2 + 3 + ... + 9
 * 对于 3 位数 : 100 ; 200 201 210 211 ; 统一 : 1 + 2^2 + 3^2 + 4^2 + ... + 9^2
 * 对于 4 位数 : 1000 ; 2000 2001 ... ; 统一 : 1 + 2^3 + 3^3 + 4^3 + ... + 9^3
 * 2、在考虑 = n 位的, 先考虑开头小于 S0 的情况
 * 1 开头 : 10000
 * 2 开头 : 2____ 2^4
 * 3 开头 : 3____ 3^4
 * 4 开头 : 4____ 4^4
 * 3、最后考虑 = n 位, 且开头元素 = S0 的情况
 * 考虑按照第几位出现不同分情况讨论 :
 * 以 54265 为例
 * 第二位不同 : 5 x _ _ _, 0 1 2 3 -> 4 * 5^3
 * 第三位不同 : 5 4 x _ _, 0 1     -> 2 * 5^2
 * 第四位不同 : 5 4 2 x _, 5 * 5^1
 * 特殊情况 : 
 *  5 4 3 2 2 
 * 最后一位 2 可以取0、1、2，并非只有 0、1可以取
 */ 

/**
 * 求 1 ~ x 有多少个蛇数 ?
 */

int pow(int a, int b) {
    int res = 1;
    while(b --) {
        res *= a;
    }
    return res;
}

int f(int x) {
    if(x < 10) return 0;

    string sx = to_string(x);
    int n = sx.size();
    int res = 0;

    // 1 : 从 2 开始枚举位数, 枚举开头 
    for(int ln = 2; ln < n; ln ++) { 
        for(int st = 1; st <= 9; st ++) {
            res += pow(st, ln - 1);
        }
    }

    // 2 : 位数 = n, 开头 < S[0]
    int S0 = sx[0] - '0';
    for(int st = 1; st < S0; st ++) {
        res += pow(st, n - 1);
    }

    // 3 : 位数 = n, 开头 = S0
    for(int i = 2; i <= n; i ++) {
        int Si = sx[i - 1] - '0';
        if(Si >= S0) { 
            res += S0 * pow(S0, n - i); // [i, n] 都可填 0 ~ S0 - 1
            break;
        }
        else {
            res += Si * pow(S0, n - i); // 这一位 Si 种, 最后几位 0 ~ S0 - 1
            if(i == n) res ++; // 特判
        }
    }
    return res;
}

void solve(){
    int x, y;
    cin >> x >> y;
    cout << f(y) - f(x - 1) << '\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0); 
    solve();
    return 0;
}

发表于 分类于

测试数据库连接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 数据库连接信息
String url = "jdbc:mysql://localhost:3306/wineCulturalJewel";
String user = "root";
String password = "1234";

try (Connection connection = DriverManager.getConnection(url, user, password)) {
// 测试连接是否成功
    if (connection != null && connection.isValid(5)) { // 超时时间为 5 秒
        System.out.println("数据库连接成功！");
    } else {
        System.out.println("数据库连接失败！");
    }
} 
catch (SQLException e) {
    System.out.println("连接数据库时发生错误：");
    e.printStackTrace();
}

JFrame 显示一张图片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void main(String[] args) {
    // 创建一个 JFrame（窗口）
    JFrame frame = new JFrame("显示图片");
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.setSize(500, 500);  // 设置窗口大小

    // 加载图片
    ImageIcon imageIcon = new ImageIcon("C:\\Users\\95432\\Desktop\\WineCulturalJewel\\images\\background1.jpg");  // 替换为你的图片路径
    JLabel label = new JLabel(imageIcon);  // 将图片放入 JLabel

    // 将 JLabel 添加到窗口中
    frame.add(label, BorderLayout.CENTER);

    // 设置窗口可见
    frame.setVisible(true);
}}

JPane功能

可以实现一些小游戏。

实现一些物品的移动，碰撞检测之类的逻辑

发表于 分类于

Frobenius 定理

核心内容

对于两个正整数 $a$ 和 $b$ （假设 $\gcd(a, b) = 1$），考虑以下整数线性组合：

$$
S = {ax + by \mid x, y \geq 0},
$$

即使用 $a$ 和 $b$ 的非负整数线性组合能够表示的所有正整数。根据 Frobenius 定理，有以下结论：

  1. 能表示的最小正整数：如果 $\gcd(a, b) = 1$，则最小能表示的正整数为 $\min(a, b)$。

  2. 不能表示的最大正整数：形如 $ax + by$ 的线性组合不能表示的最大正整数为：

    $$
    N = ab - a - b.
    $$

  3. 不能表示的正整数个数：不能表示的正整数的总个数为：

    $$
    \frac{(a-1)(b-1)}{2}.
    $$

推广到多个变量

对于 $a_1, a_2, \ldots, a_k$，$k > 2$，若 $\gcd(a_1, a_2, \ldots, a_k) = 1$，仍然有：

  • $ax_1 + bx_2 + \cdots$ 表示的正整数集合是有限缺口的；

  • 但无法通过闭式公式直接确定所有不可表示的数。

P8646 [蓝桥杯 2017 省 AB] 包子凑数

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 $N$ 种蒸笼，其中第 $i$ 种蒸笼恰好能放 $A_i$ 个包子。每种蒸笼都有非常多笼，可以认为是无限笼。

每当有顾客想买 $X$ 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 $X$ 个包子。比如一共有 $3$ 种蒸笼，分别能放 $3$ 、 $4$ 和 $5$ 个包子。当顾客想买 $11$ 个包子时，大叔就会选 $2$ 笼 $3$ 个的再加 $1$ 笼 $5$ 个的（也可能选出 $1$ 笼 $3$ 个的再加 $2$ 笼 $4$ 个的）。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 $3$ 种蒸笼，分别能放 $4$ 、 $5$ 和 $6$ 个包子。而顾客想买 $7$ 个包子时，大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

由裴蜀定理，可以得出，必须 $\gcd_{i=1}^nA_i=1$ 才能凑出所有数，不然只能凑出一些 $kg$ 的形式。

满足了 $g=1$ 之后，由 Fronebius 定理，我们知道这题不能构造的数是有限的，就是说 $A_1x_1+A_2x_2+\cdots$ 表示的正整数是有限缺口的。

考虑用完全背包求一下能表示哪些数，一共有 $\max=100$ 个数据，我们将第二维尽量放大，精准需要多大很难用数学推导出来，1 S 的时限内，可以将第二维放宽到 $10^6$ ，可以通过题目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void solve(){
    int n, g = 0;
    cin >> n;

    vector<int> f(1E6), a(n);
    for(auto &x : a) {
        cin >> x;
        g = __gcd(g, x);
    }

    if(g != 1) {
        cout << "INF\n";
        exit(0);
    }

    f[0] = 1;
    for(auto &x : a) { // 100
        for(int j = 0; j <= 1E6; j ++) {
            if(f[j] && j + x <= (int)1E6) f[j + x] = 1;
        }
    }

    int res = 0;
    for(int i = 0; i <= 1E6; i ++) {
        res += !f[i];
    }
    cout << res << '\n';
}

发表于 分类于

2025-01-12崂山

一二节

P1106

保留 $n-k$ 个数。

我们每次选择合法位置（即后面的数还够选）的数中，最小数中位置最靠左的数。

注意 ：

  • 开头不能为 0

  • 要按照左右顺序拼接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
#define int long long

int s[300], choose[300];

int ask(int l, int r) {
    return s[r] - s[l - 1];
}

void solve() {
    string str;
    int n, k;
    cin >> str >> k;
    n = str.size();
    str = ' ' + str;

    string res = "";
    for(int x = 1; x <= n - k; x ++) {
        memset(s, 0, sizeof s);
        for(int i = 1; i <= n; i ++) {
            s[i] = s[i - 1] + (choose[i] == 0);
        }
        // cout << ask(1, n) << '\n';
        pair<int, int> tmp = {1e9, 1e9};
        for(int i = 1; i <= n; i ++) {
            if(choose[i]) continue ;
            if(ask(i, n) >= n - k + 1 - x) {
                auto &[v, p] = tmp;
                auto val = str[i] - '0';
                // cout << val << ' ' << v << '\n';
                if(val < v || (val == v && i < p)) {
                    p = i;
                    v = val;
                }
            }
        }

        auto &[v, p] = tmp;
        // cout << v << ' ' << p << '\n';

        res += to_string(v);
        for(int i = 1; i <= p; i ++) {
            choose[i] = 1;
        }
    }
    int i = 0;
    while(i + 1 < res.size() && res[i] == '0') ++ i;
    cout << res.substr(i);
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0); 
    solve();
    return 0;
}

P8604

解法一 : 枚举关键点，并判断连通性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1E3 + 10;

int res = 0;
int n, m, u, v;
int g[N][N];
bool st[N];

void dfs(int s, int x) {
    st[s] = true;
    for(int i = 1; i <= n; i ++){
        if(g[s][i] && !st[i] && i != x) {
            dfs(i, x);
        } 
    }
}

bool test(int x) {
    memset(st, false, sizeof st);  
    dfs(u, x); 
    return !st[v];
}

void solve(){
    cin >> n >> m;
    for(int i = 1; i <= m; i ++){
        cin >> u >> v;
        g[u][v] = 1;
        g[v][u] = 1;
    }
    cin >> u >> v;

    dfs(u, n + 1);
    if(st[v] == false) {
        cout << "-1";
        return ;
    }

    for(int i = 1; i <= n; i ++) {
        if(i == u || i == v) continue ;
        res += test(i);
    }
    cout << res;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0); 
    solve();
    return 0;
}

解法二 :

回溯判断每个点被 $u$ 到 $v$ 的路径经过几次，并求出路径总数。

如果经过 次数 = 路径总数 ，那么这个点就是关键点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1E3 + 10;
vector<int> e[N];
int res = 0;
int n, m, u, v, sum = 0;
int cnt[N], tag[N];

void dfs(int u) {
    if(u == v) {
        sum ++;
        for(int i = 1; i <= n; i ++){
            cnt[i] += tag[i];
        }
        return; 
    }
    for(auto v : e[u]) {
        if(tag[v] == 0) {
            tag[v] = 1;
            dfs(v);
            tag[v] = 0;
        }
    }
}

void solve(){
    cin >> n >> m;
    for(int i = 1; i <= m; i ++) {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    cin >> u >> v;

    dfs(u);

    if(sum == 0) {
        cout << "-1";
        return ;
    }

    int res = 0;
    for(int i = 1; i <= n; i ++){
        res += cnt[i] == sum;
    }
    cout << res - 1 << '\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0); 
    solve();
    return 0;
}

三四节

P1765

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;

int num[26] = {1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 4};

int main(){
    string s;
    getline(cin, s);    

    int res = 0;
    for(int i = 0; s[i]; i ++){
        if(s[i] == ' ') res ++;
        else if(s[i] >= 'a' && s[i] <= 'z') res += num[s[i] - 'a'];
    }
    cout << res << '\n';

    return 0;
}

P1125

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
#define int long long

void solve(){
    string str;
    cin >> str;

    vector<int> cnt(26, 0);
    for(char x : str) {
        cnt[x - 'a'] ++;
    }

    int maxn = *max_element(cnt.begin(), cnt.end());
    int minn = 1E9;
    for(int x : cnt) {
        if(x) minn = min(minn, x);
    }

    auto judge = [&] (int x) -> bool {
        if(x <= 1) return false;
        for(int i = 2; i <= x / i; i ++) {
            if(x % i == 0) {
                return false;
            }
        }
        return true;
    };

    if(judge(maxn - minn)) {
        cout << "Lucky Word\n";
        cout << maxn - minn << '\n';
    }
    else {
        cout << "No Answer\n0";
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0); 
    solve();
    return 0;
}

P5015

曲鑫 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    getline(cin,s);
    int k=s.size();
    int cnt=0;
    for(int i=0;i<k;i++){
        if(s[i]!=' ' && s[i]!='\n'){
            cnt++;
        }
    }
    cout<<cnt;
    return 0;
}