如何形容网站开发公司技术经验,网站建设设计logo,东莞网站建设推广平台,idc主机托管蓝桥杯第十三届省赛真题-统计子矩阵
题目描述
给定一个 N M 的矩阵 A#xff0c;请你统计有多少个子矩阵 (最小 1 1#xff0c;最大 N M) 满足子矩阵中所有数的和不超过给定的整数 K?
输入格式
第一行包含三个整数 N, M 和 K.
之后 N 行每行包含 M 个整数#xf…蓝桥杯第十三届省赛真题-统计子矩阵
题目描述
给定一个 N × M 的矩阵 A请你统计有多少个子矩阵 (最小 1 × 1最大 N × M) 满足子矩阵中所有数的和不超过给定的整数 K?
输入格式
第一行包含三个整数 N, M 和 K.
之后 N 行每行包含 M 个整数代表矩阵 A.
输出格式
一个整数代表答案。
样例输入
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
样例输出
19
提示
满足条件的子矩阵一共有 19包含
大小为 1 × 1 的有 10 个。
大小为 1 × 2 的有 3 个。
大小为 1 × 3 的有 2 个。
大小为 1 × 4 的有 1 个。
大小为 2 × 1 的有 3 个。
对于 30% 的数据N, M ≤ 20. 对于 70% 的数据N, M ≤ 100.
对于 100% 的数据1 ≤ N, M ≤ 500; 0 ≤ Ai j ≤ 1000; 1 ≤ K ≤ 250000000.
思路提示
1.求每列前缀和ij 为上下边界则可看成用一维解决。 2.用双指针 l r 维护左右边界当 r 边界确定时找到了 sum k 的区间左边界 l 往右移寻找符合条件的区间。 代码表示
#include bits/stdc.h
using namespace std;const int N 510;
int f[N][N];//二维数组 f可以存储整型数据
int n, m, k;
int main()
{cin n m k;for (int i 1; i n; i )for (int j 1; j m; j )scanf(%d, f[i][j]),f[i][j] f[i - 1][j]; // 计算每列前缀和long long res 0;for (int i 1; i n; i ) // 上边界for (int j i; j n; j ) // 下边界for (int l 1, r 1, sum 0; r m; r ){sum f[j][r] - f[i - 1][r]; // 确定右边界 删去上面的 while (sum k) // 求符合条件的左边界 l{sum - f[j][l] - f[i - 1][l];//删除左面的不用的 l ;}res r - l 1; }cout res;return 0;
}
心得体会
1、f[i][j] f[i - 1][j] 时它的含义是将当前位置 (i, j) 的值加上前一行相同列位置 (i - 1, j) 的值并将结果保存在当前位置 (i, j)。这是累加前缀和的操作用于计算子矩阵的和。
2、sum f[j][r] - f[i - 1][r]; 用于计算当前子矩阵的和。f[j][r] - f[i - 1][r] 表示从上边界 i 到下边界 j、从左边界到右边界 r 的子矩阵的和
3、sum - f[j][l] - f[i - 1][l]; l ; 通过减去左边界 l 的前缀和来找到符合条件的左边界。l 逐渐向右移动直到子矩阵的和不超过 K。
4、res r - l 1; 将以当前 (i, j, r) 为边界的子矩阵的个数加到结果变量 res 中。r - l 1 表示符合条件的子矩阵的列数。 蓝桥杯第十二届省赛真题-砝码称重
题目描述
你有一架天平和 N 个砝码这 N 个砝码重量依次是 W1, W2, · · · , WN。 请你计算一共可以称出多少种不同的重量 注意砝码可以放在天平两边。
输入格式
输入的第一行包含一个整数 N。 第二行包含 N 个整数W1, W2, W3, · · · , WN。
输出格式
输出一个整数代表答案。
样例输入
3
1 4 6样例输出
10提示
【样例说明】 能称出的 10 种重量是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。 【评测用例规模与约定】 对于 50% 的评测用例1 ≤ N ≤ 15。 对于所有评测用例1 ≤ N ≤ 100N 个砝码总重不超过 100000。
代码表示
#include bits/stdc.h
using namespace std;
//砝码个数N
const int N 110, M 300000;//大一点好
int n,sum,w[N];//总重量 sum
int f[N][M];
int main()
{cin n;for (int i 1;i n; i){//读砝码每一个的重量w[i]累加到总重量 sumcin w[i];sum w[i];}f[0][0]1; //初始化 for(int i 1; i n; i){for(int j 0; j sum; j){//1、f[i-1][j]意味着不选第i个就可以达到重量j//2、f[i-1][jw[i]]意味着第i个将放在另一边抵消w[i]达到j//3、f[i-1][abs(j-w[i])]意味着用第i个补上w[i]达到jf[i][j] f[i - 1][j] || f[i - 1][j w[i]] || f[i - 1][abs(j - w[i])];}}int ans 0;//从 1 到总重量的所有可能的值 for(int i 1; i sum; i)//0不可能,故从1开始遍历if(f[n][i]) ans;cout ans;return 0;
}
心得体会
1、定义一个大小为 N×M 的二维数组 f其中 f[i][j] 表示在前 i 个砝码中是否可以通过选择一些砝码使得它们的总重量等于 j。M 的取值为 sum 的两倍因为最坏情况下所有砝码都放在一侧另一侧没有砝码。
2、当我们计算 f[i][j] 时我们需要考虑前 i 个砝码中是否存在一些砝码的选择使得它们的总重量等于 j。
f[i][j] f[i-1][jw[i]]这个转移表示我们选择了第 i 个砝码并将其放在另一侧以抵消重量 w[i]使得总重量达到 j。因此我们可以从前 i-1 个砝码中选择一些砝码使得它们的总重量为 jw[i]。f[i][j] f[i-1][abs(j-w[i])]这个转移表示我们选择了第 i 个砝码并把它加到总重量为 j 的一侧使得总重量达到 j。因此我们可以从前 i-1 个砝码中选择一些砝码使得它们的总重量为 abs(j-w[i])。
这两个转移的含义是根据砝码的放置方式进行考虑的。我们可以选择将第 i 个砝码放在天平的左侧或右侧或者不选择第 i 个砝码。因此通过考虑这些不同的放置方式我们可以计算出 f[i][j] 的值。
3、这个题一开始拿到就觉得肯定不是简单的正向思维果然是套者一个东西来做整体遍历的。 蓝桥杯2021年第十二届省赛真题-异或数列
题目描述
Alice 和 Bob 正在玩一个异或数列的游戏。初始时Alice 和 Bob 分别有一个整数 a 和 b有一个给定的长度为 n 的公共数列 X1, X2, · · · , Xn。 Alice 和 Bob 轮流操作Alice 先手每步可以在以下两种选项中选一种 选项 1从数列中选一个 Xi 给 Alice 的数异或上或者说令 a 变为 a ⊕ Xi。其中 ⊕ 表示按位异或 选项 2从数列中选一个 Xi 给 Bob 的数异或上或者说令 b 变为 b ⊕ Xi。每个数 Xi 都只能用一次当所有 Xi 均被使用后n 轮后游戏结束。游戏结束时拥有的数比较大的一方获胜如果双方数值相同即为平手。 现在双方都足够聪明都采用最优策略请问谁能获胜
输入格式
每个评测用例包含多组询问。询问之间彼此独立。 输入的第一行包含一个整数 T表示询问数。 接下来 T 行每行包含一组询问。其中第 i 行的第一个整数 ni 表示数列长度随后 ni 个整数 X1, X2, · · · , Xni 表示数列中的每个数。
输出格式
输出 T 行依次对应每组询问的答案。 每行包含一个整数 1、0 或 1 分别表示 Alice 胜、平局或败。
样例输入
4
1 1
1 0
2 2 1
7 992438 1006399 781139 985280 4729 872779 563580
样例输出
1
0
1
1提示 思路提示
使用res记录所有x的异或结果
1、res0,平局
2、res!0( num数组记录每位的1的个数从最高位for(i)查看Number[i] ) 1num[i]1该位数只要一个1Alice 先手胜 2num[i]是偶数无影响不处理 3num[i]是奇数① n是偶数1是奇数那么0是奇数只要后手把0先选完后手就获得最后一个1的支配权后手胜。②同理可得n是奇数0是偶数先手把0先选完先手获得最后一个1的支配权,先手胜
3、异或赋值运算符 ^
4、if(x1) num[cnt];判断 x 的最低位是否为 1即 x 的二进制表示的最低位是否为 1。如果是则将数组 num 中对应位置 cnt 的计数值加 1。
1x1 是按位与操作用来提取 x 的最低位的值。因为 1 的二进制表示为 0001其他位为 0所以与 1 进行按位与操作就可以得到 x 的最低位的值。
2如果 x 的最低位为 1说明当前位上有一个 1所以将数组 num 中对应位 cnt 的计数值加 1。
代码表示
#include bits/stdc.h
using namespace std;int num[22]; //记录每位的1的个数
void pre(int x)//计算一个数的二进制表示中每位上 1 的个数
{int cnt1;while(x){if(x1) num[cnt];
//将 x 右移一位即将 x 的二进制表示向右移动一位。x1;cnt;}
}
int main(){int T; //询问数cinT;while(T--){memset(num,0,sizeof(num));int n,res0; //res存储xi元素异或结果 cinn; for(int i0;in;i){int x;scanf(%d,x);pre(x);//异或 相同的数异或结果为 0不同的数异或结果为 1res^x; }if(res0){
//平局先手无论怎么选择后手都可以通过合理的选择使得异或结果保持为 0 printf(0\n); }else{for(int k20;k0;k--){if(num[k]1){printf(1\n);break;}//1的个数是奇数 if(num[k]%21){if(n%20){//1是奇数n是偶数那么0是奇数只要后手把0先选完后手就获得最后一个1的支配权后手胜 printf(-1\n); break; }else{
//同理可得n是奇数0是偶数先手把0先选完先手获得最后一个1的支配权,先手胜利printf(1\n); break;}}}}}return 0;
}蓝桥杯第十二届省赛真题-左孩子右兄弟再看
题目描述
对于一棵多叉树我们可以通过 “左孩子右兄弟” 表示法将其转化成一棵二叉树。 如果我们认为每个结点的子结点是无序的那么得到的二叉树可能不唯一。换句话说每个结点可以选任意子结点作为左孩子并按任意顺序连接右兄弟。 给定一棵包含 N 个结点的多叉树结点从 1 至 N 编号其中 1 号结点是根每个结点的父结点的编号比自己的编号小。请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树高度最高是多少。注只有根结点这一个结点的树高度为 0 。
例如如下的多叉树 输入格式
输入的第一行包含一个整数 N。 以下 N 1 行每行包含一个整数依次表示 2 至 N 号结点的父结点编号。
输出格式
输出一个整数表示答案。
样例输入
5
1
1
1
2样例输出
4提示
【评测用例规模与约定】
对于 30% 的评测用例1 ≤ N ≤ 20对于所有评测用例1 ≤ N ≤ 100000。
代码表示
方法一深搜
对于节点 i在其子节点中找出令该节点作为根节点时可以使高度最大的节点 j
令节点 j 作为 i 的子节点中最后一个出现的节点可使高度达到最大。
#include bits/stdc.h
using namespace std;
const int MAXN 100005;//最大结点数 int n, tmp;
vectorint mp[MAXN];//存储多叉树的边关系 //递归函数 dfs计算以结点 idx 为根的子树的高度。
int dfs(int idx)
{int sz mp[idx].size();//获取结点 idx 的子结点的个数int ans 0;//存储最大高度 for (int i 0; i sz; i) {//更新 ans取当前子树的高度和已有的最大高度的较大值。 ans max(ans, dfs(mp[idx][i]));}return ans sz;//最大子树高度加上当前结点的子结点个数
}int main() {cin n;for (int i 2; i n; i) {cin tmp;//读取结点 i 的父结点编号存储到 tmp 中mp[tmp].push_back(i);//将结点 i 添加为结点 tmp 的子结点}cout dfs(1) endl;//计算以结点 1 为根的子树的高度return 0;
}
方法二动态规划
用数组 s[i] 表示节点 i 的子节点个数用数组 f[i] 表示节点 i 的父节点dp[i] 表示当节点 i 作为根节点时的最大高度可以推断出如下状态转移方程dp[ f [ i ] ] max(dp[ f [ i ] ], s[ f [ i ] ] dp[ i ]);
由于子节点一定比父节点的编号大所以对节点编号逆向遍历即可。
1、逆序的循环从最后一个节点开始逐步向前遍历每个节点。
在循环中我们首先通过 int fa f[i]; 语句获取当前节点 i 的父节点编号并将其存储在变量 fa 中。然后我们使用 dp[fa] max(dp[fa], s[fa] dp[i]); 更新父节点 fa 的最大高度。这行代码的目的是比较父节点 fa 的当前最大高度 dp[fa] 可能还有其他同级的点和考虑将当前节点 i 作为子节点时的高度 s[fa] dp[i]然后取二者中的较大值并将较大值赋值给 dp[fa]从而更新父节点的最大高度。
这个循环的作用是逐步从叶节点向根节点更新每个节点的最大高度确保每个节点的最大高度都被正确计算和更新。通过这个过程我们最终可以得到整棵树的最大高度。
2、dp[fa] 表示节点 fa父节点作为根节点时的最大高度。s[fa] 表示节点 fa 的子节点个数。dp[i] 表示节点 i 作为根节点时的最大高度。
#include bits/stdc.h
using namespace std;
const int MAXN 100005;//temp:存储读取到的节点 i 的父节点编号
int n, tmp;
//下面分别是子节点个数、父节点和最大高度
int s[MAXN], f[MAXN], dp[MAXN];int main()
{cin n;for (int i 2; i n; i) {cin tmp;f[i] tmp;s[tmp];}
//逆向遍历节点编号更新节点 fa 作为根节点时的最大高度for (int i n; i 1; i--) {int fa f[i];//获取结点 i 的父结点编号dp[fa] max(dp[fa], s[fa] dp[i]);}cout dp[1] endl;return 0;
}蓝桥杯第十二届省赛真题-括号序列
题目描述
给定一个括号序列要求尽可能少地添加若干括号使得括号序列变得合法当添加完成后会产生不同的添加结果请问有多少种本质不同的添加结果。两个结果是本质不同的是指存在某个位置一个结果是左括号而另一个是右括号。 例如对于括号序列 ((()只需要添加两个括号就能让其合法有以下几种不同的添加结果()()()、()(())、(())()、(()()) 和 ((()))。
输入格式
输入一行包含一个字符串 s表示给定的括号序列序列中只有左括号和 右括号。
输出格式
输出一个整数表示答案答案可能很大请输出答案除以 1000000007 (即109 7) 的余数。
样例输入
((()
样例输出
5提示
【评测用例规模与约定】
对于 40% 的评测用例|s| ≤ 200。
对于所有评测用例1 ≤ |s| ≤ 5000。
代码表示
#include bits/stdc.h
using namespace std;const int N 5005;
int f[N][N];
int mod 1e9 7;
string s;
int n;long long get() {memset(f, 0, sizeof f);//memset 将二维数组 f 初始化为全零f[0][0] 1;for (int i 1; i n; i) {if (s[i - 1] () {for (int j 1; j n; j)f[i][j] f[i - 1][j - 1];//表示在当前位置放置一个左括号} else {
//需要考虑两种情况。
//第一是不将当前位置的括号与之前的任何位置的括号匹配 f[i][0] 的值为 f[i-1][1] f[i-1][0]。
//第二是将当前位置的括号与之前的某个位置的括号匹配 f[i][j] 的值为 f[i-1][j1] f[i][j-1]f[i][0] (f[i - 1][1] f[i - 1][0]) % mod;for (int j 1; j n; j)f[i][j] (f[i - 1][j 1] f[i][j - 1]) % mod;}}
//我们遍历 f[n] 数组的所有元素如果某个元素不为零则返回它作为结果。
//如果所有元素都为零则返回 -1for (int i 0; i n; i) {if (f[n][i])return f[n][i];}return -1;
}int main() {cin s;n s.size();long long x get();reverse(s.begin(), s.end());for (int i 0; i n; i) {if (s[i] ))s[i] (;elses[i] );}long long y get();cout (x * y) % mod;return 0;
}心得体会
在赛场上骗分的时候要用所给的示例确实有一点点的分
