题意：一棵树，点i上有ai个石头，每次操作可以选择一条两个叶子之间的简单路径，并从路径上每个节点都移除一个石头。求是否可以经过一些操作之后移除所有石头。

从下往上dp，设点i子树中需要通过该点的路径数和为sum，那么就有sum-ai条路径跨过i点，2ai-sum条路径经过ai父亲。设需要通过该点的路径数最大的子树需要通过该点的路径数为mx，那么如果sum-mx<sum-ai则无解。

#include <bits/stdc++.h>
using namespace std;
#define N 110000
int n,tot,root;
int a[N],head[N],nex[N<<1],to[N<<1];
int du[N],rem[N];
void add(int x,int y)
{
    tot++;
    nex[tot]=head[x];head[x]=tot;
    to[tot]=y;
}
void quit(){puts("NO");exit(0);}
void dfs(int x,int y)
{
    if(du[x]==1)
    {
        rem[x]=a[x];
        return;
    }
    int mx=0,sum=0;
    for(int i=head[x];i;i=nex[i])
        if(to[i]!=y)
        {
            dfs(to[i],x);
            sum+=rem[to[i]];
            mx=max(mx,rem[to[i]]);
        }
    int v1=sum-a[x],v2=a[x]-v1;
    if(v1<0||v2<0)quit();
    if(sum-mx<v1)quit();
    rem[x]=v2;
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
        du[x]++;du[y]++;
    }
    if(n==2)return puts(a[1]==a[2] ? "YES" : "NO"),0;
    root=1;
    while(du[root]==1)root++;
    dfs(root,0);
    if(rem[root])quit();
    puts("YES");
    return 0;
}

题意：一棵n个点的树，其中一些点已经有值，需要给所有没有值的点赋值，使任意相邻的两个点相差恰好为1，求是否可行，可行求一组解。

对所有有值的点建一棵虚树，每个儿子会对父亲的取值范围和奇偶性有一个限制，从下往上dp，如果出现不合法的情况无解。之后虚树上没有值的点会有一个取值范围。从上往下dp，虚树上每个点取范围内任意一个满足奇偶性的值，并对虚树边上的点赋值，最后对不在虚树边上的点赋值。

#include <bits/stdc++.h>
using namespace std;
#define N 110000
const int inf=1e9;
int n,tot,m,cnt,top;
int head[N],nex[N<<1],to[N<<1];
int fa[N][21],deep[N];
int val[N],L[N],R[N],pos[N],a[N],st[N],sig[N];
vector<int>vec[N];
void quit(){puts("No");exit(0);}
void add(int x,int y)
{
    tot++;
    nex[tot]=head[x];head[x]=tot;
    to[tot]=y;
}
void dfs(int x,int y)
{
    fa[x][0]=y;
    for(int i=1;i<=20;i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    deep[x]=deep[y]+1;
    pos[x]=++cnt;
    for(int i=head[x];i;i=nex[i])
        if(to[i]!=y)
            dfs(to[i],x);
}
int cmp(int x,int y){return pos[x]<pos[y];}
int lca(int x,int y)
{
    if(deep[x]<deep[y])swap(x,y);
    for(int i=20;i>=0;i--)
        if(deep[fa[x][i]]>=deep[y])x=fa[x][i];
    if(x==y)return x;
    for(int i=20;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
void dfs1(int x)
{
    L[x]=-inf;R[x]=inf;sig[x]=-1;
    for(int i=0,t,d,v;i<vec[x].size();i++)
    {
        dfs1(t=vec[x][i]);
        d=deep[t]-deep[x];
        v=(R[t]+d)&1;
        L[x]=max(L[x],L[t]-d);
        R[x]=min(R[x],R[t]+d);
        if(sig[x]==-1)sig[x]=v;
        else if(sig[x]!=v)quit();
    }
    if(L[x]>R[x])quit();
    if(val[x]!=val[0])
    {
        if(val[x]<L[x]||val[x]>R[x])quit();
        if(sig[x]!=-1&&(val[x]&1)!=sig[x])quit();
        L[x]=R[x]=val[x];
    }
}
void dfs2(int x)
{
    for(int i=0,t,d,d1;i<vec[x].size();i++)
    {
        t=vec[x][i];
        d=deep[t]-deep[x];
        val[t]=max(L[t],val[x]-d);
        d1=(val[x]+d-val[t])/2;
        int now=val[t],p=t;
        for(int j=1;j<=d1;j++)
            val[fa[p][0]]=val[p]+1,p=fa[p][0];
        for(int j=1;j<d-d1;j++)
            val[fa[p][0]]=val[p]-1,p=fa[p][0];
        dfs2(t);
    }
}
void dfs3(int x,int y)
{
    if(val[x]==val[0])
        val[x]=val[y]+1;
    for(int i=head[x];i;i=nex[i])
        if(to[i]!=y)dfs3(to[i],x);
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d",&n);
    for(int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    memset(val,-0x3f,sizeof(val));
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&a[i]);
        scanf("%d",&val[a[i]]);
    }
    dfs(1,0);
    sort(a+1,a+1+m,cmp);
    st[top=1]=1;
    for(int i=1,t;i<=m;i++)
    {
        while((t=lca(a[i],st[top]))!=st[top])
        {
            if(deep[t]>deep[st[top-1]])
            {
                vec[t].push_back(st[top]);
                st[top]=t;
            }
            else
            {
                vec[st[top-1]].push_back(st[top]);
                top--;
            }
        }
        if(st[top]!=a[i])
            st[++top]=a[i];
    }
    for(int i=top;i>1;i--)
        vec[st[i-1]].push_back(st[i]);
    dfs1(1);
    val[1]=L[1];
    dfs2(1);
    dfs3(1,0);
    puts("Yes");
    for(int i=1;i<=n;i++)
        printf("%d\n",val[i]);
    return 0;
}

题意：构造一个长度小于200的字符集为1到100的串，使它的全部非空子序列中恰好有n个为一个好串，其中好串为一个相同的串复制一遍接到后面得到的串。

考虑一个串$$p_1p_2...p_n 1 2 3 4 ... n$$，其中$$p_1p_2...p_n$$为一个排列，子序列中好串数量为排列的不下降子序列数
注意到在一个排列前加一个最大的数导致好串+1，在后面加导致*2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
int cnt;
vector<int>q1,q2;
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%lld",&n);n++;
    int now=100;
    while(n!=1)
    {
        if(n&1)n--,q1.push_back(now--);
        else n>>=1,q2.push_back(now--);
        cnt++;
    }
    printf("%d\n",cnt*2);
    for(int i=0;i<q1.size();i++)printf("%d ",q1[i]);
    for(int i=q2.size()-1;i>=0;i--)printf("%d ",q2[i]);
    for(int i=now+1;i<=100;i++)printf("%d ",i);
    return 0;
}

题意：一行n个球，第i个球有颜色ci和重量wi，两个球如果同色且重量和不超过X 或 不同色且重量和不超过y 就可以交换，求最终可以得到多少不同的颜色序列

如果a,b可以交换， a,c可以交换，那么b,c可以交换。
abc->bac->bca->acb
那么可以交换的一定构成一些团，最多有一个团由不同的颜色的一些重量最小的组成。求出这个团，然后组合数

#include <bits/stdc++.h>
using namespace std;
#define N 210000
#define mod 1000000007
#define ll long long
int n,X,Y,cnt;
int c[N],w[N],a[N],pos[N],num[N],jc[N],njc[N];
vector<int>v1[N],v2[N];
int cmp(int x,int y){return v1[x][0]<v1[y][0];}
int qpow(int x,int y)
{
    int ret=1;
    while(y)
    {
        if(y&1)ret=(ll)ret*x%mod;
        x=(ll)x*x%mod;y>>=1;
    }
    return ret;
}
void init()
{
    jc[0]=njc[0]=1;
    for(int i=1;i<=n;i++)jc[i]=(ll)jc[i-1]*i%mod;
    njc[n]=qpow(jc[n],mod-2);
    for(int i=n-1;i>=1;i--)njc[i]=(ll)njc[i+1]*(i+1)%mod;
}
int C(int x,int y){return (ll)jc[x]*njc[y]%mod*njc[x-y]%mod;}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d%d",&n,&X,&Y);
    init();
    for(int i=1;i<=n;i++)
        scanf("%d%d",&c[i],&w[i]),a[++cnt]=c[i];
    sort(a+1,a+1+cnt);
    cnt=unique(a+1,a+1+cnt)-a-1;
    for(int i=1;i<=n;i++)
    {
        c[i]=lower_bound(a+1,a+1+cnt,c[i])-a;
        v1[c[i]].push_back(w[i]);
    }
    for(int i=1;i<=cnt;i++)
    {
        sort(v1[i].begin(),v1[i].end());
        pos[i]=i;
    }
    sort(pos+1,pos+1+cnt,cmp);
    for(int i=1;i<=cnt;i++)
        v2[i]=v1[pos[i]];
    num[1]=upper_bound(v2[1].begin(),v2[1].end(),X-v2[1][0])-v2[1].begin();
    if(cnt>1)num[1]=max(num[1],
    (int)(upper_bound(v2[1].begin(),v2[1].end(),Y-v2[2][0])-v2[1].begin()));

    for(int i=2;i<=cnt;i++)
    {
        num[i]=upper_bound(v2[i].begin(),v2[i].end(),X-v2[i][0])-v2[i].begin();
        num[i]=max(num[i],
        (int)(upper_bound(v2[i].begin(),v2[i].end(),Y-v2[1][0])-v2[i].begin()));
    }
    int sum=num[1],ans=1;
    for(int i=2;i<=cnt;i++)
    {
        if(v2[i][0]+v2[1][0]>Y)break;
        ans=(ll)ans*C(sum+num[i],sum)%mod;
        sum+=num[i];
    }
    printf("%d\n",ans);
    return 0;
}

题意：有n个兔子，初始时第i个兔子在xi位置，每组有m次跳跃，每组的第i次跳跃为兔子$$a_i$$等概率选$$a_i-1$$或$$a_i+1$$,然后兔子$$a_i$$的位置变为原位置关于选择的兔子位置对称的位置。求进行K组后第i个兔子的期望位置。

每次跳跃相当于把兔子从位置 $$X_i$$ 变为$$X_{i-1} +X_{i+1}-X_i$$

差分之后相当于交换两个数的位置
直接对每个轮换求

#include <bits/stdc++.h>
using namespace std;
#define N 1100000
#define ll long long
ll K;
int n,m,top;
int a[N],p[N],pos[N],vis[N],fin[N],st[N];
ll v[N],v1[N];
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&v[i]),p[i]=i;
    scanf("%d%lld",&m,&K);
    for(int i=1;i<=m;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
        swap(p[a[i]],p[a[i]+1]);
    for(int i=1;i<=n;i++)pos[p[i]]=i;
    for(int i=1,now;i<=n;i++)if(!vis[i])
    {
        st[0]=i;vis[i]=1;top=1;
        now=pos[i];
        while(now!=i)
        {
            st[top]=now;vis[now]=1;top++;
            now=pos[now];
        }
        int t=K%top;
        for(int j=0;j<top;j++)
            fin[st[(j+t)%top]]=st[j];
    }
    v1[1]=v[1];
    for(int i=2;i<=n;i++)v1[i]=v[i]-v[i-1];
    for(int i=1;i<=n;i++)v[i]=v1[fin[i]];
    v1[1]=v[1];
    for(int i=2;i<=n;i++)v1[i]=v[i]+v1[i-1];
    for(int i=1;i<=n;i++)
        printf("%lld.0\n",v1[i]);
    return 0;
}