牛客算法周周练14
友谊巨轮
https://ac.nowcoder.com/acm/contest/6226/A
我按照我的AC顺序来写一下吧，A题是个线段树还没有做出来
B-Circle
- 题意已经很清楚了，主要是个人理解的快慢了
- 其实按照
这样围成一个环就好了
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int main()
{
int n;
cin >> n;
cout << n << endl;
return 0;
}D-绝地求生（pubg）
- 调用一下库函数__gcd(x,y) 算出最大公约数t，然后x*y / t
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int main()
{
int t;
cin >> t;
for(int i = 1;i <= t;i ++)
{
LL x,y;
cin >> x >> y;
LL t = __gcd(x,y);
cout << "Case " << i << ":" << " " << x/t*y << endl;
}
return 0;
}E-悠悠碧波
- 我用的字符串hash暴力做的，首先我是没有提前做出来，是赛后30秒左右才过的
- 只需要找到从大到小找前缀和后缀是不是一样，然后再从中间找到是否存在该前缀，如果存在那么此时就是找到了最大值然后break
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010 ,P = 131;
typedef unsigned long long ull;
int n, m;
char str[N];
ull h[N],p[N];
ull get(int l,int r)
{
return h[r] - h[l-1] * p[r-l+1];
}
bool solve(int l)
{
for(int i = 2;i <= n - l;i ++)
{
if(get(i,i + l - 1) == get(1,l)){
return true;
}
}
return false;
}
int main()
{
cin >> str + 1;
p[0] = 1;
n = strlen(str + 1);
for(int i = 1;i <= n;i++)
{
h[i] = h[i-1] * P + str[i];
p[i] = p[i-1] * P;
}
int i,j;
for(i = n - 1,j = 2;i > 0;i --,j ++)
{
if(get(1,i) == get(j,n)){
if(solve(i))
{
for(int j = 1;j <= i;j ++)
{
cout << str[j];
}
break;
}
}
}
return 0;
}- 接下来是我在赛后补的C题了，这个题非常好，建议大家去做一下
C-Tree
- 这个题涉及到了费马小定理，换根Dp
- 题意比较晦涩难懂
- 求一颗树中每个点包含其的联通子集的数量
- 首先还是按照换根dp的套路，以1号点为根节点算出每个点对其父亲节点的贡献度
- 而每个点对其父亲的贡献度为 base = base * (p[x] + 1) % mod;
- p[u] = base
- 这个是根据乘法原理推出来的
void dfs1(LL u,LL fa) { pre[u] = fa; LL base = 1; for(auto &x : v[u]) { if(x == fa)continue; dfs1(x,u); base = base * (p[x] + 1) % mod; } p[u] = base; } - 下面就是dfs2了，也就是换根的公式了
- 对于每个子节点x其ans[x] = (ans[u] / (p[x] + 1) + 1) * p[x] % mod;
- 这里ans[u]是父亲的值，那么父亲所收获的除了x节点的贡献度不就是
,那么其他节点对x的贡献度不就是
,那么x的其他节点对x的贡献度就是p[x]，所以
- 而在算num的时候我们需要做除法并且需要%mod,那么这个时候就涉及到了求逆元
%
%
%
LL num = (long long)ans[u] * inv(p[x] + 1) % mod;
ans[x] = (num + 1) * (p[x]) % mod;- 但是如果p[x] + 1 % mod = 0 ，那么逆元就求不出来了，这个时候我们需要找到一个新的道路来求出ans[x]
- 我们需要算出其父亲节点u对x的贡献度，那么也就是算出父亲节点的所有不包括子节点x的贡献度
- u的父亲节点对u的贡献度为 num = ans[fa] * inv(p[u] + 1) % mod
- u的其他节点对u的贡献度就是num = num * (p[y] + 1) % mod
- 那么u对x的贡献度不就是num + 1
- 所以ans[x] = (num + 1) * p[x] % mod
LL num = ans[fa] * inv(p[u] + 1) % mod + 1;
for(auto &y : v[u])
{
if(y == x || y == fa)continue;
num = num * (p[y] + 1) % mod;
}
ans[x] = (num + 1) * p[x] % mod;- 下面是这个题AC的代码
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const LL N = 1e6 + 10;
const LL mod = 1e9 + 7;
vector<LL>v[N];
LL p[N];
LL ans[N];
LL n;
LL qpow(LL a,LL k)
{
LL res = 1;
while(k)
{
if(k & 1)
res = (long long)res * a % mod;
a = (long long )a * a % mod;
k >>= 1;
}
return res;
}
LL inv(LL x)
{
return qpow(x,mod - 2) % mod;
}
void dfs1(LL u,LL fa)
{
LL base = 1;
for(auto &x : v[u])
{
if(x == fa)continue;
dfs1(x,u);
base = base * (p[x] + 1) % mod;
}
p[u] = base;
}
void dfs2(LL u,LL fa)
{
for(auto &x : v[u])
{
if(x == fa)continue;
if((p[x] + 1) % mod == 0)
{
LL num = ans[fa] * inv(p[u] + 1) % mod + 1;
// 这是算出u的父亲节点对u的贡献度，这个父亲是fa
for(auto &y : v[u])
{
if(y == x || y == fa)continue;
/*
对于这个地方是算除去x节点（fa是因为上面我已经算了，所以不需要再算了），
的其他节点对u的贡献度;(此时最好自己假象如果x的父亲的话，该怎么求，就好理解了)
*/
num = num * (p[y] + 1) % mod;
}
ans[x] = (num + 1) * p[x] % mod;
}
else
{
LL num = (long long)ans[u] * inv(p[x] + 1) % mod;
ans[x] = (num + 1) * (p[x]) % mod;
}
dfs2(x,u);
}
}
int main()
{
ios::sync_with_stdio(false);
cin >> n;
for(LL i = 0;i < n - 1;i ++)
{
LL a,b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
dfs1(1,0);
ans[1] = p[1];
dfs2(1,0);
// exit(0);
for(LL i = 1;i <= n;i ++)
{
cout << ans[i] << endl;
}
return 0;
}- 如果哪里不对希望大佬指正
