网站全站建设开题报告范文,南京本地网站,佛山网站关键词优化公司,贵阳网站开发多少钱文章目录 1.握手问题解题思路1#xff08;组合数学#xff09;解题思路2#xff08;暴力枚举#xff09; 2.小球反弹做题思路 3.好数算法思路#xff08;暴力解法#xff09;---不会超时 4.R格式算法思路 5.宝石组合算法思路---唯一分解定理 6.数字接龙算法思路----DFS 7… 文章目录 1.握手问题解题思路1组合数学解题思路2暴力枚举 2.小球反弹做题思路 3.好数算法思路暴力解法---不会超时 4.R格式算法思路 5.宝石组合算法思路---唯一分解定理 6.数字接龙算法思路----DFS 7.拔河算法思路 1.握手问题
题目描述
解题思路1组合数学
按照题目描述来说会议有五十人如果不加任何限制条件这五十个人两两握手的次数是 t o t a l 49 48 47 . . . . . . . . 1 total494847........1 total494847........1 利用高斯求和的得出 t o t a l 50 ∗ 49 / 2 total50*49/2 total50∗49/2 如果加上限制条件的话题目给定的其中有七个人不会相互握手需要用上面总的不加限制的减去七个人相互握手的次数。 c n t 6 5 . . . . . . 1 7 ∗ 6 / 2 cnt65......17*6/2 cnt65......17∗6/2 上述两式作差即可 编写代码
#includeiostream
using namespace std;
int main()
{int total 50 * 49 / 2;int cnt 7 * 6 / 2;cout total - cnt endl;return 0;
}解题思路2暴力枚举
将每个人握手的情况枚举出来即可。
#includeiostream
using namespace std;
int main()
{int ans 0;for (int i 1;i 50;i){for (int j i 1;j 50;j){//排除掉七人的情况if (!(i 1 i 7 j 1 j 7)){ans;}}}cout ans endl;return 0;
}2.小球反弹
问题描述
做题思路
这道题我们肯定不能直接做的这道题给定了 d x : d y dx:dy dx:dy的值说明这道题我们应该分解来做将小球的反弹的路径分解为x方向和y方向来做。 我们首先假设x方向上经过了p个来回y方向上经历了q个来回因为是分解的缘故所以两个分解方向上的时间是相同的。 所以可以得出两个等式 d x ∗ t 2 p x dx*t2px dx∗t2px由于这里一半的路程是x所以一个来回的路程是2x乘以来回就是总路程 d y ∗ t 2 q x dy*t2qx dy∗t2qx
将这两个式子进行比例 d x d y p x q y \frac{dx}{dy}\frac{px}{qy} dydxqypx 得到这个式子之后我们可以利用gcd对这个式子的左边进行约分。 可以得出 p d x ∗ y pdx*y pdx∗y和 q d y ∗ x qdy*x qdy∗x 算出q或者p之后可以利用公式计算t t 2 p x / d x t2px/dx t2px/dx 最后得出总路程 总路程 t ∗ ( s q r t ( 1 5 2 1 7 2 ) ) 总路程t*(sqrt(15^217^2)) 总路程t∗(sqrt(152172))
编写代码
//求最大公约数
int gcd(int a, int b)
{return b 0 ? a : gcd(b, a % b);
}
int main()
{//给出x方向和y方向的速度 int dx 15, dy 17;//给出x方向和y方向上的距离int x 343720, y 233333;//求出多少来回int q dy * x, p dx * y;//求最大公约数int g gcd(p, q);p / g, q / g;//计算时间int t 2 * p * x / dx;//求路程double ans t * sqrt(15 * 15 17 * 17);printf(%.2lf\n, ans);return 0;
}3.好数
问题描述
数据量
算法思路暴力解法—不会超时
遍历1到n的数然后写一个check函数判断每个数是否是好数这里的时间复杂度是 n ∗ l o g n n*logn n∗logn 编写代码
#include iostream
using namespace std;
int N,count;bool Check(int n)
{int i1;while(n!0){int tailn%10;if(i%21){if(tail%2!1)return false;}else{if(tail%2!0)return false;}i;n/10;}return true;
}int main()
{// 请在此输入您的代码cinN;for(int i1;iN;i){if(Check(i)){count;}}coutcountendl;return 0;
}4.R格式
题目描述
数据量
可以看到这道题的数据量是很大的涉及到了幂次肯定不可能直接去算这道题很显然是考察的是高精度算法高精度*低精度
算法思路
高精度模版题
编写代码
#includeiostream
#includealgorithm
#includestring
#includecmath
using namespace std;//数组模拟高精度高精度*低精度
const int N 2e3 10;
string s;
int a[N];
int main()
{int n;cin n s;//反转操作reverse(s.begin(), s.end());//确定小数点的位置int pos s.find(.);s.erase(pos, 1);//删除小数点方便后续计算int len s.size();for (int i 0;i len;i) a[i 1] s[i] - 0;//高精度*低精度for (int i 1;i n;i){//顺序扫描均*2for (int j 1;j len;j) a[j] * 2;//处理大于10的位数for (int j 1;j len;j){if (a[j] 10){a[j 1];a[j] % 10;if (j len) len;}}}//处理小数点后的第一位进行四舍五入if (a[pos] 5)a[pos 1];for (int i pos 1;i len;i){if (a[i] 10){a[i 1];a[i] % 10;if (i len)len;}}//打印的时候倒序打印for (int i len;i pos 1;i--) cout a[i];return 0;
}5.宝石组合
题目描述 数据范围
首先从数据量来看这道题是不能用暴力枚举的因为暴力枚举三个数的时间复杂度是 O ( N 3 ) O(N^3) O(N3)了。
算法思路—唯一分解定理
首先我们要知道什么是唯一分解定理简单来说唯一分解定理就是任意一个大于1的正整数 都可以唯一地表示为若干个质数的乘积且这些质数的顺序不影响分解的唯一性。 那么可以得出 N 1 p 1 a 1 ⋅ p 2 a 2 ⋅ … ⋅ p n a n N_1 p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_n^{a_n} N1p1a1⋅p2a2⋅…⋅pnan N 2 p 1 b 1 ⋅ p 2 b 2 ⋅ … ⋅ p n b n N_2 p_1^{b_1} \cdot p_2^{b_2} \cdot \ldots \cdot p_n^{b_n} N2p1b1⋅p2b2⋅…⋅pnbn
从上面两个式子可以得出 gcd ( N 1 , N 2 ) p 1 min ( a 1 , b 1 ) ⋅ p 2 min ( a 2 , b 2 ) ⋅ … ⋅ p n min ( a n , b n ) \gcd(N_1,N_2) p_1^{\min(a_1,b_1)} \cdot p_2^{\min(a_2,b_2)} \cdot \ldots \cdot p_n^{\min(a_n,b_n)} gcd(N1,N2)p1min(a1,b1)⋅p2min(a2,b2)⋅…⋅pnmin(an,bn) lcm ( N 1 , N 2 ) p 1 max ( a 1 , b 1 ) ⋅ p 2 max ( a 2 , b 2 ) ⋅ … ⋅ p n max ( a n , b n ) \operatorname{lcm}(N_1,N_2) p_1^{\max(a_1,b_1)} \cdot p_2^{\max(a_2,b_2)} \cdot \ldots \cdot p_n^{\max(a_n,b_n)} lcm(N1,N2)p1max(a1,b1)⋅p2max(a2,b2)⋅…⋅pnmax(an,bn)
假设HaHbHc的分解出来的相同的质数的幂次分别是xyz那么可以得出 上面的式子可以转换为幂次是 x y z max ( x , y , z ) − max ( x , y ) − max ( x , z ) − max ( y , z ) xyz\max(x,y,z)-\max(x,y)-\max(x,z)-\max(y,z) xyzmax(x,y,z)−max(x,y)−max(x,z)−max(y,z) 相当于我们只需要求出上面式子的最大值即可。
编写代码
#includeiostream
#includevector
#includealgorithm
using namespace std;
const int N 1e5 10;
int a[N];
//fac是存储因子的二维数组s是求的最大值
vectorint fac[N], s[N];
int main()
{//遍历数组for (int i 1;i 1e5;i){for (int j i;j 1e5;j i){//i是j的因子fac[j].push_back(i);}}//输入n个数int n;cin n;for (int i 1;i n;i)cin a[i];//保证字典序最小sort(a 1, a n 1);for (int i 1;i n;i){//处理i的每个因子for (int j 0;j fac[a[i]].size();j){//s[fac[a[i]][j]].push_back(a[i]);}}for (int i 1e5;i 0;i--){if (s[i].size() 3){cout s[i][0] s[i][1] s[i][2] endl;break;}}return 0;
}6.数字接龙
问题描述 数据量 根据数据量来看这道题考察的应该是DFS但是在DFS中应该还涉及到回溯因为当走到不满足条件的时候需要进行回溯。
算法思路----DFS
编写代码
#includeiostream
#includestring
using namespace std;
const int N 20;
int a[N][N];
bool vis[N][N];
int n, k;
//方向数组 0 1 2 3 4 5 6 7
int dx[8] { -1,-1,0,1,1,1,0,-1 };
int dy[8] { 0,1,1,1,0,-1,-1,-1 };
string res;void dfs(int x, int y, int prev, string s, int dep)
{//当搜到终点的时候且搜索深度是n的时候意思就是每种情况都搜索完了if (x n y n dep n * n) {if (res.empty())res s;return;}for (int i 0;i 8;i){//生成邻接点int bx x dx[i];int by y dy[i];//过滤越界节点if (bx1 || bxn || by1 || byn)continue;//过滤访问过的节点if (vis[bx][by] true)continue;//防止交叉搜索if (i 1 vis[x - 1][y] vis[x][y 1])continue;if (i 3 vis[x 1][y] vis[x][y 1])continue;if (i 5 vis[x 1][y] vis[x][y - 1])continue;if (i 7 vis[x - 1][y] vis[x][y - 1])continue;//保证路径数值为0 1 2 3 .....k-1if ((a[bx][by] k a[bx][by] prev 1) || (prev 1 k a[bx][by] 0)){//可以搜索将点标记为truevis[bx][by] true;dfs(bx, by, a[bx][by], s to_string(i), dep 1);//最优性剪枝if (!res.empty())return;vis[bx][by] false;//回溯}}
}int main()
{cin n k;for (int i 1;i n;i)for (int j 1;j n;j)cin a[i][j];string emp;//标记起点vis[1][1] true;dfs(1, 1, 0, emp, 1);if (res.empty())cout -1;else cout res endl;return 0;
}7.拔河
问题描述 数据量 对于这种涉及到区间和的题来说大概率都是用前缀和算法解决
算法思路
编写代码
#includeiostream
#includeset
#includeclimits
using namespace std;#define ll long longconst int N 1e3 10;
int a[N], s[N];//前缀和和数组
multisetint ms;int main()
{int n;cin n;for (int i 1;i n;i){cin a[i];//前缀和s[i] s[i - 1] a[i];}//用set去维护所有的区间和for (int i 1;i n;i){for (int j 1;j n;j){//维护区间和ms.insert(s[j] - s[i - 1]);}}int ans LONG_MAX;for (int i 1;i n;i){for (int j 1;j i;j){//枚举以i结尾的区间因为这里i-1只会有一个人所以应该是j-1int sum s[i] - s[j - 1];//找到与该区间和sum相似的区间和auto it ms.lower_bound(sum);if (it ! ms.end()){ans min(ans, abs(*it - sum));}if (it ! ms.begin()){it--;ans min(ans, abs(*it - sum));}}//删除以i开头且以j结尾的区间防止后续查询区间的时候出现区间重叠/交叉问题for (int j i;j n;j) ms.erase(ms.find(s[j] - s[i - 1]));}cout ans endl;return 0;
}
