考试状态

这次考试仍然很失败！

  • 其实今天的考试状态是很糟糕的，首先我拿到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();
    }
}