题意：给出一棵树，树上有一些关键点，一个点集可行当且仅当它可以表示为一个关键点与距它距离d以内的所有点的集合。求可行点集总数。

先不考虑关键点（设所有点均为关键点）
对于一个除全集以外的可行点集可以表示它的点组成树的一个子树。只在子树中d最小的点处统计这个点集。可以发现子树中这样的点只有一个。
因此计算一个点的贡献时，设以他为根时深度最大的子树距该点距离为f1，深度次大的子树距该点距离为f2。则该点的d取值范围为[0,min(f1-1,f2+1)]
当存在关键点时，选取的d必须使一个关键点包含在可行子树中，因此选取的d必须完整覆盖一个包含关键点的子树

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=210000;
int n,tot;
char s[N];
int head[N],nex[N<<1],to[N<<1];
int f1[N],f2[N],g[N],lb[N],size[N];
ll ans;
void add(int x,int y)
{
    tot++;
    nex[tot]=head[x];head[x]=tot;
    to[tot]=y;
}
void upd(int &x,int &y,int z)
{
    if(z>x)y=x,x=z;
    else if(z>y)y=z;
}
void dfs1(int x,int y)
{
    size[x]=s[x]-'0';
    for(int i=head[x],t;i;i=nex[i])if((t=to[i])!=y)
    {
        dfs1(t,x);
        size[x]+=size[t];
        upd(f1[x],f2[x],f1[t]+1);
        if(size[t])
            lb[x]=min(lb[x],f1[t]+1);
    }
}
void dfs2(int x,int y)
{
    for(int i=head[x],t,d;i;i=nex[i])if((t=to[i])!=y)
    {
        g[t]=max(g[x],f1[t]+1==f1[x] ? f2[x] : f1[x])+1;
        if(size[t]!=size[1])
            lb[t]=min(lb[t],g[t]);
        dfs2(t,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);
    }
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
        if(s[i]=='0')lb[i]=n+1;
    dfs1(1,0);
    dfs2(1,0);
    for(int i=1;i<=n;i++)
    {
        upd(f1[i],f2[i],g[i]);
        ans+=max(0,min(f1[i]-1,f2[i]+1)-lb[i]+1);
    }
    printf("%lld\n",ans+1);
    return 0;
}

题意：给出一个数列a，一个数的初始值为D，按数列顺序操作，每次把D变为$$min(D,abs(D-a[i]))$$。q个询问，每次询问任意修改a数列一个位置数后能否使操作a序列后D值不为0。

设$$b[i]$$表示最小的D初始值使经过i及以后的操作后值不为0。
则$$b[n+1]=1$$
如果$$\lfloor\frac{a[i]}{2}\rfloor\ge b[i+1]$$则$$b[i]=b[i+1]$$,因为$$a[i]$$操作无效
否则$$b[i]=b[i+1]+a[i]$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=510000;
int n,q;
int a[N],d[N];
ll b[N];
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&d[0]);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    b[n+1]=1;
    for(int i=n;i>=1;i--)
    {
        if(a[i]/2>=b[i+1])b[i]=b[i+1];
        else b[i]=b[i+1]+a[i];
    }
    for(int i=1;i<=n;i++)
        d[i]=min(d[i-1],abs(d[i-1]-a[i]));
    scanf("%d",&q);
    for(int i=1,t;i<=q;i++)
    {
        scanf("%d",&t);
        puts(b[t+1]<=d[t-1] ? "YES" : "NO");
    }
    return 0;
}

题意：n堆棋子，两个人轮流操作，每次可以从每堆中取出一个或取走最大的一堆。求是否先手必胜。

将石子堆从大到小排序，每次操作相当于从(0,0)开始，向上或向右走一步，走到边界即为获胜。
可证除边界每个左下右上对角线上的状态相同。

#include <bits/stdc++.h>
using namespace std;
const int N=110000;
int n;
int a[N];
int cmp(int x,int y){return x>y;}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n,cmp);
    for(int i=1,j;i<=n;i++)
    {
        if(a[i]==i)
        {
            for(j=i;j<=n&&a[j]==a[i];j++);j--;
            return puts((j-i)&1 ? "First" : "Second"),0;
        }
        if(a[i]>i&&a[i+1]<i)
            return puts((a[i]-i)&1 ? "First" : "Second"),0;
        if(a[i]>i&&a[i+1]==i)
        {
            for(j=i+1;j<=n&&a[j]==a[i+1];j++);j--;
            int t=(j-i-1)&(a[i]-i-1);
            return puts(t&1 ? "Second" : "First"),0;
        }
    }
    return 0;
}

题意：用三种颜色染一个长度为n的序列，m个条件，每个条件为一段区间内的颜色个数为x。求满足条件的序列个数。

设$$f[i][j][k]$$表示到$$i$$,最后出现位置最靠前的颜色最后出现位置为$$k$$，最后出现位置第二靠前的颜色最后出现位置为$$j$$的方案数。

#include <bits/stdc++.h>
using namespace std;
#define PA pair<int,int>
const int N=310,mod=1000000007;
int n,m,ans;
struct node
{
    int l,r,num;
    friend bool operator < (const node &r1,const node &r2)
    {return r1.r<r2.r;}
}a[N];
int f[N][N][N];
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].num);
    sort(a+1,a+1+m);
    f[1][0][0]=3;
    for(int i=1,now=1;i<=n;i++)
    {
        while(now<=m&&a[now].r==i)
        {
            int l=a[now].l,num=a[now].num;
            for(int j=0;j<i;j++)
                for(int k=0;k<=j;k++)
                {
                    int t=1;
                    if(j>=l)t++;
                    if(k>=l)t++;
                    if(t!=num)f[i][j][k]=0;
                }
            now++;
        }
        if(i==n)break;
        for(int j=0;j<i;j++)
            for(int k=0;k<=j;k++)
            {
                (f[i+1][j][k]+=f[i][j][k])%=mod;
                (f[i+1][i][k]+=f[i][j][k])%=mod;
                (f[i+1][i][j]+=f[i][j][k])%=mod;
            }
    }
    for(int j=0;j<n;j++)
        for(int k=0;k<=j;k++)
            (ans+=f[n][j][k])%=mod;
    printf("%d\n",ans);
    return 0;
}

一.题目大意

给出一个长度为$$N$$的整数序列$$a$$，求有多少$$1$$到$$N$$的排列$$p$$满足如下条件：
$$\bullet$$ 对于每个$$1\le i\le N$$满足$$p_i=a_i$$，$$p_{p_i}=a_i$$ 中至少一个。

答案对$$10^9+7$$ 取模。

$$1\le N\le 10^5$$
$$1\le a_i\le N$$

二.解题报告

考虑对于一个排列$$p$$，连一条从$$i$$到$$p_i$$的边。形成的图由一些环组成。考虑其中一个环。

将原来$$i$$到$$p_i$$的边改为$$i$$到$$p_i$$或$$p_{p_i}$$。
情况1：所有原来的边保持不变。则仍然为一个环。

情况2：环大小为奇数且不为$$1$$，原来$$i$$到$$p_i$$的边变为$$i$$到$$p_{p_i}$$。此时仍然为一个环。

情况3：环大小为偶数，原来$$i$$到$$p_i$$的边变为$$i$$到$$p_{p_i}$$。此时环分裂为两个。

情况4：其他情况时，形成一棵基环内向树。并且以环上每个点为根的树都为一条链。

所求即为有多少排列的图经过转化可以与$$i$$与$$a_i$$连边得到的图相同。
考虑$$i$$与$$a_i$$连边得到的图，将相同大小的环在一起处理。

可以将任意两个相同大小的环合并。
也可以单独成为一个环：对于大小为奇数且不为$$1$$的环有两种方法，对于大小为偶数或$$1$$的环有一种方法。
可以枚举合并环的对数，用组合数计算方案数。

对于基环树，如果存在以环上点为根的树不为一条链那么无解。否则对于一条链有两种放置方法：
方法1：链上的第二个点与根相距$$1$$

方法2：链上的第二个点与根相距$$2$$

一条链放置后的结尾不能超过下一条链的根。
通过当前链的根与下一个根的距离可以确定当前链有0种，一种或两种放法。
这样可以求出对于一个基环树的方案数。

有联通块不是环或基环树时无解。

时间复杂度$$O(n)$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=110000,mod=1000000007;
int n,ans;
int jc[N],njc[N],bir[N],nbir[N];
int a[N],fa[N],du[N],num[N],vis[N],tail[N],rem[N];
int f[N][2][2];
vector<int>vec[N],v1;
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()
{
    for(int i=1;i<=n;i++)fa[i]=i;
    jc[0]=njc[0]=bir[0]=nbir[0]=1;
    for(int i=1;i<=n;i++)
    {
        jc[i]=(ll)jc[i-1]*i%mod;
        bir[i]=bir[i-1]*2%mod;
    }
    njc[n]=qpow(jc[n],mod-2);
    nbir[n]=qpow(bir[n],mod-2);

    for(int i=n-1;i>=1;i--)
    {
        njc[i]=(ll)njc[i+1]*(i+1)%mod;
        nbir[i]=nbir[i+1]*2%mod;
    }
}
int find(int x){return fa[x]==x ? x : fa[x]=find(fa[x]);}
void quit(){puts("0");exit(0);}
void ins(int x)
{
    if(!tail[x])return;
    if(rem[x]<tail[x])quit();
    else if(rem[x]>tail[x])ans=ans*2%mod;
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d",&n);
    init();
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(find(i)!=find(a[i]))
            fa[find(i)]=find(a[i]);
        du[a[i]]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(du[i]>2)quit();
        vec[find(i)].push_back(i);
    }
    ans=1;
    for(int i=1,sz;i<=n;i++)if(sz=vec[i].size())
    {
        int p=-1;
        for(int j=0;j<sz;j++)
            if(du[vec[i][j]]==2)p=vec[i][j];
        if(p==-1)num[sz]++;
        else
        {
            int t=0,p1=a[p];
            vis[p]=++t;
            while(p1!=p)
            {
                if(vis[p1])quit();
                vis[p1]=++t;
                p1=a[p1];
            }
            for(int j=0,cnt;j<sz;j++)
                if(du[p1=vec[i][j]]==0)
                {
                    cnt=0;
                    while(!vis[p1])
                    {
                        cnt++;
                        if(du[p1]==2)quit();
                        p1=a[p1];
                    }
                    tail[p1]=cnt;
                }
            int now=0;p1=p;
            for(int j=1;j<=t*2;j++,p1=a[p1])
            {
                if(tail[p1])
                    rem[p1]=max(rem[p1],now+1),now=0;
                else now++;
            }
            v1.clear();
            ins(p);p1=a[p];
            while(p1!=p)
            {
                ins(p1);
                p1=a[p1];
            }
        }
    }
    for(int i=1;i<=n;i++)if(num[i])
    {
        int t=0,now=1;
        for(int j=0;j<=num[i];j+=2)
        {
            int t1=(ll)jc[num[i]]*njc[num[i]-j]%mod*njc[j>>1]%mod*nbir[j>>1]%mod*now%mod;
            if((i&1)&&i!=1)t1=(ll)t1*bir[num[i]-j]%mod;
            t=(t+t1)%mod;
            now=(ll)now*i%mod;
        }
        ans=(ll)ans*t%mod;
    }
    printf("%d\n",ans);
    return 0;
}