10-17考试总结

考试总结

今天焦老师让我们写总结,我决定开始写总结,以前除了大型的考试意外都没有写过,以后怕不是要天天写了……

这次考试……emmmmmm 先看第一次测评的成绩:

然后第一题蜜汁爆炸,第三题丢了一个点,还好还好没有炸的太狠……

  • 这次考试过程是非常爽的,感觉节奏不错,首先先看第一题,然后花了一个半小时的时间写完了第一题,用的时间有些长了,其实应该控制在一个小时之内,但是这个第一题有些复杂……真的是不好写。以后尽量控制在一个小时以内。

  • 写完第一题之后,开始看第二题,虽说是省选题,但是是比较简单的,问了帆神Map的使用方法,构建一个Topsort就能AC了,然后造了几个大数据,跑了跑没有问题。

  • 写完前两题之后还剩下一个小时,看是看第三题,一眼秒暴力。想到原来黄山学长讲过怎么写,但是需要求组合数,虽然Century告诉了我组合数的公式,但是并不会求,就开始写暴力,复杂度O(n^2).二十分钟写完加调试。检查了一遍之后去吃饭了。

这次考试期望成绩是100+100+30,实际成绩是30+100+20。实力爆炸。

  • T1的爆炸:

  • T2的爆炸:

  • T3的爆炸:

爆炸之后大家修改过后的成绩:

感觉以后写题的时候,需要注意两点,一点是把握好时间,T1尽量在一个小时内写完,而且要保证T1不会被炸掉。其次是暴力分数有可能不能拿全,要思考完整。

需要补充的知识点: 字符串哈希,乘法逆元;

勉为其难的写三篇题解吧……

表达式

题目描述

同学们需要先判 断给出的表达式是否合法。现在你的任务就是完成这个工作。
在本题中,我们对合法表达式定义如下:

  1. 任何连续(至少 1 个)数字是合法表达式;
  2. 若 x 是合法表达式,则(x)也是合法表达式;
  3. 若 x 和 y 是合法表达式,则 x+y、x-y、x*y、x/y 都是合法表达式;
  4. 若 x 是合法表达式,则在 x 前后添加任意数量的空白符也是合法表达式。 现在给你若干个表达式,请你判断这些表达式是否是合法的。

输入:

第 1 行为一个正整数 n,表示表达式个数; 接下来 n 行,每行一个字符串,表示给定的表达式。

输出:

共 n 行,若第 i 个表达式是合法的,就在第 i 行输出”Yes”(不含引号,下同),否则输出”No”。

题解:

  • 题解没有什么好说的,就是使用while循环,然后每次寻找可以化为合法状态的字符串,把他们变成’1’,然后不停地合并为’1’,如果这次循环有改变字符串,那么久继续循环,如果没有改变,那么就结束循环。

  • 判断最后的循环,如果里面只有两个元素,s1[0]=1和s1[1]=0; (这里字符串不知道为什么后面一定会有一个0),输出"Yes"即可,否则输出"No";

  • 需要注意的是把合法的化为’1’的过程的时候,有可能吧两个合法的区域化为一个,但其实他们是分开的,比如 “23333 66666” ,就会变成: 1 1 --> 1.那么只需要增加判断就行了,"()"也是同理。我就是这里炸掉的。

代码:

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<string>
using namespace std;
int n,Len,Number,ID;
string s1,s2;
char a[2000];
bool Flag[200],Now;
void Work()
{
Number=false; Now=false;
for(int i=0;i<Len;i++)
{
if(isdigit(s1[i]))
{
while(isdigit(s1[i])) i++;
s2+='1';
}
s2+=s1[i];
}
s1=s2; s2.clear();
Len=s1.size();
while(!Now)
{
Now=true;
memset(Flag,false,sizeof(Flag));
for(int i=0;i<Len;i++)
{
if(s1[i]=='1')
{
Flag[i]=true;
if(s1[i+1]==')'&&s1[i-1]=='('&&s1[i+2]!='1'&&s1[i-2]!='1')
{
Flag[i-1]=true;
Flag[i+1]=true;
Now=false;
break;
}
if(s1[i-1]==' '&&s1[i-2]!='1')
{
ID=i-1;
Now=false;
while(s1[ID]==' ')
{
Flag[ID]=true;
ID--;
}
break;
}
if(s1[i+1]==' '&&s1[i+2]!='1')
{
ID=i+1;
Now=false;
while(s1[ID]==' ')
{
Flag[ID]=true;
ID++;
}
break;
}
if(s1[i+2]=='1')
{
if(s1[i+1]=='+')
{
Now=false;
Flag[i+1]=true;
Flag[i+2]=true;
break;
}
if(s1[i+1]=='-')
{
Now=false;
Flag[i+1]=true;
Flag[i+2]=true;
break;
}
if(s1[i+1]=='*')
{
Now=false;
Flag[i+1]=true;
Flag[i+2]=true;
break;
}
if(s1[i+1]=='/')
{
Now=false;
Flag[i+1]=true;
Flag[i+2]=true;
break;
}
}
}
}
for(int i=0;i<Len;i++)
{
if(Flag[i])
{
while(Flag[i]) i++;
s2+='1';
}
s2+=s1[i];
}
s1=s2; s2.clear();
Len=s1.size();
}
if(Len==2&&s1[0]=='1'&&s1[1]==0)
cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
int main()
{
freopen("expr.in","r",stdin);
freopen("expr.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
getchar();
scanf("%[^\n]",&a);
s1=a;
Len=s1.size();
Work();
}
return 0;
}

食物链

题目描述:

某研究小组经过长期的调查研究,在此地区发现了 n 个物种,并找到了它们之间 的m对捕食关系,由于物种众多,捕食关系复杂,他们希望你尽快地计算出食物链条数,以便下一步的研究工作。

输入:

第 1 行是正整数m,接下来m行有两个字符串A和B,分别代表对应的物种名称,描述了一对捕食关系A→B,表示A被B捕食(能量从A流动到B)。

输出:

仅一行,一个非负整数,为食物链条数对 1000000007 取模的值

题解:

这道题比较简单,我们需要使用Map或者字符串哈希来吧每一个字符串和一个数组一一映射,然后构建一个图。

然后进行拓扑排序,在拓扑排序的过程中,DP转移能量。

1
2
for(int i=Link[x];i;i=a[i].Next)
F[a[i].Point]+=F[i];

然后如果这个点被加入队列并且这个点的初度为零,那么这个一定是F[i]条食物链的最顶端。我们让ans+=F[i]%Mod;就可以了。

代码:

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<string>
#include<map>
using namespace std;
#define Mod 1000000007
struct Edge
{
int Next;
int Point;
}a[4000000];
map<string,int>::iterator it;
map<string,int>MapStr;
string s1;
int n,Number,len,Min,head,tail;
int First,Second,Link[200000];
long long F[200000],ans;
int Out[200000],Queue[200000];
int In[200000];
char c[20000];
void init(int x,int y)
{
a[++len].Point=y;
a[len].Next=Link[x];
Link[x]=len;
}
void TopSort()
{
for(int i=1;i<=Number;i++)
if(!Out[i])
{
F[i]=1;
Queue[++tail]=i;
}
Min=tail;
while(++head<=tail)
{
bool Flag=false;
int This=Queue[head];
for(int i=Link[This];i;i=a[i].Next)
{
Flag=true;
F[a[i].Point]+=F[This];
F[a[i].Point]%=Mod;
Out[a[i].Point]--;
if(!Out[a[i].Point])
Queue[++tail]=a[i].Point;
}
if(!Flag&&!In[This])
ans=(ans+F[This])%Mod;
}
cout<<ans%Mod<<endl;
}
int main()
{
freopen("chain.in","r",stdin);
freopen("chain.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%s",&c); s1=c;
it=MapStr.find(s1);
if(it==MapStr.end())
{
MapStr[s1]=++Number;
First=Number;
}
else First=MapStr[s1];
scanf("%s",&c); s1=c;
it=MapStr.find(s1);
if(it==MapStr.end())
{
MapStr[s1]=++Number;
Second=Number;
}
else Second=MapStr[s1];
init(First,Second);
Out[Second]++;
In[First]++;
}
TopSort();
return 0;
}

路径

题目描述:

周三下午是模电实验课,xy 正打算从宿舍(0,0)去实验楼(n,m)上课,然而他突 然发现,由于暴雨的缘故,有 k 个路口(x,y)已经被水淹没(不知所措),根本过不了人。

xy 行走的路线很特别,必须满足:

  1. 一定平行于坐标轴;
  2. 只能在横纵坐标都 是整数的点改变方向;
  3. 行走过程中横坐标和纵坐标始终不减小。

现在有 xy 想知道有多少条满足条件的路线可以避开被淹没的路口到达实验
楼。

输入:

  1. 第1行是两个非负整数 n ,m,k表示实验楼的坐标和有 k 个路口被淹没。
  2. 接下来 k 行,每行有两个非负整数 x 和 y,表示(x, y)这个路口已被淹没

输出:

仅一行,一个非负整数,为满足条件的路线数对 1000000007 取模的值。

题解:

  • 这道题正解不会写,暴力倒是简单,直接DP,设置状态为F[i][j]为到达(i,j)这个点的所有方案数,因为只有下面和左边两种情况到达自己,所以状态转移,如果i不为零F[i][j]+=F[i-1][j],如果j不为零F[i][j]+=F[i][j-1],如果是障碍点直接跳过。

  • 注意模数的问题,和开longlong。

代码:

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cctype>
using namespace std;
#define Mod 1000000007
int n,m,k,x,y;
long long F[2000][2000];
bool a[2000][2000];
inline int Read()
{
int F=true;
int This=false;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-') F=-1;
ch=getchar();
}
while(isdigit(ch))
{
This=(This<<1)+(This<<3)+ch-'0';
ch=getchar();
}
return This*F;
}
int main()
{
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
n=Read(); m=Read(); k=Read();
for(int i=1;i<=k;i++)
{
x=Read();
y=Read();
a[x][y]=true;
}
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
{
if(a[i][j]) continue;
if(!i&&!j) F[i][j]=1;
if(i) F[i][j]+=F[i-1][j];
if(j) F[i][j]+=F[i][j-1];
F[i][j]%=Mod;
}
cout<<F[n][m]%Mod<<endl;
return 0;
}