网站怎么做数据转移,小程序技术开发公司,万网网站模板购买,wordpress空间安装教程1. 日期统计
小蓝现在有一个长度为 100100 的数组#xff0c;数组中的每个元素的值都在 00 到 99 的范围之内。数组中的元素从左至右如下所示#xff1a;
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…1. 日期统计
小蓝现在有一个长度为 100100 的数组数组中的每个元素的值都在 00 到 99 的范围之内。数组中的元素从左至右如下所示
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现在他想要从这个数组中寻找一些满足以下条件的子序列
子序列的长度为 88这个子序列可以按照下标顺序组成一个 yyyymmddyyyymmdd 格式的日期并且要求这个日期是 20232023 年中的某一天的日期例如 20230902202309022023122320231223。yyyyyyyy 表示年份mmmm 表示月份dddd 表示天数当月份或者天数的长度只有一位时需要一个前导零补充。
请你帮小蓝计算下按上述条件一共能找到多少个不同的 20232023 年的日期。对于相同的日期你只需要统计一次即可。
#include iostream
using namespace std;
bool st[100000000];
int math[13]{0,31,28,31,30,31,30,31,31,30,31,30,31};
int main()
{// 请在此输入您的代码int a[101]{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 len8;int cnt0;for(int i0;i100;i){if(a[i]2)for(int i2i1;i2100;i2){if(a[i2]0)for(int i3i21;i3100;i3){if(a[i3]2)for(int i4i31;i4100;i4){if(a[i4]3){len4;//年数完了for(int m1i41;m1100;m1){if(a[m1]1||a[m1]0)//10位只能是1或0{for(int m2m11;m2100;m2){if(a[m1]1a[m2]2||a[m1]0)//当m1是1 m2要小于等于1反之都可以{for(int d1m21;d1100;d1){int mymona[m1]*10a[m2];//月if(math[mymon]/10a[d1])for(int d2d11;d2100;d2){int daya[d1]*10a[d2];//日// coutmymon dayendl;if(daymath[mymon]day!0){int tmpa[i]*1e7a[i2]*1e6a[i3]*1e5a[i4]*1e4a[m1]*1e3a[m2]*100a[d1]*10a[d2];if(!st[tmp])//没走过cnt;// couttmpendl;st[tmp]true;// coutcnt cnt:endl;}}}}}}}}}}}}printf(%d,cnt);return 0;
}
2. 冶炼金属
小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 VV 是一个正整数这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X当普通金属 O 的数目不足 V 时无法继续冶炼。
现在给出了 N 条冶炼记录每条记录中包含两个整数 A 和 B这表示本次投入了 A 个普通金属 O最终冶炼出了 B 个特殊金属 X。每条记录都是独立的这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。
根据这 N 条冶炼记录请你推测出转换率 V 的最小值和最大值分别可能是多少题目保证评测数据不存在无解的情况。
解题思路
check函数来计算能完成构造b个的最大转换率然后求构造b1个特殊金属的最大转换1即b的最小转换率
AC代码
#include iostream
#includecstdio
#includealgorithm
using namespace std;int n;//求最大
int check(int l, int r, int sum, int x)//求最大 r sum是总共的金属 x是特殊的金属
{int mid 0;// r1e9;while (l r){mid ((l r ) 1)1;if (sum / mid x)//mid可以完成任务或者超额完成l mid;elser mid - 1;}return l;
}
int main()
{// 请在此输入您的代码scanf(%d, n);int maxin 0x3f3f3f3f;//最大值的最小值int minax 0;//最小值的最大值// coutcheck(0,9248,9248,1)endl;// couttest: check(0,75,75,3)endl;for (int i 0; i n; i){int a, b;//a个普通金属冶炼出b个特殊金属cin a b;//求最小值的最大值minax max(minax, check(0, a, a, b 1) 1);//求造b1个特殊金属的最大转换率1就是最小转换率//求最小值的最大值maxin min(maxin, check(0, a, a, b));// coutmaxin endl;}cout minax maxin endl;return 0;
}
3. 飞机降落
N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空到达时它的剩余油料还可以继续盘旋 Di 个单位时间即它最早可以于 Ti 时刻开始降落最晚可以于 TiDi时刻开始降落。降落过程需要 Li个单位时间。
一架飞机降落完毕时另一架飞机可以立即在同一时刻开始降落但是不能在前一架飞机完成降落前开始降落。
请你判断 N 架飞机是否可以全部安全降落。
解题思路
一个结构体存储到达时间可以盘旋时间降落需要时间。dfs判断是否可以全部降落。状态数组st记得重置
AC代码
#include iostream
#includealgorithm
#includecstring
using namespace std;int n;
// pairint,int td[11];
struct til
{int t;//到达时间int d;//可以盘旋的时间int l;//降落所需时间bool operator (struct til tmp){if(ttmp.t)return true;else if(ttmp.t){if(dtmp.d)return true;else if(dtmp.d)return ltmp.l;}return false;}
}til[15];bool st[15];//检测第i架飞机是否降落bool dfs(int cnt,int tim)//cur第几架飞机
{if(cntn)return true;for(int i0;in;i)//枚举所有飞机{if(!st[i])//飞机没走{if(timtil[i].ttil[i].d)//这架飞机还没走并且超时了return false;int tmptim;//当前时间if(tmptil[i].t)//下一个飞机降落的时间大于当前时间tmptil[i].t;st[i]true;if(dfs(cnt1,tmptil[i].l))//当前时间加降落所需时间与下个飞机来到时间下落的时间return true;st[i]false;//返回}}return false;
}// int l[11];
int main()
{// 请在此输入您的代码int t;scanf(%d,t);while(t--){memset(st,false,sizeof st);scanf(%d,n);for(int i0;in;i){scanf(%d%d%d,til[i].t,til[i].d,til[i].l);}sort(til,tiln);if(dfs(0,0))coutYESendl;elsecoutNOendl;}return 0;
}
4. 接龙数列
对于一个长度为 KK 的整数数列A1,A2,…,AK我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1Ai−1 的末位数字 (2≤i≤K)(2≤i≤K)。例如 12,23,35,56,61,11 是接龙数列12,23,34,56不是接龙数列因为 56 的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。
现在给定一个长度为 N 的数列 A1,A2,…,AN请你计算最少从中删除多少个数可以使剩下的序列是接龙序列
解题思路
线性DP最长公共子序列一样的模型。以第i个数字为结尾的接龙子序列的集合 暴力过一半测试用例
#includeiostream
#includecstdio
#includealgorithm
#includecmath
#includestring
using namespace std;
int f[10010];int a[10010];
int b[10010];int main()
{ int n;scanf(%d,n);for(int i0;in;i){string s;cins;a[i]s[0]-0;b[i]s[s.size()-1]-0;}for(int i0;in;i){f[i]1;for(int j0;ji;j){if(a[i]b[j]){f[i]max(f[i],f[j]1);}}}int res0;for(int i0;in;i){// coutf[i] ;if(f[i]res)resf[i];}coutn-res;return 0;
}
5. 岛屿个数
小蓝得到了一副大小为 M×N 的格子地图可以将其视作一个只包含字符 0代表海水和 1代表陆地的二维数组地图之外可以视作全部是海水每个岛屿由在上/下/左/右四个方向上相邻的 1 相连接而形成。
在岛屿 AA 所占据的格子中如果可以从中选出 k 个不同的格子使得他们的坐标能够组成一个这样的排列(x0,y0),(x1,y1),…,(xk−1,yk−1)其中 (xi1modk,yi1modk) 是由(xi,yi) 通过上/下/左/右移动一次得来的 (0≤i≤k−1)(0≤i≤k−1)此时这 k 个格子就构成了一个“环”。如果另一个岛屿 B 所占据的格子全部位于这个“环”内部此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若B 是 A 的子岛屿C 又是 B 的子岛屿那 C 也是 A 的子岛屿。
请问这个地图上共有多少个岛屿在进行统计时不需要统计子岛屿的数目。
解题思路
正难则反我们仔细想一下怎么才能知道一个岛是子岛屿呢就是这个岛所临的海只要有外海就说明这个岛能联通外界不是子岛屿而只联通内海呢就说明它被一个岛屿所包含了。至于判断是外海还是内海只要遍历边界的海(因为地图外的海一定是外海与边界的海相连的海就是外海不联通的就是内海)。遍历所有的没走过的陆地临着外海就是一个独立的岛屿
AC代码
#include iostream
#includequeue
#includecstdio
#includealgorithm
#includecstring
using namespace std;char map[55][55];
int n, m;int dxx[8] { 0,0,1,-1,1,1,-1,-1 };//看海是否是内陆海
int dyy[8] { 1,-1,0,0,1,-1,1,-1 };int dx[4] { 0,0,1,-1 };
int dy[4] { 1,-1,0,0 };
bool sth[55][55];//标记海洋是否流到
bool stl[55][55];//标记所有陆地
void bfs1(int x, int y)
{queuepairint, int q;q.push({ x,y });sth[x][y] true;//while (!q.empty()){int x1 q.front().first;int y1 q.front().second;q.pop();for (int i 0; i 8; i){int x2 dxx[i] x1;int y2 dyy[i] y1;if (x2 n || x2 0 || y2 0 || y2 m)//越界continue;if (sth[x2][y2] || map[x2][y2] ! 0)//走过了或不是海洋continue;sth[x2][y2] true;q.push({ x2,y2 });}}
}bool bfs(int x, int y)
{queuepairint, int q;q.push({ x,y });stl[x][y] true;//int f false;//标记是否通往外海while (!q.empty()){int x1 q.front().first;int y1 q.front().second;q.pop();for (int i 0; i 4; i){int x2 dx[i] x1;int y2 dy[i] y1;if (x2 n || x2 0 || y2 0 || y2 m)//越界continue;//四周的海只要有外海if (map[x2][y2] 0 sth[x2][y2])//是海并且这个海通往外海f true;if (stl[x2][y2] || map[x2][y2] ! 1)//走过了或不是陆地continue;stl[x2][y2] true;q.push({ x2,y2 });}}return f;//说明是否通往外海不连接外海的一定是环内的
}int main()
{// 请在此输入您的代码int t;scanf(%d, t);while (t--){scanf(%d %d, n, m);memset(sth, false, sizeof sth);memset(stl, false, sizeof stl);//memset(map, 0, sizeof map);//cout n m endl;for (int i 0; i n; i){cin map[i];}bool f true;for (int i 0; i n; i){if (!sth[i][0] map[i][0] 0)//没走过并且是海洋{bfs1(i, 0);f false;//表示地图周围有海}if (!sth[i][m - 1] map[i][m - 1] 0)bfs1(i, m - 1), f false;}for (int j 0; j m; j){if (!sth[0][j] map[0][j] 0)bfs1(0, j), f false;if (!sth[n - 1][j] map[n - 1][j] 0)bfs1(n - 1, j), f false;}//max(0,n-1)if (f)//四周全是陆地就输出1即可cout 1 endl;else{int cnt 0;for (int i 0; i n; i){for (int j 0; j m; j){if (!stl[i][j] map[i][j] 1)//没走过并且是陆地if (bfs(i, j))cnt;}}cout cnt endl;}//将所有最外层的海进行bfs八个方向能流到的地方肯定就不是内海}return 0;
}
6. 子串简写
程序猿圈子里正在流行一种很新的简写方法对于一个字符串只保留首尾字符将首尾字符之间的所有字符用这部分的长度代替。例如 internation-alization 简写成 i18nKubernetes 注意连字符不是字符串的一部分简写成 K8s, Lanqiao 简写成 L5o 等。
在本题中我们规定长度大于等于 KK 的字符串都可以采用这种简写方法长度小于 K 的字符串不配使用这种简写。
给定一个字符串 S 和两个字符 c1 和 c2 请你计算 S 有多少个以 c1 开头 c2 结尾的子串可以采用这种简写
解题思路
这题可以运用双指针来遍历区间但是这样还不够还可以用前缀和的思想来优化我们来从后往前维护一段长度为k的区间来预处理b的数量遇到b就统计下来b的数量遇到a就统一结算之前b的数量。
AC代码
注释掉的为暴力代码
#include iostream
#includestring
#includecstdio
using namespace std;// pairchar,char fe[500010];
int k;
string s;
char c1,c2;
int main()
{// 请在此输入您的代码scanf(%d,k);cinsc1c2;long long cnt0;long long res0;//前缀和思想for(int rs.size()-1,ls.size()-k;l0;r--,l--){if(s[r]c2) cnt;//统计可以当结尾的数量if(s[l]c1) rescnt;//遇到一个可以当头的加上所有可以当结尾的字符数量}// for(int l0;lk-1s.size();l)// {// if(s[l]c1)//以c1开头// {// int rlk-1;// while(rs.size())// {// if(s[r]c2)// cnt;// r;// }// }// }coutresendl;return 0;
}
7. 景区导游
某景区一共有 N 个景点编号 1 到 N。景点之间共有 N−1 条双向的摆渡车线路相连形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行需要花费一定的时间。
小明是这个景区的资深导游他每天都要按固定顺序带客人游览其中 K 个景点A1,A2,…,AK。今天由于时间原因小明决定跳过其中一个景点只带游客按顺序游览其中 K−1 个景点。具体来说如果小明选择跳过 Ai那么他会按顺序带游客游览 A1,A2,…,Ai−1,Ai1,…,AK(1≤i≤K)。
请你对任意一个 Ai计算如果跳过这个景点小明需要花费多少时间在景点之间的摆渡车上
暴力思路
构建邻接表通过dfs计算出所需游览所有景点的总长度。
再依次枚举要游览的景点将其删除此时有三种情况 1. 删除的景点是a[0],即第一次去的景点此时第一次就不去a[0]了直接去a[1]所以直接减去a[0]到a[1]的距离即可 2. 删除的景点是a[k-1],即最后一次要去的景点此时a[k-2]就是终点减去a[k-2]到a[k-1]的距离即可 3. 减去的景点不是第一个与最后一个那就减去当前景点去上一个景点的距离与去下一个景点的距离 暴力过一半数据
#include iostream
#includecstdio
#includecstring
#includemap
#includevector
using namespace std;vectorpairint,int edge[100010];
mappairint,int ,long long len;//记录a到b需要走多少
int n,k;
int a[100010];//其实位置当前位置上个位置终点走的距离
bool dfs(int st,int u,int father,int end,int sum)
{if(uend){len[{st,end}]sum;len[{end,st}]sum;//两个都记录一下return true;}for(auto c:edge[u]){if(c.first!father)//下一个位置不是自己的父亲节点{if(dfs(st,c.first,u,end,sumc.second)){return true;}}}return false;
}
int main()
{// 请在此输入您的代码scanf(%d%d,n,k);for(int i0;in-1;i){int u,v,t;scanf(%d%d%d,u,v,t);edge[u].push_back({v,t});edge[v].push_back({u,t}); }for(int i0;ik;i){scanf(%d,a[i]);}long long res0;//记录路径总长度for(int i0;ik-1;i){dfs(a[i],a[i],-1,a[i1],0);//计算a[i]到a[i1]所需的长度reslen[{a[i],a[i1]}];//}for(int i0;ik;i){long long tmpres;if(i0)//如果是跳过第一个景点{tmp-len[{a[i],a[i1]}];//就是直接从第二个景点开始}else if(ik-1)//跳过最后一个景点{tmp-len[{a[i-1],a[i]}];//删除倒数第二个景点去第二个景点的距离}else//计算删除景点的上一个景点去下一个景点的距离{tmptmp-len[{a[i],a[i1]}]-len[{a[i-1],a[i]}];//dfs(a[i-1],a[i-1],-1,a[i1],0);tmplen[{a[i-1],a[i1]}];}couttmp ;}return 0;
} 8.砍树
给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1,b1),(a2,b2),...,(am,bm)其中 ai 互不相同bi 互不相同ai≠bj(1≤i,j≤m)。
小明想知道是否能够选择一条树上的边砍断使得对于每个(ai,bi) 满足 ai 和 bi 不连通如果可以则输出应该断掉的边的编号编号按输入顺序从 1开始否则输出 −1。 暴力思路
记录下来所有的边与所有不能联通的边双重枚举使其不能联通即可
暴力过30%数据代码
#includeiostream
#includealgorithm
#includecstdio
#includevector
using namespace std;int n,m;
vectorint edge[100010];
pairint,int p[100010];//记录所有的边
pairint,int no[100010];//记录所有不能联通的边
//st起始位置end结束位置,u当前位置
bool dfs(int st,int end,int u,int father,int a,int b)//a和b表示被砍断的边
{// cout当前在uendl;if(uend){return true;}for(auto c:edge[u]){if(c!father)//a b不连通{if((uacb)||(ubca))//a与b不能互相联通continue;// cout可以往c走endl;if(dfs(st,end,c,u,a,b))return true;}}return false;}int main()
{scanf(%d%d,n,m);for(int i1;in-1;i){int a,b;scanf(%d%d,a,b);edge[a].push_back(b);edge[b].push_back(a);p[i]{a,b};}for(int i0;im;i){int a,b;scanf(%d%d,a,b);no[i]{a,b};}bool ftrue;// cout dfs(3,6,3,-1,6,5);for(int in-1;i1;i--){ftrue;for(int j0;jm;j){// coutjj dfs(no[j].first,no[j].second,no[j].first,-1,p[i].first,p[i].second)endl;if(dfs(no[j].first,no[j].second,no[j].first,-1,p[i].first,p[i].second)){ffalse;//说明断这条边不可以使其不联通// cout断的边p[i].first p[i].secondendl;// cout可以联通的边no[j].firstno[j].secondendl;break;}}if(f){coutiendl;break;}}if(!f)cout-1endl;return 0;
} 这篇就到这里啦(๑′ᴗ‵๑) Lᵒᵛᵉᵧₒᵤ❤
