建一个网站的手机电脑,中国建设银行开户行查询,个人网站有什么缺点,广安建设局网站A:::::::::::::::::::::::::::::::::::m计划#xff08;双指针#xff0c;滑动窗口#xff0c;倍增#xff09; 题目描述
小明是个鹅卵石收藏者#xff0c;从小到大他一共收藏了 nn 块鹅卵石#xff0c;编号分别为 1∼n#xff0c;价值分别为 a1#xff0c;a2双指针滑动窗口倍增 题目描述
小明是个鹅卵石收藏者从小到大他一共收藏了 nn 块鹅卵石编号分别为 1∼n价值分别为 a1a2⋯,an。
这天他乘船准备去往蓝桥王国然而天有不测风云小明所在的海域下起了暴雨。
很快小明船上的积水越来越多为了防止沉船小明不得不选择若干块他收藏的鹅卵石丢弃。
小明制定了一套名为m计划的选择方案其内容如下
对于任意区间 [i,i m - 1]丢弃价值最小的鹅卵石i∈[1,n−m1]。对于一块鹅卵石它在 m 计划中是可以被丢弃多次的。
请你输出将被小明丢弃的鹅卵石的价值。
输入描述
输入第 1 行包含两个正整数 n,m。
接下来一行包含 n 个正整 a1,a2,⋯,an表示鹅卵石的价值。
1≤m≤n≤5×10的5次方0≤ai≤10的9次方。
输出描述
输出共 n−m1 行每行输出一个整数第 i 行输出整数的含义为 ai,ai1,⋯,aim−1 的最小值。
输入输出样例
示例 1 输入 5 3
5 3 2 4 1输出 2
2
1 #include iostream
using namespace std;
int n,m;
int a[500005];
struct node{int xiabiao;int min1;
};
node check1(int x,int y){node ans1;ans1.xiabiao0;ans1.min11000000;for(int ix;iy;i){if(a[i]ans1.min1){ans1.min1a[i];ans1.xiabiaoi;}}return ans1;
}bool check2(int l,int r,int x){return xlxr;
}int main(){cinnm;for(int i1;in;i){cina[i];}node mmcheck1(1,m);int l2,rm1;coutmm.min1endl;while(rn){if(check2(l,r,mm.xiabiao)){if(mm.min1a[r]){mm.min1a[r];mm.xiabiaor;}}else{mmcheck1(l,r);}coutmm.min1endl;r;l;}return 0;
}B:::::::::::::::::::::::::::::::::::长草BFS
题目描述
小明有一块空地他将这块空地划分为 n 行 m 列的小块每行和每列的长度都为 1。
小明选了其中的一些小块空地种上了草其他小块仍然保持是空地。
这些草长得很快每个月草都会向外长出一些如果一个小块种了草则它将向自己的上、下、左、右四小块空地扩展
这四小块空地都将变为有草的小块。请告诉小明k 个月后空地上哪些地方有草。
输入描述
输入的第一行包含两个整数 n,m。
接下来 n 行每行包含 m 个字母表示初始的空地状态字母之间没有空格。如果为小数点表示为空地如果字母为 g表示种了草。
接下来包含一个整数 k。 其中2≤n,m≤10001≤k≤1000。
输出描述
输出 n 行每行包含 mm 个字母表示 k 个月后空地的状态。如果为小数点表示为空地如果字母为 g表示长了草。
输入输出样例
示例 输入 4 5
.g...
.....
..g..
.....
2输出 gggg.
gggg.
ggggg
.ggg.运行限制
最大运行时间1s最大运行内存: 256M
#include iostream
#include queue
using namespace std;
int n,m,k;
char a[1005][1005];
struct node{int x,y;int su;node(int xx,int yy,int suu){xxx;yyy;susuu;}
};
queuenode h;
bool check(int x,int y){return x1xny1ym;
}
int f[4][2]{{1,0},{-1,0},{0,-1},{0,1}};
int main(){cinnm;for(int i1;in;i){for(int j1;jm;j){cina[i][j];if(a[i][j]g){h.push(node(i,j,0));}} }cink;while(!h.empty()){node jh.front();h.pop();for(int i0;i4;i){int txj.xf[i][0];int tyj.yf[i][1];if(check(tx,ty) a[tx][ty]. j.su1k){a[tx][ty]g;h.push(node(tx,ty,j.su1));}}}for(int i1;in;i){for(int j1;jm;j){couta[i][j];}coutendl;}return 0;
}C:::::::::::::::::::::::::::::::::::带分数全排列
题目描述
100 可以表示为带分数的形式100 3 69258 / 714
还可以表示为100 82 3546 / 197
注意特征带分数中数字 1~9 分别出现且只出现一次不包含 0 。
类似这样的带分数100 有 11 种表示法。
输入描述
从标准输入读入一个正整数 (N1000×1000)。
输出描述
程序输出该数字用数码 1~9 不重复不遗漏地组成带分数表示的全部种数。
注意不要求输出每个表示只统计有多少表示法
输入输出样例
示例 输入 100输出 11运行限制
最大运行时间3s最大运行内存: 64M
#include iostream
#include algorithm
using namespace std;
int n;
long long ans;
int a[9]{1,2,3,4,5,6,7,8,9};
int he(int l,int r){int ans10;for(int il;ir;i){ans1ans1*10a[i];}return ans1;
}
int main(){cinn;while(next_permutation(a,a9)){for(int i0;i7;i){for(int ji1;j8;j){int ahe(0,i);int bhe(i1,j);int che(j1,8);if(a*cbn*c){ans;}}}}coutans; return 0;
} D:::::::::::::::::::::::::::::::::::合根植物并查集
题目描述
w 星球的一个种植园被分成 m×n 个小格子东西方向 m 行南北方向 n 列。每个格子里种了一株合根植物。
这种植物有个特点它的根可能会沿着南北或东西方向伸展从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象你能说出这个园中一共有多少株合根植物吗
输入描述
第一行两个整数 m,n用空格分开表示格子的行数、列数1≤m,n≤1000。
接下来一行一个整数 k (0≤k≤105 )表示下面还有 k 行数据。
接下来 k 行每行两个整数 ab表示编号为 a 的小格子和编号为 b 的小格子合根了。
格子的编号一行一行从上到下从左到右编号。
比如5×4 的小格子编号
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20输出描述
输出植物数量。
输入输出样例
示例 输入 5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17输出 5样例说明 其合根情况参考下图 运行限制
最大运行时间2s最大运行内存: 256M
#include iostream
#include algorithm
using namespace std;
int m,n,k;
int vis[1000005];
int fa[1000005];
int find(int x){if(fa[x]x) return x;return fa[x]find(fa[x]);
}
int ans;
void jiaru(int x,int y){int txfind(x);int tyfind(y);if(tx!ty){fa[tx]ty;}
}
int main(){cinmnk;for(int i0;in*m;i){fa[i]i;}for(int i0;ik;i){int a,b;cinab;jiaru(a,b);}for(int i1;in*m;i){vis[find(i)]1;}for(int i1;in*m;i){if(vis[i]){ans1;}}coutans; return 0;
} E:::::::::::::::::::::::::::::::::::修建公路(最小生成树并查集)
题目描述
LL 城一共有 N 个小区。
小明是城市建设的规划者他计划在城市修 M 条路每修建一条路都要支付工人们相应的工钱需要支付的工钱 路的长度。
然而小明所拿到的经费并不够支付修建 M 条路的工钱于是迫于无奈他只能将计划改变为修建若干条路使得 N 个小区之间两两联通。
小明希望尽量剩下更多的经费投入到别的项目中因此请你通过程序帮他计算出完成计划所需的最低开销。
输入描述
输入第一行包含三个正整数N,M。
第 2 到 M1 行每行包含三个正整数 u,v,w表示 u↔v 之间存在一条距离为 w 的路。 输出描述
输出占一行包含一个整数表示完成计划所需的最低开销。
若无法完成计划则输出 -1−1。
输入输出样例
示例 1 输入 5 6
1 2 2
1 3 7
1 4 6
2 3 1
3 4 3
3 5 2输出 8运行限制
最大运行时间3s最大运行内存: 256M、
#include iostream
#include algorithm
using namespace std;
int n,m;
int fa[100005];
int find(int x){if(fa[x]x) return x;return fa[x]find(fa[x]);
}
struct node{int qi,zhong;int juli;
};
bool cmp(node x,node y){return x.juliy.juli;
}long long ans;
node g[300005];
int main(){cinnm; //n个城市m个规划for(int i1;in;i){fa[i]i;}for(int i1;im;i){cing[i].qig[i].zhongg[i].juli;}sort(g1,gm1,cmp);for(int i1;im;i){int txfind(g[i].qi);int tyfind(g[i].zhong);if(tx!ty){ansg[i].juli;fa[tx]ty;}}int wfind(1);for(int i1;in;i){if(w!find(i)){cout-1;return 0;}}coutans;return 0;
}F:::::::::::::::::::::::::::::::::::小明的背包2完全背包
题目描述
小明有一个容量为 V 的背包。
这天他去商场购物商场一共有 N 种物品第 ii 种物品的体积为 wi价值为 vi每种物品都有无限多个。
小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少请你帮他算算。
输入描述
输入第 1 行包含两个正整数 N,V表示商场物品的数量和小明的背包容量。
第 2∼N1 行包含 2 个正整数w,v表示物品的体积和价值。 输出描述
输出一行整数表示小明所能获得的最大价值。
输入输出样例
示例 1 输入 5 20
1 6
2 5
3 8
5 15
3 3 输出 120 #include iostream
#include cmath
using namespace std;
int n,v;
int wi[1005];
int vi[1005];
int dp[1005][1005];
int main(){cinnv;for(int i1;in;i){cinwi[i]vi[i]; //体积和价值 }for(int i1;in;i){for(int j1;jv;j){dp[i][j]dp[i-1][j];if(jwi[i]){dp[i][j]max(dp[i-1][j],dp[i][j-wi[i]]vi[i]);}}}coutdp[n][v];return 0;
}G:::::::::::::::::::::::::::::::::::作物杂交搜索
题目描述
作物杂交是作物栽培中重要的一步。已知有 N 种作物 (编号 1 至 N)第 i 种作物从播种到成熟的时间为 Ti。作物之间两两可以进行杂交杂交时间取两种中时间较长的一方。如作物 A 种植时间为 5 天作物 B 种植时间为 7 天则 AB 杂交花费的时间为 7 天。作物杂交会产生固定的作物新产生的作物仍然属于 N 种作物中的一种。
初始时拥有其中 M 种作物的种子 (数量无限可以支持多次杂交)。同时可以进行多个杂交过程。求问对于给定的目标种子最少需要多少天能够得到。
如存在 4 种作物 ABCD各自的成熟时间为 5 天、7 天、3 天、8 天。初始拥有 AB 两种作物的种子目标种子为 D已知杂交情况为 A × B → CA × C → D。则最短的杂交过程为
第 1 天到第 7 天 (作物 B 的时间)A × B → C。
第 8 天到第 12 天 (作物 A 的时间)A × C → D。
花费 12 天得到作物 D 的种子。
输入描述
输入的第 1 行包含 4 个整数 N,M,K,TNN 表示作物种类总数 (编号 1 至 N)MM 表示初始拥有的作物种子类型数量KK 表示可以杂交的方案数TT 表示目标种子的编号。
第 2 行包含 N 个整数其中第 ii 个整数表示第 ii 种作物的种植时间 Ti (1≤Ti≤100)。
第 3 行包含 M 个整数分别表示已拥有的种子类型 (1≤Kj≤M)Kj 两两不同。
第 4 至 K 3 行每行包含 3 个整数 A,B,C表示第 A 类作物和第 B 类作物杂交可以获得第 C 类作物的种子。
其中1≤N≤2000,2≤M≤N,1≤K≤105,1≤T≤N, 保证目标种子一定可以通过杂交得到。
输出描述
输出一个整数表示得到目标种子的最短杂交时间。
输入输出样例
示例 输入 6 2 4 6
5 3 4 6 4 9
1 2
1 2 3
1 3 4
2 3 5
4 5 6输出 16样例说明 第 1 天至第 5 天将编号 1 与编号 2 的作物杂交得到编号 3 的作物种子。
第 6 天至第 10 天将编号 1 与编号 3 的作物杂交得到编号 4 的作物种子。
第 6 天至第 9 天将编号 2 与编号 3 的作物杂交得到编号 5 的作物种子。
第 11 天至第 16 天将编号 4 与编号 5 的作物杂交得到编号 6 的作物种子。
总共花费 16 天。
运行限制
语言最大运行时间最大运行内存C2s256MC2s256MJava3s256MPython310s256M
#include iostream
#include vector
using namespace std;
const int maxn0x3f3f3f3f;
int tim[2010];
int dp[2010];
vectorpairint, int zajiao[2010];
int f(int n){if (dp[n]!maxn) return dp[n];for (int i0;izajiao[n].size();i){int azajiao[n][i].first,bzajiao[n][i].second;int tmp max(f(a), f(b))max(tim[a],tim[b]);dp[n]min(dp[n],tmp);} return dp[n];
}
int main(){for (int i0;i2010;i){dp[i]maxn;}int n,m,k,t;cinnmkt;for (int i1;in;i){cintim[i];}for (int i1;im;i){int j;cinj;dp[j]0;}for (int i1;ik;i){int a,b,c;cinabc;zajiao[c].push_back(make_pair(a, b));}f(t);coutdp[t]endl;return 0;
} H:::::::::::::::::::::::::::::::::::序列求和(DFS唯一分解定理) 题目描述
本题为填空题只需要算出结果后在代码中使用输出语句将所填结果输出即可。
学习了约数后小明对于约数很好奇他发现给定一个正整数 tt总是可以找到含有 tt 个约数的整数。小明对于含有 tt 个约数的最小数非常感兴趣并把它定义为 S_tSt 。
例如S11,S22,S34,S46⋅⋅⋅ 。
现在小明想知道前 60 个 Si 的和是多少即 S1S2⋅⋅⋅S60 是多少
运行限制
最大运行时间1s最大运行内存: 128M
#include iostream
#include vector
#include algorithm
using namespace std;
vectorlong long m;
int su[100000];
bool check(long long x){if(x1){return false;}if(x2){return true;}for(int i2;i*ix;i){if(x%i0){return false;}}return true;
}
long long pow1(long long a,long long b){long long ans1;while(b){if(b1) ansans*a;b/2;a*a;}return ans;
}
long long ans;
long long res11e18;
long long dfs(long long x,vectorlong longg)
{if(check(x)||x1)return pow1(2,x-1); for(long long i2;i*ix;i){if(x%i0){long long tx/i;g.push_back(i);vectorlong longtmpg;tmp.push_back(t); sort(tmp.begin(),tmp.end(),greaterlong long());long long s1;for(int j0;jtmp.size();j)s*pow1(su[j],tmp[j]-1); res1min(res1,s);dfs(t,g);g.pop_back();}}return res1;
}
int main(){int cc0;for(int i2;i100000;i){if(check(i)){su[cc]i;cc;}}ans1246;for(int i5;i60;i){res11e18;m.clear();long long ans1dfs(i,m);ansans1;}coutans;return 0;
} I:::::::::::::::::::::::::::::::::::青蛙跳杯子BFS
题目描述
XX 星球的流行宠物是青蛙一般有两种颜色白色和黑色。
XX 星球的居民喜欢把它们放在一排茶杯里这样可以观察它们跳来跳去。
如下图有一排杯子左边的一个是空着的右边的杯子每个里边有一只青蛙。
∗WWWBBB
其中W 字母表示白色青蛙B 表示黑色青蛙*∗ 表示空杯子。
X 星的青蛙很有些癖好它们只做 3 个动作之一 跳到相邻的空杯子里。 隔着 1 只其它的青蛙随便什么颜色跳到空杯子里。 隔着 2 只其它的青蛙随便什么颜色跳到空杯子里。
对于上图的局面只要 1 步就可跳成下图局面
WWW∗BBB
本题的任务就是已知初始局面询问至少需要几步才能跳成另一个目标局面。
输入描述
输入为 2 行2 个串表示初始局面和目标局面。我们约定输入的串的长度不超过 15。
输出描述
输出要求为一个整数表示至少需要多少步的青蛙跳。
输入输出样例
示例 输入 *WWBB
WWBB*输出 2运行限制
最大运行时间1s最大运行内存: 256M
#include iostream
#include queue
#include string
#include map
using namespace std;
string a,b;
struct node{string a;int bu;int x;node(string aa,int buu,int xu){aaa;bubuu;xxu;}
};
string jiaohuan(string a,int x,int y){char ma[x];a[x]a[y];a[y]m;return a;
}
mapstring,bool kk;
queuenode q;
bool check(int x){return x0 xa.size();
}
int f[6]{1,-1,2,-2,3,-3};
int main(){cinab;int c0;for(int i0;ia.size();i){if(a[i]*){ci;}}kk[a]1;q.push(node(a,0,c)); while(!q.empty()){node tq.front();q.pop();if(t.ab){coutt.bu;break;}for(int i0;i6;i){int txt.xf[i];string xxjiaohuan(t.a,t.x,tx);if(check(tx) !kk[xx]){kk[xx]1;q.push(node(xx,t.bu1,tx));}}}return 0;
}J:::::::::::::::::::::::::::::::::::剪格子DFS
题目描述
如下图所示3 x 3 的格子中填写了一些整数。 我们沿着图中的红色线剪开得到两个部分每个部分的数字和都是 60。
本题的要求就是请你编程判定对给定的 m×n 的格子中的整数是否可以分割为两个部分使得这两个区域的数字和相等。
如果存在多种解答请输出包含左上角格子的那个区域包含的格子的最小数目。
如果无法分割则输出 0。
输入描述
输入描述
程序先读入两个整数 m,n 用空格分割 (m,n10)表示表格的宽度和高度。
接下来是 n 行每行 m 个正整数用空格分开。每个整数不大于 104。
输出描述
在所有解中包含左上角的分割区可能包含的最小的格子数目。
输入输出样例
示例 输入 3 3
10 1 52
20 30 1
1 2 3输出 3运行限制
最大运行时间5s最大运行内存: 64M
#include iostream
using namespace std;
int a[15][15];
int n,m;
int sum;
int he;
int ans1e9;
bool vis[15][15];
int aa[4][2]{{1,0},{-1,0},{0,-1},{0,1}};
bool check(int x,int y){return x0xny0ym;
}
void dfs(int x,int y,int g){if(gans){return;}if(hesum/2){ansmin(ans,g);}for(int i0;i4;i){int txxaa[i][0];int tyyaa[i][1];if(check(tx,ty) !vis[tx][ty]){vis[tx][ty]1;hea[tx][ty];dfs(tx,ty,g1);he-a[tx][ty];vis[tx][ty]0;}}
}
int main(){cinmn;for(int i1;in;i){for(int j1;jm;j){int x0;cinx;a[i][j]x;sumx;}}if(sum%21){cout0;return 0;}vis[1][1]1;hea[1][1];dfs(1,1,1);coutans;return 0;
}
