第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛题解

第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛题解

先抱怨一下，这场比赛的题锅太多了，而且正赶上状态不好，Ac 1/12就离谱。。

H 数羊

给定$n,m(1\le n\le 10^9,0\le m\le 2)$，计算$A(n,m)$，以下给出$A(n,m)$公式：
$$?\begin{array}{l}A(1,0)=2\\ A(0,m)=1m\ge 0\\ A(n,0)=n+2n\ge 2\\ A(n,m)=A(A(n?1,m),m?1)n,m\ge 1\end{array}$$

做法非常多的简单题：不管是打表还是按照公式推都可做。但关键在于$m$的取值范围(一定要注意$m$的范围，不然打表轻松stackoverflow，我说怎么大家都说打表可做，我就stackoverflow了。。。)
在$m$的取值范围内，打表即可找出规律：
$$\begin{gathered} m=0时，A(n,0)=n+2; \\ m=1时，A(n,1)=2?n \\ m=2时，A(n,2)=2^n \end{gathered}$$

D Seek the joker I

$n(n\le 10^5)$张扑克牌的牌堆，最下面一张是龟牌，抽到的人输。现在每人每次至多抽$k(k\le 10^5)$张，至少抽一张。判断先/后手必胜。声明：本题中的所有角色在剧情发生时均已超过18岁。

yo xi no forever！
一个简单的巴什博弈。抽到第$n$张的人输，说明胜者抽走了第$n?1$张。
套一下巴什博弈公式即可

E Seek the joker II

$n(n\le 10^5)$张扑克牌的牌堆，从上往下第$x$张是龟牌，抽到的人输。现在每人可以在牌堆底/顶/同时抽任意张，但至少抽一张，并且在牌堆上下同时抽必须抽走相同数目的牌。判断先/后手必胜。声明：本题中的所有角色在剧情发生时均已超过18岁。

yo xi no forever！
一道威佐夫博弈题。但我当时没学过威佐夫博弈，还当是尼姆博弈变形来做。。。

龟牌将牌堆分为两部分，一部分为$x?1$张，一部分为$n?x$张。

引入概念：
局势：用$(a_k,b_k)$表示两堆牌中剩余牌的数量。称之为局势
奇异局势：如果处于某种局势下的一方必输，则称为奇异局势。

威佐夫博弈的结论是：

1. 第$i$个奇异局势的差值是$i$
2. 每一个状态的第一个都是以前没有出现过的最小非负整数。
3. $a_k=[\frac{k（1+\surd 5）}{2}]，b_k=a_k+k（k=0，1，2，\dots ,n)$为奇异局势的通式。

证明不会，贴个外链吧[证明]

判断：判$a_k$是否等于两数差值乘以黄金分割比向下取整即可

#include<bits/stdc++.h>
using namespace std;int n, m;
const double lorry = (sqrt(5.0) + 1.0) / 2.0;int main() {
    cin >> n >> m;if(n < m) swap(n, m);int a = n - m;if(m == int(lorry * (double)a))cout << "NO" << endl;else cout << "YES" << endl;
}

I 买花

给定一个数$n$，即需要买$n$多花，后一天买的花数为前一天两倍。问是否能在$k(1<k\le 15)$天内恰好买到$n$朵花。

假设第一天买$x$朵花，考察以下等比数列：
$x,2x,4x,...,2^{k?1}x$，其和为$x(2^k?1)$。因为$k$有范围，我们可以枚举$k$，然后判断对于给定的$n$，是否存在$x$(也就是整除)。
(鬼知道我当时脑子抽了什么风没想到整除。。。)

C 上进的凡凡

给定一个长为$n(1\le n\le 10^5)$数组，判断数组的非降序子数组的个数。子数组定义为：在原数组头尾删除任意元素和得到的数组。子数组包含原数组，不包含空串。

我当时写的代码事后一看过了九成的测试用例。那么究竟是错哪了呢？

---

我爆int了

---

三年竞赛一场空，不开longlong见祖宗

sum += cnt * (cnt - 1) / 2 + cnt

cnt是用来计算非降序的长度的，按理说$n\le 10^5$，cnt不会爆int，但是。。
上面的代码，sum是longlong，cnt是int。但c艹规定，$int?int$ 还是int，然后就爆了。

思路很简单，直接贴一下ac代码吧。
代码：

#include <bits/stdc++.h>
using namespace std;const int maxn = 1e5 + 10;
long long a[maxn];int main()
{
    int n;scanf("%d", &n);long long cnt = 0;long long sum = 0;for (int i = 1; i <= n; i++){
    scanf("%lld", &a[i]);if (a[i] >= a[i - 1]) {
    cnt++;}else {
    sum += cnt * (cnt - 1) / 2 + cnt;cnt = 1;}}sum += (long long)cnt * (cnt - 1) / 2 + cnt;printf("%lld", sum);return 0;
}

B 小宝的幸运数组

如果一个数组的和能够整除幸运数字$k(1\le k\le 10^5)$，那么称该数组为幸运数组。给定一个长度为$n(1\le n\le 10^5)$的数组，求这个数组中最长幸运子数组的长度。

为了写这题，我们先看一个简单一点的题目：
给定数组$a$，一个整数$k$。判断$a$中满足$a_i+a_j=k$的有多少对？

思路：
两个for循环的复杂度显然是$O(n^2)$。如何优化呢？可以用一个hash。对于每一个$a$,在hash table里查询是否有$k?a$。复杂度可以达到$O(n)$预处理加$O(nlogn)$的n次查询,总复杂度为$O(nlogn)$。

回过来再看这题:既然要求一个数组连续一段的和,那必然要维护前缀和。
然后我们必须用到一些数论知识:$(a?b)\%m=(a\%m?b\%m)\%m$

知道这些,这道题就可做了。一个数组从第$l$项到第$r$项的和为:
$$\begin{array}{r}\sum _{i=l}^r{a}_i=\sum _{i=1}^r{a}_i?\sum _{i=1}^{l?1}{a}_i\end{array}$$
数组的和能够整除$k$,也就是模$k$等于$0$。
$$\begin{array}{rl}& \sum _{i=l}^r{a}_i\%k=0\\ =>& (\sum _{i=1}^r{a}_i\%k?\sum _{i=1}^{l?1}{a}_i\%k)\%k=0\end{array}$$
而${\sum }_{i=1}^r{a}_i$和${\sum }_{i=1}^{l?1}{a}_i$都是数组$a$的前缀和(取模的前缀和)。我们想要数组的和模$k$为$0$,就相当于求使得$a$在$i,j$处前缀和相等的最大$i,j$差值。

判断:一边读取数据,一边算前缀和,如果这个前缀和(注意需要取模)不在map中,那就存进去(把前缀和映射到下标)。如果这个前缀和在map中,就算当前下标和map中前缀和的下标并做差。

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;const int maxn = 1e5 + 10;
long long a[maxn];int main()
{
    int t;scanf("%d", &t);while (t--) {
    unordered_map<int, int> mp;int k, n;scanf("%d%d", &n, &k);long long sum = 0;long long dist = 0;mp[0] = 0;for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);sum = (a[i] % k + sum) % k;if (mp.count(sum)) {
    dist = std::max(dist, (long long)i - mp[sum]);}else {
    mp[sum] = i;}}if (dist != 0) {
    printf("%lld\n", dist);}else {
    printf("-1\n");}}return 0;
}

G 贪吃的派蒙

给定一个数组,长度为$n(2\le n\le 10^5)$,数组的第$i$个元素为$a_i$,表示编号为$i$的角色可以至多领取$a_i$份花酿鸡.数组中最大的一个$a_k$对应的是派蒙,派蒙每次只能拿$a_k$份花酿鸡.花酿鸡一共有$k$份,第一个没有花酿鸡领的人要洗碗.现在大家拍好队,给定的数组就是顺序.大家都想让派蒙洗碗,判断这是否可能.

这都能迫害派蒙是没想到的,不过…迫害的好

现在大家按照这样的顺序排队,其中$a_k$是派蒙:$a_1,a_2,a_3,...,a_k,...,a_{n?2},a_{n?1},a_n$.如果用$c$表示第一个人领取花酿鸡的次数,$x_1,x_2,x_3,...,a_k,...,x_{n?2},x_{n?1},x_n(1\le x_i\le a_i,这里除了派蒙每次都是一个定值以外其他的都是不固定的)$表示每人每次领取花酿鸡的个数.那么想要派蒙刷碗,也就是到派蒙这刚好没有花酿鸡,需要满足
$$\begin{gathered} k=c?(x_1+x_2+...+x_{k?1})+(c?1)?(a_k+x_{k+1}+...+x_n) \\ =>k?(c?1)a_k=c?(x_1+x_2+...+x_{k?1})+(c?1)?(x_{k+1}+...+x_n) \end{gathered}$$
这里的$x_i$都是有范围的,$1\le x_i\le a_i$带入得:
$$\begin{array}{r}(c?1)n+k?c\le k?(c?1)a_k\le c\sum _{i=1}^{k?1}{a}_i+(c?1)\sum _{i=k+1}^n{a}_i\\ =>(c?1)(n+a_k)+k?c\le k\le c\sum _{i=1}^{k?1}{a}_i+(c?1)\sum _{i=k+1}^n{a}_i+(c?1)a_k\end{array}$$

看着好像挺吓人,但仔细想一想,这个式子中的未知量应该只有$c$.也就是说,这是一个关于c的不等式组(左面右面各一个不等式).判$c$是否有正整数解即可.
继续化简即可得到下式(比上面那个漂亮多了):

$$\begin{array}{r}\frac{k+a_k+{\sum }_{i=k+1}^n{a}_i}{{\sum }_{i=1}^n{a}_i}\le c\le \frac{n+a_k}{n+a_k?1}\end{array}$$

J 这是一题简单的模拟

K 黑洞密码

这两道都是纯模拟,考验底力的题(对我这种fw是真的难,照着官方题解抄都wa了4发)