怎样制作单页网站,前端实战项目11套,wordpress数据库没有填写,游戏推广赚佣金尝试再做一次#xff0c;我记得还是有点难#xff0c;我会尽量多写一点解析#xff0c;尽量让基础比较弱的友友也能看懂#xff0c;希望能给你带来帮助
目录
1. 日期统计
题目描述
解题思路
具体代码
2. 01 串的熵
题目描述
解题思路
具体代码
3. 冶炼金属
题目… 尝试再做一次我记得还是有点难我会尽量多写一点解析尽量让基础比较弱的友友也能看懂希望能给你带来帮助
目录
1. 日期统计
题目描述
解题思路
具体代码
2. 01 串的熵
题目描述
解题思路
具体代码
3. 冶炼金属
题目描述
解题思路
具体代码
4. 飞机降落
题目描述
解题思路
具体代码
5. 接龙数列
题目描述
解题思路
具体代码
6. 岛屿个数待写
题目描述
解题思路
具体代码
7. 子串简写
题目描述
解题思路
具体代码
8. 整数删除待写
题目描述
解题思路
具体代码 1. 日期统计
题目描述
小蓝现在有一个长度为 100 的数组数组中的每个元素的值都在 0 到 9 的
范围之内。数组中的元素从左至右如下所示 5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1 0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3 现在他想要从这个数组中寻找一些满足以下条件的子序列 1. 子序列的长度为 8 2. 这个子序列可以按照下标顺序组成一个 yyyymmdd 格式的日期并且 要求这个日期是 2023 年中的某一天的日期例如 20230902 20231223 。 yyyy 表示年份 mm 表示月份 dd 表示天数当月份或者天数的长度只 有一位时需要一个前导零补充。 请你帮小蓝计算下按上述条件一共能找到多少个 不同 的 2023 年的日期。 对于相同的日期你只需要统计一次即可。
解题思路
这道题在赛场上大家可能和我一样脑子里面第一想法就是循环遍历反正就8次我也是这么做的后面我的老师给我介绍了另一种解法我都写一下
方法一
直接简单粗暴地循环唯一需要注意的是记得筛出重复的日期我用的set(不太清楚set用法的友友需要自己查一下哦)自动帮我去重我将每次符合条件的日期一个八位数的数字insert到set容器中后面循环结束后set的长度就是满足要求的日期的个数(具体代码在下面)
方法二
这是老师赛后告诉我的我看见网上也有很多这样写的。不需要循环原本的数组而是循环遍历2023年的每一天看看这一天年-月-日这八个数字是否在原数据中也顺序出现这种解法就不要考虑有相同日期的情况(我文字描述不太清楚可以直接看下面的代码看了就知道)
具体代码
方法一代码
这个代码看起来很长其实很简单(思路见上)就是八重循环但是需要仔细再仔细代码里面我也有写注释可以看看不难 // 长度为8 2023 01 24
#include bits/stdc.h
using namespace std;
typedef long long ll;
const int N 3e5 24 , M 1e9 24 , n 100;
// 原数据
int m[100] {5 ,6 ,8 ,6 ,9 ,1 ,6 ,1 ,2 ,4 ,9 ,1 ,9 ,8 ,2 ,3 ,6 ,4 ,7 ,7 ,5 ,9 ,5 ,0 ,3 ,8 ,7 ,5 ,8 ,1 ,5 ,8 ,6 ,1 ,8 ,3 ,0 ,3 ,7 ,9 ,2 ,7 ,0 ,5 ,8 ,8 ,5 ,7 ,0 ,9 ,9 ,1 ,9 ,4 ,4 ,6 ,8 ,6 ,3 ,3 ,8 ,5 ,1 ,6 ,3 ,4 ,6 ,7 ,0 ,7 ,8 ,2 ,7 ,6 ,8 ,9 ,5 ,6 ,5 ,6 ,1 ,4 ,0 ,1, 0 ,0 ,9 ,4 ,8 ,0 ,9 ,1 ,2 ,8 ,5 ,0 ,2 ,5 ,3 ,3};
// 存每月有多少天
int D[] {0 , 31 , 28 , 31 , 30 , 31, 30 , 31 , 31 , 30 , 31 , 30 , 31};
setint s; //用set记录满足要求的日期(数字)自动会去重这样set中数字的个数就是答案
int main()
{int a , b , c , d , e , f , j , h , day , month , date;
// 1、确保前面4个数字是 2023 abcdfor(a 0 ; a n ; a ){if(m[a] 2) // 2{for(b a1 ; b n ; b ){if(m[b] 0) // 0{for(c b1 ; c n ; c ){if(m[c] 2) // 2{for(d c1 ; d n ; d ){if(m[d] 3) // 3{
// 2、保证后面四位 月-日符合逻辑 efjhfor(e d1 ; e n ; e ){for(f e1 ; f n ; f ){
// 几月 满足month在1-12 month m[e]*10 m[f];if(month 1 month 12){for(j f1 ; j n ; j ){for(h j1 ; h n ; h ){
// 几日 满足day在1-D[month]对应月的日期内 day m[j]*10 m[h];if(day 1 day D[month]){date 2023*10000 month*100 day;s.insert(date);}}}}}}}}}}}} }}cout s.size();return 0 ;
}
方法二代码
代码里面的注释写的比较详细可以看看
// 方法二 // 长度为8 2023 01 24
#include iostream
#include algorithm
#include cmath
using namespace std;
typedef long long ll;
const int N 3e5 24 , M 1e9 24 , n 100;
// 原数据
int m[100] {5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7, 5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5,8, 6, 1, 8, 3, 0, 3, 7, 9, 2, 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3, 8, 5,1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6, 1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2,8, 5, 0, 2, 5, 3, 3};
// 存每月有多少天
int D[] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main()
{int month, day, i, j, ans 0 ;// 遍历2023年的12个月 for(month 1 ; month 12 ; month ){
// 遍历每一天 for(day 1 ; day D[month] ; day ){string str 2023;if(month 10) str 0; //月份只有一位数需要0填充
// to_string将数字类型的变量转换为对应的字符串表示str to_string(month);if(day 10) str 0; //天数只有一位数需要0填充 str to_string(day);
// 判断现在的str(这是一个8位数字组成的字符串表示一个日期)
// 判断字符串的8个字符是否在原数据m[]中存在按照顺序// i是原数据m[]的索引,j是str的索引 for(i 0 , j 0 ; i n j 8 ; i ){if(m[i] str[j] - 0) //如果str[j]这个这个数字在m[中存在] {j ; // j索引后移用于判断下一个 }} if(j 8) ans ;} }cout ans ;return 0 ;
}
2. 01 串的熵
题目描述
文字复制过来格式有误采用截图请见谅 解题思路
我的解法也比较没有技术含量根据题意
我们假设0出现了x次1出现了23333333-x次 可以发现H(S)的值就是等于 带入公式中之后将x从0~23333333遍历 如果答案大于23333333/2记得把答案更新为23333333-ans因为0出现的次数小于1的次数。
考试的时候我想的是根据公式推导出x的值但是实在是不好算就另辟蹊径直接粗暴的遍历【怪不得大家又称蓝桥杯为暴力杯哈哈】
答案11027421
具体代码
#include bits/stdc.h
using namespace std;
typedef long long ll;
const int N 3e5 24 , M 1e9 24 ;int n 23333333;
double Hs 11625907.5798;
int main()
{
// cout log2(4);int x , ans ;double temp;for(x 0 ; x n ; x ){double temp -x*1.0/n*log2(x*1.0/n)*x - (n-x)*1.0/n*log2((n-x)*1.0/n)*(n-x);if(abs(temp - Hs) 0.0001){if(x n/2) ans n - x;else ans x;break;}}cout ans ;return 0 ;
}// 答案11027421
3. 冶炼金属
题目描述
【问题描述】
小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个 炉子有一个称作转换率的属性 VV 是一个正整数这意味着消耗 V 个普通金 属 O 恰好可以冶炼出一个特殊金属 X当普通金属 O 的数目不足 V 时无法 继续冶炼。 现在给出了 N 条冶炼记录每条记录中包含两个整数 A 和 B这表示本次 投入了 A 个普通金属 O最终冶炼出了 B 个特殊金属 X。每条记录都是独立 的这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。 根据这 N 条冶炼记录请你推测出转换率 V 的最小值和最大值分别可能是 多少题目保证评测数据不存在无解的情况。
【输入格式】
第一行一个整数 N表示冶炼记录的数目。 接下来输入 N 行每行两个整数 A、B含义如题目所述。
【输出格式】 输出两个整数分别表示 V 可能的最小值和最大值中间用空格分开。
【样例输入】
3
75 3
53 2
59 2
【样例输出】
20 25
【样例说明】
当 V 20 时有⌊ 75/ 20 ⌋ 3⌊ 53/ 20 ⌋ 2⌊ 59/ 20 ⌋ 2可以看到符合所有冶炼 记录。 当 V 25 时有⌊ 75 /25 ⌋ 3⌊ 53/ 25 ⌋ 2⌊ 59/ 25 ⌋ 2可以看到符合所有冶炼记录。
且再也找不到比 20 更小或者比 25 更大的符合条件的 V 值了。
【评测用例规模与约定】
对于 30% 的评测用例1 ≤ N ≤ 10^2。
对于 60% 的评测用例1 ≤ N ≤ 10^3。
对于 100% 的评测用例1 ≤ N ≤ 10^41 ≤ B ≤ A ≤ 10^9。
解题思路
题目的意思还是挺好理解的主要在V的最大值和最小值其实是一个求交集的过程只有交集才能满足每一个数据的要求也就是右边界要取所有右边界的最小值每组数据求出来的最大值中的最小值左边界同理需要所有求出来的左边界的最大值每组数据求出来的最小值中的最大值这个还是挺好理解的如果实在不太理解建议用样例验证一下比较容易
现在我们来看看怎么求每组数据对应的最大值与最小值 最大值这个比较简单我们知道投入了 a 个普通金属 O最终冶炼出了 b 个特殊金属 X那么V的最大值就是a/b没有比这个还大的值了 最小值假设最小值为vmin那么肯定存在a/vmin b ,a/vmin取的是整数因为vmin是金属O转换成X的转换率最小值如果vmin减小一个单位那么肯定b的值会增加一个单位能理解吗就是本来a/vmin就能冶炼出b个X而vmin是冶炼出b个X的最小值如果vmin减少肯定b会增加所以我们可得a/(vmin-1) b1那么vmin a/(b1)1 我的表达能力不太好希望你能理解 具体代码
那看看代码我没怎么写注释就几行就能解决如果不太懂看看上面的思路
#include bits/stdc.h
using namespace std;
typedef long long ll;
int main()
{int n , a , b , vmax 0x3f3f3f3f , vmin 0;cin n;while(n --){cin a b ;vmax min(vmax , a/b);vmin max(vmin , a/(b1)1);}cout vmin vmax endl; return 0 ;
}
出现一个很变态的事发现我把int改成longlong就过不了这道题其实题目范围是在int内我就是不理解为什么用longlong就不行。
4. 飞机降落
题目描述
【问题描述】 N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻 到达机场上空到达时它的剩余油料还可以继续盘旋 Di 个单位时间即它最早 可以于 Ti 时刻开始降落最晚可以于 Ti Di 时刻开始降落。降落过程需要 Li 个单位时间。 一架飞机降落完毕时另一架飞机可以立即在同一时刻开始降落但是不 能在前一架飞机完成降落前开始降落。 请你判断 N 架飞机是否可以全部安全降落。
【输入格式】
输入包含多组数据。 第一行包含一个整数 T代表测试数据的组数。 对于每组数据第一行包含一个整数 N。 以下 N 行每行包含三个整数TiDi 和 Li。
【输出格式】
对于每组数据输出 YES 或者 NO代表是否可以全部安全降落。
【样例输入】
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
【样例输出】
YES
NO
【样例说明】 对于第一组数据可以安排第 3 架飞机于 0 时刻开始降落20 时刻完成降 落。安排第 2 架飞机于 20 时刻开始降落30 时刻完成降落。安排第 1 架飞机 于 30 时刻开始降落40 时刻完成降落。 对于第二组数据无论如何安排都会有飞机不能及时降落。
【评测用例规模与约定】
对于 30% 的数据N ≤ 2。
对于 100% 的数据1 ≤ T ≤ 101 ≤ N ≤ 100 ≤ Ti , Di , Li ≤ 10^5。
解题思路
因为这道题的数据范围比较少我用的是全排列获取了每种情况分别看是否能成功降落如果存在一种就YES如果全排列的所有情况都不行就NO
具体可以看代码里面的注释
具体代码
// 数据不多 直接全排列列举所有可能
#include bits/stdc.h
using namespace std;
typedef long long ll;
struct point{int t , d , l ; //到达 盘旋 降落时间
}p[24];
void answer()
{int n , i , j , t , d , l , now ;bool flag true;
// a是下表数据表示所有情况
// 通过全排列a的情况实则是每架飞机的情况不同的降落方案 int a[14]; // 1 n 10cin n ;for(i 1; i n ; i ){a[i] i ;cin p[i].t p[i].d p[i].l;}
// 开始全排列列举所有情况
// 只要有一种情况满足要求能成功降落就算YES,否则NO do{flag true ; //表示是否成功now 0 ; // 表示此刻的时间 for(i 1 ; i n ; i ){//到达 盘旋 降落时间 t p[a[i]].t , d p[a[i]].d , l p[a[i]].l ;/*我们知道每架飞机能够成功降落的时间在 t ~ tl那么now可以在三个区间返回内 分别是 nowt tnowtl tlnow1、now tl 这种情况肯定不行现在的时间点已经超过飞机降落 2、now tl 这又分两种2.1 tnow 需要这架飞机等一下2.2 nowt 需要等飞机在t时间到来需要等飞机一个是飞机等另一中等飞机 */if(now td){flag false ; //失败break ; //结束开始下一组排列情况 } else{if(now t){now now l ;}else{now t l ;}}}if(flag){
// 这组排列满足安排可行直接结束就行只有找到一组情况就行又不是找最优 cout YES endl;return ; }}while(next_permutation(a1 , an1));cout NO endl;
}
int main()
{int t;cin t ;while(t --){answer();}return 0 ;
}
5. 接龙数列 题目描述
【问题描述】
对于一个长度为 K 的整数数列A1, A2, . . . , AK我们称之为接龙数列当且 仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字 (2 ≤ i ≤ K)。 例如 12, 23, 35, 56, 61, 11 是接龙数列12, 23, 34, 56 不是接龙数列因为 56 的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。 现在给定一个长度为 N 的数列 A1, A2, . . . , AN请你计算最少从中删除多少 个数可以使剩下的序列是接龙序列
【输入格式】
第一行包含一个整数 N。 第二行包含 N 个整数 A1, A2, . . . , AN。
【输出格式】
一个整数代表答案。
【样例输入】
5
11 121 22 12 2023
【样例输出】
1
【样例说明】
删除 22剩余 11, 121, 12, 2023 是接龙数列。
【评测用例规模与约定】
对于 20% 的数据1 ≤ N ≤ 20。
对于 50% 的数据1 ≤ N ≤ 10000。
对于 100% 的数据1 ≤ N ≤ 10^51 ≤ Ai ≤ 10^9。所有 Ai 保证不包含前导 0。
解题思路
这道题用的dpdp[i]表示以i0i9为结尾最长可以组成多长那么答案就是n-max(dp[i]),max(dp[i])是能组成的最长的长度
对于每一个数字我会用head和tail存下这个数的第一个/最后一个数字的值 核心dp[p[i].tail] max(dp[p[i].tail] , dp[p[i].head] 1); p[i].head和p[i].tail表示第i个数的头部和尾部
dp[p[i].tail]表示以p[i].tail0p[i].tail9为结尾最长可以组成多长
在dp[p[i].tail]过去的值和dp[p[i].head] 1求最大值dp[p[i].head] 1表示在以p[i].head为结尾的数的基础上再加一家的这个值就是第i个数
具体代码
// 数据不多 直接全排列列举所有可能
#include bits/stdc.h
using namespace std;
typedef long long ll;
const int N 1e5 24;
struct point{int head , tail; //表示的是每一个整数的开头和结尾数字
}p[N];
int dp[12]; // i0i9为结尾最长可以组成多长
int main()
{int n , a , i , j , ans N;cin n ;for(i 1 ; i n ; i ){cin a;p[i].tail a%10; //尾部数字 while(a 10){a / 10;}p[i].head a; // 头部数据 }for(i 1 ; i n ; i ){dp[p[i].tail] max(dp[p[i].tail] , dp[p[i].head] 1);} for(i 0 ; i 10 ; i ){ans min(ans , n-dp[i]);}cout ans ;return 0 ;
}
6. 岛屿个数待写
题目描述
【问题描述】
小蓝得到了一副大小为 M × N 的格子地图可以将其视作一个只包含字符 ‘0’代表海水和 ‘1’代表陆地的二维数组地图之外可以视作全部是海水 每个岛屿由在上/下/左/右四个方向上相邻的 ‘1’ 相连接而形成。 在岛屿 A 所占据的格子中如果可以从中选出 k 个不同的格子使得 他们的坐标能够组成一个这样的排列(x0, y0),(x1, y1), . . . ,(xk−1, yk−1)其中 (x(i1)%k , y(i1)%k) 是由 (xi , yi) 通过上/下/左/右移动一次得来的 (0 ≤ i ≤ k − 1) 此时这 k 个格子就构成了一个 “环”。如果另一个岛屿 B 所占据的格子全部位于 这个 “环” 内部此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若 B 是 A 的子 岛屿C 又是 B 的子岛屿那 C 也是 A 的子岛屿。 请问这个地图上共有多少个岛屿在进行统计时不需要统计子岛屿的数目。
【输入格式】 第一行一个整数 T表示有 T 组测试数据。 接下来输入 T 组数据。对于每组数据第一行包含两个用空格分隔的整数 M、N 表示地图大小接下来输入 M 行每行包含 N 个字符字符只可能是 ‘0’ 或 ‘1’。
【输出格式】
对于每组数据输出一行包含一个整数表示答案。
【样例输入】
2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111
【样例输出】
1
3
【样例说明】
对于第一组数据包含两个岛屿下面用不同的数字进行了区分 01111 11001 10201 10001 11111 岛屿 2 在岛屿 1 的 “环” 内部所以岛屿 2 是岛屿 1 的子岛屿答案为 1。 对于第二组数据包含三个岛屿下面用不同的数字进行了区分 111111 100001 020301 100001 111111
注意岛屿 3 并不是岛屿 1 或者岛屿 2 的子岛屿因为岛屿 1 和岛屿 2 中均没有 “环”。
【评测用例规模与约定】
对于 30% 的评测用例1 ≤ M, N ≤ 10。
对于 100% 的评测用例1 ≤ T ≤ 101 ≤ M, N ≤ 50。
解题思路
暂无我自己写不出来先看看别人的抱歉
具体代码
暂无
7. 子串简写
题目描述
【问题描述】
程序猿圈子里正在流行一种很新的简写方法对于一个字符串只保留首 尾字符将首尾字符之间的所有字符用这部分的长度代替。例如 internationalization 简写成 i18nKubernetes 注意连字符不是字符串的一部分简 写成 K8s, Lanqiao 简写成 L5o 等。 在本题中我们规定长度大于等于 K 的字符串都可以采用这种简写方法 长度小于 K 的字符串不配使用这种简写。 给定一个字符串 S 和两个字符 c1 和 c2请你计算 S 有多少个以 c1 开头 c2 结尾的子串可以采用这种简写
【输入格式】
第一行包含一个整数 K。
第二行包含一个字符串 S 和两个字符 c1 和 c2。
【输出格式】
一个整数代表答案。
【样例输入】
4
abababdb a b
【样例输出】
6
【样例说明】
符合条件的子串如下所示中括号内是该子串
[abab]abdb
[ababab]db
[abababdb]
ab[abab]db
ab[ababdb]
abab[abdb]
【评测用例规模与约定】
对于 20% 的数据2 ≤ K ≤ |S | ≤ 10000。
对于 100% 的数据2 ≤ K ≤ |S | ≤ 5 × 105。S 只包含小写字母。c1 和 c2 都是小写字母。 |S | 代表字符串 S 的长度。
解题思路
题意很好理解其实就算找长度大于等于k且以 c1 开头 c2 结尾的连续子串的个数
这里用的是dp大家可以看我的代码里面的注释
具体代码 #include bits/stdc.h
using namespace std;
typedef long long ll;
const int N 5e5 24;
string s;
ll num[N];
int main()
{int k , i , j ;ll ans 0 ;char c1 , c2 ;cin k ;cin s c1 c2;
// 1、num[i]表示到第i个字符c1字符的个数 从第一个字符开始 for(i 1 ; i s.size() ; i ){
// 动态规划 num[i] num[i-1] (s[i-1] c1);}
// 2、从第k歌字符开始如果 第i个字符s[i-1]等于c2则以s[i]结尾字符为c2的个数有 num[i-k]个这个自己可以推算一下 for(i k ; i s.size() ; i ){if(s[i-1] c2){ans num[i-k1]; //我num的下标是从1开始的所以这里要加1 }} cout ans ; return 0;
}
8. 整数删除待写
题目描述
【问题描述】 给定一个长度为 N 的整数数列A1, A2, . . . , AN。你要重复以下操作 K 次 每次选择数列中最小的整数如果最小值不止一个选择最靠前的将其删除。并把与它相邻的整数加上被删除的数值。输出 K 次操作后的序列。
【输入格式】 第一行包含两个整数 N 和 K。 第二行包含 N 个整数A1, A2, A3, . . . , AN。
【输出格式】 输出 N − K 个整数中间用一个空格隔开代表 K 次操作后的序列。
【样例输入】
5 3 1 4 2 8 7 1 2 【样例输出】
17 7 1 【样例说明】 数列变化如下中括号里的数是当次操作中被选择的数
[1] 4 2 8 7 5 [2] 8 7 [7] 10 7 17 7 1 2 3 4 【评测用例规模与约定】 对于 20% 的数据1 ≤ K N ≤ 10000。 对于 100% 的数据1 ≤ K N ≤ 5 × 1050 ≤ Ai≤ 108。
解题思路
用优先级队列动态地获取最小的数时间复杂度为O(N*logN) 1、用懒标记标记删除的点在队列中获取数据时判断是否被标记删除是则丢弃否则就是要取的点 2、删除当前节点后左右节点加上当前节点的值并且左节点的右节点更新为当前节点的右节点、右节点的左节点更新为当前节点的左节点 模拟这个过程即可
具体代码 这个还没做完后面几道有点难我要想一下今天就不写了如果有问题麻烦大家指出一下谢谢。
