题意:用三种颜色染一个长度为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;
}

一.题目大意

Snuke王国有$$n$$座城镇,标号为$$1$$到$$n$$,城镇$$1$$为首都。
王国中每一座城镇有一个传送器:一个立即将人传送到另一个地方的设施。城镇$$i$$的传送目的地为$$a_i(1\le a_i \le N)$$,保证一个人可以在任意城镇使用几次传送器到达首都
国王Snuke喜爱数字$$K$$,这个自私的国王想要修改传送器的目的地使其满足如下条件:
$$\bullet$$ 一个人可以从任意城镇开始经过恰好$$K$$次传送后到达首都。

求要满足条件需要修改目的地的传送器个数的最小值。

$$2\le N\le 10^5$$
$$1\le a_i\le N$$
$$1\le K\le 10^9$$

二.解题报告

将城市看成点,每个城市向该城市的传送目的地连边,初始时由于每个点出度都为$$1$$且都可以到达$$1$$点,因此这个图为一棵基环内向树,且$$1$$点在环上。

修改后的图同样为基环内向树,为了满足从任意城镇经过恰好$$K$$次传送后到达首都,环必须为$$1$$点的自环,且树的深度小于等于$$K+1$$。

首先将$$1$$点的传送目的地改为自身。不考虑这个自环,将图看成一棵以$$1$$点为根的树,现在需要将一些点的父亲修改,使树的深度小于等于$$K+1$$。

显然将父亲修改为其他点不会比修改为$$1$$点更优,因此可以采用如下的贪心策略:从叶节点向上进行树形dp,到一个点时如果该点子树中深度最大的叶子到该点距离为$$K-1$$,那么将该点的父亲修改为$$1$$点。

易证这个贪心策略的正确性,因为修改深度小的点的父亲显然比修改深度大的点的父亲更优。

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

#include <bits/stdc++.h>
using namespace std;
#define N 110000
int n,K,ans;
int a[N];
vector<int>vec[N];
int dfs(int x)
{
    int ret=0;
    for(int i=0;i<vec[x].size();i++)
    {
        int t=dfs(vec[x][i]);
        if(t==K)ans++;
        else ret=max(ret,t);
    }
    return ret+1;
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&K);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(i!=1)vec[a[i]].push_back(i);
    }
    ans=(a[1]!=1);
    for(int i=0;i<vec[1].size();i++)
        dfs(vec[1][i]);
    printf("%d\n",ans);
    return 0;
}

题意:一条路上有n个店,有m张票,票i可以在店j获得$$d_{ji}$$的收益,从店i走到店i+1有$$a_i$$的花费。求从任意一个店开始能获得的最大收益。

一定不会走重复的路径
暴力:对于每一张票j,求每一家店的最大值覆盖区间,设店i的区间为[L[i],R[i]],那么将起点在[L[i],i]终点在[i,R[i]]的路径$$+d_{ij}$$,用二维树状数组维护,小范围暴力

#include <bits/stdc++.h>
using namespace std;
#define M 210
#define N 5100
#define ll long long
const int bnd = 200;
int n,m,top;
int a[N],b[M][N],st[N],L[M][N],R[M][N];
ll sum[N],tr[N][N],ans;
void insert(int x,int y,int v)
{
    for(int i=x;i;i-=i&-i)
        for(int j=y;j;j-=j&-j)
            tr[i][j]+=v;    
}
ll query(int x,int y)
{
    ll ret=0;
    for(int i=x;i<=n;i+=i&-i)
        for(int j=y;j<=n;j+=j&-j)
            ret+=tr[i][j];
    return ret;
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&b[j][i]);
    for(int i=1;i<=m;i++)
    {
        top=0;st[top]=0;
        for(int j=1;j<=n;j++)
        {
            while(top&&b[i][j]>b[i][st[top]])top--;
            L[i][j]=st[top]+1;
            st[++top]=j;
        }
        top=0;st[top]=n+1;
        for(int j=n;j>=1;j--)
        {
            while(top&&b[i][j]>=b[i][st[top]])top--;
            R[i][j]=st[top]-1;
            st[++top]=j;
        }
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if((j-L[i][j]+1)*(R[i][j]-j+1)>=bnd)
            {
                insert(j,R[i][j],b[i][j]);
                insert(L[i][j]-1,j-1,b[i][j]);
                insert(L[i][j]-1,R[i][j],-b[i][j]);
                insert(j,j-1,-b[i][j]);
            }
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            tr[i][j]=query(i,j);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if((j-L[i][j]+1)*(R[i][j]-j+1)<bnd)
            {
                for(int k=L[i][j];k<=j;k++)
                    for(int w=j;w<=R[i][j];w++)
                        tr[k][w]+=b[i][j];
            }
    for(int i=1;i<n;i++)
        sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            ans=max(ans,tr[i][j]-(sum[j-1]-sum[i-1]));
    printf("%lld\n",ans);
    return 0;
}

正解:设以i为起点的最优路径终点为p[i],那么随着i的递增p[i]单调不减。因此可以rmq预处理,设solve(l1,r1,l2,r2)表示求解起点在[l1,r1]内终点可行区间为[l2,r2]的路径。然后求出l1,r1中点mid的最优路径终点,递归处理。

#include <bits/stdc++.h>
using namespace std;
#define M 210
#define N 5100
#define ll long long
int n,m;
int a[N],b[M][N],mx[M][N][16],bir[N];
ll sum[N],ans;
int query(int x,int l,int r)
{
    int t=bir[r-l+1];
    return max(mx[x][l][t],mx[x][r-(1<<t)+1][t]);
}
void solve(int l1,int r1,int l2,int r2)
{
    if(l1>r1)return;
    int mid=(l1+r1)>>1;
    ll v=0,p=max(l2,mid);
    for(int i=max(l2,mid);i<=r2;i++)
    {
        ll t=0;
        for(int j=1;j<=m;j++)
            t+=query(j,mid,i);
        t-=sum[i-1]-sum[mid-1];
        if(t>v)v=t,p=i;
    }
    ans=max(ans,v);
    solve(l1,mid-1,l2,p);
    solve(mid+1,r1,p,r2);
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<n;i++)
        sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&b[j][i]);
    bir[1]=0;
    for(int i=2;i<=n;i++)
        bir[i]=bir[i>>1]+1;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)mx[i][j][0]=b[i][j];
        for(int j=1;j<=bir[n];j++)
            for(int k=1;k+(1<<j)-1<=n;k++)
                mx[i][k][j]=max(mx[i][k][j-1],mx[i][k+(1<<j-1)][j-1]);
    }
    solve(1,n,1,n);
    printf("%lld\n",ans);
    return 0;
}

题意:有n个整数,gcd为1,每次可以把一个大于1的数减1,并把所有数除以当前所有数的gcd。两个人轮流操作,无法操作者输,求是否先手必胜。

当n=1时先手必败。
当没有除所有数gcd时,如果有奇数个偶数先手必胜,否则后手必胜。
当有除gcd操作时,定义状态1:有奇数个偶数,至少一个奇数。
状态2:有偶数个偶数,至少2个奇数。状态3:有偶数个偶数,1个奇数。
所有数都为1的状态属于状态2,为先手必败态。
状态1时对一个偶数-1,此时gcd为奇数,因此不改变奇偶性。转移到状态2。状态2时不管如何操作操作后gcd为1,因此只能转移到状态1。所以状态1为先手必胜态,状态2为先手必败态。
状态3如果选一个偶数,会转移到状态2,因此只能选一个奇数。此时gcd至少为2。因此如果初始时为状态3,直接递归。

#include <bits/stdc++.h>
using namespace std;
#define N 110000
int n,num;
int a[N];
int main()
{
    scanf("%d",&n);
    if(n==1)return puts("Second"),0;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    while(1)
    {
        int odd=0,even=0,pos;
        for(int i=1;i<=n;i++)
        {
            if(a[i]&1)odd++,pos=i;
            else even++;
        }
        if(even&1)break;
        if(odd>=2){num++;break;}
        if(a[pos]==1){num++;break;}
        a[pos]--;int t=a[1];
        for(int i=2;i<=n;i++)t=__gcd(t,a[i]);
        for(int i=1;i<=n;i++)a[i]/=t;
        num++;
    }
    puts(num&1 ? "Second" : "First");
    return 0;
}