大家好，欢迎来到IT知识分享网。
文章目录
1. 最短路
题目描述：
如下图所示，G是一个无向图，其中蓝色边的长度是1、橘色边的长度是2、绿色边的长度是3。
则从 A 到 S 的最短距离是多少？
#include <iostream> #include <cstring> using namespace std; const int N=200,n=19; int dist[N]; int g[N][N]; void add(char x,char y,int c) {
int a=x-'A'+1; int b=y-'A'+1; g[a][b]=g[b][a]=c; } bool vis[N]; int dijkstra() {
memset(dist,0x3f,sizeof dist); dist[1]=0; for(int i=0;i<n;i++) {
int t=-1; for(int j=1;j<=n;j++) {
if(!vis[j]&&(t==-1||dist[j]<dist[t])) t=j; } vis[t]=1; for(int j=1;j<=n;j++) {
dist[j]=min(dist[j],dist[t]+g[t][j]); } } return dist[n]; } int main() {
memset(g,0x3f,sizeof g); add('A','B',2); add('A','C',1); add('A','D',1); add('A','D',1); add('B','J',2); add('B','G',1); add('C','D',3); add('C','F',3); add('C','G',3); add('D','E',1); add('D','G',2); add('D','H',1); add('D','I',2); add('E','H',1); add('E','I',3); add('F','G',1); add('F','J',1); add('G','F',1); add('G','I',3); add('G','K',2); add('H','I',1); add('H','L',2); add('I','M',3); add('J','S',2); add('K','N',1); add('K','L',3); add('K','P',2); add('L','M',1); add('L','R',1); add('M','N',2); add('M','Q',1); add('M','S',1); add('N','P',1); add('O','P',1); add('O','Q',1); add('O','R',3); add('R','S',1); cout<<dijkstra(); return 0; } 2. 数字三角形
题目描述：
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 #include<iostream> using namespace std; int a[200][200]; int dp[200][200]; int main() {
int n; cin>>n; for(int i=1;i<=n;i++) {
for(int j=1;j<=i;j++) cin>>a[i][j]; } dp[1][1]=a[1][1]; for(int i=2;i<=n;i++) {
for(int j=1;j<=i;j++) {
if(j==1)dp[i][j]=dp[i-1][j]+a[i][j]; else if(j==i)dp[i][j]=dp[i-1][j-1]+a[i][j]; else dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]; } } if(n%2==0){
cout<<max(dp[n][n/2],dp[n][n/2+1]); } else{
cout<<dp[n][n/2+1]<<endl; } } 3. 递增序列
题目描述：
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
对于一个字母矩阵，我们称矩阵中的一个递增序列是指在矩阵中找到两个字母，它们在同一行，同一列，或者在同一45度的斜线上，这两个字母从左向右看、或者从上向下看是递增的。
例如，如下矩阵中
LANN QIAO VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWIKUYMYMOVMNCBVY ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX #include <iostream> using namespace std; int main() {
char str[35][55]; long int ans = 0; for(int i=0; i<30; i++) for(int j=0; j<50; j++) {
cin >> str[i][j]; } for(int i=0; i<30; i++) for(int j=0; j<50; j++) {
int k; for(k=1; k+j<50; k++)//列 {
if(str[i][j] < str[i][j+k]) ans++; } for(k=1; k+i<30; k++)//行 {
if(str[i][j] < str[i+k][j]) ans++; } for(k=1; k+i<30 && j+k<50; k++) //从左上到右下 {
if(str[i+k][j+k] > str[i][j]) ans++; } } for(int i=1; i<30; i++) for(int j=0; j<50; j++) {
int k; for(k=1; i-k>=0 && j+k<50; k++)//左下到右上 {
if(str[i][j] != str[i-k][j+k]) ans++; } } cout << ans << endl; return 0; } 4. 杨辉三角形
题目描述：
#include<bits/stdc++.h> using namespace std; typedef long long LL; LL n; /* 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 可以发现找到第一个出现的一定在左边故右边可以直接删去 1 1 2 1 3 1 4 6 1 5 10 1 6 15 20 / / / / 从打斜杠的地方可以发现规律为C(2n,n) 故找到最大的斜行 用t来代表斜行数 最大为1e9； 故求有多少个斜行数满足？ int x;//记录第几个斜行满足 for(int t=0;;t++){ if(1e9<=C(2t,t)){ x=t; break; } } 故解得t=17; 斜线从大到小依次排列第一找到第一个数 再通过二分查找 C(t, k)对应的顺序值为：(t + 1) * t / 2 + k + 1 */ LL C(int x,int k){
LL ans=1; for(int i=x,j=1;j<=k;i--,j++){
ans=ans*i/j; if(ans>n)return ans; } return ans; } bool check(int x){
LL l=2*x,r=max(n,l); while(l<r){
int mid=l+r>>1; if(C(mid,x)>=n)r=mid; else l=mid+1; } if(C(r,x)!=n)return false; cout<<(LL)(r+1)*r/2+x+1<<endl; return true; } int main(){
cin>>n; for(int t=17;;t--){
if(check(t))break; } return 0; } 5. 跳跃
题目描述：
小蓝在一个n行m列的方格图中玩一个游戏。
开始时，小蓝站在方格图的左上角，即第1行第1列。
小蓝可以在方格图上走动，走动时，如果当前在第r行第c列，他不能走到行号比r小的行，也不能走到列号比c 小的列。同时，他一步走的直线距离不超过3。
例如，如果当前小蓝在第3行第5列，他下一步可以走到第3行第6列、第3行第7列、第3行第8列、第4行第5列、第4行第6列、第4行第7列、第5行第5列、第5行第6列、第6行第5列之一。
小蓝最终要走到第n行第m列。
在图中，有的位置有奖励，走上去即可获得，有的位置有惩罚，走上去就要接受惩罚。奖励和惩罚最终抽象成一个权值，奖励为正，惩罚为负。
小蓝希望，从第1行第1列走到第n行第m列后，总的权值和最大。请问最大是多少?
//宽度搜索 #include <iostream> #include <algorithm> #include <cmath> using namespace std; const int N = 110; int n, m; int map[N][N]; int res = -1e9; int px[9] = {
0,0,0,1,2,3,1,1,2 }, py[9] = {
1,2,3,0,0,0,1,2,1 }; void bfs(int x, int y, int sum) {
if (x == n && y == m) {
res = max(sum, res); } else {
for (int i = 0; i < 9; i++) {
int px1 = x + px[i]; int py1 = y + py[i]; if (px1 <= n && py1 <= m) {
int sum1 = map[px1][py1] + sum; bfs(px1, py1, sum1); } } } } int main() {
cin >> n >> m; for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> map[i][j]; } } bfs(1, 1, map[1][1]); cout << res << endl; } 6. 路径
题目描述：
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。
小蓝的图由2021个结点组成，依次编号1至2021。
对于两个不同的结点a, b，如果a和b的差的绝对值大于21，则两个结点之间没有边相连;如果a和b的差的绝对值小于等于21，则两个点之间有一条长度为a和 b的最小公倍数的无向边相连。
例如:结点1和结点23之间没有边相连;结点3和结点24之间有一条无向边，长度为24;结点15和结点25之间有一条无向边，长度为75。
请计算，结点1和结点2021之间的最短路径长度是多少。
#include <iostream> #include <vector> #include <algorithm> using namespace std; //动态规划 int dp[2022]; //求最小公倍数 int fun(int a,int b){
int maxv = max(a, b); int minv = min(a, b); for(int i = maxv; ;i+=maxv){
if(i % minv == 0){
return i; } } return 1; } int main(){
//第一层循环遍历所有节点1~2021 for(int i = 1; i < 2022; i++){
//第二层循环遍历这个i节点的前21个节点 for(int j = i+1; j <= i + 21; j++){
//如果j超出下标就退出循环 if(j >= 2022){
break; } //最小公倍数，即i与j之间的距离 int num = fun(i, j); if(dp[j] == 0){
//第一次来到这个节点的路径长度是 来到i的距离 + i来到j的距离 dp[j] = num + dp[i]; }else{
//如果不是第一次来到这个节点那就看来 i节点的距离 + i来到j的距离 与 上次来到j的距离比较 要更小那个 dp[j] = min(dp[j], num + dp[i]); } } } cout << dp[2021] << endl; return 0; } 7. 迷宫
题目描述：
下图给出了一个迷宫的平面图，其中标记为1的为障碍，标记为0的为可以通行的地方。
010000 000100 001001 001010 00000000000000101 000000 000001 000000 000000000 000000 00000000000001001 000000 0000000 000000 000000000 001000 000001 000100 0000000 000001 000010 0000000 000001 000010 00000000000000010 000000 00000000000 000000 0000000 000011 000000 #include <iostream> #include <algorithm> #include <string> #include <string.h> #include <queue> using namespace std; char a[40][60]; //存图 int nextx[4] = {
1,0,0,-1 }, nexty[4] = {
0,-1,1,0 }; //D<L<R<U 字典序直接把方向数组处理好就可以了 int dist[40][60]; //定义一个dist数组，用来存放各点到终点的最短距离 char dir[4] = {
'D','L','R','U' }; bool check(int x, int y) {
return x > 0 && y > 0 && x <= 50 && y <= 50 && a[x][y] == '0'&&dist[x][y] == -1; } void bfs() {
//BFS扫一遍，求出各点到终点的最短距离 queue<pair<int, int> >q; memset(dist, -1, sizeof(dist)); dist[30][50] = 0; q.push({
30,50 }); while (!q.empty()) {
pair<int ,int> t = q.front(); q.pop(); for (int i = 0; i < 4; i++) {
int newx = t.first + nextx[i]; int newy = t.second + nexty[i]; if (check(newx, newy)) {
dist[newx][newy] = dist[t.first][t.second] + 1; q.push({
newx,newy }); } } } } int main() {
for (int i = 1; i <= 30; i++) for (int j = 1; j <= 50; j++) cin >> a[i][j]; bfs(); int x = 1, y = 1; //从起点开始遍历 string res; //存答案 while (x != 30 || y != 50) {
for (int i = 0; i < 4; i++) {
int newx = x + nextx[i]; int newy = y + nexty[i]; if (newx > 0 && newy > 0 && newx <= 50 && newy <= 50 && a[newx][newy] == '0'&&dist[newx][newy]==dist[x][y]-1) {
x = newx, y = newy; res += dir[i]; break; } } } cout << res << "\n"; return 0; } 8. 装饰珠
题目描述：
在怪物猎人这一款游戏中，玩家可以通过给装备镶嵌不同的装饰珠来获取相应的技能，以提升自己的战斗能力。
已知猎人身上一共有6件装备，每件装备可能有若干个装饰孔，每个装饰孔有各自的等级，可以镶嵌一颗小于等于自身等级的装饰珠(也可以选择不镶嵌)。
装饰珠有M种，编号1至M，分别对应M种技能，第i种装饰珠的等级为Li，只能镶嵌在等级大于等于Li的装饰孔中。
对第à种技能来说，当装备相应技能的装饰珠数量达到K;个时，会产生W;(K;)的价值。镶嵌同类技能的数量越多，产生的价值越大，即W;(K;—1)<Wi(Ki)。但每个技能都有上限P;(1≤P≤7)，当装备的珠子数量超过P时，只会产生W:( P)的价值。
对于给定的装备和装饰珠数据，求解如何镶嵌装饰珠，使得6件装备能得到的总价值达到最大。
#include <bits/stdc++.h> using namespace std; int MonsterHunter() {
//6件装备 vector<int> level(5, 0); //level[i]表示6件装备总共可以装饰level[i]棵装饰珠 for (int i = 0; i < 6; i++) {
//循环输入6件装备的每个装饰孔 int n, temp; cin >> n; //装饰孔数量 for (int j = 0; j < n; j++) {
cin >> temp; //装饰孔等级 switch (temp) {
//计算每个等级最多可以装饰多少件 case 4: level[4] += 1; case 3: level[3] += 1; case 2: level[2] += 1; case 1: level[1] += 1; break; //到1级的才break，因为高等级的孔可以装低等级的装饰珠 default: break; } } } int M; //装饰珠子种类数量 cin >> M; vector<vector<int> > weighttable(4, vector<int>(8, 0)); //最优价值表weighttable[i][j]表示等级(i+1)数量为(j)时的最优价值取值 for (int i = 0; i < M; i++) {
//根据输入的装饰珠构建最优价值表 int L, P; cin >> L >> P; //装饰珠等级，上限 for (int j = 1; j <= P; j++) {
int temp; cin >> temp; if (weighttable[L - 1][j] < temp) {
//如果当前装饰珠数量的价值大于原来的价值，则替换 weighttable[L - 1][j] = temp; if ((j + 1 > P) && P < 7) {
//恰好又是上限的话，剩下的全填上限值 for (int k = j + 1; k <= 7; k++) weighttable[L - 1][k] = weighttable[L - 1][k - 1]; } } } } int maxweight = INT_MIN; //循环4次，因为一共有4个等级 for (int i = 0; i <= (level.at(4)); i++) {
for (int j = 0; j <= (level.at(3) - i); j++) {
for (int k = 0; k <= (level.at(2) - (i + j)); k++) {
for (int s = 0; s <= (level.at(1) - (i + j + k)); s++) {
int a, b, c, d; //超出装备上限的一律取最后一个数 if (i > 7) a = 7; else a = i; if (j > 7) b = 7; else b = j; if (k > 7) c = 7; else c = k; if (s > 7) d = 7; else d = s; maxweight = max(maxweight, weighttable[3][a] + weighttable[2][b] + weighttable[1][c] + weighttable[0][d]); } } } } return maxweight; //返回计算的最大值 } int main() {
// 请在此输入您的代码 cout << MonsterHunter() <<endl; return 0; } 9. 明码
题目描述：
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
汉字的字形存在于字库中，即便在今天，16点阵的字库也仍然使用广泛。
16点阵的字库把每个汉字看成是16× 16个像素信息。并把这些信息记录在字节中。
一个字节可以存储8位信息，用32个字节就可以存一个汉字的字形了。把每个字节转为2进制表示，1表示墨迹，0表示底色。每行2个字节，一共16行，布局是:
第1字节,第2字节 第3字节，第4字节 ... ... 第31字节，第32字节 这道题目是给你一段多个汉字组成的信息，每个汉字用32个字节表示，这里给出了字节作为有符号整数的值。题目的要求隐藏在这些信息中。你的任务是复原这些汉字的字形，从中看出题目的要求，并根据要求填写答案。这段信息是（一共10个汉字)∶
4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0 16 64 16 64 34 68 127 126 66 -124 67 4 66 4 66 -124 126 100 66 36 66 4 66 4 66 4 126 4 66 40 0 16 4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0 0 -128 64 -128 48 -128 17 8 1 -4 2 8 8 80 16 64 32 64 -32 64 32 -96 32 -96 33 16 34 8 36 14 40 4 4 0 3 0 1 0 0 4 -1 -2 4 0 4 16 7 -8 4 16 4 16 4 16 8 16 8 16 16 16 32 -96 64 64 16 64 20 72 62 -4 73 32 5 16 1 0 63 -8 1 0 -1 -2 0 64 0 80 63 -8 8 64 4 64 1 64 0 -128 0 16 63 -8 1 0 1 0 1 0 1 4 -1 -2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 5 0 2 0 2 0 2 0 7 -16 8 32 24 64 37 -128 2 -128 12 -128 113 -4 2 8 12 16 18 32 33 -64 1 0 14 0 112 0 1 0 1 0 1 0 9 32 9 16 17 12 17 4 33 16 65 16 1 32 1 64 0 -128 1 0 2 0 12 0 112 0 0 0 0 0 7 -16 24 24 48 12 56 12 0 56 0 -32 0 -64 0 -128 0 0 0 0 1 -128 3 -64 1 -128 0 0 #include <iostream> using namespace std; struct Character {
char bytes[32]; }; Character characters[] = {
{
4,0,4,0,4,0,4,32,-1,-16,4,32,4,32,4,32,4,32,4,32,8,32,8,32,16,34,16,34,32,30,-64,0}, {
16,64,16,64,34,68,127,126,66,-124,67,4,66,4,66,-124,126,100,66,36,66,4,66,4,66,4,126,4,66,40,0,16}, {
4,0,4,0,4,0,4,32,-1,-16,4,32,4,32,4,32,4,32,4,32,8,32,8,32,16,34,16,34,32,30,-64,0}, {
0,-128,64,-128,48,-128,17,8,1,-4,2,8,8,80,16,64,32,64,-32,64,32,-96,32,-96,33,16,34,8,36,14,40,4}, {
4,0,3,0,1,0,0,4,-1,-2,4,0,4,16,7,-8,4,16,4,16,4,16,8,16,8,16,16,16,32,-96,64,64}, {
16,64,20,72,62,-4,73,32,5,16,1,0,63,-8,1,0,-1,-2,0,64,0,80,63,-8,8,64,4,64,1,64,0,-128}, {
0,16,63,-8,1,0,1,0,1,0,1,4,-1,-2,1,0,1,0,1,0,1,0,1,0,1,0,1,0,5,0,2,0}, {
2,0,2,0,7,-16,8,32,24,64,37,-128,2,-128,12,-128,113,-4,2,8,12,16,18,32,33,-64,1,0,14,0,112,0}, {
1,0,1,0,1,0,9,32,9,16,17,12,17,4,33,16,65,16,1,32,1,64,0,-128,1,0,2,0,12,0,112,0}, {
0,0,0,0,7,-16,24,24,48,12,56,12,0,56,0,-32,0,-64,0,-128,0,0,0,0,1,-128,3,-64,1,-128,0,0} }; void printByte(char byte) {
char bytes[8] = {
0 }; for (int i = 7; i >= 0; --i) {
bytes[i] = byte % 2; byte >>= 1; } for (int i = 0; i < 8; ++i) {
if (bytes[i]) cout << "*"; else cout << " "; } } void printCharacter(char bytes[]) {
for (int i = 0; i < 32; ++i) {
printByte(bytes[i]); if (i != 0 && (i + 1) % 2 == 0) cout << endl; } } int main() {
for (int i = 0; i < 10; ++i) {
printCharacter(characters[i].bytes); cout << endl; } return 0; } 10. 字串分值
题目描述：
对于一个字符串S，我们定义S的分值f(S)为S中恰好出现一次的字符个数。例如f (aba)= 1，f (abc)= 3, f (aaa)= 0。现在给定一个字符串 So…n—1(长度为n，1<n ≤105)，请你计算对于所有S的非空子串S;…j(0≤i≤j< n)，f(Si…j)的和是多少。
#include<bits/stdc++.h> using namespace std; //子串分值和字串分值和有点类似，但是该题f(S)统计的是子串中只出现一次的字符的个数 //而子串分值和中统计的是子串中出现的不同字符的个数，很显然，该题需要考虑更多条件， //即是需要知道该字母上一次出现的位置和下一次出现的位置，通过相减得到前后子串的长度(子串长度就是子串的子串数) //通过前后子串的子串数相乘便得到前后子串连在一起的大子串的子串数 typedef long long ll; const int N=1e5+10; ll l[N];//字符左边同字符的下标 ll r[N];//字符右边同字符的下标 ll vis[30];//通过ascll码为下标存储字母下标，ascll通过字母-'a'取得。该数组在给left和right赋值前都要初始化。分别是0和size()+1; char a[N]; int main(){
string s;cin>>s; for(int i=1;i<=s.size();i++)a[i]=s[i-1]; memset(vis,0,sizeof(vis)); for(int i=1;i<=s.size();i++){
int k=a[i]-'a'; l[i]=vis[k]; vis[k]=i; } for(int i=0;i<30;i++)vis[i]=s.size()+1; for(int i=s.size();i>=1;i--){
int k=a[i]-'a'; r[i]=vis[k]; vis[k]=i; } //------------->digo！左右位置赋值完成~ //直接遍历一遍赋值就没问题了！ ll ans=0; for(int i=1;i<=s.size();i++){
ans+=(i-l[i])*(r[i]-i); } cout<<ans<<endl; return 0; } 11. 作物杂交
题目描述：
作物杂交是作物栽培中重要的一步。已知有Ⅳ种作物(编号1至N )，第i种作物从播种到成熟的时间为T。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物A种植时间为5天，作物B种植时间为7天，则AB杂交花费的时间为7天。作物杂交会产生固定的作物，新产生的作物仍然属于Ⅳ种作物中的一种。
初始时，拥有其中M种作物的种子(数量无限，可以支持多次杂交)。同时可以进行多个杂交过程。求问对于给定的目标种子，最少需要多少天能够得到。
如存在4种作物ABCD，各自的成熟时间为5天、7天、3天、8天。初始拥有AB两种作物的种子，目标种子为D，已知杂交情况为A×B→C，A×C→D。则最短的杂交过程为:
第1天到第7天(作物B的时间)，A×B→C。
第8天到第12天(作物A的时间)，A× C→D。
花费12天得到作物D的种子。
#include <iostream> #include <algorithm> #include <queue> #include <cstring> using namespace std; const int maxn = 2020; const int maxk = 2E5+10; int grow[maxn]; bool have[maxn]; int edge[maxk], head[maxn], ne[maxk], cost[maxk], target[maxk], idx = 1; int getcost(int u, int v) {
return max(grow[u], grow[v]);} void add(int u, int v, int c, int t) {
edge[idx] = v; cost[idx] = c; ne[idx] = head[u]; head[u] = idx; target[idx] = t; idx++; } struct Node{
int id, cost; bool operator > (const Node &x) const {
return cost > x.cost;} }; priority_queue<Node, vector<Node>, greater<Node> > heap; int dist[maxn]; int main() {
int N, M, K, T; cin >> N >> M >> K >> T; memset(dist, 0x3f, sizeof dist); for(int i = 1; i <= N; ++i) cin >> grow[i]; for(int i = 0; i < M; ++i) {
int u; cin >> u; have[u] = 1; dist[u] = 0; } for(int i = 0; i < K; ++i) {
int u, v, c, t; cin >> u >> v >> t; c = getcost(u, v); if(have[u] && have[v] && c < dist[t]) {
dist[t] = c; Node temp = {
t, c}; heap.push(temp); } add(u, v, c, t); add(v, u, c, t); } while(!have[T]) {
Node p = heap.top(); heap.pop(); if(!have[p.id]) {
have[p.id] = 1; for(int i = head[p.id]; i; i = ne[i]) {
int to = edge[i], c = cost[i], tar = target[i]; int bet = dist[p.id]; if(!have[tar] && have[to] && bet+c < dist[tar]) {
dist[tar] = bet+c; Node temp = {
tar, dist[tar]}; heap.push(temp); } } } } cout << dist[T]; return 0; } 12. 承压计算
题目描述：
×星球的高科技实验室中整齐地堆放着某批珍贵金属原料。
每块金属原料的外形、尺寸完全一致，但重量不同。金属材料被严格地堆放成金字塔形。
7 5 8 7 8 8 9 2 7 2 8 1 4 9 1 8 1 8 8 4 1 7 9 6 1 4 5 4 5 6 5 5 6 9 5 6 5 5 4 7 9 3 5 5 1 7 5 7 9 7 4 7 3 3 1 4 6 4 5 5 8 8 3 2 4 3 1 1 3 3 1 6 6 5 5 4 4 2 9 9 9 2 1 9 1 9 2 9 5 7 9 4 3 3 7 7 9 3 6 1 3 8 8 3 7 3 6 8 1 5 3 9 5 8 3 8 1 8 3 3 8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9 8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4 2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9 7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6 9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3 5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9 6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4 2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4 7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6 1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3 2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8 7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9 7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6 5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1 X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X #include<stdio.h> int main(){
double a[30][30]={
{
7}, {
5,8}, {
7,8,8}, {
9,2,7,2}, {
8,1,4,9,1}, {
8,1,8,8,4,1}, {
7,9,6,1,4,5,4}, {
5,6,5,5,6,9,5,6}, {
5,5,4,7,9,3,5,5,1}, {
7,5,7,9,7,4,7,3,3,1}, {
4,6,4,5,5,8,8,3,2,4,3}, {
1,1,3,3,1,6,6,5,5,4,4,2}, {
9,9,9,2,1,9,1,9,2,9,5,7,9}, {
4,3,3,7,7,9,3,6,1,3,8,8,3,7}, {
3,6,8,1,5,3,9,5,8,3,8,1,8,3,3}, {
8,3,2,3,3,5,5,8,5,4,2,8,6,7,6,9}, {
8,1,8,1,8,4,6,2,2,1,7,9,4,2,3,3,4}, {
2,8,4,2,2,9,9,2,8,3,4,9,6,3,9,4,6,9}, {
7,9,7,4,9,7,6,6,2,8,9,4,1,8,1,7,2,1,6}, {
9,2,8,6,4,2,7,9,5,4,1,2,5,1,7,3,9,8,3,3}, {
5,2,1,6,7,9,3,2,8,9,5,5,6,6,6,2,1,8,7,9,9}, {
6,7,1,8,8,7,5,3,6,5,4,7,3,4,6,7,8,1,3,2,7,4}, {
2,2,6,3,5,3,4,9,2,4,5,7,6,6,3,2,7,2,4,8,5,5,4}, {
7,4,4,5,8,3,3,8,1,8,6,3,2,1,6,2,6,4,6,3,8,2,9,6}, {
1,2,4,1,3,3,5,3,4,9,6,3,8,6,5,9,1,5,3,2,6,8,8,5,3}, {
2,2,7,9,3,3,2,8,6,9,8,4,4,9,5,8,2,6,3,4,8,4,9,3,8,8}, {
7,7,7,9,7,5,2,7,9,2,5,1,9,2,6,5,3,9,3,5,7,3,5,4,2,8,9}, {
7,7,6,6,8,7,5,5,8,2,4,7,7,4,7,2,6,9,2,1,8,2,9,8,5,7,3,6}, {
5,9,4,5,5,7,5,5,6,3,5,3,9,5,8,9,5,4,1,2,6,1,4,3,5,3,2,4,1} }; for(int i=0;i<29;i++){
for(int j=0;j<=i;j++){
a[i+1][j]+=a[i][j]/2; a[i+1][j+1]+=a[i][j]/2; } } double max=0,min=; for(int i=0;i<30;i++){
if(max<a[29][i]){
max=a[29][i]; } if(min>a[29][i]){
min=a[29][i]; } } //因为这样加起来最小的一定不会是，所以他一定存在一个转化问题且题干上说了电子秤的计量单位很小，所以显示的单位很大 printf("%.0lf",max*/min); return 0; } 13. 全球变暖
题目描述：
你有一张某海域NcN像素的照片，”.“表示海洋、”#”表示陆地，如下所示:
....... ..... ..... ..... ... .... ....... ....... ....... ....... ....... ....#.. ....... ....... 请你计算:依照科学家的预测，照片中有多少岛屿会被完全淹没。
#include<bits/stdc++.h> using namespace std; int N; const int SIZE = 1e4+4; char area[SIZE][SIZE]; bool flag; int cnt; int d[4][2]={
{
1,0}, {
-1,0}, {
0,1}, {
0,-1} }; //注意：求的是被淹没的岛屿的数量 总岛屿数量-被淹没的岛屿的数量 int ans=0;//没有被淹没岛屿的数量 int res_ans=0;//岛屿的总数量 //用DFS判断搜到的这个岛屿会不会被淹没，仅此而已，不需要返回什么 昨判断关系 void dfs(int x,int y) {
if(flag==false){
//一个岛屿只要有一个点满足就不会变淹没了 cnt = 0; for(int i=0; i<4; i++){
int tx=d[i][0]+x; int ty=d[i][1]+y; if(area[tx][ty]!='.') cnt++; } if(cnt==4){
//有一个点满足不会被淹没的条件 ans++; flag=true;//这个岛屿不需要再遍历了 } } area[x][y]='*';//将遍历过的点变为 *，下一次就不会遍历他了，所以不用标记数组 //注意这里不可以是‘.’因为上面if(area[tx][ty]!='.')cnt++ for(int i=0;i<4;i++){
int xx = x + d[i][0]; int yy = y + d[i][1]; if(area[xx][yy]=='#'&&x<N&&x>=0&&y<N&&y>=0) dfs(xx,yy); } } int main() {
cin>>N; for(int i=0; i<N; i++) for(int j=0; j<N; j++) cin>>area[i][j]; for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(area[i][j]=='#'){
res_ans++; flag=false; dfs(i,j); } } } cout<<res_ans-ans; return 0; } 14. 直线
题目描述：
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同—条。
给定平面上2×3个整点
(z, y)0 ≤a <2,0≤y < 3, a ∈ Z,g∈Z，即横坐标是0到1(包含0和1)之间的整数、纵坐标是0到2(包含0和2)之间的整数的点。这些点一共确定了11条不同的直线。
给定平面上20 × 21个整点
(z, gy)|0 <a <20,0≤y <21, a ∈ Z, gy∈Z，即横坐标是0到19(包含0和19)之间的整数、纵坐标是0到20(包含0和20)之间的整数的点。
请问这些点一共确定了多少条不同的直线。
#include <iostream> #include <cmath> #include <algorithm> using namespace std; struct zhixian{
double k; double b; }a[]; bool cmp(zhixian q, zhixian w) {
if(q.k != w.k) {
return q.k < w.k; } else {
return q.b < w.b; } } int main() {
int total = 0; for(int x1 = 0; x1 < 20; x1++) {
for(int y1 = 0; y1 < 21; y1++) {
for(int x2 = 0; x2 < 20; x2++) {
for(int y2 = 0; y2 < 21; y2++) {
if(x1 != x2) {
double k = (double)(y2 - y1) / (x2 - x1); double b = (double)(y2 - k * x2); a[total++] = {
k, b}; } } } } } sort(a, a + total, cmp); int ans = 1; for(int i = 1; i < total; i++) {
if(fabs(a[i].k - a[i - 1].k) > 1e-8 || fabs(a[i].b - a[i - 1].b > 1e-8)) {
ans ++; } } cout << ans + 20; return 0; } 15. 平面切分
题目描述：
平面上有N条直线，其中第i条直线是y = Ai xc＋B;。请计算这些直线将平面分成了几个部分。
分析：
最初的平面个数为1；
每次加入一条直线，它从无穷远处延申，它开始就会把平面分割成两个平面，所以每多一条直线，平面个数就会 +1 ,接下来只用讨论该条直线与先平面中每条直线的情况（相交或者平行）。
当它与现有的一条直线平行时，不会有新的平面产生，（最简单的情况就是原平面只有一条直线，新添加的直线与它平行，平面数= 上一个状态的平面数 + 1）
当它与现有的一条直线a 相交时，平面数就需要+1，形象的理解：把直线a 看做平面的尽头，当它穿过a 后，相当于它进入另外一个平面，又从无穷远处延申，又将该平面一分为二。直线具有无限长的特点。 该种情况下的平面数 = 上一个状态的平面数 +1 +1；
也就是说 在添加一条直线就会多一个平面的基础上，它与直线有交点就会 再 +1； 接下来只需要判断它与 平面内的多少条直线有交点即可。 同时注意，当它与多条线的交点为同一个时，只执行一次 +1，具体情况画出三条线交于一点，和三条线交于两点的情况，一目了然。
#include <iostream> #include <set> using namespace std; typedef pair<int,int> PII; typedef pair<double,double> PDD; set<PII>s; // 记录斜率和拮据 int main() {
int res = 1; int n; cin>>n; while(n--) {
int a,b; cin>>a>>b; if(s.find({
a,b}) != s.end()) // 完全相同的直线只能操作一次 continue; res++;// 每添加一条直线，平面数都得 +1 set<PDD>jd;// 记录添加一条执行，它与平面内直线的交点（一个交点只能被统计一次） for(auto it = s.begin();it !=s.end();it++) {
double x = (it->second - b)*1.0 / (a - it->first); // 计算交点的坐标值（x,y） double y = a*x+b; if(a != it->first && (jd.find({
x,y})==jd.end() || jd.empty())) {
res += 1; jd.insert({
x,y}); } } s.insert({
a,b}); } cout<<res<<endl; return 0; } 免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/120486.html
