8.21测试总结

· · 算法·理论

8.21测试总结

T638482 小梦的铁索连环

得分:0

应得:100

考点:图上搜素+DFS（深搜）

错误思路:输出a[1]-a[n]中最大值（还不如输出a[1]+a[2]+a[3]+......+a[n]和暴力分一样这样我就第一名了QAQ）

正确思路:使用邻接矩阵存储再进行dfs,遍历出最优方案

核心代码


void dfs(int step,int sum){
    ans=max(ans,sum);
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        bool flag=1;
        for(int j=1;j<step;j++){
            int v=s[j];
            if(e[i][v]==0){
                flag=0;
                break;
            }
        }
        if(flag){
            vis[i]=1;
            s[step]=i;
            dfs(step+1,sum+a[i]);
            vis[i]=0;
        }
    }
    return ;
}

正确代码:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,m,ans=0;
int s[1005],a[1005];
int e[1005][1005];
bool vis[1005];
void dfs(int step,int sum){
    ans=max(ans,sum);
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        bool flag=1;
        for(int j=1;j<step;j++){
            int v=s[j];
            if(e[i][v]==0){
                flag=0;
                break;
            }
        }
        if(flag){
            vis[i]=1;
            s[step]=i;
            dfs(step+1,sum+a[i]);
            vis[i]=0;
        }
    }
    return ;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        e[u][v]=e[v][u]=1;
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}

T638458 忙碌的老师

得分:0

应得:100

考点:结构体,sort排序

错误思路:以为是二分,就写了一段二分代码(喜提爆0)

正确思路：先用结构体存储,再使用一个数组模拟老师,如果老师不够,数组就在加一位->cnt++;,最后输出cnt(cnt初始为1)

正确代码:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,m,cnt;
struct node{
    int l,r;
}a[100005];
int b[100005];
bool cmp(node q,node h){
    if(q.l==h.l)return q.r>h.r;
    return q.l<h.l;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].l>>a[i].r;
    }
    sort(a+1,a+n+1,cmp);
    int ans=1;
    b[++cnt]=a[1].r;
    for(int i=2;i<=n;i++)
    {
        bool flag=0;
        for(int j=1;j<=cnt;j++)
        {
            if(a[i].l>b[j])
            {
                flag=1;
                b[j]=a[i].r;
                break;
            }
        }
        if(!flag)
        {
            b[++cnt]=a[i].r;
        }
    }
    cout<<cnt;
    return 0;
}