牛客练习赛 55

A - 等火车

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int mod=1e9+7; int main() { IO; int T=1; //cin>>T; while(T--) { int s,q; cin>>s>>q; while(q--) { int t; cin>>t; if(t%s) cout<<s-t%s<<'\n'; else cout<<0<<'\n'; } } return 0; }

B - 数字游戏

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int mod=1e9+7; int main() { IO; int T=1; //cin>>T; while(T--) { ll n; cin>>n; cout<<n-1<<'\n'; } return 0; }

C - 最大生成树

贪心直接求即可

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<int,int> pii; const ll mod=998244353; int main() { IO; int T=1; //cin>>T; while(T--) { ll n; cin>>n; ll a=n/2; a%=mod; cout<<((3*a*a%mod-3*a%mod+1)%mod+mod)%mod; } return 0; }

E - 树

真就化简式子呗？？？ $$dist(x,y)=dep(x)+dep(y)-2dep(lca(x,y))$$ 于是可知 $$\sum _{x=1}^n\sum _{y=1}^{n}dis{t}^2(x,y)=\sum _{x=1}^n\sum _{y=1}^{n}de{p}^2(x)+de{p}^2(y)+2dep(x)dep(y)+4de{p}^2(lca(x,y))-4dep(lca(x,y))\times (dep(x)+dep(y))$$ 对于前三项 $$\sum _{x=1}^n\sum _{y=1}^{n}de{p}^2(x)+de{p}^2(y)=2\sum _{x=1}^{n}de{p}^2(x)$$ $$2\sum _{x=1}^n\sum _{y=1}^{n}dep(x)dep(y)=2\sum _{x=1}^{n}dep(x)\sum _{y=1}^{n}dep(y)=2(\sum _{x=1}^{n}dep(x){)}^2$$ 对于后两项可以枚举公共祖先 $$\sum _{x=1}^n\sum _{y=1}^{n}de{p}^2(lca(x,y))=\sum _{u=lca(x,y)}de{p}^2(u)\times (s{z}^2(u)-\sum _{j\in son(u)}s{z}^2(j))$$ $$\sum _{x=1}^n\sum _{y=1}^{n}dep(lca(x,y))\times (dep(x)+dep(y))=\sum _{u=lca(x,y)}[2\sum _{j\in son(u)}sum(j)(sz(u)-sz(j))+2dep(u)sz(u)]$$

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=1000010; const ll mod=998244353; int h[N],e[2*N],ne[2*N],idx; ll dep[N],sum[N],sz[N]; ll res; int n; void add(int a,int b) { e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } void dfs1(int u,int fa) { dep[u]=dep[fa]+1; sz[u]=1; sum[u]=dep[u]; for(int i=h[u];i!=-1;i=ne[i]) { int j=e[i]; if(j==fa) continue; dfs1(j,u); sz[u]+=sz[j]; sum[u]=(sum[u]+sum[j])%mod; } } void dfs2(int u,int fa) { ll s1=sz[u]*sz[u]%mod,s2=2*dep[u]*sz[u]%mod; for(int i=h[u];i!=-1;i=ne[i]) { int j=e[i]; if(j==fa) continue; dfs2(j,u); s1=(s1-sz[j]*sz[j]%mod)%mod; s2=(s2+2*sum[j]*(sz[u]-sz[j])%mod)%mod; } res=(res+4*s1*dep[u]%mod*dep[u])%mod; res=(res-4*s2*dep[u]%mod)%mod; } int main() { IO; int T=1; //cin>>T; while(T--) { memset(h,-1,sizeof h); cin>>n; for(int i=1;i<n;i++) { int a,b; cin>>a>>b; add(a,b),add(b,a); } dfs1(1,0); ll s=0; for(int i=1;i<=n;i++) { s=(s+dep[i])%mod; res=(res+2ll*n*dep[i]%mod*dep[i])%mod; } res=(res+2*s*s%mod)%mod; dfs2(1,0); res=(res%mod+mod)%mod; cout<<res<<'\n'; } return 0; }

这就是数学的魅力吗？爱了爱了 要加油哦~