大大大课前测

· · 个人记录

T0:P10472 括号画家

上次考过了 。

T1: P1331 海战

思路

首先，观察所有撞船的情况，我画了两种（红色为船身）：

我们发现，这两种情况，都有任意相邻的四个格子（都挨在一起） 中，有且仅有 3 个格子有船 。

那么，根据这个性质，我们就可以枚举四个格子的左上角，来判断是否出现装船情况 ，如果出现，输出，直接结束 。

那么没撞船的情况呢？

规律很容易发现，只要挨在一起的四个格子中有且仅有右下角有船，就可以形成一艘新的船，我们通过这种方法来数船的数量 。

Code:

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[5005][5005];
int sum;
int dx[]={0,1,-1,0,0};
int dy[]={0,0,0,1,-1};
int vis[5005][5005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    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)
        {
            int cnt=0;
            if(a[i][j]=='#') cnt++;
            if(a[i+1][j]=='#') cnt++;
            if(a[i+1][j+1]=='#') cnt++;
            if(a[i][j+1]=='#') cnt++;
            if(cnt==3)
            {
                cout<<"Bad placement.";
                return 0;
            }
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            if(a[i][j]=='#'&&a[i-1][j]!='#'&&a[i][j-1]!='#'&&a[i-1][j-1]!='#') sum++;
        }
    }
    cout<<"There are "<<sum<<" ships.";
    return 0;
}

T2: P1088 火星人

STL 真好用 \sim

分析

直接循环 m 次，每次生成下一个全排列，最后输出 。

Code:

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000005];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;++i)
    {
        next_permutation(a+1,a+n+1);
    }
    for(int i=1;i<=n;++i) cout<<a[i]<<' ';
    return 0;
}

T3: P9011 Air Cownditioning II B

这题其实很简单 。

思路

第一个输入时用差分优化（不优化也行），第二个输入时，用一个结构体比较方便 。

使用 DFS 的爆搜进行选和不选的处理，每次加减时直接修改 。

如果选，则将区间 b_x.l 到 b_x.r 进行修改，而且时减去，最后判断只要判断是否小于等于 0 即可 。

如果不选，修改操作变为加法 。

Code:

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,z;
int a[1005];
int mn=1e9;
struct no{
    int l,r,t,w;
}b[1005];
void dfs(int x,int sum)
{
    if(x>m)
    {
        for(int i=1;i<=100;++i)
        {
            if(a[i]<=0) continue;
            else return;
        }
        mn=min(mn,sum);
        return;
    }
    dfs(x+1,sum);
    for(int i=b[x].l;i<=b[x].r;++i)
    {
        a[i]-=b[x].t;
    }
    dfs(x+1,sum+b[x].w);
    for(int i=b[x].l;i<=b[x].r;++i)
    {
        a[i]+=b[x].t;
    }
    return;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        cin>>x>>y>>z;
        a[x]+=z;
        a[y+1]-=z;
    }
    for(int i=1;i<=100;++i) a[i]+=a[i-1];
    for(int i=1;i<=m;++i)
    {
        cin>>b[i].l>>b[i].r>>b[i].t>>b[i].w;
    }
    dfs(1,0);
    cout<<mn;
    return 0;
}

T4: P2383 狗哥玩木棒

思路

巨简单 。

我们在 DFS 中传 5 个参数，分别代表：选到第几根木棒了，第一根木棒的长度，第二根木棒的长度，第三根木棒的长度，第四根木棒的长度 。

终止条件：是不是每根都恰好达到了总长度的 \displaystyle \frac{1}{4} ，如果是，就代表可以，如果一直没有答案，则无解 。

普通的写法会超时，那么，剪枝？

Code:

#include<bits/stdc++.h>
using namespace std;
int t,n,aa,a[1000005],sum;
bool f;
void dfs(int x,int sum1,int sum2,int sum3,int sum4)
{
    if(sum1>aa||sum2>aa||sum3>aa||sum4>aa) return;
    if(sum1==aa&&sum2==aa&&sum3==aa&&sum4==aa) f=1;
    if(f==1) return;
    int tx=x+1;
    dfs(tx,sum1+a[x],sum2,sum3,sum4);
    dfs(tx,sum1,sum2+a[x],sum3,sum4);
    dfs(tx,sum1,sum2,sum3+a[x],sum4);
    dfs(tx,sum1,sum2,sum3,sum4+a[x]);
    return;
}
void solve()
{
    cin>>n;
    memset(a,0,sizeof(a));
    aa=sum=0;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        sum+=a[i];
    }
    if(sum%4!=0)
    {
        cout<<"no\n";
        return;
    }
    aa=sum/4;
    sort(a+1,a+n+1,greater<int>());
    f=0;
    dfs(1,0,0,0,0);
    if(f) cout<<"yes";
    else cout<<"no";
    cout<<'\n';
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

T5: P1460 健康的荷斯坦奶牛

思路

我们的 DFS 有两个参数，一个表示当前选中的饲料，一个表示选了多少个饲料 。

终止条件：选完了 。

更新条件：所有的饲料的状态选完了，并且能够满足奶牛的需求，并且要比当前的最小饲料数要小 。

我们再开一个 ans 数组，储存最优答案，最后输出就行了 。

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=35;
int a[N],b[N][N],ans[N],tmp[N],n,k;
int m=INT_MAX;
bool check(int x)
{
    for(int i=1;i<=n;++i)
    {
        int sum=0;
        for(int j=1;j<=x;++j)
        {
            sum+=b[tmp[j]][i];
        }
        if(sum<a[i])
            return false;
    }
    return true;
}
void dfs(int x,int sum)
{
    if(x>k)
    {
        if(check(sum)&&sum<m)
        {
            m=sum;
            for(int i=1;i<=m;++i)
            {
                ans[i]=tmp[i];
            }
        }
        else return;
    }
    tmp[sum+1]=x;
    dfs(x+1,sum+1);
    dfs(x+1,sum);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    cin>>k;
    for(int i=1;i<=k;++i)
    {
        for(int j=1;j<=n;++j)
        {
            cin>>b[i][j];
        }
    }
    dfs(1,0);
    cout<<m<<' ';
    for(int i=1;i<=m;++i) cout<<ans[i]<<' ';
    return 0;
}

T6: P2080 增进感情

思路

我采用的是传一个参数，表示当前选中了第几件事情，而两人的好感度用两个全局变量来存 。

终止条件：所有的都选完了 。

两人的好感度都增加，当前状态设为 1 。

两人的好感度减少（因为上面加了） ，当前状态设为 0 。

如果两人的好感度的和大于等于 v 并且差值等于 0 ，此时后面的可以都不选，直接输出 0 ，结束程序 。

如果两人最大的好感度和都没达到 v ，输出 -1 ，否则输出差的最小值 。

Code:

#include<bits/stdc++.h>
using namespace std;
int n,v,mn=1e9;
int a[35],b[35];
int a1,a2;
int ans[35];
int f;
void dfs(int x)
{
    if(x>n)
    {
        if(a1+a2>=v)
        {
            mn=min(mn,abs(a1-a2));
            f=1;
        }
        return;
    }
    if(abs(a1-a2)==0&&a1+a2>=v)
    {
        cout<<0;
        exit(0);
    }
    ans[x]=1;
    a1+=a[x];
    a2+=b[x];
    dfs(x+1);
    ans[x]=0;
    a1-=a[x];
    a2-=b[x];
    dfs(x+1);
}
int main()
{
    cin>>n>>v;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i]>>b[i];
    }
    dfs(1);
    if(f==0)
    {
        cout<<-1;
        return 0;
    }
    cout<<mn;
    return 0;
}

The End.