1. Johngo学长首页
  2. 技术点详细复盘专题
  3. Python

Week 11

• Python • 阅读 41

洛谷P1796 汤姆斯的天堂梦

题目描述

汤姆斯生活在一个等级为 0 0 0 的星球上。那里的环境极其恶劣，每天 12 12 12 小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为 N N N 的星球上天堂般的生活。

有一些航班将人从低等级的星球送上高一级的星球，有时需要向驾驶员支付一定金额的费用，有时却又可以得到一定的金钱。

汤姆斯预先知道了从 0 0 0 等级星球去 N N N 等级星球所有的航线和需要支付（或者可以得到）的金钱，他想寻找一条价格最低（甚至获得金钱最多）的航线。

输入格式

第一行一个正整数 N N N（N ≤ 100 N \le 100 N ≤100），接下来的数据可分为 N N N 个段落，每段的第一行一个整数 K i K_i K i ​（K i ≤ 100 K_i \le 100 K i ​≤100），表示等级为 i i i 的星球有 K i K_i K i ​ 个。

接下来的 K i K_i K i ​ 行中第 j j j 行依次表示与等级为 i i i，编号为 j j j 的星球相连的等级为 i − 1 i – 1 i −1 的星球的编号和此航线需要的费用（正数表示支出，负数表示收益，费用的绝对值不超过 1000 1000 1000）。

每行以 0 0 0 结束，每行的航线数 ≤ 100 \le 100 ≤100。

输出格式

输出所需（或所得）费用。正数表示支出，负数表示收益。

样例 #1

样例输入 #1

3
2
1 15 0
1 5 0
3
1 -5 2 10 0
1 3 0
2 40 0
2
1 1 2 5 3 -5 0
2 -19 3 -20 0

样例输出 #1

-1

提示

对于 100 % 100 \%100% 的数据，1 ≤ N ≤ 100 1 \le N \le 100 1 ≤N ≤100，1 ≤ K i ≤ 100 1 \le K_i \le 100 1 ≤K i ​≤100。

样例解释：

Week 11

思路： 这题一眼看过去是跟图论有关的题，但根据题意，等级为 i 的星球只能由等级为 i – 1 的星球到达，因此可以用动态规划来解决。设 dp[i][j] 为登上等级为 i 编号为 j 的星球的最低价格，则状态转移方程为

dp[i][j] = min(dp[i][j], dp[i – 1][k] + v)，其中k为星球编号，v为价格

代码：

#include
using namespace std;
int n, k, dp[105][105], ans = 0x3f3f3f3f;
int main(){
    cin >> n;
    memset(dp, 0x3f, sizeof(dp));
    dp[0][1] = 0;
    for(int i = 1; i  n; i++){
        cin >> k;
        for(int j = 1; j  k; j++){
            int a;
            cin >> a;
            while(a){
                int b;
                cin >> b;
                dp[i][j] = min(dp[i][j], dp[i - 1][a] + b);
                cin >> a;
            }
        }
    }
    for(int i = 1; i  k; i++){
        ans = min(ans, dp[n][i]);
    }
    cout << ans;
    return 0;
}

洛谷P1806 跑步

题目描述

路人甲准备跑 n n n 圈来锻炼自己的身体，他准备分多次（> 1 \gt1 >1）跑完，每次都跑正整数圈，然后休息下再继续跑。

为了有效地提高自己的体能，他决定每次跑的圈数都必须比上次跑的多。

可以假设他刚开始跑了 0 0 0 圈，那么请问他可以有多少种跑完这 n n n 圈的方案？

输入格式

一行一个整数，代表 n n n。

输出格式

一个整数表示跑完这 n n n 圈的方案数。

样例 #1

样例输入 #1

212

样例输出 #1

995645335

提示

数据规模与约定

对于 100 % 100\%100% 的数据，保证 5 ≤ n ≤ 500 5\le n\le 500 5 ≤n ≤500。

思路： 用背包问题的思路就可以顺利解决。设 dp[i][j] 为跑前 i 圈且最后一圈跑了 j 圈的方案数，则状态转移方程为

dp[i][j] = dp[i – j][1] + dp[i – j][2] + … + dp[i – j][k], 其中k

代码：

#include
using namespace std;
long long n, dp[505][505], ans;
int main(){
    cin >> n;
    for(int i = 1; i  n; i++){
        dp[i][i] = 1;
    }
    for(int i = 1; i  n; i++){
        for(int j = 1; j < i; j++){
            for(int k = 1; k  i - j && k < j; k++){
                dp[i][j] += dp[i - j][k];
            }
        }
    }
    for(int i = 1; i  n; i++){
        ans += dp[n][i];
    }
    cout << ans - 1;
    return 0;
}

洛谷P8742 [蓝桥杯 2021 省 AB] 砝码称重

题目描述

你有一架天平和 N N N 个砝码, 这 N N N 个砝码重量依次是 W 1 , W 2 , ⋯ , W N W_{1}, W_{2}, \cdots, W_{N}W 1 ​,W 2 ​,⋯,W N ​ 。 请你计算一共可以称出多少种不同的重量?

注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 N N N 。

第二行包含 N N N 个整数: W 1 , W 2 , W 3 , ⋯ , W N W_{1}, W_{2}, W_{3}, \cdots, W_{N}W 1 ​,W 2 ​,W 3 ​,⋯,W N ​ 。

输出格式

输出一个整数代表答案。

样例 #1

样例输入 #1

3
1 4 6

样例输出 #1

10

提示

【样例说明】

能称出的 10 种重量是: 1 、 2 、 3 、 4 、 5 、 6 、 7 、 9 、 10 、 11 1 、 2 、 3 、 4 、 5 、 6 、 7 、 9 、 10 、 11 1 、2 、3 、4 、5 、6 、7 、9 、10 、11 。

1 = 1 2 = 6 − 4 ( 天平一边放 6 , 另一边放 4) 3 = 4 − 1 4 = 4 5 = 6 − 1 6 = 6 7 = 1 + 6 9 = 4 + 6 − 1 10 = 4 + 6 11 = 1 + 4 + 6 \begin{aligned} &1=1 \ &2=6-4(\text { 天平一边放 } 6, \text { 另一边放 4) } \ &3=4-1 \ &4=4 \ &5=6-1 \ &6=6 \ &7=1+6 \ &9=4+6-1 \ &10=4+6 \ &11=1+4+6 \end{aligned}​1 =1 2 =6 −4 (天平一边放6 ,另一边放4)3 =4 −1 4 =4 5 =6 −1 6 =6 7 =1 +6 9 =4 +6 −1 10 =4 +6 11 =1 +4 +6 ​

【评测用例规模与约定】

对于 50 % 50 \%50% 的评测用例, 1 ≤ N ≤ 15 1 \leq N \leq 15 1 ≤N ≤15 。

对于所有评测用例, 1 ≤ N ≤ 100 , N 1 \leq N \leq 100, N 1 ≤N ≤100 ,N 个砝码总重不超过 1 0 5 10^5 1 0 5。

蓝桥杯 2021 第一轮省赛 A 组 F 题（B 组 G 题）。

思路： 一道01背包问题。用 dp[i][j] 表示用前 i 个砝码能否称出 j 的重量，w[i] 为 第 i 个砝码的重量，则状态转移方程为

if(dp[i – 1][j + w[i]]) dp[i][j] = true;
else if(dp[i – 1][abs(j – w[i])]) dp[i][j] = true;
else dp[i][j] = dp[i – 1][j];

由于砝码能放在天平两边，因此要用abs(j – w[i])来表示称出的重量

代码：

#include
using namespace std;
int n, w[105], maxx, ans;
bool dp[105][200005];
int main(){
    cin >> n;
    for(int i = 1; i  n; i++){
        cin >> w[i];
        maxx += w[i];
    }
    dp[0][0] = true;
    for(int i = 1; i  n; i++){
        for(int j = 0; j  maxx; j++){
            if(dp[i - 1][j + w[i]]) dp[i][j] = true;
            else if(dp[i - 1][abs(j - w[i])]) dp[i][j] = true;
            else dp[i][j] = dp[i - 1][j];
        }
    }
    for(int i = 0; i  maxx; i++){
        if(dp[n][i]) ans++;
    }
    cout << ans - 1;
    return 0;
}

洛谷P1959 遗址

题目描述

很久很久以前有一座寺庙，从上往下看寺庙的形状正好是一个正方形，由 4 4 4 个角上竖立的圆柱搭建而成。现在圆柱都倒塌了，只在地上留下圆形的痕迹，可是现在地上有很多这样的痕迹，专家说一定是最大的那个。

写一个程序，给出圆柱的坐标，找出由 4 4 4 个圆柱构成的最大的正方形，因为这就是寺庙的位置，要求计算出最大的面积。注意正方形的边不一定平行于坐标轴。

例如图有 10 10 10 根柱子，其中 ( 4 , 2 ) , ( 5 , 2 ) , ( 5 , 3 ) , ( 4 , 3 ) (4,2),(5,2),(5,3),(4,3)(4 ,2 ),(5 ,2 ),(5 ,3 ),(4 ,3 ) 可以形成一个正方形，( 1 , 1 ) , ( 4 , 0 ) , ( 5 , 3 ) , ( 2 , 4 ) (1,1),(4,0),(5,3),(2,4)(1 ,1 ),(4 ,0 ),(5 ,3 ),(2 ,4 ) 也可以，后者是其中最大的，面积为 10 10 10。

Week 11

; 输入格式

第一行包含一个 N ( 1 ≤ N ≤ 3000 ) N(1\leq N\leq 3000)N (1 ≤N ≤3000 )，表示柱子的数量。

接下来 N N N 行，每行有两个空格隔开的整数表示柱子的坐标（坐标值在 0 0 0 到 5000 5000 5000 之间），柱子的位置互不相同。

输出格式

如果存在正方形，输出最大的面积，否则输出 0 0 0。

样例 #1

样例输入 #1

10
 9 4
 4 3
 1 1
 4 2
 2 4
 5 8
 4 0
 5 3
 0 5
 5 2

样例输出 #1

10

提示

【数据范围】

30 % 30\%30% 满足：1 ≤ N ≤ 100 1\leq N \leq100 1 ≤N ≤100。

60 % 60\%60% 满足：1 ≤ N ≤ 500 1\leq N \leq500 1 ≤N ≤500。

100 % 100\%100% 满足：1 ≤ N ≤ 3000 1\leq N \leq3000 1 ≤N ≤3000。

思路： 首先观察数据范围，由于 1 ≤ N ≤ 3000 1\leq N \leq3000 1 ≤N ≤3000，所以在搜索正方形的顶点时时间复杂度最多只能为O(n^2)，即只搜索正方形的其中两个顶点。再通过观察可知，设正方形第一个顶点坐标（x1, y1），第二个顶点坐标（x2, y2），则第三个顶点可表示为（x1 ± (y1 – y2), y1 ± (x1 – x2)），第四个顶点可表示为（x2 ± (y1 – y2), y2 ± (x1 – x2)）。最后直接用两层for循环搜索所有点即可。注意要判断所有点不能超出给定的坐标范围。

代码：

#include
using namespace std;
bool mp[5005][5005];
int n, ans;
struct pole{
    int x, y;
} p[3005];
int check(int a, int b){
    int x1 = p[a].x, x2 = p[b].x, y1 = p[a].y, y2 = p[b].y;
    int dx = x1 - x2, dy = y1 - y2;
    bool flag1 = false, flag2 = false;
    if(x1 + dy < 0 || x1 + dy > 5000 || y1 - dx < 0 || y1 - dx > 5000 || x2 + dy < 0 || x2 + dy > 5000 || y2 - dx < 0 || y2 - dx > 5000 ) flag1 = true;
    if(x1 - dy < 0 || x1 - dy > 5000 || y1 + dx < 0 || y1 + dx > 5000 || x2 - dy < 0 || x2 - dy > 5000 || y2 + dx < 0 || y2 + dx > 5000 ) flag2 = true;
    if(!flag1 && (mp[x1 + dy][y1 - dx] && mp[x2 + dy][y2 - dx])) return dx * dx + dy * dy;
    if(!flag2 && (mp[x1 - dy][y1 + dx] && mp[x2 - dy][y2 + dx])) return dx * dx + dy * dy;
    else return 0;
}
int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        mp[a][b] = true;
        p[i] = {a, b};
    }
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            ans = max(ans, check(i, j));
        }
    }
    cout << ans;
    return 0;
}

洛谷P8794 [蓝桥杯 2022 国 A] 环境治理

题目描述

LQ 国拥有 n n n 个城市，从 0 0 0 到 n − 1 n – 1 n −1 编号，这 n n n 个城市两两之间都有且仅有一条双向道路连接，这意味着任意两个城市之间都是可达的。每条道路都有一个属性 D D D，表示这条道路的灰尘度。当从一个城市 A 前往另一个城市 B 时，可能存在多条路线，每条路线的灰尘度定义为这条路线所经过的所有道路的灰尘度之和，LQ 国的人都很讨厌灰尘，所以他们总会优先选择灰尘度最小的路线。

LQ 国很看重居民的出行环境，他们用一个指标 P P P 来衡量 LQ 国的出行环境，P P P 定义为：

P = ∑ i = 0 n − 1 ∑ j = 0 n − 1 d ( i , j ) P=\sum \limits_{i=0}^{n-1} \sum \limits_{j=0}^{n-1} d(i,j)P =i =0 ∑n −1 ​j =0 ∑n −1 ​d (i ,j )

其中 d ( i , j ) d(i,j)d (i ,j ) 表示城市 i i i 到城市 j j j 之间灰尘度最小的路线对应的灰尘度的值。

为了改善出行环境，每个城市都要有所作为，当某个城市进行道路改善时，会将与这个城市直接相连的所有道路的灰尘度都减少 1 1 1，但每条道路都有一个灰尘度的下限值 L L L，当灰尘度达到道路的下限值时，无论再怎么改善，道路的灰尘度也不会再减小了。

具体的计划是这样的：

  • 第1 1 1 天，0 0 0 号城市对与其直接相连的道路环境进行改善；
  • 第2 2 2 天，1 1 1 号城市对与其直接相连的道路环境进行改善；

……

  • 第n n n 天，n − 1 n – 1 n −1 号城市对与其直接相连的道路环境进行改善；
  • 第n + 1 n + 1 n +1 天，0 0 0 号城市对与其直接相连的道路环境进行改善；
  • 第n + 2 n + 2 n +2 天，1 1 1 号城市对与其直接相连的道路环境进行改善；

……

LQ 国想要使得 P P P 指标满足 P ≤ Q P \leq Q P ≤Q。请问最少要经过多少天之后，P P P 指标可以满足 P ≤ Q P \leq Q P ≤Q。如果在初始时就已经满足条件，则输出 0 0 0；如果永远不可能满足，则输出 − 1 -1 −1。

输入格式

输入的第一行包含两个整数 n , Q n, Q n ,Q，用一个空格分隔，分别表示城市个数和期望达到的 P P P 指标。

接下来 n n n 行，每行包含 n n n 个整数，相邻两个整数之间用一个空格分隔，其中第 i i i 行第 j j j 列的值 D i , j ( D i , j = D j , i , D i , i = 0 ) D_{i,j} (D_{i,j}=D_{j,i},D_{i,i} = 0)D i ,j ​(D i ,j ​=D j ,i ​,D i ,i ​=0 ) 表示城市 i i i 与城市 j j j 之间直接相连的那条道路的灰尘度。

接下来 n n n 行，每行包含 n n n 个整数，相邻两个整数之间用一个空格分隔，其中第 i i i 行第 j j j 列的值 L i , j ( L i , j = L j , i , L i , i = 0 ) L_{i,j} (L_{i,j} = L_{j,i}, L_{i,i} = 0)L i ,j ​(L i ,j ​=L j ,i ​,L i ,i ​=0 ) 表示城市 i i i 与城市 j j j 之间直接相连的那条道路的灰尘度的下限值。

输出格式

输出一行包含一个整数表示答案。

样例 #1

样例输入 #1

3 10
0 2 4
2 0 1
4 1 0
0 2 2
2 0 0
2 0 0

样例输出 #1

2

提示

【样例说明】

初始时的图如下所示，每条边上的数字表示这条道路的灰尘度：

Week 11

此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：

  • d ( 0 , 0 ) = 0 , d ( 0 , 1 ) = 2 , d ( 0 , 2 ) = 3 d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 3 d (0 ,0 )=0 ,d (0 ,1 )=2 ,d (0 ,2 )=3；
  • d ( 1 , 0 ) = 2 , d ( 1 , 1 ) = 0 , d ( 1 , 2 ) = 1 d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 1 d (1 ,0 )=2 ,d (1 ,1 )=0 ,d (1 ,2 )=1；
  • d ( 2 , 0 ) = 3 , d ( 2 , 1 ) = 1 , d ( 2 , 2 ) = 0 d(2, 0) = 3, d(2, 1) = 1, d(2, 2) = 0 d (2 ,0 )=3 ,d (2 ,1 )=1 ,d (2 ,2 )=0。

初始时的 P P P 指标为 ( 2 + 3 + 1 ) × 2 = 12 (2 + 3 + 1) \times 2 = 12 (2 +3 +1 )×2 =12，不满足 P ≤ Q = 10 P \leq Q = 10 P ≤Q =10;

第一天，0 0 0 号城市进行道路改善，改善后的图示如下：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CDgtMFfE-1673865069268)(https://cdn.luogu.com.cn/upload/image_hosting/mrhf5wx6.png)]

注意到边 ( 0 , 2 ) (0, 2)(0 ,2 ) 的值减小了 1 1 1，但 ( 0 , 1 ) (0, 1)(0 ,1 ) 并没有减小，因为 L 0 , 1 = 2 L_{0,1} = 2 L 0 ,1 ​=2 ，所以 ( 0 , 1 ) (0, 1)(0 ,1 ) 的值不可以再减小了。此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：

  • d ( 0 , 0 ) = 0 , d ( 0 , 1 ) = 2 , d ( 0 , 2 ) = 3 d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 3 d (0 ,0 )=0 ,d (0 ,1 )=2 ,d (0 ,2 )=3，
  • d ( 1 , 0 ) = 2 , d ( 1 , 1 ) = 0 , d ( 1 , 2 ) = 1 d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 1 d (1 ,0 )=2 ,d (1 ,1 )=0 ,d (1 ,2 )=1，
  • d ( 2 , 0 ) = 3 , d ( 2 , 1 ) = 1 , d ( 2 , 2 ) = 0 d(2, 0) = 3, d(2, 1) = 1, d(2, 2) = 0 d (2 ,0 )=3 ,d (2 ,1 )=1 ,d (2 ,2 )=0。

此时 P P P 仍为 12 12 12。

第二天，1 号城市进行道路改善，改善后的图示如下：

Week 11

此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：

  • d ( 0 , 0 ) = 0 , d ( 0 , 1 ) = 2 , d ( 0 , 2 ) = 2 d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 2 d (0 ,0 )=0 ,d (0 ,1 )=2 ,d (0 ,2 )=2，
  • d ( 1 , 0 ) = 2 , d ( 1 , 1 ) = 0 , d ( 1 , 2 ) = 0 d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 0 d (1 ,0 )=2 ,d (1 ,1 )=0 ,d (1 ,2 )=0，
  • d ( 2 , 0 ) = 2 , d ( 2 , 1 ) = 0 , d ( 2 , 2 ) = 0 d(2, 0) = 2, d(2, 1) = 0, d(2, 2) = 0 d (2 ,0 )=2 ,d (2 ,1 )=0 ,d (2 ,2 )=0。

此时的 P P P 指标为 ( 2 + 2 ) × 2 = 8 < Q (2 + 2) \times 2 = 8 < Q (2 +2 )×2 =8 <Q，此时已经满足条件。

所以答案是 2 2 2。

【评测用例规模与约定】

  • 对于30 % 30\%30% 的评测用例，1 ≤ n ≤ 10 1 \leq n \leq 10 1 ≤n ≤10，0 ≤ L i , j ≤ D i , j ≤ 10 0 \leq L_{i,j} \leq D_{i,j} \leq 10 0 ≤L i ,j ​≤D i ,j ​≤10；
  • 对于60 % 60\%60% 的评测用例，1 ≤ n ≤ 50 1 \leq n \leq 50 1 ≤n ≤50，0 ≤ L i , j ≤ D i , j ≤ 1 0 5 0 \leq L_{i,j} \leq D_{i,j} \leq 10^5 0 ≤L i ,j ​≤D i ,j ​≤1 0 5；
  • 对于所有评测用例，1 ≤ n ≤ 100 1 \leq n \leq 100 1 ≤n ≤100，0 ≤ L i , j ≤ D i , j ≤ 1 0 5 0 \leq L_{i,j} \leq D_{i,j} \leq 10^5 0 ≤L i ,j ​≤D i ,j ​≤1 0 5，0 ≤ Q ≤ 2 31 − 1 0 \leq Q \leq 2^{31} – 1 0 ≤Q ≤2 31 −1。

蓝桥杯 2022 国赛 A 组 F 题。

思路： 用floyd算法能直接算出所有城市间灰尘度最小的道路，此时的时间复杂度是O(n^3)，而又因为要找出最短的天数使得 P ≤ Q P \leq Q P ≤Q，如果每一天都更新道路间的灰尘度并使用floyd计算最小值，那么想都不用想肯定会超时。而由题意可知，随着道路的改善，灰尘度是单调递减的，因此可以用二分来查找最短的天数。注意最终的答案要与二分的上界一起更新，这样才能保证最终答案是最小值

代码：

#include
using namespace std;
long long n, q, ans, dust[100][100], limit[100][100], mp[100][100];
int check(int mid){
    int a = mid / n, b = mid % n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            mp[i][j] = dust[i][j] - a;
            if(i < b) mp[i][j] -= 1;
            mp[i][j] = max(mp[i][j], limit[i][j]);
        }
    }
    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
            }
        }
    }
    long long res = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            res += mp[i][j];
        }
    }
    return res;
}
int main(){
    cin >> n >> q;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> dust[i][j];
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> limit[i][j];
        }
    }
    int st = 0, ed = 1e7;
    while(st  ed){
        int mid = (st + ed) / 2;
        if(check(mid) > q) st = mid + 1;
        else ed = mid - 1, ans = mid;
    }
    if(st == 1e7 + 1) cout << -1;
    else cout << ans;
    return 0;
}

Original: https://blog.csdn.net/Pharus/article/details/128707525
Author: Pharus25
Title: Week 11

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/812574/

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
0

【自取】最近整理的，有需要可以领取学习：



Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言 刷题答案下载！

大家都在看

亲爱的 Coder【最近整理，可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球