AtCoder Beginner Contest 284（D，E，F）
D
这可题的大意是有一个很大的数，n,它可以变成pXpXq(p,q是质数)，要我们找出这两个质数
我们可以发现，这一个n的质因数一定只有两个，p,q，而我们只要发现了n的一个因数，那么这个因数要么是p，pXp,要么是q,(只有这三种数是n的因数)，而我们是从小到大遍历的，那么第一个找到的要么是p,要么是q,我们需要判断一下，如果这一个数是x(n%x=0),如果（n/x)%x==0,那么这个数是p,(另外一个就是n/x/x),否则x就是q,那么p就是sqrt(n/x)(四舍五入)，这里使用了round()函数
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define int long long
int n,t;
void solve()
{
cin>>n;
int x=0,y=0;
for (int i=2;i*i*i<=n;i++)//最大的i，一定是i*i*i<=n
{
if (n%i) continue;
if ((n/i)%i==0)
{
x=i,y=(n/i)/i;
}
else
{
y=i;
x=round(sqrt(n/i));
}
break;
}
cout<<x<<" "<<y<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
E
题目大意是要我们求出从1到x(任意可到达的点)有多少条路径（但是这一条路径中不可以出现相同点，根据这一个，我们可以用到回溯,题目还告诉我们每个店的度不会大于10，而我们要找的数量ans=min(1e6,ans)，所以我们dfs最多在1e7的样子，应该不会超时
只要我们到达了一个点，就多了一条路径（我感觉就这句是有用的，前面在讲废话）
#include <iostream>
#include <vector>
using namespace std;
const int maxn=2e5+10;
vector<int>g[maxn];
int limit = 1000000;
int n,m;
int ans;
bool vis[maxn];
void dfs(int u,int fa)
{
ans++;
if (ans==limit)
{
cout<<ans<<'\n';
system ("pause");
exit(0);
}
for (auto v:g[u])
{
if (v==fa) continue;
if (vis[v]) continue;
vis[v]=true;
dfs(v,u);
vis[v]=false;
}
return ;
}
int main ()
{
cin>>n>>m;
for (int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
vis[1]=true;
dfs(1,-1);
cout<<ans<<'\n';
system ("pause");
return 0;
}
F
前置知识：
我看了前面还是不太明白到底要怎么用，刚好这一道题给我加深了对这一个算法的理解
我这里来浅浅表达一下我在做完了这一个题后对z_algorithm的z数组的理解
z[i]就是从i开始的后缀可以和从第一个开始字符串的最长相同序列的长度（这不就是z的意义吗？）我一开始没理解，觉得太抽象（虽然现在也很抽象）（个人拙见）
这个题呢，就是给你一个字符串f(i)，由3部分组成，
第一部分是s的0到i的子串
第二部分是原来的s的翻转
第三部分是i到n的子串
要我们知道这一个i和s,如果找不到，就输出-1
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
vector<int>z_algorithm(string s)
{
int n=s.size();
vector<int>z(n);
int l=0,r=0;
for (int i=1;i<n;i++)
{
if (i<=r)
{
z[i]=min(r-i+1,z[i-l]);
}
while (i+z[i]<n&&s[z[i]]==s[i+z[i]])
{
z[i]++;
}
if (i+z[i]-1>r)
{
l=i,r=i+z[i]-1;
}
}
return z;
}
int main ()
{
int n;
cin>>n;
string t;
cin>>t;
string a=t.substr(0,n);
string b=t.substr(n);
reverse(b.begin(),b.end());
string x=a+b;
vector<int>z_x=z_algorithm(x);
z_x.push_back(0);
string y=b+a;
vector<int>z_y=z_algorithm(y);
z_y.push_back(0);
for (int i=0;i<=n;i++)
{
if (z_x[2*n-i]==i&&z_y[n+i]==n-i)
{
cout<<(t.substr(0,i)+t.substr(n+i))<<'\n';
cout<<i<<'\n';
system ("pause");
return 0;
}
}
cout<<-1<<'\n';
system ("pause");
return 0;
}