2022.9.11模拟赛

masonpop · 2022-09-11 17:14:07 · 个人记录

题面就算了吧，见文件夹

T1 假冒泡排序

这个题目不难，我也想到了正解，但考场上忽略了对边界条件的处理，导致挂成了暴力分（50pts）,实在不应该。

这是我的考场代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*去掉最大值，找规律：
1 2 3 1 2 3（零散） 
2 3 1 2 3 1 2 3 1 2 3 1
3 1 2 3 1 2 3 1 2 3 1 2
1 2 3 1 2 3 （末尾）*/ 
int n;
const int maxn=1e5+10;
int a[maxn],b[maxn];
int idx;//最大值坐标 
int c[maxn];//a去掉max
int tot=0; 
int main()
{
    freopen("bubble.in","r",stdin);
    freopen("bubble.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]),b[i]=a[i];
        if(a[i]==n)idx=i;//1~n一个排列 
    }
    ll ans=1;//自己 
    int idxa,idxb;//a,b中1的位置 
    for(int i=1;i<=n-1;i++)
    {
        if(b[i]>b[i+1])swap(b[i],b[i+1]),ans++;//模拟交换 第一轮
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=n)c[++tot]=a[i];//缩减a 
    }
    ans+=(n-2)*n;
    ans+=(idx-1);
    printf("%lld\n",ans);
    //正解：考虑特殊情况a1=n-1 且an=n时要减1（见博客）
    //反例：n=2时不用减！ 
    return 0;
} 

规律也很简单，这里不说了，见代码

为何挂了呢？

有两点：

(1)特殊情况--增加40pts

考虑这个数组:2,1,3

• 应该是:
• 2 1 3
• 1 2 3
• 3 2 1
• 2 3 1
• 2 1 3 //完
• 输出答案是：7

  怎么这么多？

  原来，a_1=n-1并且a_n=n是一个特殊情况。

  我们的规律是[遇到n之前交换的次数]+n(n-1).

  思路是，遇到n之后看成一个环，n位置有n种，n-1个交换有n-1个，那么就是n(n-1).

  但是当a_1=n-1,a_n=n时第一次交换就相当于整体挪移(2,1->1,2)

• 这种情况就少了一种轮换的顺序，也就是减1

(2)特殊情况：n=2,a1=1,a2=2

虽然满足(1),但也是不能减少的。（算一下！）

综上，答案为：

t+n(n-1)-[n>=3 ,a_1=n-1,a_n=n]

T3 简单取石子

威佐夫(Wizhoff)博弈:

两堆石子，每次同时取若干个或单独取若干个，何时先手必胜？

通过打表(考场二维dp50pts)可以得到必败情况：

可以看到一件事情:

lim_{a,b \to \infty}(\frac{b}{a})= \frac{1+\sqrt{5}}{2}

\frac{1+\sqrt{5}}{2}:一个神奇的数字,黄金分割

事实上，根据威佐夫博弈论，这个真的是成立的，设t=\frac{1+\sqrt{5}}{2},s=t^2=\frac{3+\sqrt{5}}{2}

则所有满足条件的(a,b)形如

([it],[is]),i\in N^{+})

显然固定a,至多有一个b满足(a,b)必败。

那么，解一下这个高斯函数方程就能确定对应的b了

题目也不难，只要用map之类的容器统计一下，递推求出前缀必败局面数量即可。

(未完待续)