A：讨厌的数字

知识点：枚举

思路：枚举所用的钱数从n开始，逐个枚举，直到所用钱数中没有包含讨厌的数字为止。至于如何判断所用钱数中有没有包含讨厌的数字，我们先看各位数字，如果可以，除以10，继续看，直到这个数小于等于0或者找到讨厌的数字为止为止。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,k,x,a[10]; 
bool pd(int x){
    while(x){
        if(a[x%10])return 0;
        x/=10;
    }
    return 1;
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=k;i++){
        cin>>x;
        a[x]++;
    }
    for(int i=n;;i++){
        if(pd(i)){
            cout<<i;
            return 0;
        }
    } 
    return 0;
}

B：比大小Plus

知识点：高精度

思路：先找到两个数第一个不是0的位置，然后比较长度，长度一致时，比较字典顺序即可。

参考代码：

#include <bits/stdc++.h>
using namespace std;
string a, b;
int aL, aLen;
int bL, bLen;
int main()
{
    cin >> a >> b;
    aL = 0;
    while (aL < (int)a.size() - 1 && a[aL] == '0')
        aL++;
    bL = 0;
    while (bL < (int)b.size() - 1 && b[bL] == '0')
        bL++;
    aLen = (int)a.size() - aL + 1;
    bLen = (int)b.size() - bL + 1;
    if (aLen > bLen)
    {
        cout << "first";
        return 0;
    }
    if (bLen > aLen)
    {
        cout << "second";
        return 0;
    }
    for (int i = aL, j = bL; i < a.size(); i++, j++)
    {
        if (a[i] > b[j])
        {
            cout << "first";
            return 0;
        }
        if (b[j] > a[i])
        {
            cout << "second";
            return 0;
        }
    }
    cout << "same";
    return 0;
}

C：让字符串成为回文串的最少插入次数

知识点：搜索、记忆化、剪枝、动态规划

思路：回文串的定义是从两端开始，都朝内走的过程中，左右左右两侧的对应字符都相等，那么就是回文串，那么我们可以从两端思考，如果左侧的索引为i,右侧的索引为j，那么问题就是求s[i..j]变为回文串需要的最少修改次数。

如果s[i]=s[j],我们可以贪心的直接给他匹配了，因为如果这里不选择匹配，选择插入一个，那么选择范围小了的情况下更不可能匹配，无法得到最小，不如直接匹配了。那么问题就变为了子问题:求s[i+1...j−1]的最少修改次数。

如果s[i]!=s[j]，那么需要插入字符。在哪一侧插入字符呢？都试试就可以了，如果我们选择在左侧插入字符，就会变为子问题s[i..j−1]，如果我们选择在右侧插入字符，那么也会变为子问题s[i+1...j] 。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int dp[555][555];
string s; 
int dfs(string s,int l,int r){
    if(dp[l][r]) return dp[l][r];
    if(l==r) return 0;
    if(l+1==r) return s[l]==s[r]?0:1;
    if(s[l]==s[r]) return dfs(s,l+1,r-1);
    dp[l][r]=min(dfs(s,l+1,r),dfs(s,l,r-1))+1;
    return  dp[l][r];
} 
int main(){
    cin>>s;
    cout<<dfs(s,0,s.size()-1); 
    return 0;
}

D：廊桥分配

知识点：贪心、优先队列

思路：给每个廊桥都编上号，每次飞机入站都选择空闲的廊桥中编号最小的哪一个。

用一个优先队列来维护廊桥编号，一开始将所有廊桥入队。

对于每一架飞机可以用一个 pair 分别存储飞机出站的时间以及停靠的廊桥的编号。

用优先队列来维护 pair。

每次飞机入站时先比较有没有应该出站的飞机，如果有就把他们从队列中弹出，并把对应的廊桥编号再加入优先队列中。

然后飞机选择编号最小的廊桥停靠。并把对应的廊桥的 数量 加一。

这样就能快速的统计出每个廊桥产生的贡献，再把所有编号比它小的廊桥产生的贡献加起来，用前缀和数组来维护。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
const int N=100010;
int n,m1,m2,ans1[N],ans2[N],ans;
struct node{
    int arrive,leave;
    bool operator<(const node&b)const{
        return arrive<b.arrive;
    }
}p1[N],p2[N];
void fun(node p[],int m,int ans[]){
    priority_queue<PII,vector<PII>,greater<PII> > usedQ;
    priority_queue<int,vector<int>,greater<int> > freeQ;
    for(int i=1;i<=n;i++)freeQ.push(i);
    for(int i=1;i<=m;i++){
        while(!usedQ.empty()&&p[i].arrive>=usedQ.top().first){
            freeQ.push(usedQ.top().second);
            usedQ.pop();
        }
        if(!freeQ.empty()){
            usedQ.push({p[i].leave,freeQ.top()});
            ans[freeQ.top()]++;
            freeQ.pop();
        }
    }
    for(int i=1;i<=n;i++)ans[i]+=ans[i-1];
}
signed main(){
    scanf("%lld%lld%lld",&n,&m1,&m2);
    for(int i=1;i<=m1;i++)
        scanf("%lld%lld",&p1[i].arrive,&p1[i].leave);
    sort(p1+1,p1+1+m1); fun(p1,m1,ans1);
    for(int i=1;i<=m2;i++)
        scanf("%lld%lld",&p2[i].arrive,&p2[i].leave);
    sort(p2+1,p2+1+m2); fun(p2,m2,ans2);
    for(int i=0;i<=n;i++){
        ans=max(ans,ans1[i]+ans2[n-i]);
    }printf("%lld",ans);
    return 0;
}