C# · 12月 19, 2021

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

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 1000005

const 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<<dp[i]<<endl;

dp[i]%=mod;

}

//for(register long long i=3;i<=n;i++)cout<<dp[i]<<endl;

cout<<dp[n]%mod<<endl;

return 0;

}

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

#include

#define RG register

using 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”,stdin);

freopen(“adjoin.out”,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 100005

using 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=’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”,stdin);

//freopen(“sorting.out”,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]

for(register long long j=1;j<=n;j++){

if(a[j]>a[i]){

swap(a[i],a[j]);

goto next;

}

}

}

}

next:;

for(register long long i=2;i<=n;i++){

if(a[i]

puts(“NO”);

return 0;

}

}

puts(“YES”);

return 0;

}

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

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

#include

using namespace std;

int b[2111111],a[2111111];

int n;

int main(){

freopen(“sorting.in”,stdin);

freopen(“sorting.out”,stdout);

cin>>n;

for(int i=1;i>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"<<endl;

return 0;

}

}

cout<<"YES"<<endl;

return 0;

}

T3 Editor

【问题描述】

小(F)有一个梦想:为数列写一个最强大的编辑器!

一开始,数列为空,光标在开头位置,小F的编辑器要对这个数列作如下五种操作:

I x:在光标的后面插入一个数字x,并将光标移到这个新加入的(x)后。

D:删除光标前的最后一个数字(保证存在),光标位置不变。

L:光标左移一位,如果已经在开头则不做任何事。

R:光标右移一位,如果已经在结尾则不做任何事。

Q k:编辑器需要给出(A_1,A_2 ··· A_k)的最大前缀和(前缀长度不能为0),保证(1 ≤ k ≤ N),其中(N)为当

前光标前的数字个数。

【输入格式】

第一行,一个整数(Q),表示操作的总次数。

后(Q)行,每行是上列五种操作中的一种。

【输出格式】

对每个(Q)操作,输出一行一个整数,表示答案。

【样例输入1】

8

I 2

I -1

I 1

Q 3

L

D

R

Q 2

【样例输出1】

样例输出

2

3

【数据规模与约定】

$ 1le q le 1000000,-1000 le m le 1000 $

【题解】

模拟题,注意一下优化就好。本蒟蒻的代码风格太丑因此在此不予贴出。