数据库对网站开发的作用,网站建设 犀牛,北京百度搜索优化,cn域名多少钱一年文章目录1. 最短路2. 数字三角形3. 递增序列4. 杨辉三角形5. 跳跃6. 路径7. 迷宫8. 装饰珠9. 明码10. 字串分值11. 作物杂交12. 承压计算13. 全球变暖14. 直线15. 平面切分1. 最短路
题目描述#xff1a; 如下图所示#xff0c;G是一个无向图#xff0c;其中蓝色边的长度是…
文章目录1. 最短路2. 数字三角形3. 递增序列4. 杨辉三角形5. 跳跃6. 路径7. 迷宫8. 装饰珠9. 明码10. 字串分值11. 作物杂交12. 承压计算13. 全球变暖14. 直线15. 平面切分1. 最短路
题目描述 如下图所示G是一个无向图其中蓝色边的长度是1、橘色边的长度是2、绿色边的长度是3。 则从 A 到 S 的最短距离是多少
#include iostream
#include cstring
using namespace std;
const int N200,n19;
int dist[N];
int g[N][N];
void add(char x,char y,int c)
{int ax-A1;int by-A1;g[a][b]g[b][a]c;
}
bool vis[N];
int dijkstra()
{memset(dist,0x3f,sizeof dist);dist[1]0;for(int i0;in;i){int t-1;for(int j1;jn;j){if(!vis[j](t-1||dist[j]dist[t]))tj;}vis[t]1;for(int j1;jn;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);coutdijkstra();return 0;
}2. 数字三角形
题目描述 73 88 1 02 7 4 4
4 5 2 6 5上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径把路径上面的数加起来可以得到一个和你的任务就是找到最大的和。 路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外向左下走的次数与向右下走的次数相差不能超过1。
【输入描述】 输入的第一行包含一个整数N(1≤N ≤100)表示三角形的行数。 下面的N行给出数字三角形。数字三角形上的数都是О至100之间的整数。 【输出描述】 输出一个整数表示答案。
#includeiostream
using namespace std;
int a[200][200];
int dp[200][200];
int main()
{int n;cinn;for(int i1;in;i){for(int j1;ji;j)cina[i][j];}dp[1][1]a[1][1];for(int i2;in;i){for(int j1;ji;j){if(j1)dp[i][j]dp[i-1][j]a[i][j];else if(ji)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%20){coutmax(dp[n][n/2],dp[n][n/21]);}else{coutdp[n][n/21]endl;}}3. 递增序列
题目描述 本题为填空题只需要算出结果后在代码中使用输出语句将所填结果输出即可。 对于一个字母矩阵我们称矩阵中的一个递增序列是指在矩阵中找到两个字母它们在同一行同一列或者在同一45度的斜线上这两个字母从左向右看、或者从上向下看是递增的。 例如如下矩阵中
LANN
QIAO有LN、LN、AN、AN、IO、AO、LQ、AI、NO、NO、等13个递增序列。注意当两个字母是从左下到右上排列时从左向右看和从上向下看是不同的顺序。 对于下面的30行50列的矩阵请问总共有多少个递增序列?
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
RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY
ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX#include iostream
using namespace std;
int main()
{char str[35][55];long int ans 0;for(int i0; i30; i)for(int j0; j50; j){cin str[i][j];}for(int i0; i30; i)for(int j0; j50; j){int k;for(k1; kj50; k)//列 {if(str[i][j] str[i][jk])ans;} for(k1; ki30; k)//行 {if(str[i][j] str[ik][j])ans;} for(k1; ki30 jk50; k) //从左上到右下{if(str[ik][jk] str[i][j])ans; } }for(int i1; i30; i)for(int j0; j50; j){int k;for(k1; i-k0 jk50; k)//左下到右上 {if(str[i][j] ! str[i-k][jk]) ans;}}cout ans endl;return 0;
}4. 杨辉三角形
题目描述
如果我们按从上到下、从左到右的顺序把所有数排成一列可以得到如下数列: 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,… 给定一个正整数N请你输出数列中第一次出现N是在第几个数?
【输入描述】 输入一个整数N。 【输出描述】 输出一个整数代表答案。
#includebits/stdc.h
using namespace std;
typedef long long LL;
LL n;
/* 11 2 11 3 3 11 4 6 4 1
1 5 10 10 5 1
可以发现找到第一个出现的一定在左边故右边可以直接删去11 21 31 4 61 5 101 6 15 20
/ / / /
从打斜杠的地方可以发现规律为C(2n,n)
故找到最大的斜行
用t来代表斜行数
最大为1e9
故求有多少个斜行数满足
int x;//记录第几个斜行满足
for(int t0;;t){
if(1e9C(2t,t)){xt;break;
}
}
故解得t17;
斜线从大到小依次排列第一找到第一个数
再通过二分查找
C(t, k)对应的顺序值为(t 1) * t / 2 k 1
*/
LL C(int x,int k){LL ans1;for(int ix,j1;jk;i--,j){ansans*i/j;if(ansn)return ans;}return ans;
}
bool check(int x){LL l2*x,rmax(n,l);while(lr){int midlr1;if(C(mid,x)n)rmid;else lmid1;}if(C(r,x)!n)return false;cout(LL)(r1)*r/2x1endl;return true;
}
int main(){cinn;for(int t17;;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列后总的权值和最大。请问最大是多少?
【输入描述】 输入的第一行包含两个整数n, m表示图的大小。 接下来n行每行m个整数表示方格图中每个点的权值。其中1≤n ≤100-104≤权值≤104。 【输出描述】 输出一个整数表示最大权值和。
//宽度搜索
#include iostream
#include algorithm
#include cmathusing 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; ;imaxv){if(i % minv 0){return i;}}return 1;
}int main(){//第一层循环遍历所有节点1~2021for(int i 1; i 2022; i){//第二层循环遍历这个i节点的前21个节点for(int j i1; 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
110000迷宫的入口为左上角出口为右下角在迷宫中只能从一个位置走到这个它的上、下、左、右四个方向之一。 对于上面的迷宫从入口开始可以按DRRURRDDDR的顺序通过迷宫一共10步。其中D、U、L、R分别表示向下、向上、向左、向右走。对于下面这个更复杂的迷宫(30行50列)请找出一种通过迷宫的方式其使用的步数最少在步数最少的前提下请找出字典序最小的一个作为答案。 请注意在字典序中DLRU。
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000#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 }; //DLRU 字典序直接把方向数组处理好就可以了
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] 0dist[x][y] -1;
}
void bfs() { //BFS扫一遍求出各点到终点的最短距离queuepairint, int q;memset(dist, -1, sizeof(dist));dist[30][50] 0;q.push({ 30,50 });while (!q.empty()) {pairint ,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] 0dist[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件装备能得到的总价值达到最大。
【输入描述】 输入的第1至6行包含6件装备的描述。其中第i行的第一个整数N表示第à件装备的装饰孔数量。后面紧接着ⅣN个整数分别表示该装备上每个装饰孔的等级L (1≤L≤4)。 第7行包含一个正整数M表示装饰珠(技能)种类数量。 第8至M7行每行描述一种装饰珠(技能)的情况。每行的前两个整数Lj (1 ≤Lj≤4)和P; (1≤P≤7)分别表示第j种装饰珠的等级和上限。接下来P个整数其中第k个数表示该装备中装饰珠数量为k时的价值W;(k)。其中1≤N≤50,1 ≤M ≤104,1≤ W;(k)≤104。 【输出描述】 输出一行包含一个整数表示能够得到的最大价值。
#include bits/stdc.h
using namespace std;
int MonsterHunter() {//6件装备vectorint 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;vectorvectorint weighttable(4, vectorint(8, 0)); //最优价值表weighttable[i][j]表示等级(i1)数量为(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 *;elsecout ;}
}
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) 1f (abc) 3, f (aaa) 0。现在给定一个字符串 So…n—1(长度为n1n ≤105)请你计算对于所有S的非空子串S;…j(0≤i≤j n)f(Si…j)的和是多少。
【输入描述】 输入一行包含一个由小写字母组成的字符串 S。 【输出描述】 输出一个整数表示答案。
#includebits/stdc.h
using namespace std;
//子串分值和字串分值和有点类似但是该题f(S)统计的是子串中只出现一次的字符的个数
//而子串分值和中统计的是子串中出现的不同字符的个数很显然该题需要考虑更多条件
//即是需要知道该字母上一次出现的位置和下一次出现的位置通过相减得到前后子串的长度(子串长度就是子串的子串数)
//通过前后子串的子串数相乘便得到前后子串连在一起的大子串的子串数
typedef long long ll;
const int N1e510;
ll l[N];//字符左边同字符的下标
ll r[N];//字符右边同字符的下标
ll vis[30];//通过ascll码为下标存储字母下标ascll通过字母-a取得。该数组在给left和right赋值前都要初始化。分别是0和size()1;
char a[N];
int main(){string s;cins;for(int i1;is.size();i)a[i]s[i-1];memset(vis,0,sizeof(vis));for(int i1;is.size();i){int ka[i]-a;l[i]vis[k];vis[k]i;}for(int i0;i30;i)vis[i]s.size()1;for(int is.size();i1;i--){int ka[i]-a;r[i]vis[k];vis[k]i;}//-------------digo左右位置赋值完成~//直接遍历一遍赋值就没问题了ll ans0;for(int i1;is.size();i){ans(i-l[i])*(r[i]-i);}coutansendl;return 0;
}11. 作物杂交
题目描述 作物杂交是作物栽培中重要的一步。已知有Ⅳ种作物(编号1至N )第i种作物从播种到成熟的时间为T。作物之间两两可以进行杂交杂交时间取两种中时间较长的一方。如作物A种植时间为5天作物B种植时间为7天则AB杂交花费的时间为7天。作物杂交会产生固定的作物新产生的作物仍然属于Ⅳ种作物中的一种。 初始时拥有其中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 ,TN表示作物种类总数(编号1至N)M表示初始拥有的作物种子类型数量K表示可以杂交的方案数T表示目标种子的编号。 第2行包含N个整数其中第i个整数表示第i种作物的种植时间T (1≤T≤100)。 第3行包含M个整数分别表示已拥有的种子类型K;(1≤K;≤M)K;两两不同。 第4至K3行每行包含3个整数A,B,C表示第A类作物和第B类作物杂交可以获得第C类作物的种子。其中1≤N≤2000,2≤M≤N,1≤K 105,1≤T≤N,保证目标种子一定可以通过杂交得到。 【输出描述】 输出一个整数表示得到目标种子的最短杂交时间。
#include iostream
#include algorithm
#include queue
#include cstring
using namespace std;
const int maxn 2020;
const int maxk 2E510;
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_queueNode, vectorNode, greaterNode 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] betc dist[tar]){dist[tar] betc;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 其中的数字代表金属块的重量(计量单位较大)。最下一层的X代表30台极高精度的电子秤。 假设每块原料的重量都十分精确地平均落在下方的两个金属块上最后所有的金属块的重量都严格精确地平分落在最底层的电子秤上。 电了秤的计量单位很小所以显示的数字很大。 工作人员发现其中读数最小的电子秤的示数为:2086458231请你推算出:读数最大的电子秤的示数为多少?
#includestdio.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 i0;i29;i){for(int j0;ji;j){a[i1][j]a[i][j]/2;a[i1][j1]a[i][j]/2;}}double max0,min1000000;for(int i0;i30;i){if(maxa[29][i]){maxa[29][i];}if(mina[29][i]){mina[29][i];}}//因为这样加起来最小的一定不会是2086458231所以他一定存在一个转化问题且题干上说了电子秤的计量单位很小所以显示的单位很大printf(%.0lf,max*2086458231/min);return 0;
}13. 全球变暖
题目描述 你有一张某海域NcN像素的照片.“表示海洋、”#表示陆地如下所示:
........##.....##........##...####....###........其中上下左右四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。 由于全球变暖导致了海面上升科学家预测未来几十年岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)它就会被淹没。 例如上图中的海域未来会变成如下样子:
................................#................请你计算:依照科学家的预测照片中有多少岛屿会被完全淹没。
【输入描述】 第一行包含一个整数N (1≤N ≤1000)。 以下N行N列代表张海域照片。 照片保证第1行、第1列、第N行、第N 列的像素都是海洋。 输出一个整数表示答案。
#includebits/stdc.h
using namespace std;
int N;
const int SIZE 1e44;
char area[SIZE][SIZE];
bool flag;
int cnt;
int d[4][2]{{1,0},{-1,0},{0,1},{0,-1}
};
//注意求的是被淹没的岛屿的数量 总岛屿数量-被淹没的岛屿的数量
int ans0;//没有被淹没岛屿的数量
int res_ans0;//岛屿的总数量
//用DFS判断搜到的这个岛屿会不会被淹没仅此而已不需要返回什么 昨判断关系
void dfs(int x,int y)
{if(flagfalse){ //一个岛屿只要有一个点满足就不会变淹没了cnt 0;for(int i0; i4; i){int txd[i][0]x;int tyd[i][1]y;if(area[tx][ty]!.)cnt;}if(cnt4){//有一个点满足不会被淹没的条件ans;flagtrue;//这个岛屿不需要再遍历了}}area[x][y]*;//将遍历过的点变为 *下一次就不会遍历他了所以不用标记数组//注意这里不可以是‘.’因为上面if(area[tx][ty]!.)cntfor(int i0;i4;i){int xx x d[i][0];int yy y d[i][1];if(area[xx][yy]#xNx0yNy0)dfs(xx,yy);}
}int main()
{ cinN; for(int i0; iN; i)for(int j0; jN; j)cinarea[i][j];for(int i0; iN; i){ for(int j0; jN; j){if(area[i][j]#){res_ans;flagfalse;dfs(i,j);}}} coutres_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[405000];
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 xcB;。请计算这些直线将平面分成了几个部分。
【输入描述】 第一行包含一个整数N。 以下N行每行包含两个整数ABi。 其中1≤N≤1000,—105Ai,B;≤105 【输出描述】 一个整数代表答案。
分析 最初的平面个数为1 每次加入一条直线它从无穷远处延申它开始就会把平面分割成两个平面所以每多一条直线平面个数就会 1 ,接下来只用讨论该条直线与先平面中每条直线的情况相交或者平行。 当它与现有的一条直线平行时不会有新的平面产生最简单的情况就是原平面只有一条直线新添加的直线与它平行平面数 上一个状态的平面数 1 当它与现有的一条直线a 相交时平面数就需要1形象的理解把直线a 看做平面的尽头当它穿过a 后相当于它进入另外一个平面又从无穷远处延申又将该平面一分为二。直线具有无限长的特点。 该种情况下的平面数 上一个状态的平面数 1 1 也就是说 在添加一条直线就会多一个平面的基础上它与直线有交点就会 再 1 接下来只需要判断它与 平面内的多少条直线有交点即可。 同时注意当它与多条线的交点为同一个时只执行一次 1具体情况画出三条线交于一点和三条线交于两点的情况一目了然。
#include iostream
#include set
using namespace std;
typedef pairint,int PII;
typedef pairdouble,double PDD;setPIIs;
// 记录斜率和拮据int main()
{int res 1;int n;cinn;while(n--){int a,b;cinab;if(s.find({a,b}) ! s.end()) // 完全相同的直线只能操作一次continue;res;// 每添加一条直线平面数都得 1 setPDDjd;// 记录添加一条执行它与平面内直线的交点一个交点只能被统计一次for(auto it s.begin();it !s.end();it){double x (it-second - b)*1.0 / (a - it-first); // 计算交点的坐标值x,ydouble y a*xb;if(a ! it-first (jd.find({x,y})jd.end() || jd.empty())){res 1;jd.insert({x,y});}}s.insert({a,b});}coutresendl;return 0;
}
