8.27模拟赛 - 洛谷保存站

# 分数
**估分：**

T1:100  
T2:30  
T3:0  
T4:0

**实际：**

T1:90  
T2:30  
T3:0  
T4:0

**原因：**

T1:由于$n\le10^6$，而我没有任何输入优化，导致最后2个点TLE。  
T2:无。  
T3:无。  
T4:无。

# $miller$版题解
## T1:zero
[原题](https://www.luogu.com.cn/problem/T661054)  
题意：给定$n$个数，求他们的积末尾有几个0。

根据题意可以知道我们只需判断最后的积里有几个因数$10$。而$10=2\times5$，所以只需要在输入时分解出每个数的因数$2$与因数$5$即可。  
**注意：计算的时间复杂度为$O(3\times10^7)$，但如果不加输入优化，时间复杂度就会变为$O(6\times10^7)$**

```cpp
#include<bits/stdc++.h>
using namespace std;
int n,two,five,a;
int main()
{
    freopen("zero.in","r",stdin);
    freopen("zero.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        while(a%2==0)two++,a/=2;
        while(a%5==0)five++,a/=5;
    }
    printf("%d",min(two,five));
    return 0;
}

```
## T2:moon
[原题](https://www.luogu.com.cn/problem/T661055)  
题意：约瑟夫问题，给你人数与淘汰周期长度，求哪个位置不会被淘汰。

可以发现，如果我们每淘汰一人就拿下一人当做1号，那么倒数第$i-1$轮第$x$个人第$i$轮就是第$(x+((m-1)\%i+1)-1)\%i+1$号。我们只需要从倒数第$2$轮推至第$1$轮（倒数第$n$轮）即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=1;
int main()
{
	cin>>n>>m;
	for(int i=2;i<=n;i++)ans=(ans+((m-1)%i+1)-1)%i+1;
	cout<<ans;
	return 0;
}
```
## T3:blackhole
[原题](https://www.luogu.com.cn/problem/T661056)  
题意：给定$n\times m$的矩阵，开始时所有位置上均有棋子。每次所有棋子会朝同一方向移动一格，当棋子碰到`O`或掉出棋盘时被淘汰。请问有多少颗棋子可能成为最后被淘汰的（不包含并列）。

我不会
```cpp
//我是人机我不会
```
## T4:dfs
[原题](https://www.luogu.com.cn/problem/T661057)  
题意：一个人在一棵树上从根节点开始移动，每次他会选择没走过的一个孩子节点进入，当孩子都走过时他会回到父亲节点。每到一个房间（不管到没到过）他都会在自己手中的字符串末尾加上当前节点对应的字符（字符串初始为空）

容易发现，每个子树在字符串中都是连续的，所以我们设$f[i][j]$表示区间$[i,j]$的树的不同的种数。可以得到方程：
```cpp
#include<bits/stdc++.h>
using namespace std;
string s;
int n,f[305][305];
int main()
{
	cin>>s;
	n=s.size();
	s='A'+s;
	for(int i=1;i<=n;i++)f[i][i]=1;
	for(int len=2;len<n;len++)
	{
		for(int l=1;l+len<=n;l++)
		{
			if(s[l]!=s[l+len])f[l][l+len]=0;
			else f[l][l+len]=f[l+1][l+len-1];
			for(int k=l+2;k<l+len-1;k++)f[l][l+len]+=(s[k]==s[l])*f[l+1][k-1]*f[k][l+len];
		}
	}
	cout<<f[1][n];
	return 0;
}
```

正在渲染内容...