2022夏暑假每日一题（五）

---

这一次全部都是考研机试题目。

一、最少交换次数（基础）

任意门
这道题目的题意是让你算出这个有多少个逆序对，然后按照数字的大小顺序输出。

#include<bits/stdc++.h>

using namespace std;

const int N=1010;
int n;
int w[N];
int ans[N];

int  main()
{
    
    cin>>n;
    for(int i=0;i<n;i++)cin>>w[i];
    for(int i=0;i<n;i++)
        for(int j=0;j<i;j++)
        if(w[j]>w[i])
        ans[w[i]]++;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
    
        cout<<ans[i]<<" ";
        sum+=ans[i];
    }
    cout<<endl<<sum<<endl;
    return 0;
}

二、二叉搜索树（前序、中序、后序）

任意门
这是一个朴素版的BST。
对于每一个根节点而言，他根结点的值都是大于左儿子小于右儿子。

#include<bits/stdc++.h>

using namespace std;

const int N=110;
int n;
int l[N],r[N],w[N],idx;
int root;

void insert(int& u,int x)//加了一个&，后面如果对他进行更改，原数值也是会变的
{
    
    if(!u)u=++idx,w[u]=x;
    else if(x<w[u])insert(l[u],x);
    else if(x>w[u])insert(r[u],x);//如果相等的话，我们是不操作的
}

void dfs(int u,int t)
{
    
    if(!u)return;
    if(t==0)cout<<w[u]<<" ";
    dfs(l[u],t);
    if(t==1)cout<<w[u]<<" ";
    dfs(r[u],t);
    if(t==2)cout<<w[u]<<" ";
}

int main()
{
    
    cin>>n;
    while(n--)
    {
    
        int x;
        cin>>x;
        insert(root,x);
    }
    for(int i=0;i<3;i++)
    {
    
        dfs(root,i);
        cout<<endl;
    }
    return 0;
}

三、日期（模拟）

任意门
给定你一个日期，然后让你说出他的星期数，这道题更加简化了一些，她告诉了你一个前提，并在此前提下进行了一个约束。

#include<bits/stdc++.h>

using namespace std;
int months[]={
    0,31,29,31,30,31,30,31,31,30,31,30,31};
string k[]={
    "Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"};
int main()
{
    
    int m,d;
    cin>>m>>d;
    int mon=4,day=12,t=4;
    while(1)//mon<m||day<d
    {
    

        if(mon==m&&day==d){
    cout<<k[t-1];return 0;}
        t++;
        day++;
         if(day>months[mon]){
    day=1;mon++;}
        if(t>7)t=1;
    }

    return 0;
}

四、水仙花数（枚举）

任意门
“水仙花数”是指一个三位数，它的各位数字的立方和等于其本身
这个题目是很经典的语法题，反正我在学习c基础的时候，这道题就被老师反复出题了。

#include<bits/stdc++.h>

using namespace std;

int a[1010];

int f(int x)
{
    
    int res=0;
    while(x)
    {
    
        int t=x%10;
        res+=t*t*t;
        x/=10;
    }
    return res;
}
int main()
{
    
    int m,n,t;
    while(cin>>m>>n,m&&n)
    {
    
        int t=0;
        for(int i=m; i<=n; i++)
        {
    
            int ans=f(i);
            if(ans==i)a[t++]=i;
        }
        if(t==0)cout<<"no"<<endl;
        else
        {
    
            for(int i=0; i<t; i++)
                cout<<a[i]<<" ";
            cout<<endl;
        }

    }
    return 0;
}

五、最低票价(dp)

任意门
所给的days是要去旅行的日子

#include<bits/stdc++.h>

using namespace std;
const int N=400;

int n;
int days[N],f[N];
int c1,c7,c30;

int main()
{
    
    cin>>n;
    for(int i=1;i<=n;i++)cin>>days[i];
    cin>>c1>>c7>>c30;
    for(int i=1,j7=0,j30=0;i<=n;i++)
    {
    
        while(days[i]-days[j7+1]>=7)j7++;
        while(days[i]-days[j30+1]>=30)j30++;
        f[i]=min({
    f[i-1]+c1,f[j7]+c7,f[j30]+c30});
    }
    cout<<f[n]<<endl;
    return 0;
}

六、最大连续子序列（dp）

任意门
这也是一个十分经典的问题，这个也是中南大学的考研机试题。
最大连续子序列是所有连续子序列中元素和最大的一个

这道题是以右端点i来记录的，就是从左往右，用f[i]来表示，如果是从右往左，则用g[i]来表示。
由于f[i]的状态只与后面一个数相关，我们其实可以开一个滚动数组来记录。

#include<bits/stdc++.h>

using namespace std;
const int N=100010;
int n;
int w[N];

int main()
{
    
    while(~scanf("%d",&n))//!=-1
    {
    
        for(int i=0;i<n;i++)
            scanf("%d",&w[i]);
        int res=0,left=0,right=0;
        for(int i=n-1,f=0,g=n-1;i>=0;i--)
        {
    
            if(f<=0)//说明和是负数，所以肯定不要前面的
            {
    
                f=0;
                g=i;
            }
            f+=w[i];//负责算他的最大值
            if(f>=res)
            {
    
                res=f;
                left=i;
                right=g;
            }
        }
        printf("%d %d %d\n",res,left,right);
    }
    return 0;
}