广东营销网站建设服务,南部县建设局网站,加工平台英语,wordpress 制作论坛目录
1、有序分数#xff08;usaco training 2.1#xff09;
2、正则问题#xff08;第八届蓝桥杯省赛C A组 Java A组#xff09;
3、带分数#xff08;第四届蓝桥杯省赛Java A组/B组 C B组/C组#xff09;
4、约数之和#xff08;《算法竞赛进阶指南》…目录
1、有序分数usaco training 2.1
2、正则问题第八届蓝桥杯省赛C A组 Java A组
3、带分数第四届蓝桥杯省赛Java A组/B组 C B组/C组
4、约数之和《算法竞赛进阶指南》
5、分形之城《算法竞赛进阶指南》 1、有序分数usaco training 2.1
给定一个整数 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
思路
用一个pair对来维护最小值和对应的分子分母将所有情况枚举为了避免重复我们要用一个set来确保没有重复的数值
这里要注意进入递归函数要直接进入最里面的一层开始往上递归这样就可以做到所有分数的都是最简分数式
代码
#includebits/stdc.husing namespace std;int n;typedef pairint,int PII;typedef pairdouble,PII PDP;const int N1e5;vectorPDPres;unordered_setdoublecnt;void work(int n)
{if(n0)return ;work(n-1);for(int in-1;i0;i--){double number(double)i/n;if(cnt.find(number)!cnt.end())continue;cnt.insert(number);PII t{i,n};res.push_back({number,t});}}bool cmp(PDP a,PDP b)
{return a.firstb.first;
}int main()
{cinn;res.push_back({0,{0,1}});res.push_back({1,{1,1}});work(n);sort(res.begin(),res.end(),cmp);for(auto t:res){coutt.second.first/t.second.secondendl;}return 0;
}
2、正则问题第八届蓝桥杯省赛C A组 Java A组
考虑一种简单的正则表达式
只由 x ( ) | 组成的正则表达式。
小明想求出这个正则表达式能接受的最长字符串的长度。
例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是 xxxxxx长度是6。
输入格式
一个由x()|组成的正则表达式。
输出格式
输出所给正则表达式能接受的最长字符串的长度。
数据范围
输入长度不超过100保证合法。
输入样例
((xx|xxx)x|(x|xx))xx 输出样例
6
思路
递归回溯
代码
#includebits/stdc.husing namespace std;int k0;string s; //((xx|xxx)x|(x|xx))xx
//6
int dfs()
{int res0;while(ks.size()){if(s[k](){k;resdfs();k;}else if(s[k])){break;}else if(s[k]|){k;resmax(res,dfs());}else{k;res;}}return res;
}int main()
{cins;int resdfs();coutres;return 0;
}
3、带分数第四届蓝桥杯省赛Java A组/B组 C B组/C组
100可以表示为带分数的形式100369258/714
还可以表示为100823546/197
注意特征带分数中数字 1∼9分别出现且只出现一次不包含 0。
类似这样的带分数100 有 11种表示法。
输入格式
一个正整数。
输出格式
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。
数据范围
1≤N1e6
输入样例1
100输出样例1
11输入样例2
105输出样例2
6
思路
由于c的/并不准确我们把除法转化为乘法再进行枚举nab/c转化为ncacb
从而我们枚举出a和c就可以算出bbnc-ac;
用had_use记录用过的数ever用来在不影响并行递归的情况下把当前情况递归下去(不破坏原来的记录)
代码
#includebits/stdc.husing namespace std;const int N600;//typedef long long LL;int ever[N],had_use[N];
//数组放在最上面acwing平台由于放在了ans下面导致输出结果错误 int ans0;int n;//nab/c
//ncacb
//bnc-ac 只要推出来的b满足条件a和c都满足条件则答案1
bool check(int a,int c)
{int bn*c-a*c;if(!a || !c || !b)return false;memcpy(ever,had_use,sizeof had_use);//基于现有的情况下不破坏原来的数组//那就拷贝一份既能在原来之上操作又能不破坏原来的记录 while(b)//取出每一位用来更新用过的数字 {int tb%10;b/10;if(!t || ever[t])return false;ever[t]1;}for(int i1;i9;i)if(!ever[i])return false;return true;
}void dfs_c(int x,int a,int c)
{if(x10)return ;if(check(a,c))ans;for(int i1;i9;i){if(!had_use[i]){had_use[i]1;dfs_c(x1,a,c*10i);had_use[i]0;//回溯避免下次的递归中出现错误 }}
}void dfs_a(int x,int a)
{if(an)return;if(a)dfs_c(x,a,0);//如果a满足条件那么枚举c然后判断是否是成立的//0是c的大小 for(int i1;i9;i)//枚举一下当前能用哪些数字{if(!had_use[i]){had_use[i]1;dfs_a(x1,a*10i);had_use[i]0;//恢复现场回溯一下 } }
}int main()
{ //cout714*97;cinn;dfs_a(0,0);//第一个表示当前用了多少个数字第二个参数表示当前的a是多少 coutans;return 0;
}
4、约数之和《算法竞赛进阶指南》
假设现在有两个自然数 A 和 BS 是A的B次方的所有约数之和。
请你求出 S mod9901 的值是多少。
输入格式
在一行中输入用空格隔开的两个整数 A 和 B。
输出格式
输出一个整数代表 Smod9901 的值。
数据范围
0≤A,B≤5×1e7
输入样例
2 3输出样例
15注意: A 和 B不会同时为 0。
思路
分解质因数把每个质因数的从第0项到最高次数的和乘起来就是约数之和
由于是求A的B次方的约数之和我们可以先把A分解质因数次方B可以后来再给到质因数的次方上 代码
#includebits/stdc.husing namespace std;const int MOD9901;typedef long long LL;LL a,b;
LL res0;unordered_mapint,intprimes;LL quickmi(LL a,LL b)
{LL res1;while(b){if(b1)resres*a%MOD;aa*a%MOD;bb1;}return res%MOD;
}void divide(LL x)
{for(int i2;ix/i;i){if(x%i0){while(x%i0){primes[i];x/i;}}}if(x1)primes[x];
}//求p0....pk-1
LL sum(LL p,LL k)
{if(k1)return 1;if(k%20)return (LL)(quickmi(p,k/2)1)*sum(p,k/2)%MOD;return (LL)(quickmi(p,k-1)sum(p,k-1))%MOD;
}int main()
{cinab;divide(a);LL res1;for(auto prime :primes){int pprime.first;int kprime.second*b;//p的次数 res(LL)res*sum(p,k1)%MOD;//求约数之和 }if(!a)res0;coutresendl; return 0;
}
5、分形之城《算法竞赛进阶指南》
城市的规划在城市建设中是个大问题。
不幸的是很多城市在开始建设的时候并没有很好的规划城市规模扩大之后规划不合理的问题就开始显现。
而这座名为 Fractal 的城市设想了这样的一个规划方案如下图所示 当城区规模扩大之后Fractal 的解决方案是把和原来城区结构一样的区域按照图中的方式建设在城市周围提升城市的等级。
对于任意等级的城市我们把正方形街区从左上角开始按照道路标号。
虽然这个方案很烂Fractal 规划部门的人员还是想知道如果城市发展到了等级 N编号为 A 和 B 的两个街区的直线距离是多少。
街区的距离指的是街区的中心点之间的距离每个街区都是边长为 10 米的正方形。
输入格式
第一行输入正整数 n表示测试数据的数目。
以下 n 行输入 n 组测试数据每组一行。
每组数据包括三个整数 N,A,B表示城市等级以及两个街区的编号整数之间用空格隔开。
输出格式
一共输出 n 行数据每行对应一组测试数据的输出结果结果四舍五入到整数。
数据范围
1≤N≤31 1≤A,B≤2**2N 1≤n≤1000
输入样例
3
1 1 2
2 16 1
3 4 33 输出样例
10
30
50
思路
我们要知道第n等级城市的信息就要知道n-1等级的n-1等级的城市可以通过旋转变换得出n等级城市的坐标信息递归下去最后算出街区中心坐标然后进行勾股定理即可注意要乘上单位长度本代码为5
代码
#includebits/stdc.htypedef long long LL;using namespace std;typedef pairLL,LL PLL;#define x first#define y secondPLL calc(LL n,LL m)
{//n代表城市等级 //m代表坐标从0开始计数 if(n0)return {0,0};LL len 1ll (n-1);//本等级内象限的边长/2 LL cnt1ll(2*n-2);//上一等级的容量PLL pos calc(n - 1, m % cnt); // 上一等级的坐标信息 LL xpos.x,ypos.y;int zm/cnt;//处于哪个象限 if (z 0)return { - y - len, - x len };// 右上象限更换原点xlen,ylenelse if (z 1)return { x len, y len };// 右下象限更换原点xlen,y-lenelse if (z 2)return { x len, y - len };// 左下象限逆转90°-y,x沿y对称y,x更换原点y-len,x-lenreturn { y - len, x - len };
}int main()
{int N;cin N;while (N --){LL n, m1, m2;cin n m1 m2;PLL pos1 calc(n, m1 - 1);PLL pos2 calc(n, m2 - 1);double x (double) (pos1.first - pos2.first);double y (double) (pos1.second - pos2.second);//单位长度要乘五printf(%.0lf\n, sqrt(x * x y * y) * 5);}return 0;
}
