沙烬

2022-06-02 15:22 已编辑 C++

关注

2022年牛客竞赛六一儿童节题解~

嘿，这里是小沙组织的第一场比赛希望大家玩的都很开心~

感谢出题人小沙，嘤嘤，小七，琢喵，智乃，兰子的友情出题！

小沙：A
嘤嘤：CDF
小七：G
智乃：HI
琢喵：B
兰子：E

A

这是一道语法题
首先我们需要判断几个条件：
1.朋友和小沙的年龄差距不能超过3
2.朋友要会跑
3.小沙也是小朋友也要会跑才行

#include<iostream>
using namespace std;


int main(){
    int n,x,c;
    cin>>n>>x>>c;
    int ans=0;
    for(int i=1;i<=n;i++){
        int p;
        cin>>p;
        if(p>=x-3&&p<=x+3&&p>=c) ans++;
    }
    printf("%d",((x>=c)?ans:0));
}

B

不知道有木有勾起大家的儿时回忆呢~
出题人の夹带私货：https://www.bilibili.com/video/BV19R4y1T7Ep
第一问：可以在这个链接中找到
http://web.4399.com/ddt/remendaoju/wq/3423-2.html

关于第二大问：
勇闯地穴：
弹弹堂boss

C

解法一

810975什么意思？|【逗鱼时刻317期】片尾单品_哔哩哔哩_bilibili 视频1：40有正解。

解法二

提示中每行第一句的最后一个汉字连起来 = 衣锦夜行，B站搜索，即可得810975。

解法三

柯南的好基友+儿童节 --> 基德 --> KID --> 1412，打开文件夹找到1412，即可找到答案。

解法四

写一份代码，遍历文件夹，找到一个内容不同的文件。

解法五

来自一血的神奇做法，出题人一脸懵逼。

I3T8$~U$HN3O}{LLZWHL6Z2

解法六
图片说明
出题人意想不到的巧合。

D

第一个问题：

特判x=1和y=1，否则直接暴力乘即可。

第二个问题：

两个操作都会使数变小，所以优先操作大的数，若大的数无法操作，则无法完成。

第三个问题：

观察易知，对于从0开始的前 $2^i(i \ge 1)$ 个数，二进制下 1 的个数为奇数的数有 $2^{i-1}$ 个，并且此性质对于 $[2^i,2^i+2^j)$ 共 $2^j(j \ge 1)$ 个数也成立。所以只要算出 $[0,max(a,b)]$ 和 $[0,min(a,b)-1]$ 的二进制下 1 的个数为奇数的个数，减一下即可。

第四个问题：

让一行或一列的炮都往一个方向打，最终只能剩余两列，若一开始只有一行或一列，则行或列不能操作。所以答案是 $min(a,2)*min(b,2)$ 。

第五个问题：

对于当前 $a$ 件物品：
①若 $a$ 能整除 $b+1$ ，则我们分成 $b+1$ 堆，每堆有 $\frac{a}{b+1}$ 件物品。我们把前 $b$ 堆东西放到天平上，如果这 $b$ 堆东西一样重，那说明重的那件物品在最后一堆中，否则天平可以告诉我们，重的那件物品在这 $b$ 堆东西的哪堆中。

②若 $a$ 不能整除 $b+1$ ，则我们分成 $x+1$ 堆，前 $x$ 堆每堆有 $\frac{a}{b+1}+1$ （ $\frac{n}{m+1}$ 要向下取整）件物品，最后一堆物品数小于等于 $\frac{n}{m+1} +1$ ，可证 $x$ 一定小于等于 $b$ 。我们把前 $x$ 堆东西放到天平上，如果这 $x$ 堆东西一样重，那说明重的那件物品在最后一堆中，否则天平可以告诉我们，重的那件物品在这 $x$ 堆东西的哪堆中。
重复以上过程，最终便可找到重的那件物品，不难发现这个过程本质上就是求 $log_{m+1}n$ (向上取整)的值。

最后求一个异或和即可。

小沙的代码如下：

#include<bits/stdc++.h>
#define fre(z) freopen(z".in","r",stdin),freopen(z".out","w",stdout)

#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

#define sto                             \
    std::ios::sync_with_stdio(false);   \
    std::cin.tie(nullptr);              \
    std::cout.tie(nullptr);

using namespace std;

typedef long long ll;
typedef pair<ll,ll> PII;

ll lowit(ll x){
    return x&-x;
}

inline ll read(){
    ll x=0;char ch;bool f=true;
    for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f^=f;
    for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
    return f?x:-x;
}

void solve(){
    ll a=read(),b=read();
    auto f1=[&](ll a,ll b)->ll{
        if(a==1)return 0;
        if(a>b)return 0;
        ll c=1;
        for(int i=0;;i++,c*=a)
            if(c>b)return i-1;
        return 0;
    };
     auto f2=[&](ll a,ll b)->ll{
        int ans1=0,ans2=0,ans3=0,ans4=0;
         while(a%5==0||b%5==0){
             if(a%5==0)ans3++,a=a/5*3;
             if(b%5==0)ans4++,b=b/5*3;
         }
         while(a%3==0||b%3==0){
             if(a%3==0)ans1++,a/=3;
             if(b%3==0)ans2++,b/=3;
         }
         if(a!=b)return 0;
         return abs(ans1-ans2)+abs(ans3-ans4);
    };
     auto f3=[&](ll l,ll r)->ll{
        if(l>r)swap(l,r);
         auto f=[&](ll n)->ll{
            int x=n,cnt=0;
            while(x){
                if(x&1)cnt++;
                x/=2;
            }
            int c=0;
            if(cnt%2==0)c+=n/2;
            else c+=(n-1)/2;
            return n-c;
         };
         return f(r)-f(l-1);
    };
     auto f4=[&](ll a,ll b)->ll{
        return min(a,2ll)*min(b,2ll);
    };
     auto f5=[&](ll n,ll m)->ll{
        if(m==1)return 0;
         int res=0;
        while(n!=1){
            res++;
            n=(n+m)/(m+1);
        }
        return res;
    };
    cout<<(f1(a,b)^f2(a,b)^f3(a,b)^f4(a,b)^f5(a,b))<<"\n";
}

int main(){
    ll T=1;
    T=read();
    for(int i=1;i<=T;i++)solve();
    return 0;
}

E

答案：

等
瞬间
丢铜板
因为是你
还是好朋友

qcjj搜索法（qcjj友情提供的题解）
我们可以发现，3. 一口吃下全部看起来就非常的特别。那我们就看看能不能把这句对应的歌手搜出来
关键词，一口吃下全部歌词
图片说明
发现是王心凌的歌。结合时事，以及出题人，我们大概率就能确定歌手是王心凌了。
然后再开启万能搜索格式
"想哭了" 王心凌歌词
"你是爱我的" 王心凌歌词
"我为什么爱你" 歌词王心凌
"不要想得太多" 歌词王心凌

F

DJWCB

ELYSI

RNMTQ

AKXGU

OPHVF

A. 克蕾亚（克蕾亚·哈维，百套路战记，不熟）

B.艾斯（艾丝·华伦斯坦，在下求搞，天然呆）

C.莎夏（莎夏·涅库罗，魔王学院的不适格者，不太熟）

D.安洁莉娜（安洁莉娜·库都·希尔兹，抗世界神剧来访者篇，傲娇）

E.瑟莉卡（瑟莉卡·阿尔弗涅亚，不正经的魔术讲师与禁忌教典，涩姐姐）

F.DIO（DIO的奇妙冒险，金发傲娇吸血鬼）

G.拉娜·提耶儿（拉娜·提耶儿·夏尔敦·莱儿·凡瑟芙，Overload，变态+病娇？）

H.安洁莉卡（乙女游戏世界对路人角色很不友好，不太熟）

I.布蕾德（某知名异世界重生番，这个不好说，变态+百合）

J.菲丽希亚（百炼霸王与圣约女武神，不熟）

K.琉璃（失格纹的最强贤者，不熟）

L.莉夏（莉姿夏尔蒂·亚提司玛特，最弱无败的神装机龙，傲娇中的傲娇）

M.铃兰（明日方舟，zngg放的）

N.四门摩耶（圣剑使的禁咒咏唱，四大名著之一，不熟）

O.夏洛特（夏洛特·德诺阿，IS（无限无斯特拉托斯），名作之壁！！！不熟）

P.达克妮丝（为世界的美好献上祝福第二季第4话，变态+M）

Q.菲洛（盾之勇者憋屈录，可爱萝莉yyds）

R.艾莉亚莉亚（被神捡到的男人，不熟）

S.相泽梓（打了300年的史莱姆，不知不觉就练到了满级，不熟）

T.莉丝妲黛（这个勇者明明很强却过分慎重，不熟）

U.川建国（知名地下党员，金发傲娇！（嘴上说着讨厌**，但实际上做了很多让**非常喜欢+开心的事））

V.荧（屑妹妹！其实本来想玩考哥梗叫包包的，但想想还是算了，屑+屑+屑+屑+屑+屑+非常屑）

W.赛莉丝（赛莉丝缇雅·兰格莉思，最弱无败的神装机龙，大大大大姐姐）

X.艾莲（艾莲，关我姆事，搞笑担当？）

Y.月（贫穷职业造就业界最强，金发吸血鬼，不熟）

几乎所有角色都来源于异世界、龙傲天番剧，番剧名字基本可以在另一道融合怪题（D）的标题中找到。

不会真有人全看过吧？不会吧不会吧？

应该很简单吧，打开猛男百科随便搜一搜就有了，要是觉得难的话，下次来认下面这些京都脸

图片说明

G

小乐的房间

输出编号①的房间的周围房间编号，以及自己即可（记得去重排序）

我们可以发现无论房间的布局是：（数字代表空间编号。下图右布局仅仅是反转左布局的第二列到最后一列）

此时两种布局的每个空间的相邻空间是一样的。

换句话说，此时对于任意一个空间 R，两种布局的R的相邻空间构成的集合都是相等的

同理，可以交换第一种布局的第二行到最后一行。这两种操作使得 1周围的空间都可以成为角落。

所以找出 1周围的点然后去重即可，n >= 3 输出9个坐标，n < 3 输出 1 ～ n * n

#include <bits/stdc++.h>


constexpr int N = 1005 * 1005;

int room[N][4];

signed main() {
    int len;
    std::cin.tie(nullptr)->sync_with_stdio(false);
    std::cin >> len, len *= len;
    for (int i = 1; i <= len; ++ i) {
        for (int j = 0; j < 4; ++ j) {
            std::cin >> room[i][j];
        }
    }
    std::map<int, int> mp{{room[1][0], 2}, {room[1][1], 2}, {room[1][2], 2}, {room[1][3], 2}}; // 自动去重
    for (int i = 0; i < 4; ++ i) {
        for (int j = 0; j < 4; ++ j) {
            ++ mp[room[room[1][i]][j]];
        }
    }
    for (auto& i : mp) {
        if (i.second > 1) {
            std::cout << i.first << ' ';
        }
    }
    return 0;
}

H

按题意模拟即可（好解）
出题人：写二分的反思一下。

I

这道题是上下界最小流的模板题，拆点模型也比较好建，不会做的话说明该补一补图论了。

对于一个城堡，我们可以将其分成三个阶段拆成三个点，分别为进攻、死亡、占领三个状态。
然后我们把流量看做是士兵按照题意：
1、因为必须要合力兵力达到D才能进攻，所以建边从进攻节点到死亡节点流量下界为D，上界INF（本题中所有边的上界都是INF，后面不再提了）
2、因为进攻后会死亡A人，所以建边从死亡节点到T下界流A回收流量。
3、因为结算后必须省1个人才能占领和招募，所以从死亡节点到占领节点建边下界1。
4、占领后贪心的直接招募到P人，所以从S节点下界先流P人到占领节点。

剩下的建边就按照原本的DAG图，建INF边连起来即可。
图片说明
建图大概就如上图所示。
顺便一提，数据范围比较小，没有卡二分的最小流写法，但是最小流不会有人写二分版吧。
非二分版的最小流只需要三步，又好写又快：
1、求扩展源ss到扩展汇tt的最大流ans1。
2、连接汇点t->源点s的INF边构造循环流。
3、在残量网络上再次求扩展源ss到扩展汇tt的最大流ans2。
若ans1+ans2满流，则ans2为源s到汇t的最小流，否则源s到汇t无可行流无解。