群晖nas可以做网站,成立公司法人有什么风险,建立自己公司网站的方法,餐饮品牌设计制作目录 引言一、有序分数二、正则问题三、带分数四、约数之和 引言
本篇文章主要讲了递归的一些题型#xff0c;递归也是一种思想#xff0c;主要是在各种题中显现这种思想#xff0c;你必须要脑子里能够清楚它大概的一种路线是怎样的#xff0c;或者说要抽象出来它的功能是… 目录 引言一、有序分数二、正则问题三、带分数四、约数之和 引言
本篇文章主要讲了递归的一些题型递归也是一种思想主要是在各种题中显现这种思想你必须要脑子里能够清楚它大概的一种路线是怎样的或者说要抽象出来它的功能是干什么的看成一个模块这样写的时候才会好写并且边界条件也会清楚一些最主要还是要多练加油 一、有序分数
标签递归
思路这道题其实就是分别枚举分子和分母然后找到符合条件的最简分数最后按顺序输出即可。用两个递归或者两层 f o r for for 其实都可以因为其实时间复杂度都差不多都是 O ( N 2 ) O(N^2) O(N2) 。顺序输出用直接拿 s o r t sort sort 连带着 l a m b d a lambda lambda 表达式即可。
题目描述
给定一个整数 N请你求出所有分母小于或等于 N大小在 [0,1] 范围内的最简分数并按从小到大顺序依次输出。例如当 N5 时所有满足条件的分数按顺序依次为0/1,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,1/1输入格式共一行包含一个整数 N。输出格式
按照从小到大的顺序输出所有满足条件的分数。每个分数占一行格式为 a/b其中 a 为分子 b 为分母。数据范围
1≤N≤160
输入样例
5
输出样例
0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1示例代码1 dfs
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondint n;
vectorPII res;
unordered_setdouble sset;void dfs_up(int down)
{for(int i 0; i n; i){int up i;double t (double)up / down;if(t 1) continue;if(sset.count(t)) continue;sset.insert(t);res.push_back({up,down});}
}void dfs_down(int x)
{for(int i x; i n; i){dfs_up(i);}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n;dfs_down(1);sort(res.begin(), res.end(), [](PII a, PII b)-bool{ return ((double)a.x/a.y) ((double)b.x/b.y); });for(auto t: res) printf(%d/%d\n, t.x, t.y);return 0;
}示例代码2 两层for
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondint n;
vectorPII res;
unordered_setdouble sset;int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n;for(int i 1; i n; i){for(int j 0; j n; j){if(j i) break;double t (double)i / j;if(sset.count(t)) continue;sset.insert(t);res.push_back({j,i});}}sort(res.begin(), res.end(), [](PII a, PII b){return ((double)a.x/a.y) ((double)b.x/b.y);});for(auto t: res) printf(%d/%d\n, t.x, t.y);return 0;
}二、正则问题
标签递归
思路递归和核心就是抽象出一个功能具体就是一个函数是干什么的然后把边界处理好就行了。这题的 d f s dfs dfs 就是计算从 k k k 开始的值。如果遇到左括号就计算左括号之后的值之后遇到右括号返回中间的值如果遇到或那就计算当前的值和之后的值取一个 m a x max max 即可。
题目描述
考虑一种简单的正则表达式只由 x ( ) | 组成的正则表达式。小明想求出这个正则表达式能接受的最长字符串的长度。例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是 xxxxxx长度是6。输入格式
一个由x()|组成的正则表达式。输出格式
输出所给正则表达式能接受的最长字符串的长度。数据范围
输入长度不超过100保证合法。输入样例
((xx|xxx)x|(x|xx))xx
输出样例
6示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondint k;
string str;int dfs()
{int res 0;while(k str.size()){char t str[k];if(t (){k;res dfs();k;}else if(t |){k;res max(res,dfs());}else if(t )){break;}else{res, k;}}return res;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin str;cout dfs() endl;return 0;
}三、带分数
标签全排列、递归
思路其实我们可以看成从 1 ∼ 9 1\sim9 1∼9 中选取三个数能满足以下的式子就行了计算有多少种选法。我们可以用全排列 截取子串的方式达成目的具体细节见代码。 n a b c n a \frac{b}{c} nacb n ⋅ c a ⋅ c b n\cdot c a\cdot c b n⋅ca⋅cb
题目描述
100 可以表示为带分数的形式100369258714还可以表示为100823546197注意特征带分数中数字 1∼9分别出现且只出现一次不包含 0。类似这样的带分数100 有 11 种表示法。输入格式
一个正整数。输出格式
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。数据范围
1≤N106
输入样例1
100
输出样例1
11
输入样例2
105
输出样例2
6示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondint n;
vectorint nums {1,2,3,4,5,6,7,8,9};LL calc(int l, int r)
{LL res 0;for(int i l; i r; i) res res * 10 nums[i];return res;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n;LL res 0;do{LL a 0, b 0, c 0;for(int i 0; i 2 9; i){for(int j i 1; j 1 9; j){a calc(0,i), b calc(i1,j), c calc(j1,8);// cout a b c endl;if(c * n a * c b) res;}// exit(0);}}while(next_permutation(nums.begin(), nums.end()));cout res endl;return 0;
}四、约数之和
标签数学、递归
思路关于质数和约数的知识可以看我之前的博客 质数 、约数 我这里就不再细讲了。关于约数之和根据公式我们需要求出 a b a^b ab 的分解质因数的结果由于这个数非常的大所以直接算出结果再分解质因数是不可能的。我们可以先对 a a a 分解质因数由算数基本定理可知 N p 1 α 1 ⋅ p 2 α 2 ⋅ p 3 α 3 ⋅ ⋯ ⋅ p k α k , p i 为质数 N p_{1}^{\alpha_{1}} \cdot p_{2}^{\alpha_{2}} \cdot p_{3}^{\alpha_{3}} \cdot \cdots \cdot p_{k}^{\alpha_{k}},p_{i}为质数 Np1α1⋅p2α2⋅p3α3⋅⋯⋅pkαk,pi为质数 N b p 1 α 1 ⋅ b ⋅ p 2 α 2 ⋅ b ⋅ p 3 α 3 ⋅ b ⋅ ⋯ ⋅ p k α k ⋅ b , p i 为质数 N ^ b p_{1}^{\alpha_{1}\cdot\ b} \cdot p_{2}^{\alpha_{2}\cdot\ b} \cdot p_{3}^{\alpha_{3}\cdot\ b} \cdot \cdots \cdot p_{k}^{\alpha_{k}\cdot\ b},p_{i}为质数 Nbp1α1⋅ b⋅p2α2⋅ b⋅p3α3⋅ b⋅⋯⋅pkαk⋅ b,pi为质数 约数之和 ( p 1 0 p 1 1 ⋯ p 1 α 1 ) ⋯ ( p k 0 p k 1 ⋯ p k α k ) \text{约数之和}(p_{1}^{0}p_{1}^{1}\cdotsp_{1}^{\alpha_{1}})\cdots(p_{k}^{0}p_{k}^{1}\cdotsp_{k}^{\alpha_{k}}) 约数之和(p10p11⋯p1α1)⋯(pk0pk1⋯pkαk)所以我们只需要对 a a a 分解质因数再对该质因子的个数乘以 b b b 即可。然后就可以用公式计算了。 关于约数之和的每一项的计算使用递归计算的不然按照之前的办法 O ( N ) O(N) O(N) 是会超时的而新的计算方式是 O ( l o g N ) O(logN) O(logN) 。如果k为0那么结果为1如果k是奇数那么项数就是偶数因为指数项是从0开始的然后我们可以先算一半然后再加上这一半后移一位的结果即 s u m ( p , k / 2 ) ⋅ ( 1 q m i ( p , k / 2 1 ) ) sum(p,k/2) \cdot (1 qmi(p,k/21)) sum(p,k/2)⋅(1qmi(p,k/21)) 如果k为偶数那么项数就是奇数可以先减去最高位用偶数的公式递归去算然后再加上最高位即 s u m ( p , k − 1 ) q m i ( p , k ) sum(p,k-1) qmi(p,k) sum(p,k−1)qmi(p,k) 思路就是这样更多细节见代码。
题目描述
假设现在有两个自然数 A 和 BS 是 AB 的所有约数之和。请你求出 Smod9901 的值是多少。输入格式
在一行中输入用空格隔开的两个整数 A 和 B。输出格式
输出一个整数代表 Smod9901 的值。数据范围
0≤A,B≤5×107
输入样例
2 3
输出样例
15
注意: A 和 B 不会同时为 0。示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;const int N 5e710, MOD 9901;int a, b;
unordered_mapint,int mmap;void get_diviors(int n) // 分解质因数
{for(int i 2; i n / i; i){if(n % i 0){while(n % i 0) mmap[i], n / i;}}if(n 1) mmap[n];
}LL qmi(LL a, LL k)
{LL res 1;while(k){if(k 1) res res * a % MOD;k 1;a a * a % MOD;}return res;
}LL sum(int p, int k)
{if(k 0) return 1;else if(k % 2) return (sum(p,k/2) * (1 qmi(p,k/21)) ) % MOD;return (sum(p,k-1) qmi(p,k)) % MOD;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin a b;get_diviors(a);LL res 1;for(auto t: mmap){int p t.first, k t.second * b;res res * sum(p,k) % MOD;}if(!a) res 0;cout res endl;return 0;
}
