Contest link

link -> gym 102394

Experience

注意卡常

Problem A. Artful Paintings

Description

两类限制

限制1:在$[L_i,R_i]$内部至少有$k$个被染色;

限制2:在$[L_i,R_i]$外部至少有$k$个被染色;

求在满足限制条件下,最少染色多少个。

Solution

Analysis

容易知道可以二分。

考虑用差分约束系统限制。

Attention

注意二分边界

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define il inline
#define inc(i,a,b) for(register int i=a;i<=b;++i)
#define fo(i,a,b) for(register int i=a;i<=b;++i)
#define dec(i,a,b) for(register int i=a;i>=b;--i)
#define fd(i,a,b)  for(register int i=a;i>=b;--i)
#define pb push_back
#define re register
typedef long long ll;
typedef double db;
namespace io{
    #define gc getchar
    il int read(){
        int x=0;bool f=1;char ch=gc();
        if(ch=='-') f=0;
        while(!isdigit(ch)) ch=gc();
        while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=gc();
        return f?x:-x;
    }
}
using io::read;
using namespace std;
/*---- head -----*/
const int N=3010;
int n,m1,m2;
struct node{
    int l,r,k;
} a1[N],a2[N];
struct Edge{
    int u,v,w;
};vector<Edge> e;
int dis[N];

il bool spfa(){
    rep(i,2,n+1) dis[i]=0x3f3f3f3f;
    dis[1]=0;
    rep(i,1,n){
        bool flag=1;
        for(register unsigned j=0;j<e.size();++j){
            int u=e[j].u,v=e[j].v,w=e[j].w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                flag=0;
            }
        }
        if(flag) return true;
    }
    for(register unsigned j=0;j<e.size();++j){
        int u=e[j].u,v=e[j].v,w=e[j].w;
        if(dis[v]>dis[u]+w){
            return false;
        }
    }
    return true;
}

int main(){
    int T=read();
    while(T--){
        n=read();m1=read();m2=read();
        rep(i,1,m1) a1[i].l=read(),a1[i].r=read(),a1[i].k=read();
        rep(i,1,m2) a2[i].l=read(),a2[i].r=read(),a2[i].k=read();
        int L=0,R=n;
        while(L<R){
            int mid=(L+R)>>1;e.clear();
            rep(i,1,n){
                e.pb((Edge){i,i+1,1});
                e.pb((Edge){i+1,i,0});
            }
            rep(i,1,m1){
                e.pb((Edge){a1[i].r+1,a1[i].l,-a1[i].k});
            }
            rep(i,1,m2){
                e.pb((Edge){a2[i].l,a2[i].r+1,mid-a2[i].k});
            }
            e.pb((Edge){1,n+1,mid});
            e.pb((Edge){n+1,1,-mid});
            if(spfa()) R=mid;
            else L=mid+1;
        }
        printf("%d\n",L);
    }
    return 0;
}

Problem E. Exchanging Gifts

Description

两种操作:

操作1:给出一个序列。该序列编号为$i$。

操作2:生成一个序列编号为$i$的序列,这个序列通过之前特定的两个序列相加获得;

定义相加操作为集合合并,允许重复元素

保证最后一步操作一定为操作2;

求最后操作获得的序列的快乐值

定义快乐值为这个序列经过任意一种重新排序后,每个位置与原来位置上值不一样的个数的最大值

Solution

Analysis

首先可以通过拓扑排序,统计出最后一个序列是由之前哪些序列贡献多少值获得。

考虑影响快乐值的关键条件。

即:最后序列中出现最多的元素个数。

如果个数小于最后序列的长度,那么答案为序列长度;

否则根据鸽巢原理,最后答案为(序列长度-出现最多元素个数)*2;

Attention

卡输入

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define il inline
#define inc(i,a,b) for(register int i=a;i<=b;++i)
#define fo(i,a,b) for(register int i=a;i<=b;++i)
#define dec(i,a,b) for(register int i=a;i>=b;--i)
#define fd(i,a,b)  for(register int i=a;i>=b;--i)
#define pb push_back
#define re register
typedef long long ll;
typedef double db;
namespace io{
    这是快读;
}
using io::read;
using namespace std;
/*---- head -----*/
const int N=1000100;
int n;
vector<int> e[N];ll res[N];
int op[N][3];
il void init(){
    rep(i,1,n){ e[i].clear();res[i]=0;}
}
il void topsort(){
    res[n]=1;
    for(register int i=n;i>=1;--i){
        if(op[i][0]==1) continue;
        res[op[i][1]]+=res[i];
        res[op[i][2]]+=res[i];
    }
}

il void solve(){
    int now=0;ll sum=0,ans=0;
    rep(i,1,n){
        if(op[i][0]==2 || res[i]==0) continue;
        for(register unsigned j=0;j<e[i].size();++j){
            int v=e[i][j];
            if(now==0){ now=v;sum+=res[i];}
            else if(now==v) sum+=res[i];
            else{
                sum-=res[i];
                if(sum<0) now=v,sum=-sum;
            }
            ans+=res[i];
        }
    }
    sum=0;
    rep(i,1,n){
        if(op[i][0]==2 || res[i]==0) continue;
        for(register unsigned j=0;j<e[i].size();++j){
            int v=e[i][j];
            if(v==now) sum+=res[i];
        }
    }
    if(sum*2ll<ans) printf("%lld\n",ans);
    else printf("%lld\n",(ans-sum)*2ll);
}
int main(){
    int T=read();
    while(T--){
        n=read();
        init();
        rep(i,1,n){
            op[i][0]=read();
            if(op[i][0]==1){
                int sz=read();
                while(sz--){
                    int x=read();
                    e[i].pb(x);
                }
            }else op[i][1]=read(),op[i][2]=read();
        }
        topsort();
        solve();
    }
    return 0;
}

Problem L. LRU Algorithm

Description

给定一个操作序列,进入LRU系统。

LRU系统解释:

如果进入的值LRU内部有,将这个提到LRU顶。

如果没有,此时如果LRU超出内存上限,删除底值。新的值将会放置LRU顶。

给出$q$组询问,在内存上限为$m_i$时,是否LRU系统会出现给定的一个LRU序列。

Solution

Analysis

性质:

如果我们将内存上限设置无限大,并进行操作,那么在内存限制为$m$的时候,LRU序列即为无限大的情况的前$m$项。

可以将这个进行hash,再进行判断

对这个题可以通过再次校准来增加准确性。

Attention

卡读入

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define il inline
#define inc(i,a,b) for(register int i=a;i<=b;++i)
#define fo(i,a,b) for(register int i=a;i<=b;++i)
#define dec(i,a,b) for(register int i=a;i>=b;--i)
#define fd(i,a,b)  for(register int i=a;i>=b;--i)
#define pb push_back
#define re register
typedef long long ll;
typedef double db;
namespace io{
    这是快读;
}
using io::read;
using namespace std;
/*---- head -----*/
const int N=5010;
ll has[N][N],base=这是base,mod=这是mod;
int n,q,o[N][N],a[N],top;

int main (){
    int T = read();
    while (T--)
    {
        n = read(); q = read();
        fo(i,1,n) a[i] = read();
        rep(i,0,n) rep(j,0,n) o[i][j]=has[i][j]=0;
        top=0;
        rep(i,1,n){
            int now=0;
            rep(j,1,top){
                if(o[i-1][j]==a[i]){
                    now=j;
                    break;
                }
            }
            if(now==0){
                rep(j,1,top) o[i][j+1]=o[i-1][j];
                o[i][1]=a[i];
                top++;
            }else{
                rep(j,1,now-1) o[i][j+1]=o[i-1][j];
                rep(j,now+1,top) o[i][j]=o[i-1][j];
                o[i][1]=a[i];
            }
            rep(j,1,n) has[i][j]=(has[i][j-1]*base+o[i][j])%mod;
        }
        while(q--){
            int m=read();ll res=0;
            rep(i,1,m){a[i]=read();res=(res*base+a[i])%mod;}
            bool f=0;
            rep(i,0,n){
                if(res==has[i][m]){
                    bool fl=1;
                    rep(j,1,m){
                        if(o[i][j]!=a[j]){ fl=0;break;}
                    }
                    if(fl){puts("Yes");f=1;break;}
                }
            }
            if(!f) puts("No");
        }
    }
    return 0;
}

一个好奇的人