4.12深搜题解

明明是学深搜的一周，结果这里一道深搜的题解也没有~~

一、洛谷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

题解：

这个题的解答步骤分为两步：

1. 字符串处理
2. 贪心选择最大的数（不能用深搜，深搜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;
}