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;
}

CCPC2019哈尔滨

Contest link

Experience

Problem A. Artful Paintings

Description

Solution

Analysis

Attention

Code

Problem E. Exchanging Gifts

Description

Solution

Analysis

Attention

Code

Problem L. LRU Algorithm

Description

Solution

Analysis

Attention

Code

[LOJ 2737][JOISC 2016] 电报

更新日志[2021.10.3]

Enderturtle