2021-01-04 15:16 已编辑牛客运营

关注

【题解】牛客2020跨年场

题解赛后在本贴更新~

A 关于元旦的冷热知识

　　1、“元旦”是从什么时候开始指代公立新年的？（D）
　　A、1840年 B、1911年 C、1945年 D、1949年
公元1911年，***领导的辛亥革命推翻了满清的统治，建立了中华民国。各省都督代表在南京开会决定使用公历纪年，当时也曾有过把公历称为“元旦”而把农历岁首称为“春节”的说法，仅在与会的部分人员之间流传，并未做正式定名区分。为了“行夏正，所以顺农时，从西历，所以便统计”，民国元年决定使用公历（实际使用是1912年），并规定阳历1月1日为“新年”，但并不称为“元旦”。
1949年9月27日，中国人民政治协商会议第一届全体会议通过“中华人民共和国纪年采用公元纪年法”，农历正月初一称为“春节”，公历1月1日定为“元旦”。至此，“元旦”成为人们欢度的节日，传统年节也受到了应有的关注。

　　2、“元旦”还有什么别称吗？（ABCD）
　　A、元日 B、元正 C、元辰 D、正朔
　　元旦别称（挂一漏万，敬请指正）：
　　上日。《书·尧典》：“正月上日，受终于文祖。上日乃朔日，古特指正月初一。”
　　正日。《四民月令》：“正月元旦，是谓正日。”
　　正朔。《礼记大传》：“正谓年始，朔谓月初，故以此称一年之始日。”
　　正旦。《后汉书陈翔传》记载：“时正旦朝贺，大将军梁翼威仪不整。”
　　三始。《汉书·鲍宣传》：“今日蚀于三始，诚可畏惧。以其为岁之始，月之始，日之始，故云。”
　　岁朝。《后汉书·周磐传》：“岁朝会集诸生，讲论终日。”李贤注：“岁朝，岁旦。”
　　履端。《哀江南赋》：“天子履端废朝，单于长围高宴。”《幼学琼林岁时》：“履端是初一元旦。”
　　开元。《梁书·武尚纪》：“今开元发岁，品物惟新，思俾黔黎，告示安旧新。指新年开始，故称。”
元辰。《扬朝赋》：“岁惟元辰，阴阳代纪；履端归余，三朝告始。”

　　3、“元旦”这个词最早出现在什么地方？（D）
　　A、汉代（崔瑗《三子钗铭》中叫“元正”）
　　B、晋代（庾阐《扬都赋》一赋中称作“元辰”）
　　C、唐代（《晋书》：“颛帝以孟夏正月为元，其实正朔元旦之春。 ”）
　　D、南北朝（南朝梁人萧子云《介雅》诗:“四气新元旦，万寿初今朝。”）
ab选项没出现元旦这个词，cd当中南北朝当然在隋唐前面啊，当然南北朝比较早了。

　　4、“元旦”两个字的含义：（A）
　　A、元者始也，旦者晨也。
　　B、元为根本，旦为一日。
　　C、元称整体，旦称明亮。
　　D、元即原来，旦即天亮。
这个没什么好解释的吧……

　　5、元旦又被称为“三元”，因为这一天同时是：（ABC）
　　A、岁之元 B、季之元 C、月之元 D、日之元
元”为始、开端的意思,农历正月初一这一天为年、季、月之始,故称“三元”

　　6、古人对新年最开始的几天还有一些别称，比如将初四称为“猪日”等等，那么元旦这一天对应的是：（C）
　　A、牛日 B、羊日 C、鸡日 D、狗日
　　古代，每年正月初七日以前是为“说畜日”，初一是鸡日；初二是狗日；初三是猪日；初四是羊日；初五是牛日；初六是马日。六畜排完了，才轮到初七是“人日”。
旧时中国民间《农家杂事》一书中，说此种排法原因有三：一说是按人类驯服六畜的次序排，鸡最先驯养成家畜，狗次之，其它依次类推。二说是按六畜的大小排列，鸡、狗体积较小，排在前面，牛、马体积较大，排在后面。三说是按六畜和人的远近排列，俗说，没有鸡狗不成家。

　　7、王安石有诗：“千门万户曈曈日，总把新桃换旧符”，元旦自然要换门神，那么，以下哪两位门神因为出身不好只能被贴在牛棚，马厩，猪圈这种地方守卫六畜？（B）
　　A、神荼、郁垒 B、孟良、焦赞 C、秦叔宝、尉迟恭 D、孙膑、庞涓
　　从历史传说、神话传说、小说中请出来当门神的武将不胜枚举，孙膑，庞涓，萧何，韩信，关于，赵云，岳飞，岳云，岳雷，牛皋，孟良，焦赞，戚继光，甚至《封神演义》里的哼哈将，赵公明，燃灯道人等等，都曾被人们请出来当过门神。不过，因将军们出身作为的不同，人们请出来当门神时，也有些地位上的区分。如《杨家将》里的孟良、焦赞，他俩投降杨家军营为大宋效力之前，都曾是绿林强盗，焦赞又曾到辽邦盗取过被夺的宝马。因此，尽管后来两人也有些英名，人们也请他俩做门神，但一般是请来贴在牛棚、马厩、猪圈、羊栏门上，让他们守卫保护六畜，而不用他们把守正门。又如，赵公明和燃灯道两人曾斗宝，后来赵公明还被姜子牙封了财神，两人有财有宝，因此人们便一般请他两位来把守仓门或厨房门。还有《西游记》里说魏征斩了小白龙，小白龙要到宫中找唐太宗索命，因大殿前门有秦琼、敬德守卫；便从后宰门出入宫殿。魏征知道了便持剑在后门把守，宫中才又恢复了安宁。据此有些地方便也请魏征做门神，但一般是贴在后门，于是魏征做了后门门神。另外据说被玉皇大帝封了“驱魔帝君”的钟馗，其地位不大稳定，有时被人们请来挂在正厅里坐镇大堂镇邪辟鬼，有时被贴在栏门上当“打猪鬼”有时替魏征把把后门，当当后门门神。
——《吉庆有余年画》

　　8、说起桃符就自然想起了春联，那么，现存的最早的春联是：（C）
　　A、王羲之：春风春雨春色，新年新景新家
　　B、孟昶：新年纳余庆，嘉节号长春
　　C、刘丘子：三阳始布；四序初开
　　D、朱元璋：双手劈开生死路，一刀割断是非根
朱元璋在明朝，时间最晚先排除；王羲之虽然时间最早，但他的故事属于后人敷衍，并无可靠的史料记载；孟昶为五代后蜀皇帝，这一条春联出自《宋史》；而“三阳始布；四序初开”为敦煌文书，撰联人为唐人刘丘子，作于开元十一年(723年)，时间最早。

　　9、过节最期待的事情当然是放假，那么唐代的元旦，一共能放几天假？（D）
　　A、不放；打工人只要工作，要什么假期！
　　B、一天；一年到头只工作不休息是会猝死的！
　　C、三天；毕竟是过年，好歹要有个走亲戚的时间不是。
　　D、七天；你以为现在过年放七天假的传统哪儿来的？（误）
唐玄宗颁行《假宁令》“元正、冬至，各给假七日。”这里的“元正”指的是新年，意思是说，春节放假7天，但唐朝的春节是按“元正前后各三日”放的。也就是说，以大年初一为中心，初一之前放假三天，初一之后放假三天，加上初一，刚好七天假。

　　10、元旦作为岁首，古已有之，那么元旦是什么时候开始固定到正月一日的？（D）
　　A、传说中的尧舜禹汤
　　B、周武王
　　C、秦始皇
　　D、汉武帝
中国的“元旦”这一概念，历来指的是正月一日。“正月”的计算方法，在汉武帝时期以前也是很不统一的。因此，历代的元旦月、日也并不一致。夏时期的夏历以春季一月为正月，商时期的殷历以冬季十二月为正月，周时期的周历以冬季十一月为正月。秦始皇统一中国后，又以冬季十月为正月，即十月初一为元旦。从汉武帝起，规定春季一月为正月，把一月的第一天称为元旦，一直沿用到清朝末年。

　　11、在过年没有鞭炮可以放的时候，古人用什么来代替鞭炮增加元旦的气氛？（A）
　　A、把竹子扔进火里
　　B、用鞭子抽出响声
　　C、乐器演奏的音乐
　　D、小孩子的吵闹就够了，还要什么自行车
“爆竹声中一岁除”，爆竹爆竹，当然是把竹子扔进火里听竹子被烧爆的声音啊！

　　12、人的感情总是相通的，现在的我们讨厌拜年，但其实，古人也未必喜欢拜年这种劳心劳力的事情，那么当古人嫌拜年太麻烦偷懒不想出门的时候，会采取什么方式代替拜年呢？（C）
　　A、派家中子弟代替自己四处拜年去，年轻人嘛，就应该多见识见识，老人这是为你们好！
　　B、派仆役把自己写好的信送到对方家里，腿倒是不累了，手累。
　　C、仆役还是要派的，但仆役也是会偷懒的，把主人写好的名帖往人家门口的红纸袋子里一扔了事，你说这家人和我家主人不认识？啊，看了名帖不就认识了嘛。
　　D、不行！从小老人就说过，过年不去拜年要挨揍的，只要下得了床，就能拜得了年！扶我起来，我还能走！
　　汉族民间拜年之风，汉代已有，宋代以后便十分盛行，有时因四处拜年，分身乏术于是某些不必亲自登门的地方便改用名帖投贺。到了明代以后，由于投名帖贺年之风遍及城镇各地，所以好多人都在门上贴一红纸袋，上书主人姓氏，名为“门簿”，以便接纳名帖。对此，《良斋杂记》曰:“拜年无论识与不识，望门投帖滨主，登簿而已。”《菽园杂记》也曰:“士庶人各拜其亲友，多出实心，朝官往来，则多泛受不专。如东西饫安街，朝官居住最多淫此者，不同识与不况望门投刺，有不下马或者不至其门令人送名帖者口仆应门，则皆却而不纳，或有闭门不纳者。”以致投名帖拜年成为虚应之事，明代文学家文征明有《拜年》诗：“不求见面惟通谒，名纸朝来满敝庐。我亦随人投数纸，世情嫌简不嫌虚。”
　　——《汉族风俗史第四卷·明代及清代前期汉族风俗》

　　13、古人没有饮料，遇见什么节日都喜欢喝点酒，那么新年这一天喝的酒有什么不同寻常之处吗？（C）
　　A、我只管喝酒，没注意那么多。
　　B、长幼有序，要喝酒也应该是老人先喝。
　　C、过年自然和平常不一样，今天的酒要最年轻的先喝。
　　D、佛系，酒杯递到谁手里谁先喝。
《荆楚岁时记》：“俗有岁首用椒酒，椒花芬香，故采花以贡樽。正月饮酒，先小者，以小者得岁，先酒贺之。老者失岁，故后与酒。”年纪小的孩子，过年了就长一岁，值得庆贺；而老年人过年了则意谓着少了一个年头，变老了，因为一年比一年老，故并不是值得庆贺的事情，所以最后喝。

　　14、广义的过年要到正月十五才结束，而初一到十五之间有一天最为重要，又被称为人日，请问人日是哪一天？（D）
　　A、初一 B、初三 C、初五 D、初七
见第六题解析。

　　15、最后，作者实在憋不出来了系列：以下哪首诗是写元旦的？（AD）
　　A、燎火委虚烬，儿童衒彩衣。
　　B、火树银花合，星桥铁锁开。
　　C、江山也似随春动，花柳真成触眼新。
　　D、梅花枕上听司晨，起绾金章候拜亲。
　　AD写元旦，B写正月十五上元节，C写立春。
元日感怀
作者：刘禹锡
振蛰春潜至，湘南人未归。
身加一日长，心觉去年非。
燎火委虚烬，儿童衒彩衣。
异乡无旧识，车马到门稀。
正月十五夜
作者：苏味道
火树银花合，星桥铁锁开。
暗尘随马去，明月逐人来。
游伎皆秾李，行歌尽落梅。
金吾不禁夜，玉漏莫相催。
次韵文潜立春日三绝句
作者：黄庭坚
江山也似随春动，花柳真成触眼新。
清浊尽须归瓮蚁，吉凶更莫问波臣。
新年
作者：文天祥
梅花枕上听司晨，起绾金章候拜亲。
喜对慈颜看铺鬓，发虽疏脱未如银。

B 牛牛想起飞

B题数据赛后有加强，不进行统一重测，需要测试的同学可以提交自己之前代码进行检测

观察数据范围 $1 \leq n \leq 10^5, 1 \leq y \leq 100$ ，显然支持 $O(ny)$ 时间复杂度的算法。

由于每一位数字都可以有三种状态：

$a_i := a_i + b_i$
$a_i := a_i - b_i$
$a_i := a_i$

不妨设 $dp[i][j][k]$ 为第 $i$ 个位置，状态为 $j$ ，此时能否得到模 $y$ 意义下为 $k$ 的结果。显然有转移方程：

$dp[i][0][k] \ |= dp[i - 1][j][((k - a[i] - v[0]) % y + y) % y]$
$dp[i][1][k] \ |= dp[i - 1][j][((k - a[i] - v[1]) % y + y) % y]$
$dp[i][2][k] \ |= dp[i - 1][j][((k - a[i] - v[2]) % y + y) % y]$

其中 $v[0] = 0, v[1] = -b[i], v[2] = b[i]$ ，注意负数取模即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N];
bool dp[N][3][105]; // 不变化 加b[i] 减b[i] %y意义下最大
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n, y; 
  cin >> n >> y;
  for(int i = 1; i <= n; i++) cin >> a[i];
  for(int i = 1; i <= n; i++) cin >> b[i];
  memset(dp, false, sizeof(dp));
  dp[0][0][0] = true;
  for (int i = 1; i <= n; i++) {
    for (int k = 0; k < y; k++) {
      vector<int> v;
      v.emplace_back(0);
      v.emplace_back(-b[i]);
      v.emplace_back(b[i]);
      for (int j = 0; j < 3; j++) {
        dp[i][0][k] |= dp[i - 1][j][((k - a[i] - v[0]) % y + y) % y];
        dp[i][1][k] |= dp[i - 1][j][((k - a[i] - v[1]) % y + y) % y];
        dp[i][2][k] |= dp[i - 1][j][((k - a[i] - v[2]) % y + y) % y];
      }
    }
  }
  int ans = 0;
  for (int k = 0; k < y; k++) {
    for (int j = 0; j < 3; j++) {
      if (dp[n][j][k]) {
        ans = k;
      }
    }
  }
  cout << ans << '\n';
  return 0;
}

C 最小互质数

首先可以确定答案要么为 $1$ ，要么为一个质数，所以我们只要把 $10 ^ 5$ 以内的质数筛出来，然后对这 $n$ 个数进行质因子分解即可，没在这些因子出现的质数即为我们的答案。当然我们还得特判这 $n$ 个数中是否出现 $1$ ，如果没有出现 $1$ ，那么答案就是 $1$ 了。

筛质数也是可 $n \sqrt n$ 暴力的。

D 衔尾蛇

因为n的最大值不超过12，所以可以状压枚举。
这里共有3种颜色，所以显然要用三进制的状压。
枚举一共用 $i$ 条蛇 $(1≤i≤n)$ ，一共有 $3^i$ 种状态。由于衔尾蛇是一个有向环，所以每种状态注意要判重，这里判重方法可以用环形字符串的方式（也可以重载set的等于号但很麻烦）
这道题递归写dfs理论上也可做。
总复杂度 $O(3^n*n^2)$

#include<bits/stdc++.h>
using namespace std;
set<string>s;
int main(){
    int a,b,c,i,j,k,z,cnt=0;;
    cin>>a>>b>>c;
    int sum=1;
    int n=a+b+c;
    for(j=1;j<=n;j++){    //枚举长度为j
        sum*=3;
        for(i=0;i<sum;i++){    //共i种状态
            int p=i,ca=0,cb=0,cc=0;
            string temp="";
            for(k=0;k<j;k++){        //p转为三进制代表状压值
                if(p%3==0)temp+='a',ca++;
                if(p%3==1)temp+='b',cb++;
                if(p%3==2)temp+='c',cc++;
                p/=3;
            }
            if(ca>a||cb>b||cc>c)continue;    //判断合法

            for(k=0;k<j;k++){        //判重
                string ttemp="";
                for(z=k;z<k+j;z++){
                    ttemp+=temp[z%j];
                }
                if(s.count(ttemp))break;
            }
            if(k==j){
                s.insert(temp);
              //  Ouroboros->hikari->tairitsu->kou
                cnt++;
            }
        }
    }
    cout<<cnt;

}

E 牛牛的反函数

乍一看的话会写一个直接输出2^k的程序。
但是由于限定了定义域范围，这样大于60的情况构造不出导致WA。
所以这道题隐含限制条件是找到一个尽可能小的x满足F(x)=y。
然后瞎搞搞暴力找找规律发现大于120以后无解。

1、直接构造
对于x较小的时候直接输出2^(y-1)。
接下来分情况讨论，若y为奇数输出2^(y/2)+3。若y为偶数输出2^(y-1)+1。

2、递推法
从1开始倒着递推上去。为了让反函数的值尽可能小，贪心的每次做2后都-1是最优的。
前两次都是2，接下来*2操作和-1操作交替即可。

F 开心消消乐

这题本来要出nlogn的写法？？

好像出题人与验题人与清楚姐姐一致不同意的样子

就改成了 $n^2$ 的模拟

首先确定第一个答案肯定不删除，不删除的的答案就是正常的模拟一遍栈匹配就可以了

接着考虑删除哪一段区间， $n$ 的大小设置为10000，所以可以直接暴力枚举删除哪一段区间，最后取答案的最小值，作为ans

因为匹配完后，栈内一定是111000这种组合。

考虑删除一段区间后的答案怎么计算：

记录两个前缀

一个前缀 $pre_i$ 表示前i个不删除，匹配后还剩多少个数字
另一个前缀 $prea_i$ 表示前i个不删除，匹配后从栈顶开始连续的0的数量

记录两个后缀

一个后 $suf_i$ 表示后n-i+1个不删除，匹配后还剩多少个数字

另一个后 $sufa_i$ 表示后n-i+1个不删除，匹配后从栈顶开始连续的1的数量

所以对于一段满足区间[i,j]，就只需要：

判断是否可以删除
如果可以删除，对 $pre[i-1] + suf[j+1] - 2*min(prea[i-1],suf[j+1])$ 取最小值即可

G CoolCool的序列

首先G题在这赔罪了.

由于出题人的考虑疏忽，写错了一部分数据

非常抱歉影响了大家的跨年体验

说一下思路：

根据桶排的方法，存一下每个数出现的位置，及翻转后出现的位置。

问题转为：对于每个数的两个数组，如何排序使得绝对值差值的和最小，那么肯定是从小到大了..

所以只需要排序之后，将答案累加即可

最后不要忘记/2

H 牛清楚的裙子

由于每条裙子被选中的概率相同,这点可以认为 $n$ 条裙子没有差异

那么定义 $f[i]$ 为已经穿过 $i$ 条裙子,为了达到终止条件,期望还需要穿几次

$f[i]=\frac{i}{n}f[i]+\frac{n-i}{n}f[i+1]+1$

意思是,选中穿过的裙子概率 $\frac{i}{n}$ ,选中没穿过的 $\frac{n-i}{n}$ ,然后本次也需要穿 $1$ 次裙子

那么化简得到 $f[i]=f[i+1]+\frac{n}{n-i}$

那么 $f[0]=\sum\limits_{i=0}^{n-1}\frac{n}{n-i}$

上面提到每条裙子无差异,可以认为被穿过的次数相等,所以除以一个 $n$

每条裙子期望被穿过 $\frac{1}{1}+\frac{1}{2}+\frac{1}{3}...+\frac{1}{n}$

不难发现这个时候只需要预处理这个调和级数的前缀和就可以 $O(1)$ 知道每条裙子被穿过的期望次数

然后输出答案即可...

其实这是个经典的"邮票收集问题"，知道就很好写啦

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 5;
double f[maxn];
int main()
{
    for(int i=1;i<=10000000;i++) f[i] = f[i-1] + 1.0/i;
    int T; cin>>T;
    while(T--)
    {
        int n; scanf("%d", &n);
        double ans = (n-1) * f[n] + f[n] * 10000;
        printf("%.7f\n", ans);
    }
}

本场比赛出题团共有7位出题人(有一位小姐姐出题人！),希望大家玩的开心~

出题人1: 那我就愉快地抱走雨姐姐了，嘿嘿！

出题人2：图片说明