第十四届蓝桥杯C++B组

冶炼金属

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int n;

bool check1(int mid){
    for(int i=0;i<n;i++)
        if(a[i]/mid>b[i])
            return false;
    return true;
}

bool check2(int mid){
    for(int i=0;i<n;i++)
        if(a[i]/mid<b[i])
            return false;
    return true;
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d%d",&a[i],&b[i]);
    }
    
    int l=1,r=1e9;
    while(l<r){
        int mid=l+r>>1;
        if(check1(mid))r=mid;
        else l=mid+1;
    }
    cout<<l<<" ";
    
    r=1e9;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check2(mid))l=mid;
        else r=mid-1;
    }
    
    cout<<l<<" ";
    
    return 0;
}

飞机降落

#include<iostream>
#include <cstring>
#include<algorithm>
using namespace std;
const int N=11;
struct Plane{
    int t,d,l;
}p[N];
bool st[N];
int t,n;

bool dfs(int u,int last){
    if(u==n) return true;
    
    for(int i=0;i<n;i++){
        int t=p[i].t,d=p[i].d,l=p[i].l;
        if(!st[i]&& t+d>=last){
            st[i]=true;
            if(dfs(u+1,max(t,last)+l))return true;
            st[i]=false;
        }
    }
    
    return false;
}

int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<n;i++){
            int a,b,c;
            cin>>a>>b>>c;
            p[i]={a,b,c};
        }
        memset(st,0,sizeof st);
        if(dfs(0,0))puts("YES");
        else puts("NO");
    }
    return 0;
}

接龙数列

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int f[N];
int a[N];
int b[N];
int g[10];//用于存储第i个数字之前以末尾数字k(0 <= k <= 9)为结尾的接龙序列的max
//即g[k]表示在第i个数字以前,为k为末尾的接龙序列的最大长度


//基于集合的dp分析法
//集合表示f[i]表示以第i个数字为结尾的接龙数列的集合,属性为max
//集合划分,需要做到不重不漏!考虑最后一个不同的位置:就是在以第i个数字为结尾的接龙序列的倒数第二个数字!
//即f[i]可能从i中情况转移而来,从第1个数字到第i-1个数字转移而来,或者没有数字能转移到第i个数字,那么f[i] = 1(因为此接龙序列只有第i个数字)

int main()
{
    int n;
    cin >> n;
    //因为只需要考虑数列中每个数字的首位和尾位,那么只需要存储首位即可
    //a数组存首位,b数字存末位
    char str[20];
    for (int i = 1; i <= n; i++)
    {
        cin >> str;
        a[i] = str[0] - '0';
        b[i] = str[strlen(str) - 1] - '0';
    }

    //遍历n次,为了能算出从1-i的f[i]
    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;
        //由于第i个数字的首位为a[i],那么只关心以a[i]为结尾的数字
        f[i] = max(f[i], g[a[i]] + 1);
        //由于第i个数字的末尾为b[i],那么就要更新g[b[i]
        g[b[i]] = max(g[b[i]], f[i]);
    }

    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, f[i]);
    cout << n - res << endl;
    return 0;
}

岛屿个数

思路：在地图周围一圈增加一圈0作为外海， dfs遍历外海每一个方格，若与外海方格相邻的岛屿未被遍历过，那么这就是一个新的岛屿，再用一个dfs去遍历这个岛。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=55;
char grid[N][N];
int m,n,ans=0;
bool st[N][N];

int dx[]={0,1,0,-1},dy[]={-1,0,1,0};

// 岛屿
void dfs(int x,int y){
    st[x][y]=true;
    for(int i=0;i<4;i++){
        int a=dx[i]+x,b=dy[i]+y;
        if(a<0||a>n+1||b<0||b>m+1||st[a][b]||grid[a][b]=='0') continue;
        dfs(a,b);
    }
}

// 海水
void dfs1(int x,int y){
    st[x][y]=true;
    for(int i=-1;i<=1;i++){
        for(int j=-1;j<=1;j++){
            int a=i+x,b=j+y;
            if(a<0||a>n+1||b<0||b>m+1||st[a][b]) continue;
            if(grid[a][b]=='0')dfs1(a,b);
            else dfs(a,b),ans++;
        }
    }
}

int main(){
    int T=0;
    cin>>T;
    while(T--){
        cin>>n>>m;
        memset(st,false,sizeof st);
        memset(grid,'0',sizeof grid);
        ans=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>grid[i][j];
        dfs1(0,0);
        cout<<ans<<endl;
    }
    return 0;
}

子串简写

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=6e5;
int k;
char a,b;
string p;
long long ans=0;

int main(){
    cin>>k;
    cin>>p>>a>>b;
    vector<int>s,e;
    for(int i=0;i<p.size();i++){
        if(p[i]==a)s.push_back(i);
        if(p[i]==b)e.push_back(i);
    }
    
    for(int i=0;i<s.size();i++){
        int x=s[i];
        int X=x+k-1;
        int l=0,r=e.size()-1;
        // 左二分
        while(l<r){
            int mid=l+r >>1;
            if(e[mid]>=X)r=mid;
            else l=mid+1;
        }
        if(e[l]>=X)ans+=e.size()-l;
    }
    cout<<ans;
    return 0;
}