Logo gyh20的博客

博客

标签
暂无

InfOJ NOIP2023 模拟赛 题解

2023-11-11 23:43:38 By gyh20

A

部分分可以分讨/搜索。

这个题长得就很区间 DP。我们假设一个区间被删完,那么最后被删掉的那些数将区间划分为了若干个子区间。每个子区间是独立的,可以直接相加,最终要求剩下的数 and 值不为 $0$ 就行。

于是我们可以定义 $f_{l,r,k}$ 表示区间 $l,r$,最后被删掉的那些数 and 为 $k$ 时的最大操作次数。一种转移方法可以枚举其中第一个最后一次被删的数 $i$,那么 $[l,i-1]$ 是一个子问题,$[i+1.r]$ 是一个子问题。

总复杂度 $O(n^3V)$,看上去存在一个更有复杂度的做法不过出题人没有细想。

#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
    re int t=0;re char v=getchar();
    while(v<'0')v=getchar();
    while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
    return t;
}
int n,m,a[65],f[65][65][65];
inline int calc(re int l,re int r,re int X){
    if(~f[l][r][X])return f[l][r][X];
    re int s=0,nx=(X==0)?63:X;
    for(re int i=l;i<=r;++i)s=max(s,calc(i+1,r,nx&a[i])+calc(l,i-1,63));
    return f[l][r][X]=s+(X==0);
}
int main(){
    memset(f,-1,sizeof(f)),n=read();
    for(re int i=1;i<=n;++i)a[i]=read();
    printf("%d",calc(1,n,63));
}

B

部分分可以搜索/DP。

我们发现,减小一个数时,当且仅当其比相邻两个数都要小时式子的值才会发生变化,且变化量一定恰好为 $2$,所以,若存在这样的数,直接操作一定最优。

若不存在这样的数,一定存在极长值域相同段满足这个条件。此时使式子变小的方式只能是将这个值域相同连续段中的所有数 $-1$,使答案 $-2$。

可以证明,我们可以每次选择长度最小的满足上述条件的值域连续段。

同时我们发现,删去一个连续段可能产生新的连续段,不过总段数是 $O(n)$ 的,可以直接用优先队列维护。

知道每一段的长度,答案可以看成一个分段函数,直接二分即可。

时间复杂度 $O((n+m)\log n)$。

#include<bits/stdc++.h>
#define re register
#define int long long
using namespace std;
inline int read(){
    re int t=0;re char v=getchar();
    while(v<'0')v=getchar();
    while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
    return t;
}
int n,a[1000002],fa1[1000002],fa2[1000002],tim,W,q,sum;
inline int root1(re int x){return x==fa1[x]?x:fa1[x]=root1(fa1[x]);}
inline int root2(re int x){return x==fa2[x]?x:fa2[x]=root2(fa2[x]);}
inline void Merge(re int x){fa1[root1(x)]=root1(x-1),fa2[root2(x-1)]=root2(x);}
struct node{
    int l,r;
    bool operator <(const node A)const{return r-l>A.r-A.l;}
};
priority_queue<node>Q;
struct Node{int x,y,z;bool operator <(const Node A)const{return x==A.x?y<A.y:x<A.x;};};
vector<Node>T;
inline void ck(re int x){
    re int l=root1(x),r=root2(x);
    if(a[l]>a[l-1]&&a[r]>a[r+1])Q.push((node){l,r});
}
inline int Abs(re int x){return x>0?x:-x;}
signed main(){
    n=read(),q=read();int ss=0;
    for(re int i=1;i<=n;++i)a[i]=read(),ss+=a[i],fa1[i]=fa2[i]=i;fa1[n+1]=fa2[n+1]=n+1;
    for(re int i=0;i<=n;++i)sum+=Abs(a[i+1]-a[i]);
    a[0]=a[n+1]=-1e18;
    for(re int i=2;i<=n;++i)if(a[i]==a[i-1])Merge(i);
    for(re int i=1;i<=n;++i)if(root1(i)==i)ck(i);
    while(!Q.empty()){
        re node tmp=Q.top();Q.pop();
        if(tmp.l==1&&tmp.r==n){T.push_back((Node){tim,W,n});break;}
        else{
            T.push_back((Node){tim,W,tmp.r-tmp.l+1});
            re int dlt=max(a[tmp.l-1],a[tmp.r+1]);
            tim+=(a[tmp.l]-dlt)*(tmp.r-tmp.l+1),W+=a[tmp.l]-dlt;
            a[tmp.l]=a[tmp.r]=dlt;
            if(a[tmp.l]==a[tmp.l-1])Merge(tmp.l);
            if(a[tmp.r]==a[tmp.r+1])Merge(tmp.r+1);
            ck(tmp.l);
        }
    }
    while(q--){
        re int x=read(),pos=upper_bound(T.begin(),T.end(),(Node){x,1000000000000000000ll,0})-T.begin()-1;
        printf("%lld\n",max(0ll,sum-2*(T[pos].y+(x-T[pos].x)/T[pos].z)));
    }
}

C

部分分可以树形背包。

先考虑 $f_i=-1$ 的情况,这时我们只需要把这个点所有儿子接到这个点的父亲即可。

所以我们只用考虑 $f_i\neq -1$ 的情况。

可以发现答案可以看成对于每个子树分别求答案,最终乘起来。我们不妨假设 $g_i$ 表示子树 $i$ 恰好有 $1\sim f_i$ 这些颜色的方案书。使用容斥原理,我们钦定 $k$ 种颜色使得最终只出现这 $k$ 种之一的颜色。所以我们有 $g_x=\sum_{i=0}^{f_x}(-1)^{f_x-i}\prod_{y\in son(x)}g_y\dbinom{i}{f_y}$,直接计算复杂度 $O(nm)$。

由于这是 NOIP 模拟肯定不存在多项式。我们得用树的性质来优化。我们发现,上述式子种的 $i$ 实际上只需要从 $f$ 最大的一个儿子开始枚举。否则组合数就为 $0$。

然后我们可以合并相同的 $f$,即有多个相同的 $f$ 我们可以用快速幂计算。

我们可以证明上述算法是 $O(n\sqrt n)$ 的。

首先由于相同的 $f$ 合并后只会有 $O(\sqrt n)$ 种不同的 $f$,所以这部分是 $O(\sqrt n \log n)$ 的,然后这里可以分析到 $O(\sqrt n)$,参见上次 UR 的 T1。

我们每次从最大的 $f$ 的儿子开始枚举,其实可以看作从 size 最大的儿子开始枚举,代价 $f_x-f_y$ 求和可以看成每个点的轻儿子大小之和,是 $O(n\log n)$ 的。

所以这部分是 $O(n\sqrt n\log n)$ 的 ,据 127 称可以分析到 $n\sqrt n$,我也不太会(不过可以发现造不出卡到 $\sqrt n \log n$ 的数据)。

#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
    re int t=0,f=0;re char v=getchar();
    while(v<'0')f|=(v=='-'),v=getchar();
    while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
    return f?-t:t;
}
const int M=1e9+7;
inline int ksm(re int x,re int y){
    re int s=1;
    while(y){
        if(y&1)s=1ll*s*x%M;
        x=1ll*x*x%M,y>>=1;
    }return s;
}
inline void add(re int&x,re int y){(x+=y)>=M?x-=M:x;}
int n,m,head[200002],fac[200002],inv[200002],f[200002],ans,cnt,fa[200002];
struct edge{int to,next;}e[400002];
inline void addd(re int x,re int y){e[++cnt]=(edge){y,head[x]},head[x]=cnt;}
struct node{int x,y;};
inline int C(re int x,re int y){return 1ll*fac[x]*inv[y]%M*inv[x-y]%M;}
inline void dfs(re int x,re int y){
    map<int,int>V;vector<node>tmp;re int mx=0,num=0;
    for(re int i=head[x];i;i=e[i].next)dfs(e[i].to,x),++V[f[e[i].to]],mx=max(mx,f[e[i].to]),++num;
    ++V[1];
    for(auto z:V)tmp.push_back((node){z.first,z.second});
    if(f[x]==1)return;re int sum=0;
    for(re int i=mx;i<=f[x];++i){
        re int s=C(f[x],i);if(f[x]-i&1)s=M-s;
        for(auto z:tmp)s=1ll*s*ksm(C(i,z.x),z.y)%M;
        add(sum,s);
    }ans=1ll*ans*sum%M;
}
int main(){
    n=read(),m=read(),ans=1;
    for(re int i=fac[0]=inv[0]=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%M,inv[i]=ksm(fac[i],M-2);
    for(re int i=2;i<=n;++i)fa[i]=read();
    for(re int i=1;i<=n;++i)f[i]=read();
    for(re int i=2;i<=n;++i)if(f[fa[i]]==-1)fa[i]=fa[fa[i]];
    for(re int i=2;i<=n;++i)addd(fa[i],i);
    for(re int i=1;i<=n;++i)if(f[i]==-1)f[i]=1;
    dfs(1,1),printf("%d",ans);
}

D

部分分有一些特判。

核心思路:最短路。

容易发现对于每个 $i$ 是独立的,即令 $s_i$ 表示将一个初始仅有 $i$ 为 $1$ 其余为 $0$ 的序列变为全 $0$ 的最小步数,那答案就是 $\sum a_is_i$。

考虑怎么求 $s_i$,实际上对于一个涉及 $i$ 的转移,可以看成用 $L\sim R$ 中所有 $s$ 的和转移到 $s_i$,暴力实现可以做到 $O(nm)$。

考虑模拟 dij 的过程,每次找出最小的 $s_i$,打上确定的标记,每次找到所有操作 $L,R$ 使得 $L,R$ 中所有的 $s_i$ 都被打上了标记,那么这个操作就是可以转移的。动态判定 $L\sim R$ 是否全部打上了标记可以用线段树。

总复杂度 $O((n+m)\log n)$。

#include<bits/stdc++.h>
#define re register
#define ll long long
using namespace std;
char rbuf[20000002];
int pt=-1;
inline int read(){
    re int t=0,f=0;re char v=rbuf[++pt];
    while(v<'0')f|=(v=='-'),v=rbuf[++pt];
    while(v>='0')t=(t<<3)+(t<<1)+v-48,v=rbuf[++pt];
    return f?-t:t;
}
const int M=998244353;
int n,m,a[400002],num[400002],cnt,L[400002],R[400002],X[400002],W[400002],f[400002],sz[1600002],b[400002],head[1600002];
struct edge{int to,next;}e[14400002];
inline void add(re int x,re int y){e[++cnt]=(edge){y,head[x]},head[x]=cnt;}
ll S[1600002],sum[400002],inf=(4e18)+1,ans,inf1=(2e18)+1;
struct node{
    int x;ll dis;
    bool operator <(const node A)const{return dis>A.dis;}
}h[400002];
inline void gmn(re ll&x,re ll y){y<x&&(x=y);}
priority_queue<node>Q;
inline void Ins(re int p,re int l,re int r,re int x,re int y,re int z){
    if(l>=x&&r<=y){
        add(p,z),++num[z];
        return;
    }
    re int mid=l+r>>1;
    if(x<=mid)Ins(p<<1,l,mid,x,y,z);
    if(y>mid)Ins(p<<1|1,mid+1,r,x,y,z);
}
inline void ck(re int x,re ll y){y=min(y,inf1);if(y<h[x].dis)h[x].dis=y,Q.push(h[x]);}
inline void cg(re int p,re int l,re int r,re int x,re ll y){
    ++sz[p],S[p]+=y,S[p]=min(S[p],inf1);
    assert(sz[p]<=r-l+1);
    if(sz[p]==r-l+1){
        for(re int i=head[p];i;i=e[i].next){
            re int z=e[i].to;sum[z]+=S[p];
            if(!(--num[z]))ck(X[z],sum[z]+W[z]);
        }
    }
    if(l==r)return;
    re int mid=l+r>>1;
    if(x<=mid)cg(p<<1,l,mid,x,y);
    else cg(p<<1|1,mid+1,r,x,y);
}
int main(){
    fread(rbuf,1,20000000,stdin),n=read(),m=read();
    for(re int i=1;i<=n;++i)a[i]=read(),h[i]=(node){i,inf};
    for(re int i=1;i<=m;++i){
        X[i]=read(),L[i]=read(),R[i]=read(),W[i]=read();
        Ins(1,1,n,L[i],R[i],i);
    }
    for(re int i=1;i<=n;++i){
        re int x=read();b[i]=x;
        if(x>=0)h[i].dis=x;
    }
    for(re int i=1;i<=n;++i)if(h[i].dis!=inf)Q.push(h[i]);
    while(!Q.empty()){
        re node x=Q.top();Q.pop();
        if(x.dis!=h[x.x].dis)continue;
        cg(1,1,n,x.x,x.dis);
    }
    for(re int i=1;i<=n;++i)if(a[i]&&h[i].dis>=inf1)return puts("-1"),0;
    for(re int i=1;i<=n;++i)ans+=h[i].dis*a[i];
    printf("%lld",ans);
}

InfOJ NOIP2023 模拟赛

2023-11-05 18:20:00 By gyh20

InfOJ NOIP2023 模拟赛 将于 2023/11/11 08:30~13:00 举行!

题目来源:这篇博客 里提到的部分 “之后看情况加 infoj 上。” 的题。

比赛链接:http://119.27.163.117/contest/24/register

题目都是去年出的,均为原创不过在某地方用过,不过如果大家没见过这些题目名应该就没做过!

题目难度大致对标 NOIP,不过由于出题人实力不足 T4 低于 NOIP T4 难度,不过题目质量应该还行,对于大部分选手应该有不错的体验!

有很多部分分,有很多样例,没有 Subtask,尽量保证大家的体验!

有问题可以 infoj 私信联系 gyh20。

欢迎大家来玩!

本次比赛计入 rating,跌涨幅度为正常比赛的 $\frac 13$。若不幸见过题,请向管理员报告。

为防范赛时网络故障等造成的问题,建议加入 infoj 用户群:324364809

InfOJ 愚人节比赛 2021 题解

2021-10-28 17:50:09 By gyh20

A.Administrators

根据题意,观察样例,发现 5 个管理员个人主页中只有 Fee_cle6418 和 weilinxuan 为空的一项为 "格言" 一项,于是输出管理员的格言即可。

B.Birthday

猜测题意为判断一个生日是否为质数。

C.Cleaver

仔细阅读游戏规则,发现游戏中有负分的只有得分一项,进行分析发现即为求得分,公式为 $2\times 斩杀+安全-2\times 被斩杀$,注意 $0 0$ 时要算作被斩杀。

D.Distinct Substrings

就是求长度为 $n$ 的字符串期望子串个数,就是 $\dfrac{n\times(n+1)}{2}$。

E.Example

根据题目名猜测为输出第 $n$ 道题的样例输出。

F.Tourist

判断 Tourist 是否达到过这个 Rating,可以用 F12 复制网页信息。

G.gyh 的脑袋里有整个 OEIS

根据提示,输出 OEIS 第 $i$ 个数列的可显示第 $i$ 项,发现 $i$ 很大时一定是 Impossible,可以手动打表。

H.Hashing vs Encryption

这是一副字符画,猜猜是谁的靓照/xyx

原图:https://www.luogu.com.cn/paste/7v15wokp

输出 $\text{I AK IOI}$ 即可。

I.i058qw0d 是最妙的字符串!!!

发现这是一个洛谷剪切板,再 F12 题面发现 LCS 三个字符,题意即为求给定字符串与 fishingprince 的 LCS。

InfOJ 愚人节比赛欢迎您的参加!

2021-03-28 11:07:23 By gyh20

InfOJ 是一个好 OJ!!!

在愚人节来临之际, InfOJ 创建者 Fee_cle6418 和菜鸡 gyh20 为大家准备了一场愚人节比赛。

比赛预计于 2021-04-01 18:00:00 准时开始,时间 2.5 小时,大家可以在愚人节当天体验这份快乐。

本场比赛共有 $9$ 道题,采用 ACM 赛制,本场比赛计入 Rating,跌涨变化为平时比赛的八分之一

请注意,题目按字典序排序

题目不毒瘤,但需要一些观察与思考,希望大家能玩的开心,玩的愉快!

共 4 篇博客