2020杭电多校联合训练(第七场)
in 杭电多校多校训练 with 0 comment

2020杭电多校联合训练(第七场)

in 杭电多校多校训练 with 0 comment

摘要

/ABCDEFGHIJK
场上
zyj
wrf
lmj

题目

A.Animism

题意

题解

代码


B.Bitwise Xor

lmj 赛后

题意

有$n$个宠物,每个掌握了$m_i$种魔法,一种魔法可以表示为一个二元组$(x,y)$,效果是将一个数与$x$或$y$进行一次异或操作,现在每次询问一个区间$[l,r]$和一个数$w$,处于该区间内的宠物必须从左到右依次对着$w$释放所有魔法各一次,每个宠物有一个数字$p_i$,它会聪明地决策,使得最后$w$与$p_i$的差尽可能小,输出最后$w$的值。

题解

二选一是不好做的,考虑进行一定的转化,将$(x,y)$变成$(x \oplus y,y)$,那么就变成,$y$必选,$x \oplus y$选或者不选。
然后考虑求出每个点的前缀$x \oplus y$的线性基,在线性基中记录每一位最晚被修改的位置,那么可以发现,那一位就是受到最后的那个宠物的控制,然后询问时,先将$(l,r)$的$y$异或进答案,然后枚举每一位,如果该位被控制的位置在区间内,根据那个宠物的需求进行修改即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
const int MAXB=29;
struct Linear_Basis
{
    int b[31][2];
    void init()
    {
        memset(b,0,sizeof(b));
    }
    bool ins(int x,int id)
    {
        for(int i=MAXB;i>=0;i--)
            if (x&(1<<i))
            {
                if (!b[i][0]) {b[i][0]=x,b[i][1]=id;break;}
                else{
                    if(id>=b[i][2]){
                        swap(x,b[i][0]);
                        swap(id,b[i][3]);
                    }
                }
                x^=b[i][0];
            }
        return x>0;
    }
}LB[N];
int a[N];
int pre[N];
int ed[N];
void work()
{
    int n,q;
    scanf("%d%d",&n,&q);
    int tot=0;
    for(int i=1;i<=n;i++){
        int m;
        scanf("%d%d",&m,&a[i]);
        for(int j=1;j<=m;j++){
            int x,y;
            scanf("%d%d",&x,&y);
            x^=y;
            LB[tot+1]=LB[tot];
            LB[++tot].ins(x,i);
            pre[tot]=pre[tot-1]^y;
        }
        ed[i]=tot;
    }
    while(q--){
        int op;
        scanf("%d",&op);
        if(op==1){
            int x,y;
            scanf("%d%d",&x,&y);
            a[x]=y;
        }else{
            int l,r,w;
            scanf("%d%d%d",&l,&r,&w);
            int ll=ed[l-1]+1;
            int rr=ed[r];
            w^=pre[ll-1]^pre[rr];
            for(int i=29;i>=0;i--){
                if(!LB[rr].b[i][0]||LB[rr].b[i][4]<l)continue;
                if(((1<<i)&w)!=((1<<i)&a[LB[rr].b[i][5]]))w^=LB[rr].b[i][0];
            }
            printf("%d\n",w);
        }
    }
}
int main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

C.Counting

题意

题解

代码


D.Decision

lmj 赛后

题意

给四个数 $t,a,c,m$,$v_1,v_2$ 等概率的落在区间 $[0,t]$ 中,设 $X_0=v_1+v_2$ , $X_{n+1}=(a∗X_n+c)$ ,问 $X_{|v_1−v_2|}$ 是偶数的概率。

题解

考虑枚举$v_1+v_2$,那么$|v_1-v_2|$的值就被确定在了一个范围内,然后使用倍增解决即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=1e6+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int f[22][N];
int sum[22][N];
ll cal(int x,int l,int r)
{
    if(l==1)x=f[0][x];
    ll ans=(x%2==0),num=(r-l)/2;
    for(int i=20;i>=0;i--)if((num>>i)&1)ans+=sum[i][x],x=f[i+1][x];
    return ans;
}
void work()
{
    int t,a,c,m;
    scanf("%d%d%d%d",&t,&a,&c,&m);
    for(int i=0;i<=m;i++){
        f[0][i]=(1ll*a*i+c)%m;
    }
    for(int j=1;(1<<j)<=m;j++){
        for(int i=0;i<=m;i++){
            f[j][i]=f[j-1][f[j-1][i]];
        }
    }
    for(int i=0;i<=m;i++){
        sum[0][i]=(f[1][i]%2==0);
    }
    for(int j=1;(1<<j)<=m;j++){
        for(int i=0;i<=m;i++){
            sum[j][i]=sum[j-1][i]+sum[j-1][f[j][i]];
        }
    }
    ll ans=0;
    for(int i=0;i<=2*t;i++){
        int l=i%2,r=(i<=t)?i:t-(i-t);
        ans+=2*cal(i,l,r);
        if(l==0)ans--;
    }
    ll tmp=__gcd(ans,1ll*(t+1)*(t+1));
    printf("%lld/%lld\n",ans/tmp,1ll*(t+1)*(t+1)/tmp);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

E.Expectation

lmj 赛后

题意

数轴上的 $2n+1$ 个坐标,其中$ n+1 $个位置为洞,其余$ n $个位置上有球,分别插在两个的洞中间。
每次随机选择一个球,并随机指定一个方向,让球沿着那个方向一直滚,直到掉进洞里,之后这个洞会被填平。
问当所有球都进洞后每个球经过的路径之和的期望。

题解

考虑求每段被经过次数的期望。
$a_{2*k}=a_{2*k-1}$,因为这两段只要不动第$k$个球,那么这两段都没有贡献,当动了第$k$个球时,此时对于左右的段是相同的期望,然后这左右段可以认为是合并为同一段,所以期望相同。
$dp[i][j]$表示左边有$i$个球,右边有$j$个球时所经过次数的期望。
$dp[0][n]=1-\frac{(2*n-1)!!}{2^nn!}$,对于第一段,其不被经过的可能性为,除了最左边的点往左以外的所有情况,所以情况数为$(2*n-1)*(2*n-3)……$.
$dp[n][0]=-dp[0][n]$
$dp[n][m]=\frac{(2*n-1)*dp[n-1][m]+(2*m-1)*dp[n][m-1]}{2*(n+m)}$左边的球除了最右边的往右以外,其他的都会变成当前状态,右边的球除最左边的往左以外,其他都会变成当前状态。
然后$a_{2*k+1}=a_{2k}+dp[k][n-k]$,就是每一段的概率,乘上长度即为答案。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=998244353;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ll a[N];
ll dp[3005][3005];
ll pre[6005];
ll pre1[6005];
ll inv[6005];
ll inv1[6005];
ll pw2[6005];
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<=2*n;i++){
        scanf("%lld",&a[i]);
    }
    ll tmp=0;
    ll ans=0;
    for(int i=0;i<n;i++){
        tmp=(tmp+dp[i][n-i])%p;
        ans=(ans+tmp*(a[i*2+2]-a[i*2])%p)%p;
    }
    printf("%lld\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    pre[0]=1;
    pre1[0]=1;
    pre1[1]=1;
    pw2[0]=1;
    for(int i=1;i<=6000;i++){
        pre[i]=pre[i-1]*i%p;
        if(i>1){
            pre1[i]=pre1[i-2]*i%p;
        }
        pw2[i]=pw2[i-1]*2%p;
    }
    inv[6000]=qpow(pre[6000],p-2)%p;
    for(int i=5999;i>=0;i--){
        inv[i]=inv[i+1]*(i+1)%p;
    }
    for(int i=1;i<=6000;i++){
        inv1[i]=qpow(i,p-2);
    }
    for(int i=1;i<=3000;i++){
        dp[0][i]=(p+1-pre1[2*i-1]*qpow(pw2[i],p-2)%p*inv[i]%p)%p;
        dp[i][0]=p-dp[0][i];
    }
    for(int i=1;i<=3000;i++){
        for(int j=1;i+j<=3000;j++){
            dp[i][j]=((2*i-1)*dp[i-1][j]%p+(2*j-1)*dp[i][j-1]%p)*inv1[2*(i+j)]%p;
        }
    }
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

F.Flower

lmj 赛后

题意

给定一棵 $n$ 个节点得树,树上开了 $m$ 朵花,第 $i$ 朵花占据了到 $x_i$ 点距离不超过 $r_i$ 的所有点,且有一个价值 $v_i$ 。
你需要找一个花的集合,使得这些花占据的节点集合无交,同时最大化集合中花的价值之和。

题解

通过线性规划对偶可以变成为每个点分配权值$y_i$,使得一朵花占据的节点的权值之和不小于花的价值,同时最小化总权值。具体请看友队BonVoyage
然后就是动态点分树的模板题 震波

代码

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f
const int N=2e5+5;
int son[N],sz[N],vis[N];
int head[N*2],nxt[N*2],to[N*2],w[N*2];
int dep[N];
int f[21][N*2];
int fa[N];
int size,mx;
int rt;
int n;
int tot=0;
int cnt=0;
int pos[N];
int fa2[21][N*2];
struct NODE
{
    int x,r,v,o;
}a[N];
void add(int u,int v,int z)
{
    to[++cnt]=v;
    w[cnt]=z;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
void dfs(int x,int p)
{
    dep[x]=dep[p]+1,pos[x]=++tot,f[0][tot]=dep[x];
    if(x==1){
        fa2[0][x]=x;
    }else{
        fa2[0][x]=p;
    }
    for(int i=1;i<=20;i++){
        fa2[i][x]=fa2[i-1][fa2[i-1][x]];
    }
    for(int i=head[x];i;i=nxt[i]){
        if(to[i]!=p){
            dfs(to[i],x);
            f[0][++tot]=dep[x];
        }
    }
}
int kth(int x,int k)
{
    k=min(x,k);
    for(int i=0;i<=20;i++){
        if((k>>i)&1)x=fa2[i][x];
    }
    return x;
}
int getdis(int x,int y)
{
    //printf("%d %d\n",x,y);
    int tmp=dep[x]+dep[y];
    // if(x==277&&y==2){
    //     printf("%d %d %d\n",tmp,pos[x],pos[y]);
    // }
    x=pos[x],y=pos[y];
    if(x>y)swap(x,y);
    int len=log(y-x+1)/log(2);
    // if(x==552&&y==1872){
    //     printf("%d %d %d\n",len,x,y-(1<<len)+1);
    // }
    return tmp-2*min(f[len][x],f[len][y-(1<<len)+1]);
}
void findrt(int u,int p){
    sz[u]=1,son[u]=0;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(vis[v]||v==p) continue;
        findrt(v,u);
        sz[u]+=sz[v];
        son[u]=max(son[u],sz[v]);
    }
    son[u]=max(son[u],size-sz[u]);
    if(son[u]<mx) mx=son[u],rt=u;
}
void divide(int u){
    vis[u]=1;
    int totsz=size;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(vis[v]) continue;
        mx=inf,rt=0;
        //size=sz[v]>sz[u]?totsz-sz[u]:sz[v];
        size=sz[v];
        findrt(v,0);
        fa[rt]=u;
        divide(rt);
    }
}
void init()
{
    rt=0,mx=inf,size=n;
    for(int i=1;(1<<i)<=2*n;i++){
        for(int j=1;j<=tot-(1<<i)+1;j++){
            f[i][j]=min(f[i-1][j],f[i-1][j+(1<<(i-1))]);
        }
    }
    findrt(1,0);
    divide(rt);
}
int tot1=0;
int root[N<<1];
struct node
{
    int l,r;
    ll v;
}t[N<<6];
void update(int &x,int l,int r,int p,ll w)
{
    if(!x){
        x=++tot1;
    }
    t[x].v+=w;
    if(l==r)return;
    int m=(l+r)>>1;
    if(p<=m)update(t[x].l,l,m,p,w);
    else update(t[x].r,m+1,r,p,w);
}
void update(int x,ll w)
{
    update(root[x],0,n,0,w);
    for(int i=x;fa[i];i=fa[i]){
        int d=getdis(x,fa[i]);
        update(root[fa[i]],0,n,d,w);
        update(root[i+n],0,n,d,w);
    }
}
ll query(int x,int l,int r,int L,int R)
{
    if(!x)return 0;
    if(L<=l&&R>=r)return t[x].v;
    int mid=(l+r)>>1;
    ll ret=0;
    if(L<=mid)ret+=query(t[x].l,l,mid,L,R);
    if(R>mid)ret+=query(t[x].r,mid+1,r,L,R);
    return ret;
}
ll query(int x,int k)
{
    ll ret=query(root[x],0,n,0,k);
    for(int i=x;fa[i];i=fa[i]){
        int d=getdis(x,fa[i]);
        //printf("%d %d\n",x,fa[i]);
        //printf("%lld %d %d\n",ret,d,k);
        if(d>k)continue;
        ret+=query(root[fa[i]],0,n,0,k-d);
        ret-=query(root[i+n],0,n,0,k-d);
    }
    return ret;
}
bool cmp(NODE x,NODE y)
{
    return dep[x.o]<dep[y.o];
}
void work()
{
    tot1=0,cnt=0,tot=0;
    for(int i=0;i<=n;i++){
        head[i]=0;
        vis[i]=0;
        root[i]=root[i+n]=0;
        fa[i]=0;
    }
    for(int i=1;i<=60*n;i++){
        t[i].l=t[i].r=t[i].v=0;
    }
    int m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y,0);
        add(y,x,0);
    }
    dfs(1,0);
    //printf("????????%d %d\n",n,tot);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a[i].x,&a[i].r,&a[i].v);
        a[i].o=kth(a[i].x,a[i].r);
    }
    init();
    sort(a+1,a+m+1,cmp);
    // for(int i=1;i<=m;i++){
    //     printf("%d %d %d %d %d\n",a[i].x,a[i].r,a[i].v,a[i].o,dep[a[i].o]);
    // }
    for(int i=1;i<=n;i++){
        update(i,0);
    }
    //printf("1\n");
    ll ans=0;
    for(int i=m;i>=1;i--){
        ll tmp=query(a[i].x,a[i].r);
        //printf("---%d %d %d %d %lld\n",a[i].x,a[i].r,a[i].v,a[i].o,tmp);
        if(tmp<a[i].v){
            update(a[i].o,a[i].v-tmp);
            ans+=a[i].v-tmp;
        }
    }
    printf("%lld\n",ans);
}
int main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    for(int t=1;t<=T;t++){
        work();
    }
}

G.Game

lmj 4:20:05 +3

题意

给定n个点,两个人轮流进行操作。开始在1点,然后第一次可以随意前往一个点,接下来的操作只能走到比上次走的边的距离大的点,并且不能走到重复点,求是否能获胜。

题解

考虑从大到小枚举所有边,如果这条边的两个点都还不是必败态,那么将这两个点标记为必败态,然后最后看点1是否为必败态即可。
证明:
首先如果是最长边,显然只要到其中任意一个点,那么下一个人沿最长边走,那么就输了。然后当枚举到一个两边点至少有一个是确定为必败态时,此时无法判断另外一个点是个什么情况,跳过。枚举到一个两边点均还不是必败态时,可以发现,此时比其长的边都已经枚举,那么意味着与这两个点相连的其他较长边所对应的点都已经被标记为必败态(如果没有被标记为必败态,那么显然会在之前的操作中将当前点变成必败态),那么可以发现从这两个点往外转移都只会转移到必败态,如果转移到了其中一点,那么另外一个人可以选择转移到这条边的对应点,使得其他点依然处于必败状态,那么该点就可以认为是必胜状态。
呜呜呜 被hack了 加个对同长度特殊判断
hack样例
2
3
0 0
2 0
1 2
4
1 0
0 0
2 0
1 2
输出 YES NO

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int x[2005],y[2005];
ll vis[2005];
struct node
{
    int x,y;
    ll w;
}a[2005*2005];
bool cmp(node A,node B)
{
    if(A.w!=B.w)return A.w>B.w;
    else return A.x<B.x;
}
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x[i],&y[i]);
        vis[i]=0;
    }
    int tot=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            a[++tot]={i,j,1ll*(x[i]-x[j])*(x[i]-x[j])+1ll*(y[i]-y[j])*(y[i]-y[j])};
        }
    }
    sort(a+1,a+tot+1,cmp);
    for(int i=1;i<=tot;i++){
        if(!vis[a[i].x]&&!vis[a[i].y]){
            vis[a[i].x]=a[i].w;
            vis[a[i].y]=a[i].w;
        }else if(vis[a[i].x]==0&&vis[a[i].y]==a[i].w||vis[a[i].y]==0&&vis[a[i].x]==a[i].w){
            vis[a[i].x]=a[i].w;
            vis[a[i].y]=a[i].w;
        }
    }
    if(vis[1]){
        printf("YES\n");
    }else{
        printf("NO\n");
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

H.Heart

lmj 赛后

题意

给 n 个法术,每种法术需要一个碎片的集合,每个碎片只能被使用一次。
一个可同时使用的法术的集合的权值为各法术权值的乘积。
共 q 次询问,问恰好使用碎片集合为 x 的所有法术集合的权值和。

题解

显然需要子集卷积,即FMT。
直接做21次的话,复杂度为$O(k^32^k)$,显然无法通过,考虑按照每个数的二进制位最大值进行枚举,这样复杂度变为$\sum_{i=1}^21 i^22^i$,可以勉强通过。
并且本题卡了空间,不能开三个22*(1<<21)的数组,需要在FMT的过程中复用空间。
调了一个小时发现板子假了。

代码

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=1e6+5;
const int p=998244353;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
void FWT_or(int *a,int n,int opt)
{
    for(int i=1;i<n;i<<=1)
        for(int t=i<<1,j=0;j<n;j+=t)
            for(int k=0;k<i;++k)
                if(opt==1)a[i+j+k]=(a[j+k]+a[i+j+k])%p;
                else a[i+j+k]=(a[i+j+k]+p-a[j+k])%p;
}
int x[22][1<<21];
int y[22][1<<21];
int o[1<<21];
void FMT(int l,int limit){
    for(int i=0;i<=l;++i) FWT_or(x[i],limit,1);
    for(int i=0;i<=l;++i) FWT_or(y[i],limit,1);
    for(int i=l;i>=0;--i){
        for(int j=0;j<limit;++j) o[j]=0;
        for(int j=i;j>=0;--j){
            for(int k=0;k<limit;++k){
                o[k]=(o[k]+1LL*x[j][k]*y[i-j][k])%p;
            }
        }
        for(int j=0;j<limit;++j) x[i][j]=o[j];
    }
    for(int i=0;i<=l;++i) FWT_or(x[i],limit,-1);
}
int a[N];
int b[N];
int lg[1<<21];
int f[1<<21];
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<(1<<21);i++){
        lg[i]=(i&(i-1))?lg[i-1]:lg[i-1]+1;
    }
    int tmp=1;
    int limit=1,l=0;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i],&b[i]);
        if(b[i]==0)tmp=1ll*tmp*(a[i]+1)%p;
    }
    f[0]=1;
    for(int t=1;t<=21;t++){
        // printf("%d\n",t);
        limit<<=1,l++;
        for(int i=0;i<=l;i++){
            for(int j=0;j<limit;j++){
                x[i][j]=y[i][j]=0;
            }
        }
        y[0][0]++;
        for(int i=1;i<=n;i++){
            if(lg[b[i]]==t){
                y[__builtin_popcount(b[i])][b[i]]=(y[__builtin_popcount(b[i])][b[i]]+a[i])%p;
            }
        }
        //printf("1\n");
        for(int i=0;i<limit;i++){
            x[__builtin_popcount(i)][i]=f[i];
        }
        FMT(l,limit);
        for(int i=0;i<limit;i++){
            f[i]=x[__builtin_popcount(i)][i];
            // if(t==1){
            //     printf("%d %d\n",i,f[i]);
            // }
        }
    }
    for(int i=0;i<limit;i++){
        f[i]=1ll*f[i]*tmp%p;
    }
    int q;
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        int k;
        scanf("%d",&k);
        printf("%d\n",f[k]);
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

I.Increasing and Decreasing

lmj 0:41:01 +0

题意

给定n,x,y,n为序列长度,x为最长上升子序列长度,y为最长下降子序列长度,求是否存在一个n长度的序列满足,求最小字典序

题解

首先如果$x*y<n$或者$x+y>n+1$那么显然无法表示出来。
因为要字典序最小,所以考虑将大的往后放,所以先放最长下降子序列,将最大的y个数倒序放在最后,然后对于前面,先从$1$到$n-y$依次放,此时要考虑如何将最长上升子序列长度减小,显然是要翻转一部分序列,还要注意当前翻转的序列的长度不能超过$y$,超过$y$就会使得最长下降子序列发生变化,然后考虑从$n-y$开始翻转,这样可以尽量保证字典序较小。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int a[N];
int n,x,y;
int dp[N];
void check1()
{
    for(int i=1;i<=n;i++){
        a[i]=i;
    }
    do{
        memset(dp,0,sizeof(dp));
        a[0]=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                if(a[i]>a[j]){
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
        }
        int checkx=0;
        for(int i=1;i<=n;i++){
            checkx=max(checkx,dp[i]);
        }
        memset(dp,0,sizeof(dp));
        a[0]=1e9;
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                if(a[i]<a[j]){
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
        }
        int checky=0;
        for(int i=1;i<=n;i++){
            checky=max(checky,dp[i]);
        }
        if(x==checkx&&y==checky){
            for(int i=1;i<=n;i++){
                printf("%d ",a[i]);
            }
            printf("\n");
            printf("%d %d %d\n",n,x,y);
            exit(0);
        }
    }while(next_permutation(a+1,a+n+1));
}
void check()
{
    memset(dp,0,sizeof(dp));
    a[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            if(a[i]>a[j]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    int checkx=0;
    for(int i=1;i<=n;i++){
        checkx=max(checkx,dp[i]);
    }
    memset(dp,0,sizeof(dp));
    a[0]=1e9;
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            if(a[i]<a[j]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    int checky=0;
    for(int i=1;i<=n;i++){
        checky=max(checky,dp[i]);
    }
    if(x!=checkx||y!=checky){
        printf("%d %d %d\n",n,x,y);
        check1();
        exit(0);
    }
}
void work()
{
    // n=rand()%8+1;
    // x=rand()%10+1;
    // y=rand()%10+1;
    scanf("%d%d%d",&n,&x,&y);
    if(x+y>n+1){
        //check1();
        printf("NO\n");
    }else if(1ll*x*y<n){
        //check1();
        printf("NO\n");
    }else{
        int now=n;
        for(int i=n-y+1;i<=n;i++){
            a[i]=now--;
        }
        for(int i=1;i<=n-y;i++){
            a[i]=i;
        }
        int tmp=n-y-x+1;
        now=n-y;
        while(tmp){
            if(tmp>=y){
                for(int i=now-y+1,j=now;i<=j;i++,j--){
                    swap(a[i],a[j]);
                }
                now-=y;
                tmp-=(y-1);
            }else{
                for(int i=now-tmp,j=now;i<=j;i++,j--){
                    swap(a[i],a[j]);
                }
                tmp=0;
            }
        }
        printf("YES\n");
        for(int i=1;i<n;i++){
            printf("%d ",a[i]);
        }
        printf("%d\n",a[n]);
        //check();
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

J.Jogging

lmj 2:19:13 +0

题意

给定一个二维平面,开始在$x,y$点,每次可以从以$x,y$为中心的九宫格中选择一些点以等概率转移过去,转移过去的条件为转移到的点的$x,y$满足$gcd(x,y)>1$,求在无限次操作后回到$x,y$时的概率

题解

结论:答案为所有点直接转移到$x,y$的数量除以所有点能转移到的位置之和
证明待补

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<ll,ll>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
void work()
{
    ll x,y;
    scanf("%lld%lld",&x,&y);
    bool f=0;
    ll sum=0;
    ll cnt=0;
    map<paii,int>m;
    queue<paii>q;
    q.push({x,y});
    m[{x,y}]=1;
    while(!q.empty()){
        paii now=q.front();
        q.pop();
        if(now.fr==now.sc){
            f=1;break;
        }
        for(ll i=now.fr-1;i<=now.fr+1;i++){
            for(ll j=now.sc-1;j<=now.sc+1;j++){
                if(__gcd(i,j)!=1){
                    if(i==x&&j==y){
                        cnt++;
                    }
                    sum++;
                    if(!m.count({i,j})){
                        m[{i,j}]=1;
                        q.push({i,j});
                    }
                }
            }
        }
    }
    if(f){
        printf("0/1\n");return;
    }else{
        ll tmp=__gcd(sum,cnt);
        sum/=tmp;
        cnt/=tmp;
        printf("%lld/%lld\n",cnt,sum);
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

K.Kcats

lmj 赛后

题意

考虑一个$1$到$n$的排列,我们在上面跑一边单调栈,并在第$i$个数字入栈后记录当前栈内数字个数$p_i$,现在给定数组$p$,其中有些一些元素已知,一些未知,求合法的原排列的个数。

题解

考虑笛卡尔树,在每次加入一个元素时,利用单调栈构造时,只会有一个点从右儿子变成左儿子,然后把该点补到那个位置。可以发现所有右儿子到父亲的边数等于这个点入栈时除其自己以外的点数。
考虑$dp$,$dp[i][j][k]$代表区间$[i,j]$所形成的子树的根往真正的根跳所经过的右儿子到父亲的边。
$dp[i][j][k]=\sum_{d=i}^j dp[i][d-1][k]*dp[d+1][j][k+1]*C_{j-i}^{d-i}$

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ll pre[105];
ll inv[105];
ll dp[105][105][105];
int a[105];
ll C(int n,int m)
{
    return pre[n]*inv[n-m]%p*inv[m]%p;
}
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    memset(dp,0,sizeof(dp));

    for(int len=1;len<=n;len++){
        for(int i=1;i<=n-len+1;i++){
            int j=i+len-1;
            for(int k=i;k<=j;k++){
                int ll,rr;
                if(a[k]==-1){
                    ll=1,rr=i;
                }else{
                    ll=rr=a[k];
                }
                for(int d=ll;d<=rr;d++){
                    long long sum1;
                    long long sum2;
                    if(k!=i)sum1=dp[i][k-1][d];
                    else sum1=1;
                    if(k!=j)sum2=dp[k+1][j][d+1];
                    else sum2=1;
                    dp[i][j][d]=(dp[i][j][d]+sum1*sum2%p*C(j-i,k-i)%p)%p;
                }
            }
        }
    }
    printf("%lld\n",dp[1][n][1]);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    pre[0]=1;
    for(int i=1;i<=100;i++){
        pre[i]=pre[i-1]*i%p;
    }
    inv[100]=qpow(pre[100],p-2);
    for(int i=99;i>=0;i--){
        inv[i]=inv[i+1]*(i+1)%p;
    }
    //cin>>T;
    while(T--){
        work();
    }
}
Responses