2024.10.26 2024 CCPC哈尔滨站

Solved：6/13

Penalty：635

Rank：72

Rank（ucup）：170

打到后面困了（而且不会 L 心态爆炸）睡觉去了，不然还能多做个 E 题（

被 L 单防了啊。。

CGKM：签到，不放了。

J. New Energy Vehicle

$n$ 种汽油，$m$ 个加油站，每个加油站只能加一种油，每种油都是一单位能走一公里，求最远能走多少公里。$n,m\leq 10^5$。

贪心，优先用下次出现最早的那种油。

set<pair<int,int>> 维护（下次出现位置，编号）即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int N=1e5+5;
int n,m,a[N],c[N],x[N],t[N],fir[N],lst[N],nxt[N];
ll solve(){
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i],c[i]=a[i];
    for(int i=1;i<=m;++i)cin>>x[i]>>t[i];
    for(int i=1;i<=n;++i)fir[i]=m+1,lst[i]=0;
    for(int i=1;i<=m;++i){
        if(fir[t[i]]>m)fir[t[i]]=i;
        if(lst[t[i]])nxt[lst[t[i]]]=i;
        lst[t[i]]=i;
    }
    for(int i=1;i<=n;++i)if(lst[i])nxt[lst[i]]=m+1;
    set<pii> s;
    for(int i=1;i<=n;++i)s.insert(pii(fir[i],i));
    ll sum=0;
    for(int i=1;i<=m;++i){
        int r=x[i]-x[i-1];
        while(!s.empty()&&c[s.begin()->second]<=r){
            int k=s.begin()->second;
            sum+=c[k],r-=c[k],c[k]=0;
            s.erase(s.begin());
        }
        if(s.empty()&&r>0)return sum;
        c[s.begin()->second]-=r,sum+=r;
        c[t[i]]=a[t[i]];
        if(s.find(pii(i,t[i]))!=s.end())s.erase(pii(i,t[i]));
        s.insert(pii(nxt[i],t[i]));
    }
    for(int i=1;i<=n;++i)sum+=c[i];
    return sum;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T;
    cin>>T;
    while(T--)cout<<solve()<<'\n';
}

A. Build a Computer

构造一个有限状态自动机，使其能且只能识别$[L,R]$范围内的所有二进制串（无前导零）。

$1\leq L\leq R\leq 10^6$，不能超过 100 个节点。

直接造 trie 树节点数多达 2e6，肯定不行。

注意到很多子树都是满二叉树，我们可以用一条01重边的链把这些满二叉树全都缩掉，即如果这个节点是满二叉树就直接连到链上。这样可以证明总点数不超过 $5\log n$，正好在 100 的范围内。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int N=105;
int L,R,c[N][2],tot,rt,m;
void dfs(int &x,int L,int R,int l,int r,int k){
    if(l==L&&r==R){
        m=max(m,k),x=-k;
        return;
    }
    x=++tot;
    int mid=(l+r)>>1;
    if(L<=mid)dfs(c[x][0],L,min(R,mid),l,mid,k-1);
    if(R>mid)dfs(c[x][1],max(L,mid+1),R,mid+1,r,k-1);
}

vector<pii> e[N];
void adde(int x,int y,int z){
    e[x].push_back(pii(y,z));
}
bool del[N];
int id[N];
int ID(int x){return x>0?id[x]:-x;}
int main(){
    cin>>L>>R;
    dfs(rt,L,R,0,(1<<__lg(R)+1)-1,__lg(R)+2);
    int cnt=m;
    for(int i=m;i>1;--i)adde(i,i-1,0),adde(i,i-1,1);
    int r=rt;
    while(c[r][0])del[c[r][0]]=1,r=c[r][0];
    for(int i=1;i<=tot;++i)if(!del[i])id[i]=++cnt;
    r=rt;
    while(r)adde(ID(rt),ID(c[r][1]),1),r=c[r][0];
    for(int i=2;i<=tot;++i)if(!del[i]){
        if(c[i][0]&&!del[c[i][0]])adde(id[i],ID(c[i][0]),0);
        if(c[i][1])adde(id[i],ID(c[i][1]),1);
    }
    cout<<cnt<<'\n';
    for(int i=1;i<=cnt;++i){
        cout<<e[i].size()<<' ';
        for(auto [x,y]:e[i])cout<<x<<' '<<y<<' ';
        cout<<'\n';
    }
}