按权值建树，平面几何

14天阅读挑战赛

 MEX vs MED 

可以发现只有当序列中的中位数等于时才会满足条件,也就是中位数之前的那些数也必须在序列中才可以，那我们就可以从0~n-1的顺序来枚举，用l和r来表示前i个数出现的范围，根据上面的那个公式其实也可以看出每个i可以满足的区间是2*(i+1)-1和2*(i+1),然后根据这个来看看有多少区间合法就可以，其实最后这一步很简单，但是我老是把控不好区间的边界，最后才想明白原来这么简单，，，

#include 
#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
        {
            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<
            if(l==1&&r==n&&res>0) break;
        }
        cout<
    }
    return 0;
}
/*
5
0 4 3 2 1
2
*/

Mex Tree 河南省赛 J 按权值建树

按照普通的思路来之后发现子树的mex很难统计，然后就做不出来了，，，但是要是按权值建树之后，按0为根节点，就不会出现子树的mex等于根节点的情况了，所以这题就很好做了

#include 
#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<" ";
        cout<
    return 0;
}
/*
5
0 4 3 2 1
2
*/

Keiichi Tsuchiya the Drift King 焦作 D 

一般的情况就是w=

但是如果d很小的话，那么车尾还是在平路上，那就要求出他在弯路上的长度，车的实际的角度是,然后用这个度数du减去d后这个角度所对应的边就是那个答案的边，再用w*cos(du)就得到答案了

#include 
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-d;
            ans=ans*cos(du);
        }
        ans-=r;
        cout<setprecision(10)<
   }
    return 0;
}
//

P2518 [HAOI2010]计数 - 全排列

不会有前导0其实也就是把0放前面，0012和12是同样大小的，这样就转化成了求n个数的排列数，这些排列都符合小于给出的那个数，回想一下康托展开求一个排列是第几个排列的时候，比如4231，第一个数可以选1，2，3有三种选择，后面的位可以随便选，那就是3*3！，第二位选的话有1种选择，后面的位可以随便选就是2！，这样依次推下去，但这个题是数可以重复的，那样的话也是可以用组合数来算的，比如后面还有m个空，从0开始，tx[0]表示0的个数，那么放0的话就有c[m][tx[0]]种，之后还剩下m-tx[0]个空，那么放1的话就有c[m-tx[0]][tx[1]]种，这样依次推下去也会得到全排列

题解 P2518 【[HAOI2010]计数】 - C3H5ClO的博客 - 洛谷博客

题解 P2518 【[HAOI2010]计数】 - 巨型方块 的博客 - 洛谷博客

#include 
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-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
        {
            if(tx[j])
            {
                tx[j]--;
                ans+=cal(nn-i);
                tx[j]++;
            }
        }
        tx[x]--;
   }
   cout<
    return 0;
}
//