等比数列三角形题解 实现思路 代码实现 /* * @Description: 电影和人生不一样，电影太仁慈了，人生太辛苦了 * @CSDN: https://blog.csdn.net/godhandsjoker?spm=1000.2115.3001.5343 * @Github: https://github.com/godhandsjoker * @QQ: 3124406837 * @Author: godhands * @LastEditTime: 2022-04-28 10:42:09 */ #include <bits/stdc++.h> using ...

植树造林 思路： 求有几棵树满足到所有树的距离最小等于求这排树有几个中位数，奇数棵树有1个中位数，偶数则为2个. 代码实现 代码： #include <bits/stdc++.h> using namespace std; int main() { int n; cin>>n; if(n % 2 == 0) cout<<"2"<<endl; else cout<<"1"<<endl; return 0; }

了断局 题目大意： 该数列为Tribonacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) for n >= 3 with a(0) = a(1) = 0 and a(2) = 1. 代码实现： 预处理前100项数存入long long数组里. 代码： #include <bits/stdc++.h> using namespace std; const int N = 1e2+10; long long s[N]; int main() { int n; s[1] = 0; s[2] = 1; s[3]...

题目名称 华华和月月逛公园 题目大意 给定n个点，m条边，找出其中非割边的数量，即m-割边数量 实现思路 求割边数量，直接Tarjan算法板子即可。 《算法竞赛进阶指南》P397 代码实现 #include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f const double eps=1e-8; const int maxn=1e5+7; const int SIZE = 1e6; int head[SIZE], ver[SIZE * 2], Next[SIZE * 2]; int dfn[SIZE], l...

题目名称 Rinne Loves Study 题目大意 n*m的格子，给T个操作，(1) ”1 x“ : 将第x行标记为i，(2) “2 y”将第y列标记为i，其中i为第几个操作 问最终每个格子的标记为多少，输出n*m的矩阵的标记 实现思路 第一种操作，就row[x]=i, 第二种操作，就col[y]=i, 输出时，row[x]和col[y]谁最大谁就是该格子最终标记 代码实现 #include<bits/stdc++.h> using namespace std; #define ll long long int n,m; const int maxn=1e5+7; c...

题目名称 小A的数学题 题目大意 给定n、m,求 ∑i=1n∑j=1mgcd(i,j)2\sum_{i=1}^n\sum_{j=1}^mgcd(i,j)^2∑i=1n​∑j=1m​gcd(i,j)2 实现思路 容斥原理： 易知gcd(i,j)范围是1~min(n,m),因此枚举gcd即可 求出每个gcd的数目cnt[] 答案为：ans+=gcd*gcd*cnt[gcd] gcd=i时，i的数目为(n/i)*(m/i),但是i的倍数也被包含了，因此可减去cnt[i*2]...cnt[i*k],其中i*k<=min(n,m) i*(k+1)>min(n,m);减去后得到的值为最终i的...

题目大意： 给一个数，求和墙能围成的最大面积 思路： 如图所示，半圆是最大的，直接计算求解 代码实现： #include <iomanip> #include "iostream" #include "math.h" using namespace std; const double PI = acos(-1); int main(){ int n; cin >> n; double r = (double )n / (PI); double ans = (PI * r * r) / 2; cout << set...

题目大意： 给一个n x n 的矩阵，求从1,1到n,n有多少中不同的点权和。每次只能向下或右走一步 思路： dfs的板子题 代码实现 #include "iostream" #include "map" using namespace std; int a[20][20], b[20][20]; map<int, bool> num; int n; int sum = 0; pair<int, int> q[50 * 50], dir[2] = {{1, 0}, {0, 1} }; void dfs(int i, int j){ if(i == n){ ...

题目大意： 一条线上有n个高度不同的位置，m个询问（ai)，求水位为ai时海岛有多少块 思路： 直接模拟题目要求即可 代码实现 #include "iostream" using namespace std; const int N = 1e3 + 10; int h[N], a[N]; int main(){ int n, m; cin >> n >> m; for(int i = 1; i <= n; i ++){ cin >> h[i]; } for(int i = 1; i <...

题目大意： 给了一个又要求的三角形，三角形一共有 n 层，其中第 i 层共有 i个数，且第 1 个数和第 i 个数均为 i 。其余的数中，第 j 个数是上一层中第 j−1 个数和第 j 个数的和。有m次询问，求第 x 层到第 y 层所有数的和。 思路： 根据题目要求先递推三角形， 然后用前缀和处理 代码实现： #include "iostream" using namespace std; const int N = 1e3 + 10; const int mod = 1e9 + 7; int a[N][N]; long long sum[N]; int main(){ int n...

题目大意： 电梯上升或者下降都需要1S， 给了n个人的楼层和自己的楼层，找到自己需要等待的时间 思路： 直接找到n个人楼层的最大值就行 代码实现； #include "iostream" #include "vector" using namespace std; int main(){ int n, k; cin >> n >> k; int ans = 0; int x; for(int i = 0; i < n; i ++){ cin >> x; ans = max(an...

题目大意： 找出n天中m个安排后1~n中没有安排的天数的最大连续值 思路： 类似于区间合并，不过不用合并这个步骤，只用上个区间的r 和下个区间的l维护ans就行 代码实现： #include "iostream" #include "vector" #include "algorithm" using namespace std; const int N = 1e5 + 10; typedef pair<int, int> PII; vector<PII> a; int main(){ int n, m; cin >> n >&gt...

题目描述 首先给定了我们一个矩阵的个数n，然后接下来就是给我们n个矩阵，对于我们的每一个矩阵会给我们一个行数和列数，然后我们再给我们一个矩阵的运算法则，我们就是可以进行计算，我们对于矩阵的计算是这样解释的 我们矩阵的运算次数等于我们a∗b==a.x∗a.y∗b.xa * b == a.x * a.y * b.xa∗b==a.x∗a.y∗b.x，然后我们的新的矩阵的行和列分别就是a.xa.xa.x和b.yb.yb.y，然后要记住的就是我们的矩阵是没有交换律的 题解 解法一：栈 实现思路 我们可以考虑这么一个问题，我们先把我们的矩阵存储下来，然后我们可以每次遇到左括号什么也不考虑，如果我们遇到了右...

题目描述 首先我们有两个字符串，第一个字符串是我们的s1s1s1这个里面是含有我们的匹配符号的，然后第二个字符串是我们的s2s2s2这个里面是没有匹配符号的，我们需要判断我们的s1s1s1是否可以正好匹配s2s2s2 规则如下： 如果是*号我们可以匹配0，1，多个字符 如果是？号我们只可以匹配一个字符 我们*和？匹配的只能是字母或者是数字 匹配时不区分大小写 题解 解法一：还是取巧的做法 实现思路 事实上这个题目，我们完全可以用正则表达式给过掉，首先我们可以先把我们的两个字符串都变成小写，然后分别对应我们的一个匹配规则，然后最后查看是否可以完全匹配即可 代码实现 from re impor...