2020牛客暑期多校训练营(第三场)
in 牛客多校多校训练 with 0 comment

2020牛客暑期多校训练营(第三场)

in 牛客多校多校训练 with 0 comment

摘要

/ABCDEFGHIJKL
场上
zyj
wrf
lmj

题目

A.Clam and Fish

lmj 00:21:51 +1

题意

n个时间 0代表没有鱼没有蚯蚓 1代表没有鱼有蚯蚓 2代表有鱼没蚯蚓 3代表有鱼有蚯蚓
每个时间仅可以做一件事 如果有蚯蚓,可以将其做成鱼饵,鱼饵+1;如果有鱼,可以抓鱼,鱼数量加一,不消耗鱼饵;消耗鱼饵抓一条鱼;什么都不做

题解

显然如果有鱼直接抓即可,剩下的就是判断1的时候是抓鱼还是抓蚯蚓,采用后缀和求后面还有多少个0和1可以抓鱼,然后从前往后遍历,1的时候抓蚯蚓,0的时候用鱼饵抓鱼,如果当前的鱼饵数大于等于了后面可以抓鱼的次数,那么后面就只抓鱼,答案加上后面的可用抓鱼次数即可

代码

#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=2e6+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;}
char a[N];
int sum[N];
void work()
{
    int n;
    scanf("%d",&n);
    scanf("%s",a+1);
    int ans=0;
    for(int i=1;i<=n;i++){
        if(a[i]=='2'||a[i]=='3'){
            ans++;
            sum[i]=0;
        }
        if(a[i]=='1'||a[i]=='0'){
            sum[i]=1;
        }
    }
    sum[n+1]=0;
    for(int i=n-1;i>=1;i--){
        sum[i]+=sum[i+1];
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(a[i]=='1'){
            cnt++;
        }
        if(a[i]=='0'){
            if(cnt){
                cnt--;
                ans++;
            }
        }
        if(cnt>=sum[i+1]){
            ans+=sum[i+1];break;
        }
    }
    printf("%d\n",ans);
}
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();
    }
}

B.Classical String Problem

lmj 00:10:50 +0

题意

对于一串字符串有两种操作 M x代表x为正时将前x位放到最后去,为负时将后x位放到前面, A x代表询问当前第x个位置的值

题解

将字符串复制三份,将l,r指向len和2*len-1,然后M就直接对l,r进行加减,如果超出了这3个字符串的长度,考虑加减len使其依然在该3个字符串内

代码

#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=6e6+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;}
char a[N];
void work()
{
    scanf("%s",a);
    int len=strlen(a);
    for(int i=len;i<3*len;i++){
        a[i]=a[i%len];
    }
    int n;
    scanf("%d",&n);
    int l=len;
    int r=2*len-1;
    for(int i=1;i<=n;i++){
        char b[10];
        int x;
        scanf("%s%d",b,&x);
        if(b[0]=='A'){
            printf("%c\n",a[l+x-1]);
        }else{
            l+=x;
            r+=x;
            if(l>=2*len){
                l-=len;
                r-=len;
            }
            if(r<len){
                l+=len;
                r+=len;
            }
        }
    }
}
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();
    }
}

C.Operation Love

lmj+zyj (03:07:54) +21

题意

给出20个点的坐标和一个手掌的标准形状,手掌可以旋转和平移,问你是左手还是右手;

题解

找到长为9的边之后判一下与其垂直的6和9的朝向(叉积)
赛中叉积写成点积wa了21发

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
const double eps=1e-3;
const double inf=10000;
const int maxP=1100;
const double PI=acos(-1.0);
inline double sqr(double d){return d*d;}
inline int dcmp(double d){return d<-eps?-1:d>eps;}

struct Point{
    double x,y;
    Point(){}
    Point(const double &_x,const double &_y):x(_x),y(_y){}
    bool operator ==(const Point &p)const{return(dcmp(x-p.x)==0&&dcmp(y-p.y)==0);}
    bool operator <(const Point &p)const{return y+eps<p.y||(y<p.y+eps&&x+eps<p.x);}
    Point operator +(const Point &p)const{return Point(x+p.x,y+p.y);}
    Point operator -(const Point &p)const{return Point(x-p.x,y-p.y);}
    Point operator *(const double &k)const{return Point(x*k,y*k);}
    Point operator /(const double &k)const{return Point(x/k,y/k);}
    double operator *(const Point &p)const{return x*p.y-y*p.x;}
    double operator /(const Point &p)const{return x*p.x+y*p.y;}
    double len2(){return x*x+y*y;}
    double len(){return sqrt(x*x+y*y);}
    Point scale(const double &k){return dcmp(len())?(*this)*(k/len()):(*this);}
    Point turnLeft(){return Point(-y,x);}
    Point turnRight(){return Point(y,-x);}
    void input(){scanf("%lf%lf",&x,&y);}
    void output(){printf("%.2lf %.2lf\n",x+eps,y+eps);}
    double Distance(Point p){return sqrt(sqr(p.x-x)+sqr(p.y-y));}
    Point rotate(const Point &p,double angle,double k=1){
        Point vec=(*this)-p;
        double Cos(cos(angle)*k),Sin(sin(angle)*k);
        return p+Point(vec.x*Cos-vec.y*Sin,vec.x*Sin+vec.y*Cos);
    }
}a[2200];
void solve(){
    rep(i,1,20) a[i].input();
    int st=0,ed=0,z=0;
    // vector<double> v;
    rep(i,1,20) rep(j,i+1,20){
        // v.pb(a[i].Distance(a[j]));
        // printf("%.10lf\n",a[i].Distance(a[j]));
        if(fabs(a[i].Distance(a[j])-9)<=eps){st=i;ed=j;break;}
    }
    assert(st>0);assert(ed>0);
    // sort(v.begin(),v.end());
    // for(auto u:v) printf("%.10lf\n",u);
    rep(i,1,20) if(i!=st&&i!=ed){
        if(fabs(a[st].Distance(a[i])-6)<=eps||fabs(a[st].Distance(a[i])-8)<=eps){z=i;break;}
    }
    assert(z>0);
    double len=a[st].Distance(a[z]);
    double tmp=(a[z].x-a[st].x)*(a[ed].y-a[st].y)-(a[z].y-a[st].y)*(a[ed].x-a[st].x);
    // printf("%d %d %d\n",st,ed,z);
    if(fabs(len-6.0)<=eps){
        // printf("%f\n",len);
        if(tmp<0) printf("right\n");
        else printf("left\n");
    }else{
       // printf("%f\n",len);
        if(tmp>0) printf("right\n");
        else printf("left\n");
    }
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

D.Points Construction Problem

lmj 3:51:35 +1

题意

要求在平面内构造n个黑点,其余为白点,使得相邻为黑白两色的对数量为m

题解

显然最多的时候为4*n,最少的时候为构成一个正方形同时往外扩,考虑开始为构成一个正方形,可以发现,,只在刚好是正方形时再往外加1格和加(x,x)的位置时会使得答案+2,那么接下来就考虑如何去拟合答案m,对于没有贡献的点,将其移到前一个点的另一个方向,可以获得加2的贡献,将其整体移出去可以获得加4的贡献,对于有贡献的点,将其整体移出去可以获得加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=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;}
struct node
{
   int x,y; 
}a[10005];
int vis[205];
void work()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int tmp=sqrt(n);
    int tmpp=tmp*4;
    if(n>tmp*tmp){
        tmpp+=2;
    }
    if(n>tmp*tmp+tmp){
        tmpp+=2;
    }
    //printf("%d\n",tmpp);
    if(n*4<m||m<tmpp||m&1){
        printf("No\n");return;
    }
    int cnt=0;
    for(int i=1;i<=tmp+1;i++){
        int xx,yy;
        if(i&1){
            xx=1;
            yy=i;
        }else{
            xx=i;
            yy=1;
        }
        while(cnt<n&&xx&&yy){
            a[++cnt].x=xx;
            a[cnt].y=yy;
            if(i&1){
                if(xx<i){
                    xx++;
                }else{
                    yy--;
                }
            }else{
                if(yy<i){
                    yy++;
                }else{
                    xx--;
                }
            }
        }
    }
    int nowx=100;
    int nowy=100;
    for(int i=cnt;i>=2;i--){
        if(m==tmpp)break;
        if(!vis[i]){
            if(m>=tmpp+4){
                tmpp+=4;
                a[i].x=nowx;
                a[i].y=nowy;
                nowx+=2;
            }else if(m==tmpp+2){
                if(a[i].x==a[i-1].x){
                    a[i].x=a[i-1].x+1;
                    a[i].y=a[i-1].y;
                }else{
                    a[i].x=a[i-1].x;
                    a[i].y=a[i-1].y+1;
                }
                tmpp+=2;
            }
        }else{
            if(m>=tmpp+2){
                tmpp+=2;
                a[i].x=nowx;
                a[i].y=nowy;
                nowx+=2;
            }
        }
    }
    printf("Yes\n");
    for(int i=1;i<=n;i++){
        printf("%d %d\n",a[i].x,a[i].y);
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    vis[1]=1;
    int now=1;
    for(int i=1;i<=10;i++){
        now+=i;
        vis[now]=1;
        now+=i;
        vis[now]=1;
    }
    //cin>>T;
    while(T--){
        work();
    }
}

E.Two Matchings

lmj+zyj 02:02:17 +7

题意

对于一个序列,找若干个长度为2的置换,答案为每个点和他置换的差绝对值的和/2,要求找两种这样的置换,使得两种置换中没有任何的重复置换,问最小的答案

题解

将序列排序,第一种置换显然是两两相邻的置换,第二种分别考虑4个和6个的情况,可以发现考虑相邻点的贡献时,答案为所有相邻点的差乘2再减去一些东西,减去的是什么呢,我们考虑8个的情况,4和4,这时候第4个和第5个的差没有被计算在内,考虑10个的时候,6和4,第6个和第7个的差没有被计算在内,那么考虑使用动态规划$dp[i]=max(dp[i-4],dp[i-6])+a[i]-a[i-1]$。然后最后取$dp[n]$即可

代码

#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 a[N];
ll dp[N];
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        dp[i]=0;;
    }
    sort(a+1,a+n+1);
    a[n+1]=a[n];
    ll ans=0;
    for(int i=2;i<=n;i++){
        ans+=a[i]-a[i-1];
    }
    for(int i=2;i<=n;i+=2){
        if(i>=4){
            dp[i]=max(dp[i],dp[i-4]+(a[i+1]-a[i]));
        }
        if(i>=6){
            dp[i]=max(dp[i],dp[i-6]+(a[i+1]-a[i]));
        }
    }
    printf("%lld\n",(ans-dp[n])*2);
}
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();
    }
}

F.Fraction Construction Problem

lmj 2:57:09 +3

题意

求$c/d-e/f=a/b$,已知$a,b$,要求$d<b,f<b$,求是否存在$c,d,e,f$满足条件,并输出

题解

如果$a,b$不互质,显然直接简化后,将$c/d$设为整数,$e/f$为$c/d-a/b$即可。如果b只有一种质因子,那么显然没有答案,必然无法满足$d<b,f<b$。那么考虑d*f=b的情况,那么就是要$c*f-e*d=a$,此时我们可以设定f和d的值,这就可以变化为$c*f=a (mod d)$,这就是一个exgcd所解决的东西,然后求出c,再求出e,注意c,e要大于0。

代码

#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;}
void exgcd(ll a,ll b,ll& x,ll& y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return ;
    }

    exgcd(b,a%b,x,y);
//cout<<a<<" "<<b<<" "<<x<<" "<<y<<"^"<<endl;
    ll k=x;
    x=y;
    y=k-(a/b)*y;
//cout<<a<<" "<<b<<" "<<x<<" "<<y<<"$"<<endl;
    return ;
}

ll inv(ll a,ll p)
{
    if(a==0)
    {
        return 0LL;
    }
    ll x,y;

    exgcd(a,p,x,y);

    return (x%p+p)%p;
}

void work()
{
    int a,b;
    scanf("%d%d",&a,&b);
    if(__gcd(a,b)!=1){
        int tmp=__gcd(a,b);
        a/=tmp;
        b/=tmp;
        if(a%b==0){
            printf("%d %d %d %d\n",(a+b-1)/b+1,1,(b-a%b)%b+b,b);
        }else{
            printf("%d %d %d %d\n",(a+b-1)/b,1,(b-a%b)%b,b);
        }
        return;
    }
    ll d=1,f=1;
    for(int i=2;i*i<=b;i++){
        if(b%i==0){
            while(b%i==0){
                b/=i;
                d*=i;
            }
            break;
        }
    }
    f=b;
    if(f==1||d==1){
        printf("-1 -1 -1 -1\n");return;
    }
    ll c=inv(f,d)*a%d;
    ll e=(c*f-a)/d;
    if(e<0){
        ll tmp=abs(e)/f+1;
        c+=d*tmp;
        e+=f*tmp;
    }
    printf("%lld %lld %lld %lld\n",c,d,e,f);
}
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();
    }
}

G.Operating on a Graph

wrf(赛后)

题意

给出一个点有颜色的图,起初每个点的颜色都等于它自己。
给出若干次操作,每次操作有一个参数 $o$,表示对于所有颜色为 $o$ 的点,把它周围所有和它颜色不同的单色连通块染成 $o$(如果没有这样的点,则跳过该操作)。
输出按顺序执行这些操作之后,每个点的颜色。

题解

做法

定义某个颜色『内部』的点为,和周围所有点颜色相同的点。定义颜色没有改变过的点为该颜色的根。
对每个根维护一个链表,表示该点所属颜色中,不在和目前不能确定在内部的点。
对于每次操作 $o$,如果颜色 $o$ 没有根,跳过;否则,首先建立一个临时链表 $tmp$,初始为空。遍历 $o$ 上的链表,对每个链表中的点,再遍历其相邻的所有点。在这些点中,如果有颜色不为 $o$ 的,将它根的链表合并进 $tmp$,并将根的颜色染成 $o$,删除该点的原始数据。最后用 $tmp$ 取代 $o$ 上的链表。
注意每次查询某个点的颜色时,查询的事实上是它根的颜色。这可以用一个并查集维护。

证明

先证它迭代之后性质不变
显然每次操作之后,原本在链表中的点都已经到达内部了,所以这些点都不应该留在链表中。而刚刚被『侵略』的根所属链表,目前都暂不能确定是否在内部,所以应当存在于链表中。最后,如果一个根不再是根了,那么我们就不再维护它的链表了。
再证它能收敛到解
显然。每次都是按题意做的。

时间复杂度

首先每个点最多存在于一个链表中,且当某个点不存在于任何链表中之后,它就不可能加回某个链表中了。因为在整个过程中没有新增点的操作,只有链表的转移、取代和删除。所以链表中的点数是单调不增的
再考虑在什么情况下一个点会从链表中被删除。首先整个过程中只会删除整条链。这种情况只可能是链所在的根发起了一次操作。每次操作会遍历链中每个点的每条出边,所以每个点被删除的代价就是它的出边数量*原子操作的代价
而链表中的点数单调不增,且最坏的情况就是没有点在链表中。此时的代价就是总边数*原子操作的代价。而原子操作就是(无启发式合并的)并查集查询、修改和链表连接。
所以总时间复杂度就是 $O(n \log n)$

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=100020;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int fa(int n,vector<int> &un)
{
    if(un[n]!=n) un[n]=fa(un[n],un);
    return un[n];
}

int main(void)
{
    for(int _=read();_>0;_--)
    {
        int n=read(),m=read();
        vector<vector<int> > g(n);
        vector<int> un(n);
        vector<list<int> > ls(n);

        for(int i=0;i<n;i++)
        {
            un[i]=i;
            ls[i].push_back(i);
        }
        for(int i=0;i<m;i++)
        {
            int l=read(),r=read();
            g[r].push_back(l);
            g[l].push_back(r);
        }

        for(int __=read();__>0;__--)
        {
            int o=read();

            list<int> t;
            for(auto i:ls[o])
            {
                for(auto j:g[i])
                {
                    if(fa(j,un)!=o)
                    {
                        int y=fa(j,un);
                        t.splice(t.end(),ls[y]);
                        un[fa(y,un)]=o;
                    }
                }
            }
            ls[o].clear();
            ls[o].splice(ls[o].end(),t);
        }

        for(int i=0;i<n;i++)
        {
            printf("%d ",fa(i,un));
        }
        printf("\n");
    }
    
    return 0;
}

H.Sort the Strings Revision

lmj (赛后)

题意

给定一个长度为n的序列,序列为0123456789的循环,再给出0——n-1的一个排列,和对应位置的值,每次操作将排列所对应的序列位置改成对应的值,求所有操作完成后的n个序列排序后乘某个数的i次幂的和

题解

考虑笛卡尔树,将n次操作以操作位置进行排序,dfs笛卡尔树时,通过当前点的值改变将序列分成两块,优先dfs小的那个,l等于r时记录排名即可,注意当值不进行改变时,需要将其压入前一个操作,比前一个操作的排名大1

代码

#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=2e6+5;
const int mod=1e9+7;
int stk[N];
int h[N];
int p[N];
int d[N];
vector<int>v[N];
int ans[N];
int ls[N];
int rs[N];
int tot;
void dfs(int l,int r,int rt)
{
    if(l>r)return ;
    if(l==r){
        for(auto x:v[l]){
            ans[x]=tot++;
        }
        return;
    }
    if(!rt)return;
    if(d[rt]<p[rt]%10){
        dfs(rt,r,rs[rt]);
        dfs(l,rt-1,ls[rt]);
    }else{
        dfs(l,rt-1,ls[rt]);
        dfs(rt,r,rs[rt]);
    }
}
void work()
{
    int n;
    scanf("%d",&n);
    tot=0;
    ll pseed,pa,pb,pmod;
    scanf("%lld%lld%lld%lld",&pseed,&pa,&pb,&pmod);
    for(int i=0;i<=n-1;i++){
        p[i]=i;
    }
    for(int i=1;i<=n-1;i++){
        swap(p[i],p[pseed%(i+1)]);
        pseed=(pseed*pa+pb)%pmod;
    }
    ll dseed,da,db,dmod;
    scanf("%lld%lld%lld%lld",&dseed,&da,&db,&dmod);
    for(int i=0;i<=n-1;i++){
        d[i]=dseed%10;
        dseed=(dseed*da+db)%dmod;
    }
    for(int i=0;i<=n;i++){
        v[i].clear();
        ls[i]=0;
        rs[i]=0;
        ans[i]=0;
    }
    v[0].push_back(0);
    for(int i=n;i>=1;i--){
        p[i]=p[i-1];
        d[i]=d[i-1];
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(p[i]%10==d[i]){
            ans[i]=ans[i-1];
        }else{
            ans[i]=++cnt;
            p[cnt]=p[i];
            d[cnt]=d[i];
        }
        v[ans[i]].push_back(i);
    }
    int top=0;
    for (int i = 1; i <= n; i++) {
      int k = top;
      while (k > 0 && p[stk[k]] > p[i]) k--;
      if (k) rs[stk[k]] = i;  // rs代表笛卡尔树每个节点的右儿子
      if (k < top) ls[i] = stk[k + 1];  // ls代表笛卡尔树每个节点的左儿子
      stk[++k] = i;
      top = k;
    }
 
    for(int i=0;i<=n;i++){
        ans[i]=0;
    }
    int root=stk[1];
    dfs(0,cnt,root);
    ll sum=0;
    ll tmp=1;
    for(int i=0;i<=n;i++){
        sum=sum+ans[i]*tmp;
        sum%=mod;
        tmp=tmp*10000019%mod;
    }
    printf("%lld\n",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();
    }
}

I.Sorting the Array

zyj (赛后)

题意

给出一个n的排列,用一个长为m的滑动窗口扫一遍这个排列,每次把滑窗内的数sort,给出最终操作完的数组ret,问你所有可能的原串中字典序第k小的。($n,m \leq 8*10^5,k \leq 10^{18}$ ,保证有解)

题解

假设数组$a$为一个可能的原数组,我们有:

重要性质:

对于一个i,若存在一个$ret[j]>ret[i]$且$j < i$,那么$a[i+m-1]=ret[i]$

简要证明:
首先我们来考虑一个简单的问题,如果$ret[i-1]>ret[i]$,那么必有$a[i+m-1]=ret[i]$,因为当滑窗处于$[i-1,i-1+m-1]$并且排好序之后,滑窗的最左边是$ret[i-1]$,并且滑窗内其他的数都是大于$ret[i-1]$并且递增的,那么当滑动窗口向后滑动一位时,要使得$ret[i] < ret[i-1]$,$ret[i]$只能是新加进来的那个数。
并且我们发现,如果一个数的位置是固定的,那么他加入到滑窗时对于滑窗内的状态是不会产生影响的,并且$ret[]$的所有前缀中除去固定位置,其余位置的值是递增的。
不难看出,确定位置的数对于序列是不会产生影响的,换句话说我们完全可以忽略那些已经确定位置的数;那既然这样,由于前缀递增,那么前缀最大值也就等于前缀的最后一位;
因此推广到一般情况,上述性质成立。

对于未确定位置的数,第i位数在原序列a中可能的位置是$[1,min(i+m-1,n)]$。既然这样,不难算出原串一共有$\prod_{i=1}^{cnt} \min (m, n-i+1)$种可能(cnt为未确定点的个数)。

那么我们可以从0到n-1枚举i,在$a[0] - a[min(n-1,i+m-1)]$中选一个尚未确定的值定为i。这样我们就能得到所有可能的原数组$a$,那既然我们能确定所有的a数组,不难发现我们也能比较容易的算出每一位的贡献。
因此我们可以找到一个尽可能大的数$v$,满足$\prod_{i=v}^{n-1} \min (m, n-i) \geq k$,则字典序第$k$小的$a$中,对于所有$i < v$必有$a[i]=i$。

最后数组$a$至多只剩下$\min (n, \log k)=s$个不确定位置的数,我们令$ret$数组第$i$位在原数组中可选位置的方案数初值为$val[i]=min(m,n-i+1)$,接下来写一个贪心确定每一位的位置我们可以对每个位置枚举要放那个数字,并按照类似上页所列的排组方式以$O(s)$的时间计算该位置摆该数字时$b$数组含有多少种可能性。有$O(s)$个位置,每个位置至多枚举$O(s)$个数,每次花$O(s)$的时间计算,于是我们就得到一个单组数据$O(s3)$的方法。而所有数据实际是时间复杂度分析出来会是$O(n log^2 k)$的。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
typedef __int128 il;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int ret[maxn],ans[maxn],use[maxn],vis[maxn],sta[maxn],id[maxn],top,st;
ll n,m,k,val[maxn];
il sub[maxn];
il cal(int x){
    il res=1;
    rep(i,st,top) if(!use[i]&&i!=x) res*=(i<x?(val[i]-1):val[i]);
    return res;
}
void solve(){
    scanf("%lld%lld%lld",&n,&m,&k);
    rep(i,1,n) scanf("%d",&ret[i]);
    int pre=ret[1],pos=2;top=0;sta[++top]=ret[1];id[1]=1;
    rep(i,2,n){
        if(ret[i]<pre) vis[i+m-1]=1,ans[i+m-1]=ret[i];
        else{
            sta[++top]=ret[i];
            while(vis[pos]) pos++;
            id[top]=pos++;
        }pre=max(pre,ret[i]);
    }sub[top+1]=1;st=0;
    rep(i,1,top) val[i]=min(m,1ll*top-i+1);
    dep(i,top,1) sub[i]=sub[i+1]*val[i];
    dep(i,top,1) if(sub[i]>k){st=i;break;}
    rep(i,1,st-1) ans[id[i]]=sta[i]; k--;
    rep(i,st,top){
        pos=-1;
        rep(j,st,top) if(!use[j]){
            il x=cal(j);
            if(k-x<0){
                ans[id[i]]=sta[j];
                rep(c,st,j) val[c]=max(val[c]-1,0ll);
                pos=j;break;
            }else k-=x;
        }use[pos]=1;
    }rep(i,1,n) printf(i==n?"%d\n":"%d ",ans[i]);
    rep(i,0,n) vis[i]=use[i]=0;
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

J.Operating on the Tree

题意

题解

代码


K.Eleven Game

lmj (赛后)

题意

给出n长度的序列,由0-9和?组成,a和b分别对?填数,如果最后的结果不是11的倍数,那么要取反,如果问号的个数为奇数,a先填,否则b先填,a要使答案尽量大,b要使答案尽量小,问最后的结果

题解

首先先判断答案的正负的情况,如果某个数为11的倍数,那么奇数位的和减去偶数位的和为11的倍数,考虑每个问号对答案的贡献,如果问号在奇数位,那么填0-9对答案的贡献是-1+x,1<=x<=10,如果问号填偶数位,那么填9-0对答案的贡献为-10+x,1<=x<=10,那么就可以变成一个抢三十游戏,就可以判断答案的正负情况。
然后再是如何求到最后的答案,显然如果开始时不是11的倍数,那么先手必胜,若先手是a,那么显然答案为正,否则答案为负,为11倍数时则相反。然后如何考虑各种情况看代码注释。

代码

#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;}
char a[N];
deque<int>d1,d2;
void work()
{
    int n;
    scanf("%d",&n);
    scanf("%s",a);
    d1.clear();
    d2.clear();
    int sum=0;
    int cnt=0;
    if(n%2==0){
        for(int i=0;i<n;i++){
            if(i&1){
                if(a[i]=='?'){
                    d1.push_back(i);
                    sum-=1;
                    cnt++;
                }else{
                    sum+=a[i]-'0';
                }
            }else{
                if(a[i]=='?'){
                    d2.push_back(i);
                    sum-=10;
                    cnt++;
                }else{
                    sum-=a[i]-'0';
                }
            }
        }
    }else{
        for(int i=0;i<n;i++){
            if(i%2==0){
                if(a[i]=='?'){
                    d1.push_back(i);
                    sum-=1;
                    cnt++;
                }else{
                    sum+=a[i]-'0';
                }
            }else{
                if(a[i]=='?'){
                    d2.push_back(i);
                    cnt++;
                    sum-=10;
                }else{
                    sum-=a[i]-'0';
                }
            }
        }
    }
    sum=(sum%11+11)%11;
    if(sum){                            //如果开局不是11倍数,那么显然先手的人要将其变成11的倍数
        if(!d1.empty()&&!d2.empty()){
            if(d1.front()<d2.front()){  //显然越往前放越大(取反后越小)
                if(sum!=10){            //如果不是放的0,那么直接放,否则考虑放另一个位置
                    a[d1.front()]=10-sum+'0';
                    d1.pop_front();
                }else{
                    a[d2.front()]='9';
                    d2.pop_front();
                }
            }else{
                if(sum!=1){
                    a[d2.front()]='0'+sum-1;
                    d2.pop_front();
                }else{
                    a[d1.front()]='9';
                    d1.pop_front();
                }
            }
        }else if(!d1.empty()){      //如果只能放一个位置,放的不是0的话,就放前面,否则放最后
            if(sum!=10){
                a[d1.front()]=10-sum+'0';
                d1.pop_front();
            }else{
                a[d1.back()]='0';
                d1.pop_back();
            }
        }else if(!d2.empty()){
            if(sum!=1){
                a[d2.front()]='0'+sum-1;
                d2.pop_front();
            }else{
                a[d2.back()]='0';
                d2.pop_back();
            }
        }
    }
    while(!d1.empty()||!d2.empty()){
        if(d1.size()+d2.size()==1){         //只能放一个的情况
            if(!d1.empty()){
                a[d1.front()]='0';
                d1.pop_front();
            }else{
                a[d2.front()]='0';
                d2.pop_front();
            }
        }if(min(d1.size(),d2.size())==1){   //有一组只有一个?的情况,此时考虑直接在只有1个的那组放0
            a[d1.back()]='0';               //那么显然另外一个人要保证结果依然为11的倍数,要在另一组放0
            a[d2.back()]='0';               //显然放最后更优
            d1.pop_back();
            d2.pop_back();
        }else if(!d1.empty()&&!d2.empty()){     //两组都能放2个以上的情况,考虑其次大位置的前后顺序
            int b1=d1.front(),b2=d2.front();
            d1.pop_front(),d2.pop_front();
            int c1=d1.front(),c2=d2.front();
            d1.push_front(b1),d2.push_front(b2);
            if(c1>c2){
                a[d1.front()]='0';
                d1.pop_front();
                a[d1.front()]='9';
                d1.pop_front();
            }else{
                a[d2.front()]='0';
                d2.pop_front();
                a[d2.front()]='9';
                d2.pop_front();
            }
        }else if(!d1.empty()){                  //如果仅有一个位置,那么在最后放9,另外一个人只能放0,优先放在最后
            a[d1.back()]='9';
            d1.pop_back();
            a[d1.back()]='0';
            d1.pop_back();
        }else if(!d2.empty()){
            a[d2.back()]='9';
            d2.pop_back();
            a[d2.back()]='0';
            d2.pop_back();
        }
    }
    if(cnt%2==0){
        if(sum){
            printf("-");
        }
    }else{
        if(!sum){
            printf("-");
        }
    }
    for(int i=0;i<n;i++){
        printf("%c",a[i]);
    }
    printf("\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();
    }
}

L.Problem L is the Only Lovely Problem

lmj 00:03:09 +0

题意

若字符串前面为lovely,输出lovely,否则输出ugly

题解

签到

代码

#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;}
char a[20];
void work()
{
    scanf("%s",a);
    int l=strlen(a);
    if(l<6){
        printf("ugly\n");return;
    }
    for(int i=0;i<l;i++){
        if(a[i]>='A'&&a[i]<='Z'){
            a[i]+=32;
        }
    }
    if(a[0]=='l'&&a[1]=='o'&&a[2]=='v'&&a[3]=='e'&&a[4]=='l'&&a[5]=='y'){
        printf("lovely\n");
    }else{
        printf("ugly\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();
    }
}
Responses