2022-08-04 22:54 北京第二外国语学院成都附属中学 C++

关注

牛客2022年七夕题解

嘿！这里是七夕甜蜜题解！
今天你是否有和喜欢的人一起干喜欢的事情呢?偶尔让对象一起感受一些比赛的激情或许她就可以体会到你为什么喜欢打比赛了吧！

A:宝藏（出题人：小沙）

首先题目的名字是宝藏，对于一个人来说，他想要的东西就是一个宝贝，那么对本题来说，你想要的东西是什么呢，显然是AC或者答案，所以你可以点击题目中的AC或者答案进入游戏页面，然后还原魔方就可以得到答案了，如果你不知道怎么提取RGB的话，在本题样例中给定了一个色块，你可以选择一些取色工具来获得这个颜色的RGB。

对于不想拼魔方或者不会拼魔方的人来说，F12也是一个不错的选择，这里我没有选择将属性以js的方式注入，而是选择放在css里面，让大家找的快一点，当然由于#114514是16进制的表示，所以你可能会产生一次罚时。

ps:114514不是出题人的本愿

B:小红的孑串查询（出题人：兰子）

根据题目描述里的计算式 $1847/13/27/37/77*31*2$ ，不难算出，该数等于0.114514 114514……的循环。

我们讨论随机选一段长度为 $k$ 的子串，对于首位取在"1"、"1"、"4"、"5"、"1"、"4"中任意一个可以得到一个子串数量，而这六个位置显然是等概率的（因为是无限循环小数）。从而我们可以算出最终的期望：当长度模6为5时，期望为整数（例如，长度11的子串114514数量永远为1），长度每增加1，期望则增加 $\frac{1}{6}$

参考代码：

#include <bits/stdc++.h>

using namespace std;

#define ll long long
int mod=1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1,a=a*a%mod;
    }
    return res;
}
ll inv(ll x){
    return power(x,mod-2);
}
void solve(){
    ll k;cin>>k;
    ll cnt=k/6,cnt2=max(cnt-1,0LL);
    ll c=k%6+1;
    ll a=(cnt*c+cnt2*(6-c))%mod*inv(6)%mod;
    cout<<a;
}

int main()
{
    solve();
    return 0;
}

C:小红的情侣系统（出题人：兰子）

本题本意是想玩个梗，顺便让大家百度去检索答案（不会真有人所有番都看过吧，滑稽），不过看大家过题太吃力了，于是在赛中削弱了以下两个版本：

给出了所有人物的名字——罗马音对应。
后宫番输入男主名字时，输出任意女主都算通过;特殊的输入雪菜时输出春希或冬马都算通过，输入冬马时同理。
考虑到有没加寒假集训营/多校群的选手，不知道群里的jiangly-heltion的cp梗，因此删除了heltion输入，修改了spj，如果输入jiangly时，输出heltion或aqua都算通过。

下面给出本题出现过的人物所在的番剧对应情况（给出角色名字和昵称）：

《刀剑神域》，网游番，又名SAO（推荐人：兰子）：

桐谷和人/桐人（kirito）：

alt

结城明日奈/亚丝娜（asuna）：

alt

《柑橘味香气》，百合番，橘里橘气梗的来源（推荐人：兰子）：

蓝原芽衣（mei）：

alt

蓝原柚子（yuzu）：

alt

《徒然喜欢你》，狗粮番（推荐人：小沙）：

菅原卓郎（takurou）：

alt

高野千鹤（chizuru）：

alt

高濑春彦（haruhiko）：

alt

神田沙希（saki）：

alt

《白色相簿2》，gal改，白学番（推荐人：兰子&嘤嘤）

北原春希（haruki）：

alt

小木曾雪菜（setsuna）：

alt

冬马和纱（kazusa）：

alt

《堀与宫村》，搞笑番（推荐人：嘤嘤）

堀京子（kyoko）：

alt

宫村伊澄（izumi）：

alt

仙石翔（kakeru）：

alt

绫崎礼美（remi）：

alt

《to love》，后宫番，又名出包王女（推荐人：兰子）

结城梨斗（rito）：

alt

菈菈（lala）：

alt

梦梦（momo）：

alt

娜娜（nana）：

alt

金色暗影（yami）：

alt

结城美柑（mikan）：

alt

《clannad》，gal改，催泪番（推荐人：嘤嘤）

冈崎朋也（tomoya）：

alt

古河渚（nagisa）：

alt

藤林杏（kyou）：

alt

《缘之空》，gal改，骨科番，番很烂游戏很好（推荐人：兰子）

春日野悠（haruka）：

alt

春日野穹（sora）：

alt

天女目瑛（akira）（本题中没出现但是提一下）：
alt

《school days》，gal改，柴刀番，番一般游戏神作（推荐人：兰子）

伊藤诚（makoto）：

alt

桂言叶（kotonoha）：

alt

西园寺世界（sekai）：

alt

《jiangly fan》

本来准备玩JHcp的梗，可惜很多不是群友或者平时不水群的同学不知道“H炉”的梗。下面介绍两位：

jiangly，中国顶尖算法选手，目前cf rating全球第二（8月4日晚）。
heltion，中国顶尖算法选手，目前cf红黑名。

（本题仅供娱乐，玩梗需适度，jls现实中也是有npy的！）

这道题原本是输入jiangly输出heltion，输入heltion时输出jiangly才能通过，但考虑到不知道这个梗的同学，因此后面删去了输入heltion的数据，当输入jiangly时输出heltion或者aqua时都算通过。毕竟jiangly也是老阿夸粉了，备注中的aqua图片也算一个小提示qwq

alt

D:潮or先辈（出题人：阿宁）

阿宁突然灵光一闪，两道题都会做了，现在正在和潮约会。
~~如果你不会做，你也可以和先辈约会。~~

数学题：
画一个二叉树如下：
图片说明
每次变化相当于两个儿子挑一个。
变化 $n$ 次就是第 $1$ 层走到第 $n+1$ 层。
观察上图，容易发现每一层的数是连续的，范围是 $[2^n,2^{n+1})$ 。
根据高中的等差数列公式得到（头加尾乘项数除2）： $\frac{(2^n+2^{n+1}-1) \times (2^{n+1}-2^n)}{2}$

根据期望等于概率乘以结果值，还需将上面算出的东西除以情况数得到答案 $\frac{(2^n+2^{n+1}-1) }{2}$

使用py，因为有一个小数，但是固定是5，算出整数位，再输出".5"。（py这么大的浮点数会寄）

代码：

n = int(input())
print(1, end=" ")
print((2**(n + 1) + 2 ** n - 1) // 2,end="")
print(".5")

（一开始想的一个做法是考虑贡献的，后面发现这堆数是连着的...）

程序题：
根据潮提示的"先辈"，可能的seed有114514和114514 1919810？（连起来会被河蟹）
隔壁"小红的孑串查询"题和本题联动，告诉seed是114514 1919810。

（本来是想让大家猜一下的）
代码：

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const LL seed = 114514 1919810LL;

int main() {
    int n;
    mt19937 rnd(seed);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        rnd();
    }
    cout << "2 " << rnd() << endl;
    return 0;
}

E:七夕心动（出题人：小七）

当ｔ大于等于8192时输出0，小于直接两重循环暴力即可。

证明：

1 ：A中若有任意一段的异或和为0，则答案显然为0。

2 ：设ｔ为8192，则Ａ的8192个前缀异或和的值中必然存在一组相同的值（或者存在0），即preXOR_l = preXOR_r，根据异或的基本定理可知[A_l ～A_r]异或和为0。

Code :

#include <bits/stdc++.h>



const int mod = 1777777777;

int main() {
    int64_t t, ans(1);
    std::cin >> t;
    std::vector<int> v(t);
    for (auto& i : v) std::cin >> i;
    if (t > 8191) return std::cout << 0, 0;
    for (int i = 0; i < t; ++ i) {
        int Xor = 0;
        for (int j = i; j < t; ++ j) {
            Xor ^= v[j];
            ans = ans * Xor % mod;
        }
    }
    return std::cout << ans, 0 ^ 0;
}

F:把喜欢藏进代码里（出题人：派派）

题意

摘取出代码中的所有注释，并使用　std::quoted 输出。
题目保证多行注释都在一行中。

解答

小心 php 与转义字符（如果不使用 std::quoted 的话），除此之外都十分容易。
实际的数据远远小于 $1314520$ 字符。
祝大家七夕与意中人共度良宵！

参考代码

#include <bits/stdc++.h>

using lang = enum { C, HTML, PYTHON, size };

static const std::string opens[lang::size] = { "/*", "<!--", R"(""")", };
static const std::string closes[lang::size] = { "*/", "-->", R"(""")", };
static const std::string lines[lang::size] = { "//", "", "#", };

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);

  std::string filename;
  std::cin >> filename;
  filename = filename.substr(filename.find('.') + 1);

  int id = filename == "html" ? lang::HTML : filename == "py" ? lang::PYTHON : lang::C;
  int isPhp = filename == "php";

  std::string op = opens[id];
  std::string ed = closes[id];
  std::string ln = lines[id];

  int line;
  std::cin >> line;
  std::cin.ignore();

  for (int i = 0; i < line; ++i) {
    std::string s;
    std::getline(std::cin, s);

    int n = s.size();

    for (int j = 0; j < n; ++j) {
      if (bool ok = isPhp && s[j] == '#'; id != lang::HTML && (s.substr(j, ln.size()) == ln) || ok) {
        std::cout << "#" << i + 1 << ": "
                  << std::quoted(s.substr(j + (ok ? 1 : ln.size())))
                  << "\n";
        break;
      }

      if (s.substr(j, op.size()) == op) {
        std::string res;
        j += op.size();
        while (j < n && s.substr(j, ed.size()) != ed) {
          res += s[j++];
        }
        std::cout << "#" << i + 1 << ": " << std::quoted(res) << "\n";
      }
    }
  }

  return 0 ^ 0;
}

G:心有灵犀一点通（出题人：嘤嘤。兰子友情提供最后两题，原来的两道题过于牛头人被纯爱战神小沙砍了）

根据第一题的选择，即为与你比较心意之人，同步率达到百分之七十（十个对七个，第一题无论选谁都会是正确的）即可，可以翻正确通过的代码寻找正确答案。

关于sjjj的?解释说明：由于嘤嘤设置选项一开始非常的牛头人，作为纯爱战神的sjjj非常生气，所以选择了两个?，在sjjj不断的谴责下，后来嘤嘤增加了两个非牛头人选项，但是笨蛋王-嘤嘤不知为何spj出现了问题，所以sjjj变成了地狱选项，需要在剩余的7个中选对6个才可以。

本题的spj代码：

#include<bits/stdc++.h>
#define AC 0
#define WA 1

using namespace std;

int main(){
    string s;
    ifstream cin("user_output");
    auto check = [&](string a,string b)->int{
        int ans=0;
        for(int i=0;i<10;i++)
            ans+=a[i]==b[i];
        return ans;
    };
    cin>>s;
    if(s.size()!=10) return WA;
    string sjjj="ABD?DDA?AC";
    string lzjj="BAAEBABBBD";
    string yymm="CCCADCBABD";
    string qcjj="DECFCCBBBD";
    string angg="EEABCBADBA";
    int ans=0;
    if(ans) ans=0;
    else if(s[0]=='A') ans=check(s,sjjj);
    else if(s[0]=='B') ans=check(s,lzjj);
    else if(s[0]=='C') ans=check(s,yymm);
    else if(s[0]=='D') ans=check(s,qcjj);
    else if(s[0]=='E') ans=check(s,angg);
    if(ans>=7) return AC;
    return WA;
}

H:过了这道题你就能找到对象（出题人：嘤嘤）

短边长为2时，构造方法显然：

1 1 4 5 1 4 1 1 4 5 1 4
5 1 4 1 1 4 5 1 4 1 1 4

短边长大于等于3且场边长大于3时（即至少为3*4的矩阵），无解：

5 x x x    0 0 x x    5 x x x    0 x x 0
0 x x x    0 5 x x    0 x x x    5 x x 5
0 0 5 0    0 0 x x    0 0 0 5    0 x x 0

某一个坐标(x,y)为5，则与(x,y)曼哈顿距离不超过3的位置都不可以填5，那么，一定会存在至少一个2*3的子矩阵，离5的曼哈顿距离都小于等于3（例如上例中的x）

若矩阵为3*3，则有一个精妙的构造：

4 1 4
1 5 1
4 1 4

过了这道题你不一定能找到对象，但至少你能找到homo！

——by 世界第一可爱的嘤嘤嘤
图片说明

I:清楚姐姐的统计（idea：qcjj 数据：小沙）

清楚姐姐在统计多校发衣服时遇见的问题，然后就把他出成题目了，要你们不好好填表，累死qcjj了！

本题只需要对每行字符串处理一些，对于一行只有一个码号的适合进行特判，其他情况读取字符串后查看后面尺码进行计数即可。

注意输出的字符串后面可能会存在空格2333。

code:

#include<bits/stdc++.h>
using namespace std;
int cnt[10];    
string f(string s){
    for(char &x:s)if(x>='a')x-=32;
    if(isdigit(s[0])){
        string t;
        for(int i=1;i<=s[0]-'0';i++)t+="X";
        t+="L";
        s=t;
    }
    return s;
}
int get(string s){
    if(s=="ONE")return 1;
    else if(s=="TWO")return 2;
    else if(s=="THREE")return 3;
    return 0;
}
map<string,int> mp;
string ans[]={"M","L","XL","XXL","XXXL","XXXXL","XXXXXL"};
int main(){
    string s;
    for(int i=0;i<7;i++)mp[ans[i]]=i;
    while(getline(cin,s)){
        while(s.size()&&s.back()==' ')s.pop_back();
        stringstream ss(s);
        string a;
        int res=3;
        while(ss.rdbuf()->in_avail()!=0){
            ss>>a;a=f(a);
            int x=get(a);
            if(x==0){
                x=mp[a];
                if(ss.rdbuf()->in_avail()==0){
                    cnt[x]+=res;
                    res=0;
                }
                else{
                    cnt[x]++;
                    res--;
                }
            }else {
                string b;ss>>b;
                b=f(b);
                cnt[mp[b]]+=x;
                res-=x;
            }
        }
    }
    for(int i=0;i<7;i++)cout<<cnt[i]<<" \n"[i==6];
}

J,K:温温的那些年（出题人：温巨）

判断序列的可图性，经典的Havel-Hakimi定理。
1，Havel-Hakimi定理主要用来判定一个给定的序列是否是可简单图化的。
2，首先介绍一下度序列：若把图 G 所有顶点的度数排成一个序列 S，则称 S 为图 G 的度序列。
3，一个非负整数组成的有限序列如果是某个无向图的序列，则称该序列是可简单图化的。
4，判定过程：（1）对当前数列排序，使其呈递减，（2）从S[2]开始对其后S[1]个数字-1，（3）一直循环直到当前序列出现负数（即不可简单图化的情况）或者当前序列全为0 （可简单图化）时退出。
5，举例：序列S：7,7,4,3,3,3,2,1 删除序列S的首项 7 ，对其后的7项每项减1，得到：6,3,2,2,2,1,0，继续删除序列的首项6，对其后的6项每项减1，得到：2,1,1,1,0，-1，到这一步出现了负数，因此该序列是不可简单图化的。
easy直接模拟即可，复杂度O(n^2logn)
hard的情况下可以用线段树等数据结构进行优化，重点是维护序列的单调非增。我的做法是假设需要减一的最小值为x，且一共需要对k个x进行操作，那么就从最后一个x开始减1，
比如当前的度序列为2 2 1 1 1, 我们需要对一个2和一个1进行操作，那么我们就在第二个2（第一个2已经被删了）和最后一个1上减去1，整个序列变为1 1 1 0.
执行这个操作需要我们找到剩下序列里第k大的数，找到这个数在序列里第一次出现和最后一次出现的位置，以及对对应的区间的所有元素减一，这些操作都可以用线段树实现。

Code :

#include<bits/stdc++.h>
using namespace std;
#define len(i) (R[i] - L[i] + 1)
int L[2000010], R[2000010], tag[2000010], first[2000010], last[2000010];
int a[500010];
void build(int i, int l, int r)
{
    L[i] = l;
    R[i] = r;
    tag[i] = 0;
    first[i] = a[l];
    last[i] = a[r];
    if(l==r)
    {

        return;
    }
    int mid = (l+r) >> 1;
    build(i<<1, l, mid);
    build(i<<1|1, mid+1, r);
}
void pushdown(int i)
{
    if(tag[i])
    {
        tag[i<<1] += tag[i];
        tag[i<<1|1] += tag[i];
        first[i<<1] += tag[i];
        last[i<<1] += tag[i];
        first[i<<1|1] += tag[i];
        last[i<<1|1] += tag[i];
        tag[i] = 0;
    }
}
void update(int i,int l,int r,int delta)
{
    if(l > r) return;
    if(l <= L[i] && r >= R[i])
    {
        tag[i] += delta;
        first[i] += delta;
        last[i] += delta;
        return ;
    }
    pushdown(i);
    int mid = (L[i]+R[i]) >> 1;
    if(l <= mid) update(i<<1, l, r, delta);
    if(r > mid) update(i<<1|1, l, r, delta);
    first[i] = first[i<<1];
    last[i] = last[i<<1|1];
}
int query_val(int i, int x)
{

    if(R[i] == x) return last[i];
    pushdown(i);
    int mid = (L[i] + R[i]) >> 1;
    int ans = (x<=mid)? query_val(i<<1, x) : query_val(i<<1|1, x);
    first[i] = first[i<<1];
    last[i] = last[i<<1|1];
    return ans;
}
int query_left_bound(int i, int x)
{
    if(L[i] == R[i]) return L[i];
    pushdown(i);
    int ans = (x < last[i<<1])? query_left_bound(i<<1|1, x):query_left_bound(i<<1, x);
    first[i] = first[i<<1];
    last[i] = last[i<<1|1];
    return ans;
}
int query_right_bound(int i, int x)
{
    if(L[i] == R[i]) return R[i];
    pushdown(i);
    int ans= (x > first[i<<1|1])? query_right_bound(i<<1, x):query_right_bound(i<<1|1, x);
    first[i] = first[i<<1];
    last[i] = last[i<<1|1];
    return ans;
}
int n;
bool cmp(int a, int b){
    return a>b;
}
int main()
{

        scanf("%d", &n);
        for(int i=1;i<=n;i++)scanf("%d", a+i);
        sort(a+1, a+n+1, cmp);
        build(1,1,n);
        bool flag = true;
        for(int i=1;i<=n;i++)
        {
            int k = query_val(1, i);
            if(!k) break;
            if(k>n-i)
            {
                flag = false;
                break;
            }
            int j = i + k, sum_j = query_val(1, j);
            if(sum_j < 1) 
            {
                flag = false;
                break;
            }
            int left_bound = query_left_bound(1, sum_j), right_bound = query_right_bound(1, sum_j);
            if (left_bound > i+1)
            {
                update(1, i+1, left_bound-1, -1);
                update(1, right_bound - (j - left_bound + 1) + 1, right_bound, -1);
            }
            else
            {
                update(1, right_bound - (j - i) + 1, right_bound, -1);
            }
        }
        printf((flag)?"YES\n":"NO\n");
    return 0;
}