11-03考试总结

考试状态

这次考试仍然很失败!

  • 其实今天的考试状态是很糟糕的,首先我拿到T1之后就开始看,想着T1应该比较简单,然后就开始找规律,事实上这道题的规律是很难找到的,然后就不停的找规律找规律然。然而并没有找到任何规律,于是就想去写DP的式子,然后想了集中状态都没有办法找到状态转移的式子,这个时候考试已经过去了两个小时了,真的是严重的失误,于是就草草的写了DFS搜索枚举了所有的状态,打表写了70分。
  • 这时候一个小时考试就结束了,然后就去看第二题,也没有心思沉下心来了,就想着超级裸的暴力,发现代码非常不好实现,于是就开始打表骗分,emmmmmm,其实这道题的规律是非常容易想出来了,但是T1用了两个半小时后我已经慌了,不想再写下去了,真是的,每次考试的时候我应该每次认真对待,就像这次考试是NOIP一样,无论难度如何,把自己能够拿到的分数拿到手,给每一道题目一定的时间思考,不要过度的浪费到同一道题目上面。
  • 最后大概写了100分,GG,被各种大佬吊起来打……

还有一些重要的东西,距离NOIP仅仅只剩下一个星期了,这一个星期我该干什么,我想我应该做出规划了:

  1. 一个星期内,简单学一下数论和组合数学(认真脸,不能再拖了!)

  2. 然后就是再写一些模板题,各种算法的模板题,还有自己的blog,写了很多很多东西的,我要把里面的东西全部复习一遍,各种题目的思路全部再想一遍,代码就不码了,只记住模板就行了。

  3. 然后就是认真的对待每一次的考试,写好总结,加油!

最后放上前两道题目的题解:

兔子(rabbit)

题目描述:

做一只明媚的兔子…

  • 兔子都比较喜欢蹦蹦跳跳.但是蹦蹦跳跳的时候如果一直往高处跳的话就太累了,如果一直往低处跳的话就太无聊了.所以兔子希望跳的时候能够往上跳一步,往下跳一步,往上跳一步,往下跳一步….一共经过n个高度互不相同的位置(只要向上跳和向下跳相间分布就可以了,第一步可以往上跳也可以往下跳).如果下一个位置的高度比前一个位置高,就是往上跳,比前一个位置低,就是往下跳.

  • 兔子今天又蹦蹦跳跳依次经过了n个位置.现在它想知道经过的n个位置的高度有多少种不同的可能.我们认为n个位置的高度形成了1到n的一个排列,这个排列要么满足奇数项的高度比相邻位置都大,要么满足偶数项的高度比相邻位置都大.

  1. n=1时,有1种可能,就是这1个位置的高度为1
  2. n=2时,有2种可能,可以是(1,2)或(2,1)
  3. n=3时,有4种可能,(1,3,2) (2,3,1),(2,1,3),(3,1,2)

答案可能很大,只需要输出答案对mod取模的结果.

输入:

一行两个整数n,mod

输出:

一行一个整数ans,表示所有可能的排列数目对mod取模后的结果.

题解:

  • emmmmmm,其实这道题真的是DP里面比较难得一种了,无论是DP式子的状态转移还是状态设置,都不太好想,这道题需要两个DP式子,F[i][j]表示的是对于长度为i,第一个数字为j,且第一个数字比第二个数字大的数列的数量。G[i][j]表示的是对于长度为i,第一个数字为j,且第一个数字比第二个数字小的数列的数量,其中j<=i。

  • 那么我们可以这样想,对于一个长度为i-1,第一个数字为k(k<j)且第一个数字小于第二个数字的数列来说,我们只要将 j 添加在这个数列的前面,那么我们就有了一个长度为i,第一个数字为j,且第一个数字大于第二个数字的数列。这个数列的数量就是F[i][j],那么F[i][j]的转移式子就出来了:

F[i][j]=G[i-1][1]+G[i-1][2]+…+G[i-1][j-1];

  • 那么对于G[i][j]的状态转移方程我们也可以用相同的思路去想,对于一个长度为i-1,第一个数字为k(j<=k<=i-1)且第一个数字大于第二个数字的数列来说,我们只需要将j添加在这个数列前面,就有了一个长度为i,第一个数字为j,且第一个数字小于第二个数字的数列,也就是G[i][j];

G[i][j]=F[i-1][j]+F[i-1][j+1]+…+F[i-1][i-1];

  • 这里状态转移我们可以利用前缀和优化设置Fall[i][j]表示F[i][1]+F[i][2]+…F[i][j],同理Gall[i][j]表示G[i][1]+G[i][2]+…+G[i][j],然后我们就可以O(i)转移F[i][j]和G[i][j]了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
long long n,Mod,ans;
long long F[2001][2001];
long long G[2001][2001];
long long Fall[2][2001];
long long Gall[2][2001];
int main()
{
freopen("rabbit.in","r",stdin);
freopen("rabbit.out","w",stdout);
cin>>n>>Mod;
Gall[1][1]=1;
Fall[1][1]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=n;j++)
{
F[i][j]=Gall[(i-1)&true][j-1];
G[i][j]=(Fall[(i-1)&true][i-1]-Fall[(i-1)&true][j-1]+Mod)%Mod;
Fall[i&true][j]=(Fall[i&true][j-1]+F[i][j])%Mod;
Gall[i&true][j]=(Gall[i&true][j-1]+G[i][j])%Mod;
}
for(int i=1;i<=n;i++)
ans=(ans+F[n][i]+G[n][i])%Mod;
if(n==true) ans=true;
cout<<ans<<endl;
return 0;
}

被子(quilt)

题目描述:

作为一只明媚的兔子,需要学会叠被子…

  • 被子是方形的,上面有很多小写字母.可以认为被子是一个n*m的字符矩阵被子能够被叠起来,当且仅当每一行,每一列都是回文串.兔子可以把同一条被子上任意两个位置的字母交换位置,而且兔子不嫌麻烦,为了把被子叠起来它愿意交换任意多次.但是兔子不能交换两条不同的被子之间的字母.

  • 现在兔子翻箱倒柜找出来了很多被子,请你帮兔子判断每条被子能否被叠起来.

输入:

  1. 第一行一个Q,表示被子的条数

  2. 接下来描述Q条被子.

  3. 描述每条被子时,第一行输入两个整数n,m表示由n行m列组成

  4. 接下来n行每行一个长度为m的字符串.字符串中只含小写字母.

输出:

Q行,依次输出对每条被子的判断结果.如果可以叠起来,输出一行“Yes”(不包括引号),如果叠不起来,输出一行“No”(不包括引号).

题解:

  • 其实这道题是非常简单的,不过细节有些多,所以需要好好想想其中有四种情况:
  1. n和m都是偶数,那么所有字符的出现次数必须是4的倍数,否则输出"No".

  2. n是偶数,m是奇数,然后就判断不能有字符出现次数为奇数,如果有输出"No",然后去掉所有的4的倍数,枚举累加2的倍数,要求累加和要小于等于n。

  3. n是奇数,m是偶数,然后就判断不能有字符出现次数为奇数,如果有输出"No",然后去掉所有的4的倍数,枚举累加2的倍数,要求累加和要小于等于m。

  4. n是奇数,m是奇数,所有字符出现次数只能有一个为奇数,否则输出"no",然后累加非4倍数的%4值,如果超过m+n-2,那么输出"No,“否则输出"Yes”。

其实就是一道找规律的题目,超级简单,只不过需要注意细节问题,想明白所有的情况,思路需要比较广!

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
using namespace std;
const int Maxx=30;
char a[2000][2000];
int n,vis[40],Num;
int m,all,This;
void Solve_First()
{
for(int i=1;i<=Maxx;i++)
if(vis[i]%4)
{
cout<<"No"<<endl;
return;
}
cout<<"Yes"<<endl;
}
void Solve_Second()
{
Num=false;
for(int i=1;i<=Maxx;i++)
if(vis[i]&true)
{
cout<<"No"<<endl;
return;
}
for(int i=1;i<=Maxx;i++)
vis[i]=vis[i]>>true;
for(int i=1;i<=Maxx;i++)
if(vis[i]&true) Num++;
if(Num>(n>>true))
{
cout<<"No"<<endl;
return;
}
cout<<"Yes"<<endl;
}
void Solve_Third()
{
Num=false;
for(int i=1;i<=Maxx;i++)
if(vis[i]&true)
{
cout<<"No"<<endl;
return;
}
for(int i=1;i<=Maxx;i++)
vis[i]=vis[i]>>true;
for(int i=1;i<=Maxx;i++)
if(vis[i]&true) Num++;
if(Num>(m>>true))
{
cout<<"No"<<endl;
return;
}
cout<<"Yes"<<endl;
}
void Solve_Forth()
{
Num=false; This=n+m-1;
for(int i=1;i<=Maxx;i++)
if(vis[i]&true)
{
This--;
vis[i]=false;
break;
}
for(int i=1;i<=Maxx;i++)
if(vis[i]&true)
{
cout<<"No"<<endl;
return;
}
for(int i=1;i<=Maxx;i++) Num+=vis[i]%4;
if(Num>This) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
int main()
{
cin>>all;
while(all-->false)
{
cin>>n>>m;
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
vis[a[i][j]-'a'+1]++;
}
if(!(n&true)&&!(m&true)) Solve_First();
if(!(n&true)&&(m&true)) Solve_Second();
if((n&true)&&!(m&true)) Solve_Third();
if((n&true)&&(m&true)) Solve_Forth();
}
}