沙烬

2023-01-03 13:58 已编辑北京第二外国语学院成都附属中学 C++ 发布于北京

关注

牛客跨年题解

牛客2023年跨年五百AK赛！

AK人数还是没有赶上群名，悲。

这里小沙祝大家新年快乐！！！！

A:猜群名

首先对于每个题的字都是粗题加粗之后的。

也可以通过F12查看html标签。

每题信息一一对应为

ABCDEFGH

!AK百跨赛年

EGHDBCFA

跨年五百AK赛！

所以输出EDGHDCFA即可。

B:分赃

我们可以发现，对于一个数出现两次，他可以一人分一个，或者都给一个人，所以两人的积分差值不变，对于大于两个的，我们可以都给一个，分值不变，或者给一个人一个，其他全给另一个，分值变化 $1$ ，对于只有一个的，分值变化 $1$ ，所以可以将只有一个的先对半分，如果已经相等，你们其他的全给一个人，没有贡献，最后全部相等，如果分值相差 $1$ ，就看有没有大于两个的用来补齐，代码有

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    map<int,int> mp;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        mp[x]++;
    }
    int ans =0;
    for(auto [x,y]:mp)
        if(y==1)ans^=1;
        else if(y>=3)ans = 2;
    if(ans>=2 || ans ==0)cout<<"YES\n";
    else cout<<"NO\n";
}

C:翻卡牌

你可以使用全排列算出所有情况然后计算，时间复杂度最坏为 $9! \times 9$ 。也可以发现复制一份之后等价于乘以 $10^9 + 1$ ，而他是可以被 $7$ 整除的，所有答案恒为 $0$ 。直接输出0即可。

D:ygg的分数运算

由于 $a$ ， $b$ 都是质数，所以不会被其他的数约分掉，所以对于加法 $\frac{1}{a} + \frac{1}{b}$ 还是 $\frac{1}{a} \times \frac{1}{b}$ ，他们的分母都会变成 $a\times b$ ，且无法被除 $a,b$ 以外的因子约分掉，所以他的分母一定是 $a^{p_1} \times b^{p_2}$ 的形式，且 $0 \le p_1,p_2$ 。所以可以选择把因子 $a,b$ 排掉之后看剩余的是否为 $1$ 。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    while(c%a==0)c/=a;
    while(c%b==0)c/=b;
    if(c==1)cout<<"YES\n";
    else cout<<"NO\n";
}

E:摇色子

首先，对于本题给出对应的数字分别是 $114514$ ，不知道有没有人通过第3种方式测出来。

其次本体中每个数字都有 $6$ 个数据点，每个点正确的概率为 $\frac{1}{2}$ ，所以直接随机，如果能正确，那么你可以买彩票了~~~

所以本题考查的是将 $n$ 的参数加入到随机的srand中，这样可以保证对于相同的 $n$ 答案可以相同，这样的话每次猜中的概率为 $\frac{1}{2^6}$ 。他是可以接受的，多使几次就可以试出来。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    mt19937 rng(37 * 6 + n);
    cout << 1 <<" "<< rng() % 2 + 1 <<"\n";
}

F:回顾往昔

找到该账号，发现该账号只有一个视频是元旦那天发的，点击进去之后有你所以想要的信息，对于AV/BV号不知道的可以看一下网页网址，里面有哦~

G:李哥跨年

问跨年夜星期几，拿电脑看一下即可。

H:nana吃蛋糕

我们可以将当前所在坐标设为(i,j),可以发现，每一次移动都会将i+j 的奇偶性发生改变。而我们的起始点是在(1,1) 。如果是有奇数×奇数个格子，即n为奇数，那么nana是肯定可以将所有的格子都遍历完的，因为会偶数（n²−1）次地改变i+j的奇偶性，同时终点的x坐标＋y 坐标之和是一个偶数；如果是偶数×偶数个格子，那么肯定是需要放弃至少一个格子的，因为nana只能走奇数次。因为首尾都是i+j为偶数的格子，同时每次移动都会改变所在格子的奇偶性，那么肯定是需要把所有i+j为偶数的格子都用了才可以保证最优，所以(i,j)同奇偶的格子必须都走到，只能放弃一个(i,j)奇偶不同的格子。

对于变成为偶数的正方形，放弃 $(i,j)$ 不同的任意一个格子，仍然可以从 $(1,1) \to (n,n)$ 的证明：

首先，我们对该正方形进行切割，每两行划分为一块：

当我们经过没放弃格子的块时，从左上角出发，可以选择如下方法进行遍历：

即，我们从从左上角出发，一定能回到左下角，这样使得我在进入下一个块时，一定处于左上角。

当我们进入想要放弃格子的块时：

由于第一行是奇数行，所以无法到达的格子用红色标注。

当我们从左上角出发，采用如下方式进行遍历时，由于我们每次经过一列都会改变我们第一次到达该列的行数，即我们处于奇数列是，我们会在奇数行，在偶数列时，我们会在偶数行，所以当我们行进到红色格子该列时，我们一定与其位置不同，并且该列不会改变其奇偶性，所以我们最终会到达该块的 $(2,n)$ 格。

随后进入下一块会处于 $(1,n)$ 的位置，我们与最开始没块的方法形成一致：

即我们进入下一块也会处于 $(1,n)$ 的位置，直至到达 $(n,n)$ 。

#include<bits/stdc++.h>
using namespace std;
int  main(){
    int n;cin>>n;
    long long ans = 0,x = 1e9;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            long long c;
            cin>>c;
            ans += c;
            if(i%2 != j%2)
                x= min(x,c);
        }
    }
    if(n%2==0)
        ans-=x;
    cout << ans <<"\n";
}

（刚copy的祝福语）

冒泡排序，选择排序，插入排序，快速排序，堆排序，归并排序，希尔排序，桶排序，基数排序新年帮您排忧解难。

有向图，无向图，有环图，无环图，完全图，稠密图，稀疏图，拓扑图祝您新年宏图大展。

最长路，最短路，单源路径，所有节点对路径祝您新年路路通畅。

二叉树，红黑树，van Emde Boas树，最小生成树祝您新年好运枝繁叶茂。

最大流，网络流，标准输入流，标准输出流，文件输入流，文件输出流祝您新年顺顺流流。

线性动规，区间动规，坐标动规，背包动规，树型动归为您的新年规划精彩。

散列表，哈希表，邻接表，双向链表，循环链表帮您在新年表达喜悦。

O(1), O(log n), O(n), O(nlog n), O(n^2), O(n^3), O(2^n), O(n!)祝大家新年渐进步步高。

区间DP，树形DP，数位DP，概率DP，分数规划，线性规划，教你规划人生；

平衡树，划分树，归并树，k-d树，主席树，树套树，替罪羊树，让你运筹帷幄。

BFS，DFS，A*，记忆化，使你在大千世界里寻找难觅幸福；Bellman-Ford，Johnson，Floyd，Dijkstra，让你在匆匆人生中走上成功捷径。