Polaris-hzn8

onlineJ杨氏矩阵 原题链接：http://oj.haizeix.com/problem/600 题目描述 给定一个n行m列的二维矩阵和一个目标数t， 二维矩阵中对于每一行从左到右不下降(右边的数≥左边的数)，对于每一列从上到下不下降(下边的数≥上边的数)。 现要在数组中找到目标数t，并输出其所在位置的行数和列数。 输入 第一行两个整数n, m（1 ≤ n, m ≤ 3000） 接下来输入一个二维矩阵，矩阵内所有数均小于 200000。 最后输入一个整数t（1 ≤ t ≤ 200000） 输出 输出用空格隔开的数表示位置（从1开始计数），答案有唯一解。 123453 41 2 3 45 6 15 207 10 20 2515 12 3 1.暴力法：==思路==： 使用两个for循环对矩阵进行遍历操作，当遍历到target值时输出其行、列的下标值。 12345678910111213141516171819202122232425#include<iostream>using namespace std;int n, m, target;int num[3005][3005];int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { scanf("%d", &num[i][j]); } } scanf("%d", &target); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (num[i][j] == target) { printf("%d %d\n", i, j); return 0; ...

OnlineJ两数之和 原题链接：http://oj.haizeix.com/problem/599 题目描述 给定一个从小到大的数组和一个目标数t，在其中找到两个数，使得两数之和与目标数相等，输出两个数在数组中的位置。 输入 第一行输入两个整数 n, t（1 ≤ n ≤ 1000000, 1 ≤ t ≤ 20000000） 接下来一行 n 个数，均小于10,000,000 输出 输出两个用空格隔开的数表示位置（从零开始计数），答案有唯一解 126 151 5 6 7 10 26 11 4 1.暴力法：1234567891011121314151617181920212223#include<iostream>#include<cstdio>using namespace std;int num[1000005];int n, target;int main() { scanf("%d%d", &n, &target); for (int i = 0; i < n; ++i) { scanf("%d", &num[i]); } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (num[i] + num[j] == target) { cout << i << " " << j << endl; return 0; } } } cout << "not fimd" << endl; return 0;} 注意：由于数据范围(1≤n≤1000000, 1≤t≤20000000)，暴力枚举的时间复杂度为O(n^2)一定会超时，空间复杂度为O(1) 2.二分法：=&# ...

Euler枚举 1.E22：Name score在文本文件names.txt 中包含了五千多个名字， 首先将它们按照字母序排列，然后计算出每个名字的字母价值，乘以它在按字母顺序排列后的位置，就算出了这个名字的得分。 例如，按照字母序排列后，位于第938位的名字是COLIN，它的字母价值是3 + 15 + 12 + 9 + 14 = 53 因此，COLIN这个名字的得分是 938 × 53 = 49714. 上述文本文件中，所有名字的得分之和是多少？ 1.暴力枚举 将name.txt文件下载下来，进行初步处理%s/","/ /g（将连接符替换为空格分隔）、%s/"/ /g（处理开头结尾的单引号） 将名字输入保存到name[6005]数组中 首先使用sort算法对name数组进行排序 外循环遍历name数字中的每一个名字，内循环遍历name的每一个字母计算每个名字的价值value 输出最后累加的score分数 123456789101112131415161718192021222324#include<iostream>#include<string>#include<algorithm>using namespace std;string name[6005];int n;int main(){ while(cin >> name[n]){ n++; } sort(name, name + n); long long score = 0; for(int i = 0; i < n; ++i){ int value = 0;//name的价值 for(int j = 0; j < name[i].size(); ++j){ value += name[i][j] - 'A' + 1; } score += value * (i + 1); } cout << score << endl; return 0;& ...

数塔问题 1.onlineJ43：数塔问题 原题链接：http://oj.haizeix.com/problem/43 有一个由数字组成的三角形数塔，站在上一层的某个点，只能到达其下方左右的两个点。现在请找到一条从上到下的路径，使得路径上所有数字相加之和最大 1.递推法从上向下求和 由数塔中到达任意一点的数字和sum = 左上方数字和suml or 右上方数字和sumr + 该数字数值num 知到达该点最大和为ans[x][y] = max(ans[x - 1][y - 1], ans[x - 1][y]) + num[x][y]==关键== 遍历最后一行，找出最大的数字即为结果 12345678910111213141516171819202122232425262728#include<iostream>#include<cstdio>using namespace std;int n;int num[1005][1005];int main(){ scanf("%d", &n); for(int i = 1; i <= n; ++i){ for(int j = 1; j <= i; ++j){ scanf("%d", &num[i][j]); } } //1.从两个方向取数值大的方向max(num[i - 1][j - 1], num[i - 1][j]); for(int i = 1; i <= n; ++i){ for(int j = 1; j <= i; ++j){ num[i][j] += max(num[i - 1][j - 1], num[i - 1][j]); } } int ans = 0; //2.遍历最后一行，找出最大的数字即为结果 for(int i = 1; i <= n; ++i){ ans = max(a ...

Lattice paths Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. How many such routes are there through a 20×20 grid? 1.递推法递推法：dp[x][y] = dp[x - 1][y] + dp[x][y - 1] 网格中到达任意一点的路径方案数 = 正上方方案数 + 正下方方案数:dp[x][y] = dp[x - 1][y] + dp[x][y - 1] 递推边界为左上角点（1，1）,结果为右下角点坐标（4，4） 定义循环(i, j)需要从点(1, 1)点开始 这样外边界有一圈保护0，不需要判断边界、不用考虑数组越界问题（数字0不会影响答案） 12345678910111213141516171819#include<iostream>using namespace std;long long ans[25][25];int main(){ for(int i = 1; i <= 21; ++i){ for(int j = 1; j <= 21; ++j){ //初始化左上角点的值为(1, 1) if(i == 1 && j == 1){ ans[i][j] = 1; continue; } ans[i][j] = ans[i - 1][j] + ans[i][j - 1]; } } cout << ans[21][21] << endl; return 0;} 2.组合问题123456789101112#include<iostream>using namespac ...

1000-digit Fibonacci number The Fibonacci sequence is defined by the recurrence relation：Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1. Hence the first 12 terms will be: F1 = 1F2 = 1F3 = 2F4 = 3F5 = 5F6 = 8F7 = 13F8 = 21F9 = 34F10 = 55F11 = 89F12 = 144 The 12th term, F12, is the first term to contain three digits. What is the index of the first term in the Fibonacci sequence to contain 1000 digits? 1.大整数加法将两个数组循环相加——用指针将数组的地址作为函数参数传递到函数中，通过交换二维数组第一个下标交换数组地址 123456789101112131415161718192021222324252627282930313233343536373839404142/*思路：大整数加法 + 循环使用两个变量求fib数列1.将大整数加法封装在一个函数中2.循环使用两个变量(数组)求斐波那契数列项3.当出现某一项大于1000时，输出项数结束循环*/#include<iostream>using namespace std;//1.将大整数加法封装在一个函数中void func(int *n1, int *n2){ //注意：初始的n2可能比n1短，需要首先更新答案的长度 n2[0] = n1[0]; for(int i = 1; i <= n2[0]; ++i){ n2[i] += n1[i]; if(n2[i] > 9){ n2[i + 1] += n2[i] / 10; n2[i] %= ...

Large sum Work out the first ten digits of the sum of the following one-hundred 50-digit numbers. 37107287533902102798797998220837590246510135740250463769376774900097126481248969700780504170182605387432498619952474105947423330951305812372661730962991942213363574161572522430563301811072406154908250230675882075393461711719803104210475137780632466768926167069662363382013637841838368417873436172675728112879812849979408065481931592621691275889832738442742289174325203219235894228767964876702721893184745144573600130643909116721685684458871160315327670386486105843025439939619828917593665686757934951621764571418565606295021572231965867550793241933316490635246274190492910143244581382266334794475817892575867718337217661963751590579239728245598838407582035653253593990084026335689488301894586282278288018119938482628201427819413994056758715117009439035398664372827112653829987240784473053190104293586865155060062958648615320752733719591914205172558297169388870771546649911559348760353292171497005693854 ...

大整数运算 1.大整数加法 整数存储类型 范围 short（2 byte） - 215 ~ (215 - 1) int（4 byte） - 231 ~ (231 - 1) long long（8 byte） - 263 ~ (263 - 1) 使用字符串进行数字的输入 将数字拆分存储在数组中，num[0]存储数字长度，num[1]存储个位、num[2]十位、num[3]百位……以此类推==倒序存储== 按照==加法规则==将数组中对应的数字相加后存入结果数组中 对需要进位的数字进行进位 12345678910111213141516171819202122232425262728293031323334353637383940414243#include<iostream>#include<cstring>using namespace std;char s1[1005], s2[1005];//输入的两个数字存储在字符串中int num1[1005], num2[1005];//输入的两个数字转化存储在数组中int sum[1005];//数字相加后的结果存储数组int main(){ //1.使用字符串进行数字的输入 cin >> s1 >> s2; num1[0] = strlen(s1); num2[0] = strlen(s2); //2.将数字拆成一位位数字存储在数组中 for(int i = 0, j = num1[0]; s1[i]; ++i, --j){ num1[j] = s1[i] - '0'; } for(int i = 0, j = num2[0]; s2[i]; ++i, --j){ num2[j] = s2[i] - '0'; } //3.按照加法规则将数组中对应的数字相加后存入结果数组中 sum[0] = max(num1[0], num2[0]); for(int i = 1; i <= ...

斐波那契数列的递推与递归求法 斐波那契数列求法：递推（从前向后计算）、递归（从后向前计算），递归由于重复计算导致计算速度很慢——记忆化数组解决 1.递推求Fibonacci：1234567891011121314#include<iostream>using namespace std;long long num[50] = {1, 1};int main(){ for(int i = 2; i < 50; ++i ){ num[i] = num[i - 1] + num[i - 2]; } for(int i = 1; i < 50; ++i){ cout << i << " : " << num[i] << endl; } return 0;} 2.递归求Fibonacci：1234567891011121314151617#include<iostream>using namespace std;long long func(int x){ if(x == 0 || x == 1){ return 1; } return func(x - 1) + func(x - 2);}int main(){ for(int i = 1; i < 50; ++i){ cout << i << " : " << func(i) << endl; } return 0;} 注意：可以看到这里利用递归法求斐波那契数列在进行到30项时，每一项的运算时间已经达到秒级 3.递归求Fibonacci（记忆化数组优化）： 递归法中存在的大量重复计算导致递归递归太深、运算速度降低，可以使用记忆数组优化程序 定义一个记忆化数组用于存储运算过程中的中间值 当发现数字没有计算过，将数字计算一遍并将其存入数组中 当发现数字 ...

Even Fibonacci numbers Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms. 1.利用数组求fib数列 开一个足够大的数组，并初始化前两项1，2 通过递推法逐个将斐波那契数列的每一项存入数组 将所有为偶数的项的数字相加 1234567891011121314151617181920212223#include<iostream>using namespace std;long long num[4000005] = {1, 2};int main(){ long long sum = 0; int i = 2; //1.利用递推法求出斐波那契数列的每一项，并存入数组中 while(num[i - 1] <= 4000000){ num[i] = num[i - 1] + num[i - 2]; i++; } //2.对数组每一项进行判断，若为偶数将其加入sum中 for(int j = 0; j < i; j++){ if(num[j] % 2 == 0){ sum += num[j]; } } cout << sum; return 0;}//空间复杂度:O(n) 2.两个变量求fib数列 不需要定义数组，在运算的过程中就可以知道哪些项是偶数 计算过程中只保留两个数字：前一个数 和 后一个数，两个数循环相加即可 123 ...