A

可知 $lcm(x,y)=\frac{x*y}{\gcd(x,y)}$ ,直接令 $lcm(x,y)=y$ 即可,判断 $2l\le r$ 即可。

B

观察 $z$ 很小,考虑 $\Theta(nz)$ 的 DP,

有 $f_{i,j}$ 表示已经移动了 $i$ 步,其中有 $j$ 步是向左的最大贡献。

直接上代码

const int N=3e5+5;
int f[N][6],a[N],n,k,z;
bool pd(int x){return x>=1&&x<=n;}
int pos(int i,int j){return i+1-2*j;}
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&k,&z);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            for(int j=0;j<=z;j++)f[i][j]=0;
        }
        f[0][0]=a[1];
        for(int i=1;i<=k;i++)
            for(int j=0;j<=z;j++)
                if(pd(i+1-2*j))
                {
                    if(i>=2&&j>=1)
                        f[i][j]=f[i-2][j-1]+a[pos(i-2,j-1)-1]+a[pos(i-2,j-1)];
                    f[i][j]=max(f[i][j],f[i-1][j]+a[pos(i,j)]);
                }
        int ans=0;
        for(int i=0;i<=z;i++)
            ans=max(ans,f[k][i]);
        for(int i=0;i<z;i++)
            ans=max(ans,f[k-1][i]+a[pos(k-1,i)-1]);
        printf("%d\n",ans);
    }
    return 0;
}

C

不难发现最优方案如果是偶数的话,是两种数字交错放置;

如果是奇数的话,是一种数字连续出现。

枚举第一个数字,第二个数字,暴力判断即可。

D

贪心来讲,我们要使贡献尽可能提前。

因此不妨把两个区间排一下序。

于是有两种情况:

当 $r_1\ge l_2$ ,一切都很简单。。

否则,先尝试填满一对区间,看看是否已经完成。

然后有 $w=l_2-r_1$ ,这时候有一个问题,我们是继续填另一对,还是拓展当前这一对。

讨论一下可以得知,$less\le w$ ,第一种方案需要 $w+less$ ,而第二种方案需要 $less*2$ ,明显第二种更优。

因此做完了。

E

这种题有模数,直接大力式子就可以了。

$\begin{aligned}(x-1)*d+y\equiv (y-1)*d+x(\text{mod } w)\\x*(d-1)\equiv y*(d-1)(\text{mod } w)\end{aligned}$

显然存在循环节 $\frac{lcm(d-1,w)}{d-1}$,然后再找一些等差数列性质就做完了,注意 $x,y\in[1,\min\{m,d\}]$

ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        ll m,d,w;scanf("%lld%lld%lld",&m,&d,&w);
        if(d==1){puts("0");continue;}
        ll lcm=w/gcd(d-1,w);
        ll T=min(m,d),div=T/lcm,less=T-div*lcm;
        ll ans=less*(div+1)*(div)/2+(lcm-less)*(div)*(div-1)/2;
        printf("%lld\n",ans);
    }
    return 0;
}

F

两种方法:

观察法:

答案序列一定是形如 $1111222212111$ 的序列。

但是我们并不关心这个序列的具体构造,我们只需要记录最后一个 $1$ 或 $2$ 出现的位置即可。

然后我们考虑贪心构造这样一个序列。

给区间分类后,按右端点排序,然后按右端点顺序插入序列。

对于当前区间 $[l_i,r_i]$ ,分类为 $u$ ,从另外一个分类 $v$ 中找出第一个不包含 $l_i$ 的区间 $j$ ,然后在 $v$ 线段树上打上一个 $[0,j]$ 的区间 $+1$ 标记,表示我们可以在这些位置上多放上一个 $u$ 区间,但是显然这样不包含未来插入一个 $v$ 区间,它的最优贡献,因此还要在 $u$ 线段树 $i$ 这个位置更新一下它的最优贡献 $cur$ 。

不难发现这样统计一定包含最优方案。

const int N=2e5+5,inf=0xcfcfcfcf;
struct vec
{
    int x,y;
    vec(int x=0,int y=0):x(x),y(y){}
    bool operator <(const vec &a)const{return x==a.x?y<a.y:x<a.x;}    
}a[2][N];
bool cmp(const vec &a,const vec &b){return a.x==b.x?a.y>b.y:a.x<b.x;}
struct segtree
{
    int n;struct node{int d,lz;}t[N<<2];
    void build(int p,int l,int r)
    {
        if(l==r){t[p].d=t[p].lz=0;return ;}
        int mid=l+r>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    }
    void pushdown(int p)
    {
        if(t[p].lz)
            t[p<<1].lz+=t[p].lz,t[p<<1|1].lz+=t[p].lz,
            t[p<<1].d+=t[p].lz,t[p<<1|1].d+=t[p].lz,t[p].lz=0;
    }
    void upd(int p,int l,int r,int pos,int val)
    {
        if(l==r){t[p].d=val;return ;}
        pushdown(p);int mid=l+r>>1;
        if(pos<=mid)upd(p<<1,l,mid,pos,val);
        else upd(p<<1|1,mid+1,r,pos,val);
        t[p].d=max(t[p<<1].d,t[p<<1|1].d);
    }
    void add(int p,int l,int r,int L,int R,int lz)
    {
        if(L<=l&&R>=r){t[p].d+=lz;t[p].lz+=lz;return ;}
        pushdown(p);int mid=l+r>>1;
        if(L<=mid)add(p<<1,l,mid,L,R,lz);
        if(R>mid)add(p<<1|1,mid+1,r,L,R,lz);
        t[p].d=max(t[p<<1].d,t[p<<1|1].d);
    }
    int get(int p,int l,int r,int L,int R)
    {
        if(L<=l&&R>=r)return t[p].d; 
        pushdown(p);int mid=l+r>>1,val=0;
        if(L<=mid)val=get(p<<1,l,mid,L,R);
        if(R>mid)val=max(val,get(p<<1|1,mid+1,r,L,R));
        return val;
    }
    void upd(int pos,int val){upd(1,0,n,pos,val);}
    void add(int pos,int val){add(1,0,n,0,pos,val);}
    int get(int pos){return get(1,0,n,0,pos);}
}t[2];int s[2];
int main()
{
    int n;scanf("%d",&n);
    for(int i=1,l,r,t;i<=n;i++)
    {
        scanf("%d%d%d",&l,&r,&t);--t;
        a[t][++s[t]]=vec(r,l);
    }
    for(int i=0;i<2;i++)sort(a[i]+1,a[i]+s[i]+1,cmp),t[i].n=s[i],t[i].build(1,0,s[i]);
    int ans=0;
    for(int i=1,j=1;i+j<=n+1;)
    {
        if(i<=s[0]&&(j==s[1]+1||a[0][i].x<=a[1][j].x))
        {
            int pos=upper_bound(a[1]+1,a[1]+s[1]+1,vec(a[0][i].y,inf))-a[1];
            int cur=t[1].get(pos-1)+1;
            ans=max(ans,cur);
            t[0].upd(i,cur);
            t[1].add(pos-1,1);
            ++i;
        }    
        else
        {
            int pos=upper_bound(a[0]+1,a[0]+s[0]+1,vec(a[1][j].y,inf))-a[0];
            int cur=t[0].get(pos-1)+1;
            ans=max(ans,cur);
            t[1].upd(j,cur);
            t[0].add(pos-1,1);
            ++j;
        }
    }
    printf("%d\n",ans);
    return 0;
}

结论法:

如果给无法兼并的区间对 $(i,j)$ 连上一条边,不难发现这是一个二分图,题目就转化为求这个二分图的最大独立集,即最大匹配数。

但是如果真的建图,复杂度是受不了的。

但是对于这道题,有特殊的构造方法可以构造出最大匹配。

即维护两个 $set$ ,排序之后扫描线维护。

不难发现如果我们遇到 $r_i$ 表示区间终止端点,如果当前另一集合存在点,则说明区间有交。

基于贪心地思想,我们选择删除另一集合最早结束的那个区间,使得剩下的区间有更多的机会得到贡献。

因此可以贪心求得最大匹配。

const int N=2e5+5;
struct node
{
    int x,y;
    node(int x=0,int y=0):x(x),y(y){}
    bool operator <(const node &a)const{return x==a.x?y<a.y:x<a.x;}    
};
struct vec
{
    int x;node y;
    vec(int x=0,node y=node(0,0)):x(x),y(y){}
    bool operator <(const vec &a)const{return x==a.x?y<a.y:x<a.x;}
};
vector<vec>e;
set<node>s[2];
int l[N],r[N],t[N];
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&l[i],&r[i],&t[i]),--t[i];
    for(int i=1;i<=n;i++)
        e.push_back(vec(l[i],node(0,i))),
        e.push_back(vec(r[i],node(1,i)));
    sort(e.begin(),e.end());int ans=0;
    for(auto it:e)
    {
        int op=it.y.x,i=it.y.y;
        if(op)
        {
            int j=t[i],k=j^1,c=s[j].count(node(r[i],i));
            if(c&&!s[k].empty())++ans,s[k].erase(s[k].begin());
            if(c)s[j].erase(node(r[i],i));
        }
        else s[t[i]].insert(node(r[i],i));
    }    
    printf("%d\n",n-ans);
    return 0;
}

G

显然图中的 $e-dcc$ 边可以有向,只需要考虑桥边如何贡献。

每一个节点表示一个 $e-dcc$ ,边表示桥边。

设计一个状态表示 $dp_x$ ,表示子树 $x$ 内的最大贡献,且 $x$ 必须产生贡献(不考虑外界关键点的干扰

考虑一个子节点 $y$ ,$(x,y)$ 之间的连边的方向如何。

如果关键点都在 $y$ 里,那么连边一定是朝 $x$ 的,如果都不在,那么连边一定是朝 $y$ 的,因为没有必要无向。

否则其他情况,考虑一下 $dp_y-w_i$ 的大小,决定是否无向,还是指向 $x$。

但是这样需要枚举根,于是来做一个换根 $dp$ 。

当即将进入 $y$ 时,把 $(x,y)$ 的连边砍掉,换上 $(y,x)$ ,即可。

const int N=3e5+5;
struct node{int x,y;node(int x=0,int y=0):x(x),y(y){}};
int dfn[N],low[N],tmp;bool bri[N<<1];
vector<node>e[N];
void tarjan(int x,int in_edge)
{
    dfn[x]=low[x]=++tmp;
    for(auto it:e[x])
        if(it.y!=in_edge)
        {
            int y=it.x;
            if(!dfn[y])
            {
                tarjan(y,it.y);
                low[x]=min(low[x],low[y]);
                if(low[y]>dfn[x])bri[it.y]=1;
            }
            else low[x]=min(low[x],dfn[y]);
        }
}
int bel[N],cnt[N],c[N],w[N],v[N],k;ll f[N],d[N];
void rebuild(int x,int scc)
{
    if(bel[x])return;
    bel[x]=scc;cnt[scc]+=v[x];d[scc]+=c[x];
    for(auto it:e[x])if(!bri[it.y])
        rebuild(it.x,scc);
}
vector<node>g[N];
void upd(int x,int y,int op,int weight)
{
    ll now=f[y];
    if(0<cnt[y]&&cnt[y]<k)now=max(0ll,now-weight);
    cnt[x]+=op*cnt[y];
    f[x]+=op*now;
}
void add(int x,int y,int weight)
{
    upd(x,y,1,weight);
}
void cut(int x,int y,int weight)
{
    upd(x,y,-1,weight);
}
void dfs1(int x,int fa)
{
    f[x]=d[x];
    for(auto it:g[x])
    {
        int y=it.x;if(y==fa)continue;
        dfs1(y,x);add(x,y,w[it.y]);
    }
}
ll ans[N];
void dfs2(int x,int fa)
{
    ans[x]=f[x];
    for(auto it:g[x])
    {
        int y=it.x,i=it.y;if(y==fa)continue;
        cut(x,y,w[i]);add(y,x,w[i]);
        dfs2(y,x);
        cut(y,x,w[i]),add(x,y,w[i]);
    }
}
int u1[N],u2[N];
int main()
{
    int n,m;scanf("%d%d%d",&n,&m,&k);
    for(int i=1,x;i<=k;i++)scanf("%d",&x),v[x]=1;
    for(int i=1;i<=n;i++)scanf("%d",&c[i]);
    for(int i=1;i<=m;i++)scanf("%d",&w[i]);
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);u1[i]=x,u2[i]=y;
        e[x].push_back(node(y,i));
        e[y].push_back(node(x,i));
    }
    tarjan(1,0);int scc=0;
    for(int i=1;i<=n;i++)if(!bel[i])rebuild(i,++scc);
    for(int i=1;i<=m;i++)if(bri[i])
    {
        g[bel[u1[i]]].push_back(node(bel[u2[i]],i));
        g[bel[u2[i]]].push_back(node(bel[u1[i]],i));
    }
    dfs1(1,0);dfs2(1,0);
    for(int i=1;i<=n;i++)printf("%lld ",ans[bel[i]]);
    return 0;
}