【题解】牛客算法周周练14

题目链接：

https://ac.nowcoder.com/acm/contest/6226

B、Circle

相邻的两个数字一定是互质的，所以我们只需要从1放到n即可，直接输出n

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int main()
{
    int n;
    sc("%d", &n);
    pr("%d", n);
}

C、Tree

题意：

给一棵树，求包含第 i 个点的连通子集数量

做法：

首先看到范围1e6，并且题目是一棵树，显然考虑换根dp。

但是这个题目居然存在整除，然后逆元直接变成0了的情况。那也太自闭了。。。

所以每次整除的时候，我们考虑重新使用dfs1求出这个点的值来代替换根的做法即可。

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e6 + 5;
struct edge
{
	int to;
	int nex;
}e[MAXN * 2];
int head[MAXN], tot;
void init()
{
	memset(head, -1, sizeof(head));
	tot = 1;
}
void add(int a, int b)
{
	e[tot] = edge{ b,head[a] };
	head[a] = tot++;
}
ll dp[MAXN];
ll cost[MAXN];
ll temp[MAXN];
const ll mod = 1e9 + 7;
ll power(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1)
			res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
ll dfs1(int u, int fa, ll temp[])
{
	ll ans = 1;
	for (int i = head[u]; i + 1; i = e[i].nex)
	{
		int v = e[i].to;
		if (v == fa)
			continue;
		ans = ans * (dfs1(v, u, temp) + 1) % mod;
	}
	temp[u] = ans;
	return ans;
}
void dfs2(int u, int fa)
{
	for (int i = head[u]; i + 1; i = e[i].nex)
	{
		int v = e[i].to;
		if (v == fa)
			continue;
		if ((dp[v] + 1) % mod == 0)
		{
			dfs1(v, 0, temp);
			dp[v] = temp[v];
		}
		else
		{
			cost[v] = dp[u] * power(dp[v] + 1, mod - 2);
			dp[v] = (cost[v] + 1) % mod * dp[v] % mod;
		}
		dfs2(v, u);
	}
}
int main()
{
	init();
	int n;
	sc("%d", &n);
	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		sc("%d%d", &a, &b);
		add(a, b);
		add(b, a);
	}
	dfs1(1, 0, dp);
	dfs2(1, 0);
	for (int i = 1; i <= n; i++)
		pr("%lld\n", dp[i]);
}
/*
10
1 3
3 5
5 9
9 4
1 6
1 7
2 8
3 8
7 10
*/

D、绝地求生（pubg）

显然题意就是要求 lcm(x,y) ，即最小公倍数，先使用欧几里得算法求出最大公因数即可得到最小公倍数，注意要用long long，并且由于 x*y 可能超出 long long范围，可以考虑使用java的Biginteger或者先除以gcd再乘另一个数字

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
    int T, cas = 1;
    sc("%d", &T);
    while (T--)
    {
        ll x, y;
        sc("%lld%lld", &x, &y);
        ll ans = x / gcd(x, y) * y;
        pr("Case %d: %lld\n", cas++, ans);
    }
}

E、[水] 悠悠碧波

题意：

求一个串，要求他给给定串的前缀，也是给定串的后缀，也在给定串中间出现过，求这个串的最大长度

做法：

显然我们可以通过依次kmp求出满足中间出现过，并且是前缀的最长长度，那么同理，我们讲整个串反过来，再求一边kmp，这样就可以得到满足中间出现过，并且是后缀的最长长度，然后我们将这两个数组比较一下长度是否相等，就可以得到满足题意的最长长度了

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
char s1[100005], s2[100005];
int nex1[100005], nex2[100005];
void pre(char b[], int nex[], int len)
{
    int i = 0, j = -1;
    nex[0] = -1;
    while (i < len)
    {
        if (j == -1 || b[i] == b[j])
            nex[++i] = ++j;
        else
            j = nex[j];
    }
}
int main()
{
    sc("%s", s1);
    int len = strlen(s1);
    for (int i = 0; i < len; i++)
        s2[i] = s1[len - i - 1];
    pre(s1, nex1, len);
    pre(s2, nex2, len);
    int ans = 0;
    for (int i = 1; i < len; i++)
    {
        if (nex1[i] == nex2[len - i + nex1[i]] && ans < nex1[i])
        {
            ans = nex1[i];
        }
    }
    for (int i = 0; i < ans; i++)
        pr("%c", s1[i]);
}