2020杭电暑期多校第五场
1001.Tetrahedron
标签：数学、结论
结论题。设直角四面体一点到底面3个顶点距离分别为a、b、c，顶点到底面高为h，则有$\frac{1}{h^2}=\frac{1}{a^2}+\frac{1}{b^2}+\frac{1}{c^2}$
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=6e6+5,MOD=998244353;
int T,n,m;
int A[N],sum[N],inv[N];
int qpower(int x,ll p)
{
int res=1;
for (int base=x;p;p>>=1,base=(1ll*base*base)%MOD)
if (p&1==1) res=(1ll*res*base)%MOD;
return res;
}
ll ans;
int main()
{
for (int i=1;i<=N-5;i++)
{
inv[i]=qpower(i,MOD-2);
A[i]=qpower((1ll*i*i)%MOD,MOD-2);
sum[i]=(sum[i-1]+A[i])%MOD;
}
cin>>T;
while(T--)
{
scanf("%d",&n);
printf("%d\n",((1ll*sum[n]*3)%MOD*inv[n])%MOD);
}
return 0;
}
1009.Paperfolding
标签：数学
上下折k下，左右折n-k下的方案数为$C_n^k$，剪下来的片数为$(2^k+1)(2^{n-k}+1)$
所以$sum=\sum_{k=0}^{n}C_n^k(2^k+1)(2^{n-k}+1)=\sum_{k=0}^{n} C_n^k(2^n+2^k+2^{n-k}+1)=2^n2^n+2^n+2\sum_{k=0}^{n}C_n^k2^k$
(最后一项$\sum_{k=0}^{n}C_n^k2^k=3^n$)
除去总方案数$2^n$得到期望$exp=2^n+1+\frac{3^n}{2^{n-1}}$
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,MOD=998244353;
int T,m;
ll n;
int inv2;
int qpower(int x,ll p)
{
int res=1;
for (int base=x;p;p>>=1,base=(1ll*base*base)%MOD)
if (p&1==1) res=(1ll*res*base)%MOD;
return res;
}
ll ans;
int main()
{
cin>>T;
inv2=qpower(2,MOD-2);
while(T--)
{
scanf("%lld",&n);
if (n==0){
printf("4\n");
continue;
}
ans=0;
ans+=qpower(2,n);
ans+=1;
ll temp=(1ll*qpower(3,n)*qpower(inv2,n-1))%MOD;
ans=(ans+temp)%MOD;
printf("%lld\n",ans);
}
return 0;
}
1003.Boring-Game
标签：模拟
模拟，一层一层把它翻下来。
起始状态可以视作一堆，每翻一层可以拆分成两个过程。
- 把当前状态每一堆一分为二，在上面的一段继承原来的编号，下面的一段编号乘2
- 把上面那段内部的值整体翻转，然后按照编号倒着放在左边
随便画一下就是
然后实现的话用A记录内部的翻转，B记录整体的编号情况（因为不能push_front所以先push_back然后再reverse，写的有点绕）。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5,MOD=998244353;
int T,n,m,k;
int jc[20];
int A[N],ans[N];
vector<int>B;
void solve()
{
cin>>n>>k;
int tot=2*n*jc[k];
for (int i=1;i<=tot;i++) A[i]=i;
int len=tot/2;
B.clear();
B.push_back(1);
for (int i=1;i<=k;i++)
{
for (int j=1;j<=tot;j+=len*2)
{
reverse(A+j,A+len+j);
}
len/=2;
}
for (int i=1;i<=k;i++)
{
for (int i=0;i<B.size();i++) B[i]*=2;
for (int i=B.size()-1;i>=0;i--) B.push_back(B[i]-1);
}
reverse(B.begin(),B.end());
for (int i=1;i<=tot;i++)
{
int x;
scanf("%d",&x);
ans[i]=x;
}
len*=2;
for (int i=1;i<=n*2;i++)
for (int j=1;j<=jc[k];j++)
{
printf("%d",ans[A[i+len*(B[j-1]-1)]]);
if (i!=n*2 || j!=jc[k]) printf(" ");
}
printf("\n");
}
int main()
{
cin>>T;
jc[0]=1;
for (int i=1;i<=15;i++) jc[i]=jc[i-1]*2;
while(T--) solve();
return 0;
}
1012.Set1
标签：找规律， 组合数，概率
这题我感觉题解可能稍微讲复杂了一点。。
对于当前的i，我们的目标是对于前i-1个数，每个数都能找到另一个对应的数，并且最终除了i之外每个数都能匹配上。这样一来每自动消去一个数，就选择删掉它对应的那个数，最终一定对应了一种合法方案。
首先当i<=n/2时，前i-1个数不能使后n-i个数都匹配，答案为0。
当i>n/2时，先固定住后n-i个数，用前i-1个数去匹配，一共有$P_{i-1}^{n-i}$种方案，对于剩下的$2i-1-n$个数再两两匹配并消除先后顺序，也就是$\binom{2i-1-n}{2,2,2,…}\times \frac{1}{(\frac{2i-1-n}{2})!}$
乘起来计算一下就是$\frac{(i-1)!}{2^{(2i-1-n)/2}}\times (\frac{2i-1-n}{2})!$
最后再除以总方案数$(n-1)!!$
可以$O(n)$线性计算
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=5e6+5,MOD=998244353;
int T,n,sjc[N],jc[N],inv[N];
int bin(int base,int p) {
int res=1;
for (;p;p>>=1,base=(1ll*base*base)%MOD) {
if (p&1) res=(1ll*res*base)%MOD;
}
return res;
}
void init() {
jc[0]=jc[1]=sjc[0]=sjc[1]=inv[1]=1;
for (int i=2;i<=N-5;i++) {
sjc[i]=(1ll*sjc[i-2]*i)%MOD;
jc[i]=(1ll*jc[i-1]*i)%MOD;
inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
}
}
void solve() {
cin>>n;
int ans;
for (int i=1;i<=n;i++) {
if (i<=n/2) {
printf("0%c",i==n?'\n':' ');
continue;
}
if (i==n/2+1) ans=1ll*jc[i-1]*bin(bin(2,(2*i-1-n)/2),MOD-2)%MOD*bin(sjc[n-1],MOD-2)%MOD;
else ans=1ll*ans*(i-1)%MOD*inv[2]%MOD*inv[(2*i-1-n)/2]%MOD;
printf("%d%c",ans,i==n?'\n':' ');
}
}
int main() {
init();
cin>>T;
while(T--) solve();
return 0;
}
1007.Tree
标签：树形dp
用dp[n][0]表示对于当前子树根n，任何子结点度数都小于等于k的最大权值(n当前度数最多为k-1)。
用dp[n][1]表示对于当前子树根n，存在结点度数大于k时的最大权值。
定义好之后转移起来就不是很麻烦了。
dp[n][0]为子树中最大的k-1个dp[x][0] （x为子树根）
dp[n][1]要么为所有子树的dp[x][0]，要么为k-2个dp[x][0]+1个dp[x][1]权值最大的方案。
然后还需要特判一种情况，就是当前的n向下连了k棵子树并不再向上连边。判断方法和dp[n][1]的求法类似。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int N=2e5+5;
struct Edge{
int to;
ll v;
};
vector<Edge>G[N];
vector<pii>ve[N];
ll ans;
int T,n,m,k;
ll dp[N][2];
void dfs(int x,int f) {
if (G[x].size()==1 && f!=-1) return;
for (auto now:G[x]){
int to=now.to,v=now.v;
if (to==f) continue;
dfs(to,x);
ve[x].push_back({dp[to][0]+v,dp[to][1]+v});
}
sort(ve[x].begin(),ve[x].end(),[&](pii a,pii b){return a.first>b.first;});
ll sum1=0,sum2=0,sum3=0,mx1=0,mx2=0;
for (int i=0;i<ve[x].size();i++){
if (i<k-1) sum1+=ve[x][i].first;
sum2+=ve[x][i].first;
if (i<k-1) mx1=max(mx1,ve[x][i].second-ve[x][i].first);
if (i>=k-1 && k>=2) mx1=max(mx1,ve[x][i].second-ve[x][k-2].first);
}
if (ve[x].size()>=k) {
for (int i=0;i<ve[x].size();i++){
if (i<k) mx2=max(mx2,ve[x][i].second-ve[x][i].first);
if (i>=k) mx2=max(mx2,ve[x][i].second-ve[x][k-1].first);
}
sum3=sum1+ve[x][k-1].first;
ans=max(ans,sum3+mx2);
}
dp[x][0]=max(dp[x][0],sum1);
dp[x][1]=max(dp[x][1],sum2);
dp[x][1]=max(dp[x][1],sum1+mx1);
ans=max(ans,dp[x][0]);
ans=max(ans,dp[x][1]);
}
void solve() {
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++) {
G[i].clear();
ve[i].clear();
}
for (int i=1;i<=n-1;i++) {
int u,v; ll w;
scanf("%d%d%lld",&u,&v,&w);
G[u].push_back({v,w});
G[v].push_back({u,w});
}
if (k==0) {
printf("0\n");
return;
}
ans=0;
for (int i=1;i<=n;i++) dp[i][0]=dp[i][1]=0;
dfs(1,-1);
printf("%lld\n",ans);
}
int main() {
cin>>T;
while(T--) solve();
return 0;
}