# Building trees by weight, plane geometry

14 Day Reading Challenge

## MEX vs MED

It can be found that only when the median in the series is equal toWhen the condition is met, that is, the numbers before the median must also be in the sequence, then we can enumerate from 0~n-1, and use l and r to indicate the occurrence of the first i number According to the above formula, it can be seen that the interval that each i can satisfy is 2*(i+1)-1 and 2*(i+1), and then according to this, we can see how many intervals are legal. Yes, in fact, the last step is very simple, but I always can't control the boundaries of the interval, and finally I want to understand that it is so simple,

```#include <bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-x))
#define endl '\n'
#define double long double
using namespace std;
const int mod=999911659;
const int inf=1e9-1;
const int N=1e6+7;
int qpow(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int getinv(int a){return qpow(a,mod-2);}
int t,n,p[200005],pos[200005];
int cal(int l,int r,int len)
{
int res=0;
int ml=max(r-len+1,1LL),mr=min(n-len+1,l);
if(mr>=ml) res=mr-ml+1;
return res;
}
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
//freopen("in.txt", "r", stdin);
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>p[i];
pos[p[i]]=i;
}
int ans=0,l=pos[0],r=pos[0];
for(int i=0;i<n;i++)
{
l=min(pos[i],l);r=max(pos[i],r);
int len1=2*(i+1)-1,len2=2*(i+1);
int res=0;
res+=cal(l,r,len1);
res+=cal(l,r,len2);
ans+=res;
// cout<<len1<<" "<<len2<<" "<<ans<<endl;
if(l==1&&r==n&&res>0) break;
}
cout<<ans<<endl;
}
return 0;
}
/*
5
0 4 3 2 1
2
*/
```

## Mex Tree Henan Province Competition J Build Trees by Weight

According to the general idea, it is found that the mex of the subtree is difficult to be counted, and then it cannot be done. However, if the tree is built according to the weight, and 0 is used as the root node, there will be no mex of the subtree equal to the root node. situation, so this question is well done

```#include <bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-x))
#define endl '\n'
#define double long double
using namespace std;
const int mod=999911659;
const int inf=1e9-1;
const int N=1e6+7;
int qpow(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int getinv(int a){return qpow(a,mod-2);}
int head[2000006],cnt;
struct Edge
{
int to,next;
}e[2000006];
void addedge(int from,int to)
{
e[++cnt].to=to;
e[cnt].next=head[from];
head[from]=cnt;
}
int n,a[1000006],siz[1000006],ans[1000006];
int dfs(int u,int fa)
{
siz[u]=1;
int minn=u,maxx=0;
for(int i=head[u];i;i=e[i].next)
{
int j=e[i].to;
if(j==fa) continue;
int tmp=dfs(j,u);
minn=min(minn,tmp);
maxx=max(maxx,siz[j]);
siz[u]+=siz[j];
}
if(u>minn) ans[u]=0;
else ans[u]=n-siz[u];
if(u==0) ans[u]=max(ans[u],maxx);
return minn;
}
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
//freopen("in.txt", "r", stdin);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=0;i<=n;i++) ans[i]=0;
for(int i=2;i<=n;i++)
{
int u;cin>>u;
addedge(a[u],a[i]);
addedge(a[i],a[u]);
}
dfs(0,-1);
ans[n]=n;
for(int i=0;i<=n;i++) cout<<ans[i]<<" ";
cout<<endl;
return 0;
}
/*
5
0 4 3 2 1
2
*/
```

## Keiichi Tsuchiya the Drift King Jiaozuo D

In general, w =

But if d is small, then the rear of the car is still on the flat road, then ask for its length on the curved road, and the actual angle of the car is, and then subtract d from this degree du, the side corresponding to this angle is the side of the answer, and then use w*cos(du) to get the answer

```#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+100;
const double eps=1e-8;
const double pi=acos(-1);
double a,b,r,d;
signed main()
{
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--)
{
cin>>a>>b>>r>>d;
d=d/180*pi;
double du=atan(b/(a+r));
double ans=sqrt((r+a)*(r+a)+b*b);
if(d<du)
{
du=du-d;
ans=ans*cos(du);
}
ans-=r;
cout<<fixed<<setprecision(10)<<ans<<endl;
}
return 0;
}
//
```

## P2518 [HAOI2010] Counting - full array

There will be no leading 0. In fact, 0 is put in front. 0012 and 12 are the same size, which is transformed into the number of permutations of n numbers. These permutations are smaller than the number given. Recall the Cantor expansion. When looking for the number of permutations, such as 4231, the first number can be selected from 1, 2, and 3, and there are three options, and the following digits can be selected at will, that is 3*3! , if the second place is chosen, there is 1 choice, and the latter place can be chosen as 2! , and so on in turn, but this question can be repeated, in that case, it can also be calculated by combining numbers. For example, there are m empty spaces in the back, starting from 0, tx[0] represents the number of 0s, then put If it is 0, there will be c[m][tx[0]], and then there will be m-tx[0] empty, then if you put 1, there will be c[m-tx[0]][tx[1]] If you push them down in sequence, you will get a full arrangement.

Problem Solving P2518 [[HAOI2010] Counting] - C3H5ClO's Blog - Luogu Blog

Problem Solving P2518 [[HAOI2010] Counting] - Giant Cube Blog - Luogu Blog

```#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+100;
const double eps=1e-8;
const double pi=acos(-1);
int tx[11],c[55][55];
char n[55];
int cal(int l)
{
int res=1;
for(int i=0;i<=9;i++)
{
res*=c[l][tx[i]];
l-=tx[i];
}
return res;
}
signed main()
{
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n+1;
c[0][0]=1;
for(int i=1;i<=50;i++)
{
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1];
}
int nn=strlen(n+1),ans=0;
for(int i=1;i<=nn;i++) tx[n[i]-'0']++;
for(int i=1;i<=nn;i++)
{
int x=n[i]-'0';
for(int j=0;j<x;j++)
{
if(tx[j])
{
tx[j]--;
ans+=cal(nn-i);
tx[j]++;
}
}
tx[x]--;
}
cout<<ans<<endl;
return 0;
}
//
```

Tags: C++ Algorithm

Posted by tryingtolearn on Thu, 20 Oct 2022 18:28:00 +0300