190801测试-总结(题目-题解)

20190802的上机测试题目和题解!!

1.判断素数个数

题目描述

输入两个整数和,输出两者之间的素数个数(包括

输入格式

两个整数和
()

输出格式

输出一个整数,表示之间的素数个数(包括

样例

样例输入

1
1 100

样例输出

1
25

注意点:有坑😭 不一定大于

题解:

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
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

bool p(int x) {
bool f = 1;
for (int i = 2; i <= sqrt(x); i++)
if (x % i == 0) {
f = 0;
break;
}
return f;
}

int main() {
// freopen("prime.in","r",stdin);
// freopen("prime.out","w",stdout);
int x, y;
cin >> x >> y;//有问题就交换一下
if (x > y)
swap(x, y);
int ans = 0;
for (int i = x; i <= y; i++)
if (p(i) && i != 1)
ans++;
cout << ans;
return 0;
}

2.火车调度序列统计

就是Catalan数(虽然知道但是还是没有AC

题目描述

有辆各不相同的火车在车道上等待出站(火车的两端都可以当动力源),火车进站前可以通过一个调度站调整火车出站次序,调度站不限定所能停放的火车数量,每次只能进或出一辆火车。请你编程求出辆火车的不同出站序列的总数。

输入格式

一个数

输出格式

一个数,即可能输出序列的总数目。

样例

样例输入

1
3

样例输出

1
5

题解:

公式+高精度

以上公式可以化成

考的时候没有推出公式 所以就GG了
代码

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
#include <iostream>
#include <cstdio>

using namespace std;

int a[100001],h=1;


int main()
{
int n;
a[0]=1;
cin>>n;

for (int i=n+2;i<=n*2;i++)//高精度乘单精度
{
for (int j=0;j<h;j++)
a[j]*=i;
for (int j=0;j<100001;j++)//进位处理
if (a[j]/10>0) {
a[j+1]+=a[j]/10;
a[j]=a[j]%10;
}
h=100001;
while (a[h]==0) h--;//扫一遍找h
h++;
}

for (int i=2;i<=n;i++) //高精度除单精度
{
for (int j=h-1;j>=0;j--)
{
if (a[j]%i!=0)
a[j-1]+=10*(a[j]%i);
a[j]=a[j]/i;
}
}
h=100001;
while (a[h]==0) h--;//扫一遍找h
for (int i=h;i>=0;i--)//输出
cout<<a[i];
}

贪心的小精灵

题目描述

圣诞节到了,一个小精灵想在圣诞树上拿到小礼物。圣诞树一共有层高,在圣诞树的第层,一共有个放置礼物的礼物点,每个礼物点有对应的礼物数量。。小精灵必须从圣诞树的最顶端(1,1)开始拿礼物,每层只能拿从一个礼物点拿对应数量的礼物。小精灵很懒,他每次只会向距离最近的礼物点前进。圣诞树上有个特殊的礼物点,那里的礼物是小精灵必须要拿到的。小精灵既想要经过特殊点,又想要在圣诞树上拿到最多的礼物,请你帮他算出他最多能拿到多少个礼物。

输入格式

第1行只有一个整数,表示层圣诞树;

第2到行,每层每个礼物点的礼物数量,数字之间有一个空格;

行有两个数,表示小精灵必须要经过的礼物点,即第层的第个礼物点。

输出格式

礼物数量总和的最大值

样例

样例输入

1
2
3
4
5
6
7
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
2 2

样例输出

1
28

题解

两边动态规划 就是从上往下和从下往上两次DP
这样求出从(1,1)到必经点的最大和必经点到底部的最大
然后就AC啦

代码如下:

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
#include <iostream>
#include <cstdio>

using namespace std;

int a[103][103],ft[103][103],fb[103][103];

int main()
{
//freopen("gift.in","r",stdin);
//freopen("gift.out","w",stdout);
int n,x,y;
cin>>n;
for (int i=1;i<=n;i++)
for (int j=1;j<=i;j++)
cin>>a[i][j];
cin>>x>>y;
for (int i=1;i<=n;i++)//从上往下 ft[x][y]是从上往下到x,y的最大收获
for (int j=1;j<=i;j++)
ft[i][j]=max(ft[i-1][j],ft[i-1][j-1])+a[i][j];
for (int i=n;i>=1;i--)//从下往上 fb[x][y]是从下往上到x,y的最大收获
for (int j=i;j>=1;j--)
fb[i][j]=max(fb[i+1][j],fb[i+1][j+1])+a[i][j];
/*这些是测试的输出 莫得感情的
for (int i=1;i<=n;i++)
{
for (int j=1;j<=i;j++)
cout<<ft[i][j]<<" ";
cout<<endl;
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=i;j++)
cout<<fb[i][j]<<" ";
cout<<endl;
}*/
cout<<ft[x][y]+fb[x][y]-a[x][y];
return 0;
}

取火柴游戏

→题目在这←

描述

和Nim的石子游戏一摸一样 只是石头变成了火柴

关于Nim游戏可以看这里 Nim游戏

就是说 对于每一种形式 都是必胜态与必败态中的一个
并且每个必胜态肯定存在使情况变为必败态的移动策略
而每个必败态无论如何移动都会让局面成为必胜态

这是代码↓

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
#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
int n;
cin>>n;
int a[n+2],tmp=0;
for (int i=1;i<=n;i++)
{
cin>>a[i];
tmp=tmp ^ a[i];
}
if (tmp==0) {
cout<<"lose";
return 0;
}
int k;
for (int i=1;i<=n;i++)
if ((a[i]^tmp)<=a[i])
{k=i;break;}
cout<<a[k]-(a[k]^tmp)<<" "<<k<<endl;
a[k]=a[k]^tmp;
for (int i=1;i<=n;i++)
cout<<a[i]<<" ";
return 0;
}

十二号诛杀者

介于懒得复制题目(太多用公式大的复制不了)

题目链接

这道题30分

使用Dijkstra最短路

代码如下 极丑无比

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

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
#include <iomanip>

using namespace std;

bool book[600];

int main()
{
freopen("killer.in","r",stdin);
freopen("killer.out","w",stdout);
int n,m,q1,q2,q3,s,u,v,w,l,r,a,b,c,d;
int e[502][502];
cin>>n>>m>>q1>>q2>>q3>>s;
int f[n+3];
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
e[i][j]=2147483647;
for (int i=1;i<=m;i++)
{
cin>>u>>v>>w;
e[u][v]=w;
}
for (int i=1;i<=q1;i++)
{
cin>>u>>l>>r>>w;
for (int j=l;j<=r;j++)
if (w<e[u][j])
e[u][j]=w;
}
for (int i=1;i<=q2;i++)
{
cin>>l>>r>>v>>w;
for (int j=l;j<=r;j++)
if (w<e[j][v])
e[j][v]=w;
}
for (int i=1;i<=q3;i++)
{
cin>>a>>b>>c>>d>>w;
for (int j=a;j<=b;j++)
for (int k=c;k<=d;k++)
if (w<e[j][k])
e[j][k]=w;
}
for(int i=1;i<=n;i++)
e[i][i]=0;
/*
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
cout<<setw(9)<<e[i][j]<<" ";
cout<<endl;
}
*/

int k;

for (int i=1;i<=n;i++)
f[i]=e[s][i];
for (int i=1;i<=n;i++)
{
int mi=2147483647;
for (int j=1;j<=n;j++)
if ((f[j]<mi)&&(book[j]==0))
{
mi=f[j];
k=j;
}
book[k]=1;
//cout<<mi<<" "<<k<<endl;
for (int j=1;j<=n;j++)
if (e[k][j]<2147483647)
if (f[j]>f[k]+e[k][j])
f[j]=f[k]+e[k][j];
}
//for (int i=1;i<=n;i++)
// cout<<book[i]<<" ";
//cout<<endl;
for (int i=1;i<=n;i++)
if (f[i]==2147483647) cout<<-1<<" ";
else
cout<<f[i]<<" ";
return 0;
}

坐等讲解

-------------本文结束,感谢您的阅读-------------