explain ： This paper is about co_fun Algorithm training activity reference answer , Interested in participating in co_fun Algorithm training students can pay attention to b standing “co_fun Algorithm push community ” Get group number .co_fun Algorithm training activities , For students with general algorithm foundation , Start training at common test sites , Three questions a day , There will be explanations . Three months to tackle the written interview algorithm problem of large factories .

2022.5.9-1

Ideas ： We can know that the problem is equivalent to the shortest path problem ,bfs that will do .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
char mp[105][105];
int len[105];
signed main()
{
    
    memset(len,0x3f,sizeof(len));
    int n;cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>mp[i][j];
    queue<pair<int,int>> q;
    q.push({
    1,0});
    while(q.size())
    {
    
        auto now=q.front();
        q.pop();
        for(int i=1;i<=n;i++)
        {
    
            if(mp[now.first][i]=='N')
                continue;
            if(len[i]<=now.second+1)
                continue;
            len[i]=now.second+1;
            q.push({
    i,len[i]});
        }
    }
    if(len[2]==0x3f3f3f3f3f3f3f3f)
        cout<<-1<<endl;
    else
        cout<<len[2]-1<<endl;
}

2022.5.9-2

Ideas ： greedy , Walk past every gas station without refueling , Put the amount of fuel that can be added into the priority queue , When the fuel is insufficient for the next gas station at a certain time, greedily select the maximum fuel in the queue to join .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
priority_queue<int> pq;
struct P
{
    
    int a,b;
    bool operator<(const P& p)const&{
    
        return a<p.a;
    }
}pn[MAXN];
signed main()
{
    
    int l,p,n;cin>>l>>p>>n;
    for(int i=1;i<=n;i++)
        cin>>pn[i].a>>pn[i].b;
    pn[n+1].a=l;
    sort(pn+1,pn+1+n);
    int cnt=0;
    for(int i=1;i<=n+1;i++)
    {
    
        while(p<pn[i].a)
        {
    
            if(pq.size()==0)
            {
    
                cout<<-1<<endl;
                return 0;
            }
            p+=pq.top();
            pq.pop();
            cnt++;
        }
        pq.push(pn[i].b);
    }
    cout<<cnt<<endl;
}

2022.5.9-3

Ideas ： You can know that the cars in the same line must be the same color , Therefore, the cars that can be connected by ranks are directly regarded as a group , Just count how many groups there are .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
char mp[25][25];
bool delr[25],delc[25];
int n,m;
void clr(int x,int y)
{
    
    mp[x][y]='.';
    if(!delr[x])
    {
    
        delr[x]=1;
        for(int i=1;i<=m;i++)
            if(mp[x][i]=='R')
                clr(x,i);
    }
    if(!delc[y])
    {
    
        delc[y]=1;
        for(int i=1;i<=n;i++)
            if(mp[i][y]=='R')
                clr(i,y);
    }
}
signed main()
{
    
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>mp[i][j];
    int cnt=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
    
            if(mp[i][j]!='R')continue;
            cnt++;
            clr(i,j);
        }
    cout<<cnt<<endl;
}

2022.5.10-1

Ideas ： Simulation question , Exercise strength .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
int q[30][30];
int g[30],t[30];
void mov(int x,int gp)
{
    
    g[x]=gp;
    q[gp][++t[gp]]=x;
}
signed main()
{
    
    int n,m;cin>>n>>m;
    for(int i=1; i<=n; i++)
        t[i]=1,g[i]=i,q[i][1]=i;
    for(int i=1; i<=m; i++)
    {
    
        string s;int a,b=0;
        cin>>s>>a;
        if(s=="move")
        {
    
            cin>>s>>b;
            if(g[a]==g[b])continue;
        }
        int ga=g[a],gb=g[b],pos=0;
        for(int i=1; i<=t[ga]; i++)
            if(q[ga][i]==a)
                pos=i;
        if(s=="over")pos--;
        for(int i=pos+1; i<=t[ga]; i++)
        {
    
            if(gb) mov(q[ga][i],gb);
            else mov(q[ga][i],q[ga][i]);
        }
        t[ga]=pos;
    }
    for(int i=1; i<=n; i++)
    {
    
        cout<<i<<": ";
        for(int j=1; j<=t[i]; j++)
            cout<<q[i][j]<<' ';
        cout<<endl;
    }
}

2022.5.10-2

Ideas ： Dynamic programming ,$dp[i][j]$ Before considering $i$ A course , And the total time that can be spent is $j$ The biggest benefit of .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
int dp[105][105];
int a[105][105];
signed main()
{
    
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
    
            dp[i][j]=dp[i-1][j];
            for(int k=1;k<=j;k++)
                dp[i][j]=max(dp[i-1][j-k]+a[i][k],dp[i][j]);
        }
    cout<<dp[n][m]<<endl;
}

2022.5.10-3

Ideas ： Two points answer , Half is the length of the cut stick .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
int n,m;
int a[MAXN];
bool check(int x)
{
    
    if(x==0)return true;
    int cnt=0;
    for(int i=1;i<=n;i++)
        cnt+=a[i]/x;
    return cnt>=m;
}
signed main()
{
    
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int L=0,R=0x3f3f3f3f3f3f3f3f;
    while(L<R)
    {
    
        int mid=(L+R+1)/2;
        if(check(mid)) L=mid;
        else R=mid-1;
    }
    cout<<L<<endl;
}

2022.5.11-1

Ideas ： greedy , If from 0 To x After sorting, it is part of an ordered array , be 0 To x The maximum value of is x, If this condition is met, this paragraph can be cut off , The following numbers are the same .

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int a[100010];
int main()
{
    
    int n, ma = 0, ans = 0;
    cin >> n;
    for(int i = 0; i < n; i ++)
        cin >> a[i];
    for(int i = 0; i < n; i ++)
    {
    
        ma = max(ma, a[i]);
        if(i == ma)
            ans ++;
    }
    cout << ans << endl;
    return 0;
}

2022.5.11-2

Ideas ：bfs When you go to the next step, you can judge whether there are obstacles at this position at two time points .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
char mp[10][10];
int t[10][10];
struct P{
    int x,y;};
signed main()
{
    
    queue<P> q;
    int sx=0,sy=0,tx=0,ty=0;
    for(int i=1; i<=8; i++)
        for(int j=1; j<=8; j++)
        {
    
            cin>>mp[i][j];
            if(mp[i][j]=='M')
                sx=i,sy=j;
            if(mp[i][j]=='A')
                tx=i,ty=j;
        }
    memset(t,0x3f,sizeof(t));
    t[sx][sy]=0;
    q.push({
    sx,sy});
    while(q.size())
    {
    
        P now=q.front();
        q.pop();
        for(int i=-1; i<=1; i++)
            for(int j=-1; j<=1; j++)
            {
    
                int nx=now.x+i,ny=now.y+j,nt=t[now.x][now.y]+1;
                if(nx<1||nx>8||ny<1||ny>8)continue;
                if(nx-nt+1>=1&&mp[nx-nt+1][ny]=='S')continue;
                if(nx-nt>=1&&mp[nx-nt][ny]=='S')continue;
                if(nt>=t[nx][ny])continue;
                q.push({
    nx,ny});
                t[nx][ny]=nt;
            }
    }
    if(t[tx][ty]==0x3f3f3f3f3f3f3f3f)
        cout<<"Lost"<<endl;
    else cout<<"Win"<<endl;
}

2022.5.11-3

Ideas ： Dynamic programming , $dp[i][j]$ Before you think about it $i$ Stage , And the first $i$ The value of the phase is $j$ The number of solutions at that time . You can know $dp[i][j]$ The result of is by ${\sum }_{k=1}^{j-1}dp[i-1][k]$ Transfer to , The latter can be prefixed and accelerated .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
const int MOD=998244353;
int l[205],r[205];
int dp[205][10005];
int pre[205][10005];
signed main()
{
    
    int n;cin>>n;
    for(int i=1;i<=n;i++)
        cin>>l[i]>>r[i];
    for(int i=0;i<10005;i++)
        pre[0][i]=1;
    for(int i=1;i<=n;i++)
    {
    
        for(int j=l[i];j<=r[i];j++)
            dp[i][j]=pre[i-1][j-1];
        for(int j=1;j<10005;j++)
            pre[i][j]=(pre[i][j-1]+dp[i][j])%MOD;
    }
    cout<<pre[n][r[n]]<<endl;
}