第十届“图灵杯”NEUQ-ACM程序设计竞赛个人赛 部分题解

2023/2/4 算法竞赛 题解 图灵杯 NEUQ

做几道签到题去补作业了(逃)

A. 有用的算法

题面

把题意翻译一下即可.

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
const int N=1e6+5;
int a[N];
int main() {
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    bool flag1=false,flag2=false;
    for(int i=1;i<n;i++)
    {
        if(a[i+1]<a[i])
        {
            flag1=true;
            break;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i+1]>a[i])
        {
            flag2=true;
            break;
        }
    }
    if(!flag1||!flag2)
        cout<<"erfen is useful!"<<'\n';
    else
        cout<<"bukeyi"<<'\n';
    return 0;
}

B. 平衡数

题面

翻译一下题面意思.

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        string s;
        cin>>s;
        if(s[0]+s[1]==s[2]+s[3])
            cout<<"YES"<<'\n';
        else
            cout<<"NO"<<'\n';
    }
    return 0;
}

C. 三角形

题面

题目已经将初始条件极度简化了.

只需要 且 .

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
int main() {
    ios::sync_with_stdio(false);
    int xb,xc,yc;
    cin>>xb>>xc>>yc;
    int xp,yp;
    cin>>xp>>yp;
    if(xc*yp<xp*yc&&(double)yp/(xp-xb)>(double)yc/(xc-xb))
        cout<<"yes"<<'\n';
    else
        cout<<"no"<<'\n';
    return 0;
}

E. 减肥计划

题面

很小，dfs一下是可以的.

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
struct food
{
    int x;
    int y;
    int z;
    int w;
}f[15];
bool vis[15]={false};
int ans=0;
int an=0;
int n,a,b,c;
int a0,b0,c0;
void dfs(int x)
{
    if(x>n||x<1||vis[x])
        return;
    if(f[x].x+a0>a||f[x].y+b0>b||f[x].z+c0>c)
    {
        ans=max(an,ans);
        return;
    }
    vis[x]=true;
    a0+=f[x].x;
    b0+=f[x].y;
    c0+=f[x].z;
    an+=f[x].w;
    for(int i=1;i<=n;i++)
    {
        dfs(i);
    }
    a0-=f[x].x;
    b0-=f[x].y;
    c0-=f[x].z;
    an-=f[x].w;
    vis[x]=false;
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>a>>b>>c;
    for(int i=1;i<=n;i++)
    {
        cin>>f[i].x>>f[i].y>>f[i].z>>f[i].w;
    }
    for(int i=1;i<=n;i++)
        dfs(i);
    cout<<ans<<'\n';
    return 0;
}

F. 吃包子

题面

用前缀和 表示 内有多少素包子.

从前往后扫描，如果一段区间内的素包子数小于 ，那就继续拓展.

拓展到不能动了就移动区间头继续扫描.

发现继续扫描时并不需要移动区间另一头，复杂度差不多在 ，可以过.

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
const int N=1e6+5;
int a[N],cnt[N];
int main() {
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        cnt[i]=cnt[i-1]+!a[i];
    }
    int ans=0;
    for(int i=1,j=1;i<=n;i++)
    {
        while(j<=n&&cnt[j]-cnt[i-1]<=m)
        {
            ans=max(ans,j-i+1-cnt[j]+cnt[i-1]);
            j++;
        }
    }
    cout<<ans<<'\n';
    return 0;
}
img_show