编程知识 cdmana.com

co_ Fun recruitment algorithm may activity schedule 5.5-5.7

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.5-1

Ideas : greedy , For reporting x For a rabbit , You can put x+1 Make a group of , There are deficiencies x+1 Make up for each one .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
int a[1005];
signed main()
{
    
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
    
        int t;cin>>t;
        a[t]++;
    }
    int ans=0;
    for(int i=0;i<=1000;i++)
    {
    
        ans+=a[i];
        if(a[i]%(i+1))
            ans+=i+1-a[i]%(i+1);
    }
    cout<<ans<<endl;
}

2022.5.5-2

Ideas : Stack matching , After each successful match, the bracket pair on the match will be removed , Then you can know the total length of all parentheses on the correct match of the current match through the subscript of the unmatched parentheses at the top of the stack .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
int a[1005];
signed main()
{
    
    string s;cin>>s;
    stack<int> stk;
    stk.push(-1);
    int ans=0;
    for(int i=0; i<s.size(); i++)
    {
    
        if(stk.size()>1&&s[i]==')'&&s[stk.top()]=='(')
        {
    
            stk.pop();
            ans=max(ans,i-stk.top());
            continue;
        }
        stk.push(i);
    }
    cout<<ans<<endl;
}

2022.5.5-3

Ideas : You know, if you do on a bipartite graph dfs Every step will jump from the current set to another set , Therefore, the graph can be dyed according to the parity of the number of steps taken , If there is no conflict in coloring, it is a bipartite graph .

#include<bits/stdc++.h>
#define int long long
#define MAXN 505
using namespace std;
vector<int> edge[MAXN];
int col[MAXN];
int ans=1;
void dfs(int now,int p)
{
    
    if(col[now]!=-1)
    {
    
        if(col[now]!=p)
          ans=0;
        return;
    }
    col[now]=p;
    for(int i=0;i<edge[now].size();i++)
        dfs(edge[now][i],1-p);
}
void solve()
{
    
    ans=1;
    memset(col,-1,sizeof(col));
    for(int i=0;i<MAXN;i++)
        edge[i].clear();
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    
        int u,v;cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        if(col[i]==-1)
            dfs(i,0);
    if(ans)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}
signed main()
{
    
    int T;cin>>T;
    while(T--)
        solve();
}

2022.5.6-1

Ideas : Complete knapsack board

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

2022.5.6-2

Ideas :dfs Backtracking directly enumerates what numbers are filled in each grid , But you need to prune . After enumerating the numbers in one grid at a time , Check the nine palaces in the same row and belong to the same person to see if there is no conflict , It's legal to fill in , If it's illegal, go back . And if you find more than 1 When you create a scheme, you don't search and return directly , You can pass this question .

#include<bits/stdc++.h>
#define int long long
#define MAXN 200005
using namespace std;
int a[10][10];
int out[10][10];
int cnt=0;
bool check(int x,int y)
{
    
    for(int i=1; i<=9; i++)
        if(a[i][y]==a[x][y]&&i!=x
                ||a[x][i]==a[x][y]&&i!=y)
            return false;
    int bx=(x-1)/3*3+1,by=(y-1)/3*3+1;
    for(int i=0; i<=2; i++)
        for(int j=0; j<=2; j++)
            if(a[bx+i][by+j]==a[x][y]&&((bx+i)!=x||(by+j)!=y))
                return false;
    return true;
}
void dfs(int x,int y)
{
    
    if(cnt>1)return;
    if(x==10)
    {
    

        if(y==9)
        {
    
            for(int i=1; i<=9; i++)
                for(int j=1; j<=9; j++)
                    out[i][j]=a[i][j];
            cnt++;
            return;
        }
        x=1,y++;
    }
    if(a[x][y]&&check(x,y))
        dfs(x+1,y);
    else
    {
    
        for(int i=1; i<=9; i++)
        {
    
            a[x][y]=i;
            if(check(x,y))
                dfs(x+1,y);
        }
        a[x][y]=0;
    }
}
signed main()
{
    
    for(int i=1; i<=9; i++)
        for(int j=1; j<=9; j++)
            cin>>a[i][j];
    dfs(1,1);
    if(cnt!=1)cout<<"No Solution"<<endl;
    else
    {
    
        for(int i=1; i<=9; i++)
        {
    
            for(int j=1; j<=9; j++)
                cout<<out[i][j]<<' ';
            cout<<endl;
        }
    }
}

2022.5.6-3

Ideas : It can be seen that the sorting method according to bubble sorting is the one with the least number of exchanges , And each exchange makes the number of pairs in the array in reverse order -1, So find the reverse order pair , Here we use the merge sort method , There is also discretization + Tree array method , But the latter is not in the school recruitment program .

#include<bits/stdc++.h>
#define int long long
#define MAXN 200005
using namespace std;
int a[MAXN],b[MAXN];
int ans=0;
void merg(int l,int r)
{
    

    if(l==r)return;
    int mid=(l+r)/2;
    merg(l,mid);
    merg(mid+1,r);
    int p1=l,p2=mid+1,p3=p1;
    while(p1<=mid&&p2<=r)
    {
    
        if(a[p1]<=a[p2])
            b[p3++]=a[p1++];
        else
        {
    
            ans+=mid+1-p1;
            b[p3++]=a[p2++];
        }
    }
    while(p1<=mid) b[p3++]=a[p1++];
    while(p2<=r) b[p3++]=a[p2++];
    for(int i=l; i<=r; i++)a[i]=b[i];
}
signed main()
{
    
    int n;cin>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    merg(1,n);
    cout<<ans<<endl;
}

2022.5.7-1

Ideas : Double pointer template question , Pay attention to how to write clearly .

#include<bits/stdc++.h>
#define int long long
#define MAXN 500005
using namespace std;
int a[MAXN];
signed main()
{
    
    int s,n;cin>>s>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int ans=0x3f3f3f3f3f3f3f3f;
    int L=1,sum=0;
    for(int R=1;R<=n;R++)
    {
    
        sum+=a[R];
        while(sum-a[L]>=s)
            sum-=a[L++];
        if(sum>=s)
            ans=min(ans,R-L+1);
    }
    if(ans!=0x3f3f3f3f3f3f3f3f)
        cout<<ans<<endl;
    else cout<<0<<endl;
}

2022.5.7-2

Ideas : The same number of Islands , Flooding algorithm .

#include<bits/stdc++.h>
#define int long long
#define MAXN 500005
using namespace std;
char mp[1005][1005];
void dfs(int x,int y)
{
    
    if(mp[x][y]!='W')return;
    mp[x][y]='.';
    for(int i=-1;i<=1;i++)
        for(int j=-1;j<=1;j++)
            dfs(x+i,y+j);
}
signed main()
{
    
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>mp[i][j];
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(mp[i][j]=='W')
            {
    
                ans++;
                dfs(i,j);
            }
    cout<<ans<<endl;
}

2022.5.7-3

Ideas :meet in middle,30 The number can be divided into two parts to enumerate whether to select , enumeration 2 15 2^{15} 215 Next time , The enumeration method is used to compress the state .

#include<bits/stdc++.h>
#define int long long
#define MAXN 500005
using namespace std;
int a[35];
int getsum(int x,int b)
{
    
    int ret=0;
    for(int i=0;i<20;i++)
        if((x>>i)&1)
            ret+=a[i+b];
    return ret;
}
int getmin(int a,int b)
{
    
    for(int i=0;i<35;i++)
        if(((a>>i)&1)!=((b>>i)&1))
            return (a>>i)&1?a:b;
    return a;
}
unordered_map<int,int> L;
signed main()
{
    
    int n,m;cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    for(int i=0;i<(1<<(n/2));i++)
    {
    
        int now=getsum(i,0);
        if(!L.count(now))L[now]=i;
        else L[now]=getmin(L[now],i);
    }
    int ans=0;
    for(int i=0;i<(1<<(n-n/2));i++)
    {
    
        int now=getsum(i,n/2);
        if(now==m)ans=getmin(ans,(i<<n/2));
        else if(L.count(m-now))
            ans=getmin(ans,L[m-now]+(i<<n/2));
    }
    if(ans==0)
        cout<<"No solution"<<endl;
    else
        for(int i=0;i<35;i++)
            if((ans>>i)&1)
                cout<<a[i]<<' ';
}

版权声明
本文为[GreyKa]所创,转载请带上原文链接,感谢
https://cdmana.com/2022/134/202205141349063771.html

Scroll to Top