竞赛讨论区 > 【题解】牛客2020跨年场
头像
王清楚
编辑于 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题数据赛后有加强,不进行统一重测,需要测试的同学可以提交自己之前代码进行检测

观察数据范围,显然支持 时间复杂度的算法。

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

不妨设 为第个位置,状态为 ,此时能否得到模 意义下为 的结果。显然有转移方程:

其中 ,注意负数取模即可。

#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 最小互质数

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

筛质数也是可暴力的。

D 衔尾蛇

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

#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的写法??

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

就改成了的模拟

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

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

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

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

记录两个前缀

  • 一个前缀表示前i个不删除,匹配后还剩多少个数字

  • 另一个前缀表示前i个不删除,匹配后从栈顶开始连续的0的数量

记录两个后缀

  • 一个后表示后n-i+1个不删除,匹配后还剩多少个数字
  • 另一个后表示后n-i+1个不删除,匹配后从栈顶开始连续的1的数量

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

  • 判断是否可以删除
  • 如果可以删除,对取最小值即可

G CoolCool的序列

首先G题在这赔罪了.

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

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

说一下思路:

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

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

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

最后不要忘记/2

H 牛清楚的裙子

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

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

意思是,选中穿过的裙子概率,选中没穿过的,然后本次也需要穿次裙子

那么化简得到

那么

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

每条裙子期望被穿过

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

然后输出答案即可...

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

#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: 图片说明

出题人3: 图片说明

出题人4:图片说明

出题人5: 我是一个CoolCool的出题人,不cool就图片说明

出题人6: 图片说明

出题人7:我永远喜欢清楚姐姐!!!

希望大家可以玩的开心~

(这个比赛本来的名字应该是跨年AK场的,比赛说明本来时这样的:牛客为您准备了一场难度极其简单的比赛,希望大家都能AK~
后来收到了题以后,我就把比赛名称和比赛说明就改掉了

图片说明

(比赛期间随缘直播唠嗑,谁知道有没有呢,大概率是会咕的吧http://live.bilibili.com/22711151

全部评论

(19) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐