co

说明：本文为co_fun算法集训活动参考答案，有兴趣参与co_fun算法集训的同学可以关注b站 “co_fun算法内推社区” 获得群号。

co_fun算法集训活动，针对算法基础一般的同学，从常见考点开始训练，每日三道题，会有讲解。

三个月攻坚大厂笔试面试算法题。

2022.4.11-1

#include
#define int long long
#define MAXN 2000005
using namespace std;
signed main()
{
    int n;cin>>n;
    int maxn=0;
    while(n)
    {
        maxn=max(maxn,n%10);
        n/=10;
    }
    cout<<maxn;
}

2022.4.11-2

#include
#define int long long
#define MAXN 2000005
using namespace std;
signed main()
{
    stack<int> stk;
    int n;cin>>n;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        int a,b;cin>>a>>b;
        if(b==1)stk.push(a);
        else
        {
            while(stk.size()&&stk.top()<a)
                stk.pop(),cnt++;
            if(stk.size())cnt++;
        }
    }
    cout<<n-cnt<<endl;
}

2022.4.11-3

#include
#define int long long
#define MAXN 2000005
using namespace std;
int a[4]={2,3,5,7};
int ans=0,n;
void dfs(int now,int cnt,int val)
{
    if(now==4)
    {
        if(!cnt)return;
        if(cnt%2)ans+=n/val;
        else ans-=n/val;
        return;
    }
    dfs(now+1,cnt+1,val*a[now]);
    dfs(now+1,cnt,val);
}
signed main()
{
    cin>>n;
    dfs(0,0,1);
    cout<<n-ans<<endl;
}

2022.4.12-1

#include
#define int long long
#define MAXN 2000005
using namespace std;
unordered_map<int,int> um;
signed main()
{
    int now=0;
    for(int i=0;now<=1e9;i++)
    {
        um[++now]=1;
        now+=i;
    }
    int t;cin>>t;
    while(t--)
    {
        int x;cin>>x;
        cout<<um[x]<<endl;
    }
}

2022.4.12-2

#include
#define int long long
#define MAXN 2000005
using namespace std;
int pre[MAXN];
signed main()
{
    int n,m;cin>>n>>m;
    pre[0]=0x3f3f3f3f3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        cin>>pre[i];
        pre[i]=min(pre[i],pre[i-1]);
    }
    int now=n,ans=0;
    for(int i=1;i<=m;i++)
    {
        int t;cin>>t;
        while(pre[now]<t)
            now--;
        if(now==0)break;
        ans++,now--;
    }
    cout<<ans<<endl;
}

2022.4.12-3

#include
#define int long long
#define MAXN 2000005
using namespace std;
signed main()
{
    vector<pair<int,int>> v;
    int maxn=0,ans=0;
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        int l,r;cin>>l>>r;
        v.push_back({l,r});
    }
    sort(v.begin(),v.end());
    for(int i=0;i<n;i++)
    {
        int l=v[i].first,r=v[i].second;
        if(maxn>l)ans=max(ans,min(maxn,r)-l);
        maxn=max(maxn,r);
    }
    cout<<ans<<endl;
}

2022.4.13-1

#include 
#define int long long
#define MAXN 100005
using namespace std;
unordered_set<int> us;
vector<pair<int,int>> v;
signed main()
{
    int k,n;cin>>k>>n;
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        if(us.count(k-x))
        {
            if(x<=k-x)v.push_back({x,k-x});
            else v.push_back({k-x,x});
        }
        us.insert(x);
    }
    sort(v.begin(),v.end());
    if(v.size())
        for(int i=0;i<v.size();i++)
            cout<<v[i].first<<' '<<v[i].second<<endl;
    else cout<<"No Solution"<<endl;
}

2022.4.13-2

#include 
#define int long long
#define MAXN 100005
using namespace std;
vector<string> dict;
bool check(string& s,vector<string>& v)
{
    for(int i=0;i<dict.size();i++)
    {
        if(s==dict[i])return true;
        if(s.size()==dict[i].size())
        {
            int cnt=0;
            for(int j=0;j<s.size();j++)
                if(s[j]!=dict[i][j])cnt++;
            if(cnt==1)v.push_back(dict[i]);
        }
        else if(abs((int)(s.size()-dict[i].size()))==1)
        {
            string s1=s,s2=dict[i];
            if(s1.size()>s2.size())swap(s1,s2);
            int cnt=0,flag=1;
            for(int i=0;i<s1.size();i++)
            {
                if(!cnt&&s1[i]!=s2[i])cnt++;
                if(s1[i]!=s2[i+cnt])flag=0;
            }
            if(flag)v.push_back(dict[i]);
        }
    }
    return false;
}
signed main()
{
    string s;
    while(cin>>s)
    {
        if(s=="#")break;
        dict.push_back(s);
    }
    while(cin>>s)
    {
        if(s=="#")break;
        vector<string> v;
        if(check(s,v))cout<<s<<" is correct"<<endl;
        else
        {
            cout<<s<<": ";
            for(int i=0;i<v.size();i++)
                cout<<v[i]<<' ';
            cout<<endl;
        }
    }
}

2022.4.13-3

#include 
#define int long long
#define MAXN 200005
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
int a[105][105];
signed main()
{
    int n;cin>>n;
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i-1;j++)
        {
            string s;cin>>s;
            if(s=="x") a[i][j]=inf;
            else a[i][j]=stoll(s);
            a[j][i]=a[i][j];
        }
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                a[i][j]=min(a[i][k]+a[k][j],a[i][j]);
    int maxn=0;
    for(int i=1;i<=n;i++)
        maxn=max(maxn,a[1][i]);
    cout<<maxn<<endl;
}