如何通过网站开发客户,wordpress会员互动,淮北电子商务网站建设,app对接广告联盟十二届省赛题
第十二届蓝桥杯省赛CC 研究生组-卡片 第十二届蓝桥杯省赛CC 研究生组-直线 第十二届蓝桥杯省赛CC 研究生组-货物摆放 第十二届蓝桥杯省赛CC 研究生组-路径 第十二届蓝桥杯省赛CC 研究生组-时间显示 第十二届蓝桥杯省赛CC 研究生组…十二届省赛题
第十二届蓝桥杯省赛CC 研究生组-卡片 第十二届蓝桥杯省赛CC 研究生组-直线 第十二届蓝桥杯省赛CC 研究生组-货物摆放 第十二届蓝桥杯省赛CC 研究生组-路径 第十二届蓝桥杯省赛CC 研究生组-时间显示 第十二届蓝桥杯省赛CC 研究生组-砝码称重 第十二届蓝桥杯省赛CC 研究生组-异或数列 第十二届蓝桥杯省赛CC 研究生组-双向排序
三年小小结
水过了最新三年的题目小小复盘一下~
简单模拟 卡片填空从1开始计算每位所用卡片当某个数字的卡片不足时则找到能拼到的最大数。注意最后的这个数是拼不出来的第一个数所以答案记得减一。作为填空题枚举即可解决该题目进一步思考的话一定是卡片1消耗量最大可转化为1出现2021次的数字 直线填空判断给定范围内的点能组成多少条不同直线表面考算法其实是考数学公式~注意分母不为0直接把平行于y轴的单算即可记得后续加上。 时间显示常见的时间处理类问题小小注意下小时是24小时制。需要显示的时间是时0-23分0-59秒0-59给的输入是从00-00-00开始的毫秒数则该先除的先除该求余的求余。给的年份就是迷惑性信息了木用忽略即可。 裁纸刀填空先裁四下去掉边缘再把行分开行数-1再把列分开列数-1*行数。甚至都没啥小坑温柔 灭鼠先锋填空手动可以直接模拟~ 再优化一点点的话对于一行空内容的话谁先手谁必输问题等价于谁后把第一行填满谁就一定能保证自己赢。问题分解的思想很有效简单分割也许就能大幅简化问题 与或异或填空电路图看起来挺唬人的但枚举就能解决的纸。本质上就是按照a[i][j] a[i-1][j] op a[i-1][j1]其中op可选、^、|其一统计结果为1的组合个数。 翻转翻转规则为出现010或101就可以把中间的值翻转借助翻转的情况下是否能把两个串变相同如果是输出最小翻转次数。虽然题设中有“翻转操作可无限重复”但其实一次翻转即可翻完了其实也就不能出现不同了属于干扰信息。以s串1010101为例翻转第一次1000101翻转第二次1000111搞定。
excel
工作时长填空本质上要求的是两个时间段之差的和。用excel先排序再选择时间格式[h]:mm:ss注意小时的选择以处理超出24小时的情况计算两个时间段的差关于求出整列的上下行间的时间差先手算两个单元格后续直接下拉即可自动计算求和
数学问题
质因数
很稳定每年都考了一个或直接或加了点马甲
货物摆放填空整数分解问题。n较大直接暴力枚举不可行考虑当时质因数模块学过整数范围内一定能用十个质因数表示类推n的约数也不会太多转化为先求出n的约数别漏了1和n再计算相乘为n的组合个数质因数个数给出整数n的质因数个数
sqr sqrt(1.0*n);
num 0;
for(int i 2; i sqr; i){if(n % i 0){num;while(n % i 0) n / i;}
}
if(n 1) num;//别漏了最后这个顽固分子~公因数匹配找到首次出现或同时出现但最短的区间满足头尾元素有大于1的公因数。直接暴力的话两层的105超时有了之前的经验也考虑下先分解看看。分解每个数的所有质因数如果没出现过则记录首次出现的位置如果已经出现过判断是否需要更新最左位置。判断该数满足的区间是否早于或短于已有的区间若是则更新。
#includestdio.h
#includemath.h
const int maxn 1e6 10;
int p[maxn] {0};
int main(){int n, x, l, ansL, ansR 0, sqr;scanf(%d, n);ansL n 1;for(int i 1; i n; i){l n 1;scanf(%d, x);sqr sqrt(1.0 * x);for(int j 2; j sqr; j){if(x % j 0){if(!p[j]) p[j] i;else if(p[j] l) l p[j];while(x % j 0) x / j;}}if(x 1){if(!p[x]) p[x] i;else if(p[x] l) l p[x];}if(l ansL || (ansL l ansR i)){ansL l;ansR i;}}printf(%d %d, ansL, ansR);return 0;
} 说都说了顺带复习下最小公约数最大公倍数
int gcd(int a, int b){//辗转相除法求最大公约数时间复杂度O(logn) if(!b) return a;return gcd(b, a % b);
}最小公倍数为a * b / gcd(a, b) 数的拆分给出整数n将其拆分为x2* y3(大于2和偶数次幂可以转化为底数先升幂再把幂次调到2奇数次幂同理,例如x4x2的平方y5y2的平方 *y)的形式则可拆分返回yes否则返回no。n最大为10e18,开五次方大约是4000则我们对4000以内的质数打表分解后的约数就不会太大了。判断是否能够融入我们要求的模式即能否转化为平方或立方能则该数可以拆分否则是个单蹦不能拆分。
进制转换
异或数列十进制转二进制。各方初始值为0给定数列选数异或每个数只能选用一次。显然谁先抢到最高位的“唯一”1个或奇数的单蹦1一个1则必胜。问题转化为寻找 最高位的唯一的一个1最高位的偶数个1 总的零的数量为偶数个先手拿到单蹦1则必胜总的零的数量为奇数个后手拿到单蹦1则必胜
否则为平局 2.
阶乘特点
阶乘的和直接算的话肯定超时而且仔细想来只是求最大的m并不需要真的算出和只是能进行比较即可算出来也是多余工作。回到问题本身阶乘m!我们有多个ai!对于多个阶乘有(m1)m! (m1)!我们对ai进行排序顺带统计每个数的出现次数要有序且有映射关系考虑用map自底到高统计每位是否能进位第一个不能进位前的数就是我们要找的m
求余
GCD考查辗转相除法和求余的简化。思维更简单的解法观察知最大公约数是abs(a-b)从1开始依次枚举即可能骗些分数。进一步思考的话回到问题本身 找使得gcd(ak,bk)最大的k根据辗转相除算法知gcd(ak,bk)gcd(bk,b-a)gcd(bk,b-a) b-a假设已经处理好能保证b a转化为找到满足(bk)%(b-a) 0的最小值记g b- a则(bk)%g (b % g k % g) % g 0 b % g g, k % g g,则g - b % g k
#includeiostream
#includealgorithm
using namespace std;
int main(){long long a, b, g;scanf(%lld%lld, a, b);if(a b) swap(a, b);g b - a;printf(%lld, g - b % g);return 0;
} 观察规律
全排列的价值观察给出的样例知对于1~n, 前后两两价值相加的和都相等为(n-1)*n/2;那再看可以组数也就是排列数n!/2除2是因为两两一组相加才为定值
动态规划
砝码称重很经典的一个问题。我们能称出来的最大重量是所有砝码重量之和最小的可能重量是1其中题设告诉我们砝码总重范围也是一种暗示了。 利用dp的话我们依次计算有1~n个砝码能称出来的重量首先前i个砝码能称出来的重量也一定能用前i1个砝码称出来。对于前i个砝码的判断之前称不出来的重量m考虑 第i个砝码重量w[i] m已经可以称出来m w[i]已经可以称出来abs(m - w[i]) m w[i],能称出来m-w[i]则再加个w[i]w[i] m,能称出来w[i]-m则在对面来个w[i]
最后统计用n个砝码所能称出的重量个数即可
int dp[N][maxn] {0};
count 0;
for(int i 1; i n; i){for(int j 1; j sum; j){dp[i - 1][j] 1;if(!dp[i][j]){if(w[i] j || a[i - 1][j w[i]] || a[i - 1][abs(j - w[i])]) dp[i][j] 1;}}
}for(int i 1; i sum; i)count dp[n][i];莫队算法
重复的数很直给的一个莫队情况大致思想是首先只适用于可离线的情况对元素进行分块对查询区间排序同块则按照右边界排序不同块按照块号排序处理查询
m叉树
子树的大小 对于m叉树的第i个结点第一个结点号为(i - 1) * m 2满m叉树时第i个结点的最右孩子为i*m 1(这个1是根节点)总结点数为n的完全m叉树最后一个分支节点的最右孩子为n
