JX Round#1 千花の机房日常 题解

题解 比赛-JX Round
编辑文章

关于这次比赛

这次比赛本来想全用原创题的,但是@Terrasse大佬的题还没有验题和数据(现在有了,下次考),@Ofnoname大佬的题考察范围很多人应该都没学,我的另一道题太过码农和毒瘤,所以在徐妈的建议下就找了洛谷2279 消防局的设立作为T3。

背景使用的是以正在连载的新番辉夜大小姐想让我告白~天才们的恋爱头脑战~中人气角色藤原千花为主人公的故事。墙裂推荐大家去看这部番!书记太可爱了awsl

因为只能按照题号排序的原因,这次比赛题目的真正顺序是B->A->C,下面的题解按照真正顺序排序

这三道题分别考察了搜索、模拟和贪心+图论。难度分别为普及/提高- 普及+/提高 提高+/省选-

比赛总结

我们的锅

  1. x连弩那道题标程出错,主要原因是我菜和我们验题不仔细,后来已修复。

总体情况

最高分90。。。还有T3是原题只有1个人得了10分。。。毒瘤出题人的名号甩不掉了

来放一张前10合照:

题解

A-千花与x连弩

其实就是一道搜索题,对于剩下的4张牌用队列维护。

其实@Ofnoname大佬本来想出一道状压的搜索,但是出出来才发现因为皇室战争特殊的卡牌轮回机制,似乎只能暴力解决。如果您有更优解,欢迎提供给我们。

具体做法就是先按照出场顺序排序,然后用 $cur[]$ 记录当前的手牌 , $nxt[]$ 记录剩下的牌。每一次搜索时枚举使用的手牌,计算对答案的贡献然后放到队尾,把队头放入当前手牌并删除($front++$)。

对于 $40\%$ 的数据直接这么做就行了,而 $100\%$ 的数据需要加一个剪枝:

if (cost>ans) return;

意思就是已经比当前得到的最小值大了就可以不用再算了,对算法效率提升明显。

//Code: Llf0703
//Check: Terrasse,Ofnoname
#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int x,a,b,c,ans,cur[5],nxt[1005];
struct card{
    int cost,hp,id;
} s[10];

inline bool cmp(card x,card y)
{
    return x.id<y.id;
}

void dfs(int cnt,int cost,int front)
{
    if (cost>ans) return;
    if (cnt>=160)
    {
        if (cost<ans) ans=cost;
        return;
    }
    for (int i=1;i<=4;i++)
    {
        int now=cur[i];
        cur[i]=nxt[front];
        nxt[front+4]=now;
        dfs(cnt+(s[now].hp+x-1)/x,cost+s[now].cost,front+1);
        cur[i]=now;
    }
}

int main()
{
    x=read();
    for (int i=1;i<=8;i++) s[i].hp=read(),s[i].cost=read(),s[i].id=read();
    sort(s+1,s+9,cmp);
    ans=1e9;
    for (int i=1;i<=4;i++) cur[i]=i,nxt[i]=i+4;
    dfs(0,0,1);
    printf("%d",ans);
    return 0;
}

B-千花与头文件

原名:PS++语言。这是一道@Ofnoname大佬在初二时便出出来的题,但一直没有人写标程,后来@Terrasse大佬和我在探讨中完成并完善了标程。为了防止比赛中得分太难看,我还专门加上了对于语句用法的解释以及正确语法的示范,还有子任务。(以前只有不cewarning我是不是很良心啊)。不过为了子任务的牺牲也有很多,有些易错点就因为照顾子任务被删了。

还有原来只需要输出ce,但测试点中的ce有6个,感觉太容易骗分了,所以我又加了个输出行号。

题解我就直接从原文复制过来了 洛谷T32219 PS++语言 - Llf0703's blog

我们先来梳理下编译错误有哪些情况:

  1. #define#undef后面没有空格
  2. #define后没有空格相隔的两个及以上元素(可以只有一个元素,感谢@ljq大佬的指出)
  3. #undef后有两个及以上元素
  4. #include后面不是由尖括号或引号包裹起来的一串字母
  5. 甚至不是这三个关键字
  6. 还没有#define#undef某个元素
  7. 重复#define
  8. #include的右尖括号后还有东西
  9. #include尖括号或引号中元素为空

需要注意的是空格无论留多少都不会影响编译,#include后面可以不留空格(像我自己打代码就从来不留)。

上面的东西前五个直接用字符串基础知识判断即可,对于第6个,我们可以使用map去重,当#undef的时候判断一下是否存在,如果不存在则给出ce,否则把这个元素删除即可。

剩下的就是统计答案了,注意头文件可能会有重复的情况,这时我们再开一个map去下重就行了。

然后是我的清(巨)晰(长)易(无)懂(比)的代码,各位将就看看吧,欢迎hack:

// ©2019 Llf0703
// It's the std code of https://www.luogu.org/problemnew/show/T32219
// visit https://llf0703.com/p/luogu-t32219.html to hack me in the comment

#include<bits/stdc++.h>

using namespace std;

map <string,int> mp,mp2;

int main()
{
    string s;
    int n,ans=0;
    scanf("%d",&n);
    getline(cin,s);
    for (int i=1;i<=n;i++)
    {
        getline(cin,s);
        int len=s.length();
        string x=s.substr(0,8),y=s.substr(0,8),z=s.substr(0,7); //include ' '
        if (x!="#include" && y!="#define " && z!="#undef ") 
        {
            printf("Compile Error\n%d",i);
            return 0;
        }
        if (x=="#include")
        {
            int j=8;
            while (s[j]==' ' && j<len) j++;
            if ((s[j]!='\"' && s[j]!='<') || j==len)
            {
                printf("Compile Error\n%d",i);
                return 0;
            }
            int stat=j+1;
            char goal;
            if (s[j]=='\"') goal='\"';
            else goal='>';
            j++;
            while (s[j]!=goal && j<len) j++;
            if (j==len)
            {
                printf("Compile Error\n%d",i);
                return 0;
            }
            int ed=j-1;
            if (ed-stat+1==0)
            {
                printf("Compile Error\n%d",i);
                return 0;
            }
            j++;
            while (s[j]==' ' && j<len) j++;
            if (j!=len)
            {
                printf("Compile Error\n%d",i);
                return 0;
            }
            string name=s.substr(stat,ed-stat+1);
            if (mp.find(name)==mp.end()) ans++;
            mp[name]=1;
        }
        else if (y=="#define ")
        {
            int j=8;
            while (s[j]==' ' && j<len) j++;
            if (j==len)
            {
                printf("Compile Error\n%d",i);
                return 0;
            }
            int stat=j;
            while (s[j]!=' ' && j<len) j++;
            int ed=j-1;
            string name=s.substr(stat,ed-stat+1);
            if (mp2.find(name)!=mp2.end())
            {
                printf("Compile Error\n%d",i);
                return 0;
            }
            mp2[name]=1;
        }
        else if (z=="#undef ")
        {
            int j=7;
            while (s[j]==' ' && j<len) j++;
            if (j==len)
            {
                printf("Compile Error\n%d",i);
                return 0;
            }
            int stat=j;
            while (s[j]!=' ' && j<len) j++;
            int ed=j-1;
            while (s[j]==' ' && j<len) j++;
            if (j!=len)
            {
                printf("Compile Error\n%d",i);
                return 0;
            }
            string name=s.substr(stat,ed-stat+1);
            if (mp2.find(name)==mp2.end())
            {
                printf("Compile Error\n%d",i);
                return 0;
            }
            mp2.erase(name);
        }
    }
    printf("%d",ans);
    return 0;
}

C-千花与辉夜


原题

这是徐妈要求的贪心题,我寻思这道题难度还比较适中,所以就选了这道,改了下背景。

题解我还是直接粘贴原来我写的 洛谷P2279 消防局的设立

虽说放在DP板块,但贪心就能水过。。。

我们肯定要保证覆盖到叶节点,而对于每一个结点,他能覆盖到的地方就是最远到它爷爷,它孙子和它兄♂弟。它的爷爷节点就可以把它和它兄弟都覆盖了。

也就是说对于每个 叶节点或子节点及以下都已经被覆盖了 的点,选取它的爷爷节点一定是最优的。所以用一个优先队列每次找到深度最深的没有被覆盖的点的爷爷节点放上消防站,然后更新周围即可。

#include<bits/stdc++.h>
#define pr pair<int,int>
#define mp make_pair

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge{
    int next,to;
} edge[2005];
int head[1005],deep[1005],cnt=1,n,m,a,b,c,fa[1005],ans;
priority_queue <pr> q;
bool vis[1005];

inline void add(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

void dfs(int x,int f,int dep)
{
    deep[x]=dep;
    fa[x]=f;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        dfs(y,x,dep+1);
    }
}

void dfs2(int x,int f,int dep)
{
    if (dep>2) return;
    vis[x]=1;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        dfs2(y,x,dep+1);
    }
}

inline void work(int x)
{
    if (!x) x=1;
    dfs2(x,0,0);
}

int main()
{
    n=read();
    for (int i=2;i<=n;i++)
    {
        a=read();
        add(a,i);
        add(i,a);
    }
    dfs(1,0,1);
    for (int i=1;i<=n;i++) q.push(mp(deep[i],i));
    while (!q.empty())
    {
        int x=q.top().second;
        q.pop();
        if (vis[x]) continue;
        work(fa[fa[x]]);
        ans++;
    }
    printf("%d",ans);
    return 0;
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空

第一次提交的评论将在审核后显示。