2017.9.17 noip模拟赛 总结

昨天的WC模拟真是喜（sang）闻（xin）乐（bing）见（kuang）。还好今天的noip模拟比较正常。

怎么说呢，今天可能是奶牛专场。

第一题：题意 有N个学生顺时针围在一圆桌上开会，他们对身高很敏感。 因此决定想使得任意相邻的两人的身高差距最大值最小。 如果答案不唯一，输出字典序最小的排列，指的是身高的排列。

让最大的最小，显然的二分答案题，之后就是如何判断了。

我想的是后面排最大的可行的，前面排最小的可行的。之后再翻转一下就可以了，但是不知道为什么WA了三个点。（当然这道题20个数据点，可以猜到会卡一些不优的贪心方法）。

第二题：bzoj3048原题，不是权限号看不了题。。。

用一个队列让其中有k+1类数，然后更新答案。

#include<bits/stdc++.h>
#include<set>
using namespace std;
long long l,r,ans,n,k,tot;
map<long long,long long>mp;
long long flag[100010],a[100010];
long long q[100010];
int main()
{
    freopen("line.in","r",stdin);
    freopen("line.out","w",stdout);
    cin>>n>>k;
    for (long long i=1;i<=n;i++)
    {
        cin>>a[i];
        if (!mp[a[i]]) mp[a[i]]=++tot;
        a[i]=mp[a[i]];
    }
    l=1;r=0;
    long long kind=0,i=0;
    while (i<n)
    {
        while (i<n&&kind<=k)
        {
            q[++r]=a[++i];
            if (!flag[a[i]]) kind++;
            flag[a[i]]++;
            ans=max(ans,flag[a[i]]);
        }
        while (kind==k+1&&i<n)
        {
            if (!flag[a[i+1]]) break;
            q[++r]=a[++i];
            flag[a[i]]++;
            ans=max(ans,flag[a[i]]);
        }
        if (flag[q[l]]==1) kind--;
        flag[q[l]]--;
        l++;
    }
    cout<<ans;
}

long long 范围内，要离散化一下，不想写unique之类的，map凑合一下吧。。

第三题，bzoj3298加强。

首先，如果一个点先手必败，这它对应的横排，竖排，斜排都不是必败的，显然（0，0）必败，然后填充，找下一个（1，2）与（2，1）。

大概手推几个，发现一定的规律，大概是，从行枚举，如果没确定的话，列就为行+tot，tot++，然后这一行就确定了（显然对称）。这样O（n）处理，O（1）询问，bzoj上就可以过了。

但是，这道题N<=2*1e9,过不了的，就强行找规律，做了几阶等差，貌似有些规律，但我看不出233。

最后得了245分，应该还是在预料之内吧。

三题题解来了。

先安利一个新东西——威佐夫博弈。

百度百科

特别神奇，这样，然后套用公式

t=floor((1.0+sqrt(5.0))/2*(y-x));(y>x)
若t=x先手必败
否则 先手必胜
另人窒息的操作。。。