2019.8.1效实模拟赛题解
loutianchi
·
·
个人记录
话不多说先上题
1、判断素数个数
这是一道十分简单的题目。
（我是不会告诉你们输入的两个端点是无序的）
如此简单的题目就上代码吧
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
int a[110000];
int main()
{
// freopen("prime.in","r",stdin);
// freopen("prime.out","w",stdout);
int n,m;
cin>>n>>m;
if (m<=n) swap(m,n);
memset(a,0,sizeof(a));
a[1]=1;
for (int i=2;i<=317;i++)
for (int j=2;j<=100000/i;j++)
{
a[i*j]=1;
}
int tmp=0;
for (int i=n;i<=m;i++)
{
tmp+=1-a[i];
}
cout<<tmp<<endl;
return 0;
}
2、火车调度序列统计
这也是一道十分简单的题目，但是我们需要有一双明亮的眼睛来发现这其实是catalan数（像我就是在比赛的时候受到了大佬的提示）
catalan数的计算公式如下：
**\frac{1}{n+1}
但是这道题要用高精度，但是我忘了高精度除法，so看代码
```cpp
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
int a[1010];
int gcd(int x,int y)
{
int a,b,c;
a=x,b=y,c=a%b;
while (c!=0)
{
a=b,b=c,c=a%b;
}
return b;
}
int p,ans[3000];
int cheng(int x)
{
int k=0;
for (int i=1;i<=p;i++)
{
k+=ans[i]*x;
ans[i]=k%10;
k/=10;
}
while (k>0)
{
p++;
ans[p]=k%10;
k/=10;
}
return 0;
}
int main()
{
freopen("stack.in","r",stdin);
freopen("stack.out","w",stdout);
int n;
cin>>n;
for (int i=1;i<=n;i++)
a[i]=n+i;
int x,j,y;
for (int i=2;i<=n+1;i++)
{
x=i;j=1;
while (x>1)
{
y=gcd(x,a[j]);
a[j]/=y;
x/=y;
j++;
}
}
p=1;ans[1]=1;
for (int i=1;i<=n;i++)
cheng(a[i]);
for (int i=p;i>=1;i--)
cout<<ans[i];
cout<<endl;
return 0;
}
```
下面要总结一下catalan数的几个常用使用处：
1、括号匹配问题（n对括号有多少种匹配方式）
2、进栈出栈问题（一个栈(无穷大)的进栈序列为1，2，3，……，n，有多少个不同的出栈序列）
3、二叉树的种类问题（n个节点构成的二叉树，共有多少种情形）
4、凸多边形分割问题（求一个凸多边形区域划分成三角形区域的方法数）
5、集合划分问题（对于集合{1,2,3...2n}的不交叉划分的数目为多少）
6、连线不相交问题（在圆上有2n个点，将这些点成对连接起来使得所得到的n条线段不相交的方法数）
7、门票找钱问题
有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零
---
## 3、[贪心的小精灵](http://www.nbxiaoshi.net:8011/problem/5002)
很基础的一道动态规划的题目，和数字三角形很像（不同点是此题要过一个规定的点）
那么我们就按数字三角形的思想方法来解决这个问题：将到了这个点以后就将一定无法到达的点（在这个点下方的，因为我是自下而上动规的）清为-$\infty$。然后就可以做一个基本动规了。
代码如下：
```cpp
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
int a[110][110],f[110][110];
int main()
{
// freopen("gift.in","r",stdin);
// freopen("gift.out","w",stdout);
int n;
cin>>n;
for (int i=1;i<=n;i++)
for (int j=1;j<=i;j++)
cin>>a[i][j];
int x,y,y1;
cin>>x>>y;
y1=y;
for (int i=x;i<=n;i++)
{
for (int j=1;j<=y-1;j++)
a[i][j]=-2000000;
for (int j=y1+1;j<=i;j++)
a[i][j]=-2000000;
y1++;
}
memset(f,0,sizeof(f));
for (int i=1;i<=n;i++) f[n][i]=a[n][i];
for (int i=n-1;i>=1;i--)
{
for (int j=1;j<=i;j++)
f[i][j]=a[i][j]+max(f[i+1][j],f[i+1][j+1]);
}
cout<<f[1][1]<<endl;
return 0;
}
```
---
## 4、[取火柴游戏](http://www.nbxiaoshi.net:8011/problem/5003)
这是一个博弈论的经典题目。
又称Nim取石子游戏(^_^)
这道题目存在必胜态和必败态：
首先，我们可以确定：如果当前状态为必胜态的话，一定有方法将其转化为必败态（也就是一定会让对手必败）。
其次，如果当前状态为必胜态的话，无论如何操作都会使状态转化为必胜态（也就是对手在必败态的情况下一定会使你重新变回必胜态)。
所以我们要思考就是如何将一个必胜态转化为一个必败态。
我们设：
x=a[1]^a[2]^a[3]^……^a[n]
若x=0，则当前状态属于必败态。
否则，我们要将一个必胜态转化为必败态，方法如下：
我们可以确定：存在k使 a[k]>=a[k]^x (x的最高位是来自于a中的，所以我们可以确定一定存在k)
将a[k]替换为a[k]^x，则可以得到：
a[1]^a[2]^……^a[k]^x^……^a[n]=x^x=0
得到了必败态
那么我们就知道了a[k]-a[k]^a[n]是一个可行的操作。
下面是代码
```cpp
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
int a[20],x[500001];
int main()
{
// freopen("stick.in","r",stdin);
// freopen("stick.out","w",stdout);
int n,xorh=0;
cin>>n;
for (int i=1;i<=n;i++)
{
scanf("%d",&x[i]);
xorh=x[i]^xorh;
}
if (xorh==0)
{
cout<<"lose"<<endl;
return 0;
}
int answei,anszhi;
for (int i=1;i<=n;i++)
{
if (x[i]>=(x[i]^xorh))
{
answei=i;
anszhi=x[i]-(x[i]^xorh);
x[i]-=anszhi;
break;
}
}
cout<<anszhi<<" "<<answei<<endl;
for (int i=1;i<=n;i++)
cout<<x[i]<<" ";
cout<<endl;
return 0;
}
```
---
## 5、[十二号诛杀者](http://www.nbxiaoshi.net:8011/problem/40)
一个图论中的题目
用中间节点、线段树优化和最短路算法来实现，代码正在赶来的途中……