明明是学深搜的一周,结果这里一道深搜的题解也没有~~
一、洛谷P1082同余方程
题目描述
求关于x xx的同余方程 ax≡1(mod b) 的最小正整数解。
输入格式
一行,包含两个正整数 a,b 用一个空格隔开。
输出格式
一个正整数 x0,即最小正整数解。输入数据保证一定有解。
输入输出样例
输入 #1
3 10
输出 #1
7
说明/提示
【数据范围】
对于 40%的数据,2≤b≤1,000
对于 60%的数据,2≤b≤50,000,000
对于 100%的数据,2≤a,b≤2,000,000,000
NOIP 2012 提高组 第二天 第一题
解析:
ax≡1(mod b)
可以化为ax+by=gcd(a,b)
,而ax+by=gcd(a,b)
的求解是依赖于拓展欧几里得算法实现的,所以这个题实际上就是在考拓展欧几里得算法,那么,拓展欧几里得算法是什么呢?
我们先来看看欧几里得算法:
欧几里得算法,又称为辗转相除法,是利用gcd(a,b) = gcd(b,a % b)
这个原理来计算两个数的最大公因子的算法,代码如下:
/*
* @Author: Mr.Sen
* @LastEditTime: 2020-04-16 20:03:11
* @Website1: https://449293786.site
* @Website2: https://sluowanx.cn
* @原创代码,版权所有,转载请注明原作者
* >> 欧几里得算法 <<
*/
int gcd(int a,int b)
{
while( b> 0)
{
int tmp = a % b;
a = b;
b = tmp;
}
return a;
}
而拓展欧几里得算法就是在欧几里得算法上做了一些修改,以用来计算ax+by=gcd(a,b)
的结果
/*
* @Author: Mr.Sen
* @LastEditTime: 2020-04-16 20:03:11
* @Website1: https://449293786.site
* @Website2: https://sluowanx.cn
* @原创代码,版权所有,转载请注明原作者
*/
#include <bits/stdc++.h>
typedef long long ll;
ll gcd(ll a,ll b,ll &x,ll &y){
if(!b)
{
x=1;y=0;
return a;
}
ll t=gcd(b,a%b,y,x);
y-=a/b*x;
return t;
}
int main()
{
ll a,b,x,y;
cin>>a>>b;
gcd(a,b,x,y);
cout<<x<<endl;
// cout<<gcd(a,b)<<endl;
// 拓展欧几里得算法同样可以用来求最大公因子
return 0;
}
emmm ,如果觉得cpp代码不好理解,这里还有一份Python代码:
'''
@Author: Mr.Sen
@Website1: https://449293786.site
@原创代码,版权所有,转载请注明原作者
'''
def ext_euclid(a, b):
if b == 0:
return 1, 0, a
else:
x, y, q = ext_euclid(b, a % b)
x, y = y, (x - (a // b) * y)
return x, y, q
但是上面的代码是过不了的,因为题目要求的是最小正整数,所以我们再后面加b/gcd(a,b)
直到变成正整数为止
剩下的大概就看一下这里吧:https://www.cnblogs.com/Mr-WolframsMgcBox/p/7868283.html
反正我也没学拓展欧几里得算法,现学现卖
二、洛谷P1323删数问题
题目描述
一个集合有如下元素:111 是集合元素;若 PPP 是集合的元素,则 2×P+1,4×P+5也是集合的元素。
取出此集合中最小的 k 个元素,按从小到大的顺序组合成一个多位数,现要求从中删除 m 个数位上的数字,使得剩下的数字最大,编程输出删除前和删除后的多位数字。
注:不存在所有数被删除的情况。
输入格式
只有一行两个整数,分别代表 k 和 m。
输出格式
输出为两行两个整数,第一行为删除前的数字,第二行为删除后的数字。
输入输出样例
输入 #1
5 4
输出 #1
137915
95
说明/提示
数据规模与约定
- 对于 30% 的数据,保证 1≤k,m≤3001
- 对于 100% 的数据,保证 1≤k,m≤3e4
题解:
这个题的解答步骤分为两步:
- 字符串处理
- 贪心选择最大的数(不能用深搜,深搜100亿%超时)
/*
* @Author: Mr.Sen
* @LastEditTime: 2020-04-16 22:45:06
* @Website: https://449293786.site
* @原创代码,版权所有,转载请注明原作者
*/
#include <bits/stdc++.h>
using namespace std;
priority_queue <int,vector<int>,greater<int> > q;
queue <int> wait;
string str(int k)
{
string ans;
q.push(1);
while (k--)
{
//利用优先队列排序
int now=q.top();
q.push(now*2+1);
q.push(now*4+5);
wait.push(now);
q.pop();
}
while(!wait.empty())
{
//将数字转换成字符串
stringstream ss;
ss<<wait.front();
ans+=ss.str();
wait.pop();
}
return ans;
}
int main()
{
int m,k;
cin>>k>>m;
string s=str(k);
cout<<s<<endl;
//贪心
string::iterator it =s.begin();s.insert(it,'9');
int r=0;
int n=s.size();
int sum=0;
int h=1;
while(h<=n&&sum!=m){
if(s[h]<=s[r]){
s[++r]=s[h++];
}
else
r--,sum++;
}
while(h<=n) s[++r]=s[h++];
for(int i=1;i<n-m;i++) cout<<s[i];
cout<<endl;
return 0;
}
出处:https://grimoire.cn/acm/412-dfs.html
版权:本文《4.12深搜题解》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任