CCF-NOIP-2018 提高组(复赛) 模拟试题(七)-白红宇

CCF-NOIP-2018 提高组(复赛) 模拟试题(七)

阅读量：6863 次

发布时间：2019-06-26

本文共 5621 字，大约阅读时间需要 18 分钟。

T1 Adjoin

【问题描述】

定义一种合法的$0-1$串：串中任何一个数字都与$1$相邻。例如长度为$ 3 的 0-1 $串中，$101$是非法的，因为两边的$1$没有相邻的$1，011$是合法的，因为三个数都有$1$相邻。现在问，长度为$N$的$0-1$中有多少是合法的。

【输入格式】

一行，一个整数$N$

【输出格式】

一行，合法$0-1$串的个数，答案对$1000000007$取模。

【样例1】

样例输入
3

样例输出
3

样例说明

$110、111、011$是所有长度为$3$的合法$0-1$串

数据规模与约定

所有测试点的数据规模与约定如下：

$30\%$输入数据，保证$n<=50。$

$60\%$输入数据，保证$ n<=5000$

$80\%$输入数据，保证$ n<=1000000$

$100\%$输入数据，保证$ 1<=n<=10^{18}$

题解

一道很经典的需要~~反向优化~~的题目。我们首先考虑暴搜得到较小范围内每一个$n$所对应的答案，如下所示

|i|f[i]|

|-|-

|1|0

|2|1

|3|3

|4|4

|5|5

|6|9

|7|16

|8|25

|9|29

|10|54

然而直接观察数据似乎没有什么明显的规律。于是我们选择将奇偶数分开判断。经过一段时间的观察，似乎所有的数满足这样一个规律：\[f[i]=\begin{cases} 0 & i=1\\ 1 & i=2\\ f[i-1]+f[i-2] & i\%2=0\\ f[i-1]+f[i-2]+(flag=1)?-2:2 & i\%2=1\\ \end{cases} \]

其中我们将flag的初值赋为1，在每碰到一个奇数时为其取反即可。

#include
    
     #define maxn 1000005const long long mod = 1000000007;using namespace std;long long n;long long dp[maxn];bool flag=1;int main(){    //freopen("adjoin.in","r",stdin);    //freopen("adjoin.out","w",stdout);    ios::sync_with_stdio(false);    cin.tie(0);    cin>>n;    dp[1]=0;    dp[2]=1;    for(register long long i=3;i<=n;i++){        if(i%2==0)dp[i]=dp[i-1]+dp[i-2];        else{            if(flag){                dp[i]=dp[i-1]+dp[i-2]+2;                flag=0;            }            else{                dp[i]=dp[i-1]+dp[i-2]-2;                flag=1;            }        }        //cout<
     
      <

这时我们就拥有了85分的总分。最大数据范围为$n\le 10^{18}$，早已超出了$O(n)$的复杂度能到达的极限。此时，我们思考所有和动态规划有关的优化。经过一番思索后，我们会发现只有矩阵优化稍微与目前的$dp$有点联系。然而矩阵优化要求使用通项公式，而我们当前只有一个递推式。那么我们现在考虑将方程式反向优化，从一维方程变为三维方程，使整个式子具有通项公式，再使用矩阵优化来降低整体的复杂度。想到了这一点后，实现起来应该并不难。

#include 
    
     #define RG registerusing namespace std;typedef long long ll;const int maxn = 1000010;const int mod = 1e9+7;const int P = 1e9+7;ll n;struct Matrix {    ll val[4][4];} A, I, ans;Matrix operator*(const Matrix &A,const Matrix &B){    Matrix C;    for(int i = 0;i < 4;i++)        for(int j = 0;j < 4;j++){            C.val[i][j] = 0;            for(int k = 0;k < 4;k++)                C.val[i][j] = (1ll * A.val[i][k] * B.val[k][j] + C.val[i][j]) % P;        }    return C;}Matrix fpm(Matrix x, long long y){    Matrix ret = I;    while(y){        if(y & 1) ret = ret * x;        x = x*x;        y >>= 1;    }    return ret;}int main(){    freopen("adjoin.in","r",stdin);    freopen("adjoin.out","w",stdout);    scanf("%lld",&n);    if(n == 1){        puts("0");        return 0;    }    for(int i = 0;i < 4;i++){        for(int j = 0;j < 4;j++){            I.val[i][j] = (i == j ? 1 : 0);            A.val[i][j] = 0;        }    }    ans.val[0][0] = 0;    ans.val[0][1] = 1;    ans.val[0][2] = 0;    ans.val[0][3] = 1;    A.val[2][0] = A.val[0][1] = A.val[2][1] = A.val[3][2] = A.val[1][3] = A.val[3][3] = 1;    A = fpm(A,n-2);    ans = ans * A;    ll ansss = (ans.val[0][2] + ans.val[0][3]) % mod;    printf("%lld",ansss);    return 0;}

T2 Sorting

【问题描述】

小F不喜欢递减，他会想尽一切办法将看到的一切东西排序！

现在小F得到了一个数列，他当然要将这个数列排序了，但他太累了，以至于最多只能交换其中两个元素，如果这样不能使得这个数列不递减，他就要先睡觉了。你能告诉他是否可行吗？

【输入格式】

第一行：一个整数N表示小F的数列中数的个数。

第二行，N个正整数，描述小F的数列。

【输出格式】

一行，YES或NO，表示通过一次“最多交换其中两个元素（可以不交换）”的操作，是否可使得小F的数列不递减。

【样例1】

样例输入
3
1 3 1

样例输出
YES

数据规模与约定

$30\%的数据，N ≤ 10^2 。$

$60\%的数据，N ≤ 10^4 。$

$100\%的数据，N ≤ 10^5 ，所有数为正整数且在longint范围内。$

题解

是的，本蒟蒻又一次和AC插肩而过。拿到这道题时，大多数人都会联想到逆序对和最长不降子序列问题，然而几组充分设置的样例就可以卡掉这两种思路，使得其得分甚至不如60分的暴力。

附六十分的暴力写法

#include
    
     using namespace std;int main(){    puts("YES");    return 0;}

对于LIS来说，改变一个数有时可以导致多对大小关系的改变；对于逆序对来说，逆序对个数不一定可以决定最终大小关系。对两种思路最好的反驳样例如下：

|5 3 2

在排除了这样的思路后，蒟蒻的我开始思考自己的做法。我们直接从头往后寻找第一对不满足条件的组合$a_i,a_{i-1}$。此时我们取出$a_i$，从头往后将其与第一个大于他的值交换。此时我们再重新在原串中查找是否存在不合法情况，若存在则输出NO，否则输出YES。

#include
    
     #define maxn 100005using namespace std;inline char get(){    static char buf[30],*p1=buf,*p2=buf;    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++;}inline long long read(){    register char c=get();register long long f=1,_=0;    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();    return _*f;}long long n;long long a[maxn];long long ans=0;bool cd=1;int main(){    //freopen("sorting.in","r",stdin);    //freopen("sorting.out","w",stdout);    n=read();    for(register long long i=1;i<=n;i++)a[i]=read();    for(register long long i=2;i<=n;i++){        if(a[i]
     
      a[i]){                    swap(a[i],a[j]);                    goto next;                }            }        }    }    next:;    for(register long long i=2;i<=n;i++){        if(a[i]

为什么我们选择了这样一个奇怪的算法呢？事实上，在比赛中选择算法的第一原则是能否证明其错误性。在这道题中，蒟蒻无法证明该算法是错误的，于是就这么得到了85分的安慰分。

其实题目已经提示得很明显了。Sorting，就是在暗示我们进行一次排序操作。我们只需要比较排序前后的两个两个序列，若其中同一位置不一样的元素的个数在两个以内（一次交换最多导致4对大小关系发生改变），则输出YES，否则就记其为非法情况，输出NO。

#include 
    
     using namespace std;int b[2111111],a[2111111];int n;int main(){    freopen("sorting.in","r",stdin);    freopen("sorting.out","w",stdout);    cin>>n;    for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];    sort(b+1,b+1+n);    int len=0;    for(int i=1;i<=n;i++){        if(a[i]!=b[i])len++;        if(len>2){            cout<<"NO"<