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<bits/stdc++.h> #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分的总分。最大数据范围为\(n\le 10^{18}\),早已超出了\(o(n)\)的复杂度能到达的极限。此时,我们思考所有和动态规划有关的优化。经过一番思索后,我们会发现只有矩阵优化稍微与目前的\(dp\)有点联系。然而矩阵优化要求使用通项公式,而我们当前只有一个递推式。那么我们现在考虑将方程式反向优化,从一维方程变为三维方程,使整个式子具有通项公式,再使用矩阵优化来降低整体的复杂度。想到了这一点后,实现起来应该并不难。
#include <bits/stdc++.h> #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","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<bits/stdc++.h> using namespace std; int main(){ puts("yes"); return 0; }
对于lis来说,改变一个数有时可以导致多对大小关系的改变;对于逆序对来说,逆序对个数不一定可以决定最终大小关系。对两种思路最好的反驳样例如下:
|5 3 2
|-
在排除了这样的思路后,蒟蒻的我开始思考自己的做法。我们直接从头往后寻找第一对不满足条件的组合\(a_i,a_{i-1}\)。此时我们取出\(a_i\),从头往后将其与第一个大于他的值交换。此时我们再重新在原串中查找是否存在不合法情况,若存在则输出no,否则输出yes。
#include<bits/stdc++.h> #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<='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-1]){ 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]<a[i-1]){ puts("no"); return 0; } } puts("yes"); return 0; }
为什么我们选择了这样一个奇怪的算法呢?事实上,在比赛中选择算法的第一原则是能否证明其错误性。在这道题中,蒟蒻无法证明该算法是错误的,于是就这么得到了85分的安慰分。
其实题目已经提示得很明显了。sorting,就是在暗示我们进行一次排序操作。我们只需要比较排序前后的两个两个序列,若其中同一位置不一样的元素的个数在两个以内(一次交换最多导致4对大小关系发生改变),则输出yes,否则就记其为非法情况,输出no。
#include <bits/stdc++.h> 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"<<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 |
【数据规模与约定】
$ 1\le q \le 1000000,-1000 \le m \le 1000 $
【题解】
模拟题,注意一下优化就好。本蒟蒻的代码风格太丑因此在此不予贴出。
下一篇: 【Java集合之二】Set集合