概要

我 AK 了 ，srds因为有Q老师的免费测试套餐，才发现题目名错了( 。

题目难度不大

题目

T1

随便脚算一下人数完了

比赛后 $-$ 比赛前 $+$ 晋级的。

code:

#include<bits/stdc++.h>
using namespace std;
int x[10],y[10],yin,huang,bai; 
int main()
{
    freopen("promotion.in","r",stdin);
    freopen("promotion.out","w",stdout);
    for(int i=1;i<=4;i++)
    {
        cin>>x[i]>>y[i];
    }
    bai=y[4]-x[4];
    huang=y[3]+bai-x[3];
    yin=y[2]+huang-x[2];
    cout<<yin<<"\n"<<huang<<"\n"<<bai<<"\n";
    return 0;
}

T2

枚举 boom 的源头，再 bfs 一下，把当前能连锁 boom 的 boom 了。

#include<bits/stdc++.h>
using namespace std;
int n,a[110],ans;
int vis[110];
struct node
{
    int x,r;
};
queue <node> q; 
void bfs(int X)
{
    //int times=0;
    while(!q.empty()) q.pop();
    node l;l.x=X;l.r=1;q.push(l);
    while(!q.empty())
    {
        //times++;
        l=q.front();q.pop();
        int x=l.x,r=l.r;
        if(vis[x] || x<1 || x>n) continue;
        //cerr<<"**"<<x<<" "<<r<<"\n";
        vis[x]=1;
        l.r=r+1;
        for(int i=1;i<=n;i++)
        {
            if(abs(a[i]-a[x])<=r && !vis[i])
            {
                l.x=i;
                q.push(l);
                //cerr<<"**"<<x<<" to "<<i<<"\n";
            } 
        }
    }
}
int main()
{
    freopen("angry.in","r",stdin);
    freopen("angry.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        bfs(i);
        int cnt=0;
        for(int j=1;j<=n;j++)
        {
            cnt+=vis[j];
            //cerr<<vis[j]<<" ";
        }
        ans=max(ans,cnt);
        //cerr<<"\n";
    }
    cout<<ans<<"\n";
    return 0;
}

T3

从 $(1,1)$ 开始 bfs，把当前能点亮的访问，如果点亮的四周有，就 $\texttt{push}$ 一下。

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
const int dx[]={114514,1,-1,0,0},dy[]={1919810,0,0,1,-1};
struct NodeV
{
    int x,y;
};
struct NodeBfs
{
    int x,y;
};
vector <NodeV> v[110][110];
bool vis[110][110],islight[110][110];
queue <NodeBfs> q;
int main()
{
    freopen("lightson.in","r",stdin);
    freopen("lightson.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,a,b;
        scanf("%d%d%d%d",&x,&y,&a,&b);
        v[x][y].push_back({a,b});
    }
    q.push({1,1});
    while(!q.empty())
    {
        int x=q.front().x,y=q.front().y;
        q.pop();
        if(x<1 || y<1 || x>n || y>n || vis[x][y]) continue;
        vis[x][y]=1;
        islight[x][y]=1;
        for(int i=0;i<v[x][y].size();i++)
        {
            int nx=v[x][y][i].x;
            int ny=v[x][y][i].y;
            islight[nx][ny]=1;
            if(vis[nx][ny]==0)
            {
                if(vis[nx-1][ny] || vis[nx+1][ny] || vis[nx][ny-1] || vis[nx][ny+1]) q.push({nx,ny});
            }
        }
        for(int i=1;i<=4;i++)
        {
            int nx=x+dx[i],ny=y+dy[i];
            if(!vis[x][y] || !islight[nx][ny]) continue;
            q.push({nx,ny});
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            //cerr<<islight[i][j];
            ans+=islight[i][j];
        }
        //cerr<<"\n";
    }
    cout<<ans<<"\n";
    return 0;
}

T4

我太菜了，不会用 DP。

可以考虑减半只会对一次影响(因为如果两次及以上就可以换成整的 $+$ 一半)

枚举 $4$ 种情况即可

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL T,t,a,b,c,d,ans=11919810;
int main()
{
    freopen("feast.in","r",stdin);
    freopen("feast.out","w",stdout);
    cin>>T>>a>>b;
    if(a<b) swap(a,b);
    T*=2;
    c=a;
    d=b;
    a*=2;
    b*=2;
    
    //the fang'an of 1st
    t=T;
    for(int i=0;i<=t/a;i++)
    {
        ans=min(ans,t-(i*a)-(t-i*a)/b*b);
        //cerr<<ans<<"\n";
    }
    
    //the fang'an of 2nd
    t=T-c;
    for(int i=0;i<=t/a;i++)
    {
        ans=min(ans,t-(i*a)-(t-i*a)/b*b);
        //cerr<<ans<<"\n";
    }
    
    //the fang'an of 3rd
    t=T-d;
    for(int i=0;i<=t/a;i++)
    {
        ans=min(ans,t-(i*a)-(t-i*a)/b*b);
        //cerr<<ans<<"\n";
    }
    
    //the fang'an of 4th
    t=T-c-d;
    for(int i=0;i<=t/a;i++)
    {
        ans=min(ans,t-(i*a)-(t-i*a)/b*b);
        //cerr<<ans<<"\n";
    }
    //cerr<<ans<<"\n";
    cout<<(T-ans)/2<<"\n";
    return 0;
}
/*
4 possible
1st all do not use
2nd use a/2
3rd use b/2
4th use (a+b)/2
*/