2026海南大学校赛简要题解

L1-1 Welcome to campus competition！

按题目输出即可。

代码：

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <array>
#include <unordered_map>
#include <numeric>
#include <functional>
#include <ranges>
#include <iomanip>
#include <chrono>
#include <random>
//#define int long long //赫赫 要不要龙龙呢
using ll=long long;
using namespace std;

signed main()
{
    auto T_start=chrono::steady_clock::now();
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cout<<"HAPPY COMPETITION!\n";
    return 0;
}

L1-2 坏蛋小方的毙题计划

做简单判断即可。

代码：

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <array>
#include <unordered_map>
//#define int long long //赫赫 要不要龙龙呢
using ll=long long;
using namespace std;

signed main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int l,r,k;cin>>l>>r>>k;
    if(k<l) cout<<"ben dan\n";
    else if(k>r) cout<<"bi diao\n";
    else cout<<"wan mei\n";
    return 0;
}

L1-3 不要再打舞萌了！

做简单模拟即可。

代码：

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <array>
#include <unordered_map>
//#define int long long //赫赫 要不要龙龙呢
using namespace std;

signed main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n; cin>>n;
    string s;cin>>s;
    int flag=0;
    for(int i=1;i<s.size();i++){
        if(s[i-1]>='0'&&s[i-1]<='9'&&s[i]>='0'&&s[i]<='9'){
            flag=1;
            break;
        }
    }
    if(flag) cout<<"lose\n";
    else cout<<"win\n";
    return 0;
}

L1-4 字符串

做简单模拟即可。

代码：

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <array>
#include <unordered_map>
#include <numeric>
#include <functional>
#include <ranges>
#include <iomanip>
#include <chrono>
#include <random>
//#define int long long //赫赫 要不要龙龙呢
using ll=long long;
using namespace std;

signed main()
{
    auto T_start=chrono::steady_clock::now();
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    string s;cin>>s;
    int n=s.size();
    if(n<=2) {
        cout<<"0.00"<<endl;
    }
    else{
        int ans=0;
        for(int i=0;i<n-2;i++){
            if(s.substr(i,3)=="HNU"){
                ans++;
            }
        }
        cout<<fixed<<setprecision(2)<<(double)ans/(n-2)<<endl;
    }
    return 0;
}

L1-5 围栏计划

找出围栏边界的左上点和右下点，按要求模拟即可。

代码：

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <array>
#include <unordered_map>
//#define int long long //赫赫 要不要龙龙呢
using namespace std;

signed main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,m;cin>>n>>m;
    vector<vector<int>> a(n+1,vector<int>(m+1));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    int mnx=1e9,mny=1e9,mxx=0,mxy=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]==1){
                mnx=min(mnx,i);
                mny=min(mny,j);
                mxx=max(mxx,i);
                mxy=max(mxy,j);
            }
    for(int i=mnx+1;i<mxx;i++)
        for(int j=mny+1;j<mxy;j++)
            a[i][j]=2;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
    return 0;
}

L1-6 小鱼学数论

枚举， $O(\sqrt{n})$ 朴素判断质数即可。当然你闲的发慌写个筛法我也不反对。

朴素做法复杂度： $O(n\sqrt{n})$ 筛法复杂度： $O(n)$

代码：

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <array>
#include <unordered_map>
//#define int long long //赫赫 要不要龙龙呢
using namespace std;

signed main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int l,r,p;cin>>l>>r>>p;
    int ans=0;
    auto chk=[&](int x){
        for(int i=2;i<=sqrt(x);i++){
            if(x%i==0) return 0;
        }
        return 1;
    };
    for(int i=l;i<=r;i++){
        if(i%6==p&&chk(i)){
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

L1-7 小飞飞刀

前缀和一下，贪心的选择每个不合法区间的最左端点，把他变成一个极小值即可。我这边的写法是通用的区间最小点覆盖。原问题是给你多个区间，让你找最小的点数去覆盖这些区间。按区间右端点排序，然后维护最右端点就行了。记得开long long。

代码复杂度 $O(n\log n)$

出题人比较良心的给了 $O(n^2)$ 的60pt部分分。

代码：

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <array>
#include <unordered_map>
//#define int long long //赫赫 要不要龙龙呢
using ll=long long;
using namespace std;

signed main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,k,x;cin>>n>>k>>x;
    vector<int> a(n+1);
    vector<ll> pre(n+1,0);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];
    vector<array<int,2>> lr;
    for(int i=1;i+k-1<=n;i++){
        if(pre[i+k-1]-pre[i-1]>=x){
            lr.push_back({i,i+k-1});
        }
    }
    int nr=-1e9,ans=0;
    sort(lr.begin(),lr.end(),[](array<int,2> a,array<int,2> b){
        return a[1]<b[1];
    });
    for(auto [l,r]:lr){
        if(l>nr){
            nr=r;
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

L1-8 编辑蛋糕塔

注意到给出的蛋糕字符串长度最多20，并且互相不为前缀，于是我们可以暴力匹配。然后用map统计一下每个蛋糕出现的次数，在map上修改即可。要注意字符串不存在和修改后字符串一致的情况。当然匹配过程你用tire或者acam也是可以的，但是我会觉得你是神人。

复杂度 $O(20m + q \cdot len \cdot \log(cnt))$ ， $len$ 是字符串均长， $cnt$ 是本质不同字符串个数。出题人比较良心的给了60pt暴力分（虽然这题暴力很不好写）。

代码：

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <array>
#include <unordered_map>
//#define int long long //赫赫 要不要龙龙呢
using namespace std;

signed main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,m,q;cin>>n>>m>>q;
    set<string> st;
    for(int i=1;i<=n;i++){
        string str;cin>>str;
        st.insert(str);
    }
    string s;cin>>s;s="#"+s;
    map<string,int> cnt;
    for(int i=1;i<=m;){
        for(int len=1;len<=20&&i+len-1<=m;len++){
            string str=s.substr(i,len);
            if(st.count(str)){
                cnt[str]++;
                i+=len;
                break;
            }
        }
    }
    while(q--){
        int op;cin>>op;
        string tar;cin>>tar;
        string ntar=tar;
        if(op==1){
            int le;string s;
            cin>>le>>s;
            if(!cnt.count(tar)||cnt[tar]==0) continue;
            ntar.insert(le-1,s);
            if(ntar!=tar) {
                cnt[ntar]+=cnt[tar];
                cnt.erase(tar);
            }
        }
        else if(op==2){
            int l,r;cin>>l>>r;
            if(!cnt.count(tar)||cnt[tar]==0) continue;
            ntar.erase(l-1,r-l+1);
            if(ntar!=tar) {
                cnt[ntar]+=cnt[tar];
                cnt.erase(tar);
            }
        }
        else{
            string tp;cin>>tp;
            if(!cnt.count(tar)||cnt[tar]==0) continue;
            if(tp!=tar){
                cnt[tp]+=cnt[tar];
                cnt.erase(tar);
            }
        }
    }
    int mx=-1;
    string fin;
    for(auto [str,num]:cnt){
        if(num>mx){
            mx=num;
            fin=str;
        }
        else if(num==mx){
            fin=min(fin,str);
        }
    }
    cout<<mx<<'\n'<<fin<<'\n';
    return 0;
}

L2-1 小方拼火车

双向链表典题。注意到操作3，4操作的车厢数<=1e6,于是我们暴力做，复杂度是均摊的。

复杂度 $O(q + len)$ ， $len$ 是操作3、4涉及的车厢总数。

40pt暴力分。

代码：

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <array>
#include <unordered_map>
//#define int long long //赫赫 要不要龙龙呢
using namespace std;

signed main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,q;cin>>n>>q;
    vector<int> l(n+1,0),r(n+1,0);
    while(q--){
        int op;cin>>op;
        if(op==1){
            int x,y;cin>>x>>y;
            r[x]=y;
            l[y]=x;
        }
        else if(op==2){
            int x,y;cin>>x>>y;
            r[x]=0,l[y]=0;
        }
        else if(op==3){
            int x;cin>>x;
            int hd=x;
            while(l[hd]) hd=l[hd];
            vector<int> tp;
            while(hd){
                tp.push_back(hd);
                hd=r[hd];
            }
            cout<<tp.size()<<endl;
            for(int i=0;i<tp.size();i++){
                cout<<tp[i]<<" ";
            }
            cout<<endl;
        }
        else{
            int x;cin>>x;
            int hd=x;
            while(l[hd]) hd=l[hd];
            vector<int> tp;
            while(hd){
                tp.push_back(hd);
                hd=r[hd];
            }
            for(auto x:tp){
                swap(l[x],r[x]);
            }
        }
    }
    return 0;
}

L2-2 好多猫猫！

简单跑个dfs就行了。猫猫可爱。

完全没道理的部分分，不知道出出来干嘛，可能是有什么神人算法吧。

复杂度 $O(n)$

代码：

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <array>
#include <unordered_map>
//#define int long long //赫赫 要不要龙龙呢
using namespace std;

signed main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,k;cin>>n>>k;
    vector<int> maomao(n+1,0);
    vector<vector<int>> tr(n+1);
    for(int i=1;i<=n;i++) cin>>maomao[i];
    for(int i=1;i<n;i++) {
        int x,y;cin>>x>>y;
        tr[x].push_back(y);
        tr[y].push_back(x);
    }
    int ans=0;
    auto dfs=[&](auto&& dfs,int u,int fa,int cnt){
        if(maomao[u]) cnt++;
        else cnt=0;
        if(cnt>k) return ;
        int flag=1;
        for(auto v:tr[u]) {
            if(v==fa) continue;
            flag=0;
            dfs(dfs,v,u,cnt);
        }
        if(flag) ans++;
    };
    dfs(dfs,1,0,0);
    cout<<ans<<endl;
    return 0;
}

L2-3 不要再打女神异闻录了！

同样简单跑个dfs就行，记忆化搜索也是对的。

dfs复杂度 $O(4^{n+m})$ 记忆化搜索 $O(n \cdot m \cdot (n+m) \cdot \Sigma(a_i))$ ，实际状态很稀疏下面的代码是记忆化搜索。

代码：

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <array>
#include <unordered_map>
//#define int long long //赫赫 要不要龙龙呢
using namespace std;
bool vis[7][7][15][50000];
signed main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,m;cin>>n>>m;
    vector<vector<int>> val(n+1,vector<int>(m+1));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>val[i][j];
    int ans=0;
    auto dfs=[&](auto&& dfs,int x,int y,int cnt,int sum){
        if(vis[x][y][cnt][sum]) return ;
        vis[x][y][cnt][sum]=true;
        if(cnt==0||val[x][y]>=sum/cnt){
            if(x==n&&y==m){
                ans=max(ans,sum+val[x][y]);
                return ;
            }
            else{
                if(x+1<=n) dfs(dfs,x+1,y,cnt+1,sum+val[x][y]);
                if(y+1<=m) dfs(dfs,x,y+1,cnt+1,sum+val[x][y]);
            }
        }
        if(x==n&&y==m){
            ans=max(ans,sum);
            return ;
        }
        else{
            if(x+1<=n) dfs(dfs,x+1,y,cnt,sum);
            if(y+1<=m) dfs(dfs,x,y+1,cnt,sum);
        }
    };
    dfs(dfs,1,1,0,0);
    cout<<ans<<endl;
    return 0;
}

L2-4 服务器通信

把一个极大联通块里面的服务器种类看成一个颜色，这个过程可以用dsu维护，bfs也行。问题转化为，对一个序列，有num次交换机会，要求最大化最长颜色连续段。这个事情是可以双指针做的，把每个颜色的下标存起来，对每个颜色的下标数组双指针扫描即可。好像二分做也是可以的？

时间复杂度： $O(m \cdot \alpha(n) + k)$

良心出题人暴力给了60pt

代码：

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <array>
#include <unordered_map>
//#define int long long //赫赫 要不要龙龙呢
using namespace std;
class DSU{
    public:
        int n;vector<int> fa,sz;
        DSU(int n):n(n)
        {
            srand(time(NULL));
            fa.resize(n+1);
            sz.resize(n+1);
            for(int i=1;i<=n;i++)
            {
                fa[i]=i;
                sz[i]=1;
            }
        }
        int find(int u){
            return fa[u]==u?u:fa[u]=find(fa[u]);
        }
        void merge(int a,int b)
        {
            int u=find(a),v=find(b);
            if(u==v) return;
            fa[u]=v;
            sz[v]+=sz[u];
        }
        int same(int a,int b)
        {
            return find(a)==find(b);
        }
        int size(int u){
            return sz[find(u)];
        }
        vector<vector<int>> get(){
            vector<vector<int>> ans(n+1);
            for(int i=1;i<=n;i++)
            {
                ans[find(i)].push_back(i);
            }
            ans.erase(remove(ans.begin(),ans.end(),vector<int>()),ans.end());
            return ans;
        }
};
signed main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,m,k,num;cin>>n>>m>>k>>num;
    DSU dsu(n);
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b;
        dsu.merge(a,b);
    }
    vector<vector<int>> idx(n+1);
    for(int i=1;i<=k;i++){
        int a;cin>>a;
        idx[dsu.find(a)].push_back(i);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        int tot=idx[i].size();
        auto& p=idx[i];
        int l=0;
        for(int r=0;r<tot;r++){
            while((p[r]-p[l]-1)-(r-l-1)>num){
                l++;
            }
            ans=max(ans,min(tot,r-l+1+num));
        }
    }
    cout<<ans<<'\n';
    return 0;
}

L3-1 不要再打艾尔登法环了

考虑反着贪心。二分分隔点也是正确的。

来着出题人的解释：正攻可以发现：我们需要尽量把扣信心的操作放在后面。因为，对于一个可能的取法，使得打一个难的boss导致后面有一个boss打不了，那么不打这个boss而打后面那个boss也是可行的。因此二分一个pos，pos之前都只打不扣信心的，pos后全都打，看看信心够不够。然后二分出最小的合法pos，遍历一遍出答案。

时间复杂度：二分 $O(n\log n)$ 反着贪心 $O(n)$

下面的代码是反着贪心。

出题人给了二进制枚举20pt，第二档是神人分，不知道出出来干嘛的。

代码：

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <array>
#include <unordered_map>
//#define int long long //赫赫 要不要龙龙呢
using namespace std;

signed main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;cin>>t;
    while(t--){
        int n,q;cin>>n>>q;
        vector<int> a(n+1);
        for(int i=1;i<=n;i++) cin>>a[i];
        vector<int> ans(n+1,0);
        int cur=0;
        for(int i=n;i>=1;i--){
            if(a[i]>cur){
                if(cur<q){
                    ans[i]=1;
                    cur++;
                }
            }
            else ans[i]=1;
        }
        for(int i=1;i<=n;i++) cout<<ans[i];
        cout<<endl;
    }
    return 0;
}

L3-2 小鱼的木棍猜想

小鱼睡觉的时候想到的题。考虑任意一对直线被选择的概率，这个是恒定的，是是 $k*(k-1)/n*(n-1)$ 。于是我们只用考虑每对直线是否产生相交，如果相交，那么对答案的贡献是1，否则是0。发现此时我们只要算所有交点的个数就行了，这个考虑正难则反，先假设所有的直线两两相交，然后减去所有平行直线组对交点减少的贡献即可。判断平行的一个比较好的方法是向量规范化，放到map里统计即可。

时间复杂度： $O(nlogn)$

出题人给了30pt的特殊性质分，30(包括特殊性质)+10pt的暴力分。

代码：

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <array>
#include <unordered_map>
#include <numeric>
#include <functional>
#include <ranges>
#include <iomanip>
#include <chrono>
//#define int long long //赫赫 要不要龙龙呢
using ld=long double;
using namespace std;
using ll=long long;
const int mod=1e9+7;
template <int MOD>
struct SMC {
    int val;
    SMC(ll v=0) : val(v%MOD) { if (val<0) val+=MOD; }
    SMC& operator+=(const SMC &r) { val+=r.val; if (val>=MOD) val-=MOD; return *this; }
    SMC& operator-=(const SMC &r) { val-=r.val; if (val<0) val+=MOD; return *this; }
    SMC& operator*=(const SMC &r) { val=1LL*val*r.val%MOD; return *this; }
    SMC& operator/=(const SMC &r) { return *this*=r.inv(); }
    friend SMC operator+(SMC a,const SMC &b) { return a+=b; }
    friend SMC operator-(SMC a,const SMC &b) { return a-=b; }
    friend SMC operator*(SMC a,const SMC &b) { return a*=b; }
    friend SMC operator/(SMC a,const SMC &b) { return a/=b; }
    SMC pow(ll k) const {
        SMC res=1,a=*this;
        for (;k;k>>=1,a*=a) if(k&1) res*=a;
        return res;
    }
    SMC inv() const { return pow(MOD-2); }
    friend istream& operator>>(istream &in,SMC &a) { ll v; in>>v; a=v; return in; }
    friend ostream& operator<<(ostream &out,const SMC &a) { return out<<a.val; }
};
using Z=SMC<mod>;
signed main()
{
    auto T_start=chrono::steady_clock::now();
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,k;cin>>n>>k;
    map<array<int,2>,int> mp;
    auto norm=[&](int x1,int y1,int x2,int y2)->array<int,2>{
        int dx=x2-x1,dy=y2-y1;
        int g=gcd(abs(dx),abs(dy));
        dx/=g,dy/=g;
        if(dx<0||(dx==0&&dy<0)) dx=-dx,dy=-dy;
        return {dx,dy};
    };
    for(int i=1;i<=n;i++){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        mp[norm(x1,y1,x2,y2)]++;
    }
    Z ans=Z(n)*(n-1)/2;
    for(auto &[_,c]:mp) ans-=Z(c)*(c-1)/2;
    Z p=Z(k)*(k-1)/(Z(n)*(n-1));
    cout<<ans*p<<endl;
    return 0;
}

L3-3 管道调温 (Easy version)

读题，可以注意到操作1的热量是从管道头来的，而操作2只能操作管道头。提示我们只需要维护管道头的dp值即可。转移的时候暴力转移，用二分找最近的管道头转移即可，或者注意到这个转移指针是单调的，也可以用双指针维护。

时间复杂度：二分 $O(k \cdot \Sigma(cnt) \cdot \log m)$ 双指针 $O(k \cdot \Sigma(cnt))$

下面的代码是双指针。

出题人给了50分的暴力分。第一档分依旧是不知所谓的神人分。

代码：

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <array>
#include <unordered_map>
#include <numeric>
#include <functional>
#include <ranges>
#include <iomanip>
#include <chrono>
#include <random>
//#define int long long //赫赫 要不要龙龙呢
using ll=long long;
using namespace std;

signed main()
{
    auto T_start=chrono::steady_clock::now();
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;cin>>t;
    while(t--){
        int n,m,k,q;cin>>n>>m>>k>>q;
        vector<int> f(m+1);
        for(int i=1;i<=m;i++){
            cin>>f[i];
        }
        vector<vector<int>> a(n+1),id(n+1),b(m+1);
        int sum=0,tim=0;
        while(q--){
            int r,cnt;cin>>r>>cnt;
            sum+=cnt;
            while(cnt--){
                int c;cin>>c;
                a[r].push_back(c);   
                b[c].push_back(r);         
            }
        }
        vector<int> cur(n+1,0);
        vector<ll> dp(sum+1,0);
        for(int j=1;j<=m;j++){
            for(auto i:b[j]){
                dp[++tim]=(i+j)^f[j];
                id[i].push_back(tim);
                if(j>=2){
                    for(int p=max(i-k,1);p<i;p++){
                        dp[tim]=max(dp[tim],((ll)(p+j-1)^f[j-1])+(i^f[j]));
                        if(a[p].size()){
                            while(cur[p]+1<a[p].size()&&a[p][cur[p]+1]<=j-1){
                                cur[p]++;
                            }
                            dp[tim]=max(dp[tim],dp[id[p][cur[p]]]+(i^f[j]));
                        }
                    }
                }
            }
        }
        ll mx=0;
        for(int i=1;i<=n;i++){
            if(a[i].size()){
                int cnt=a[i].size();
                mx=max(mx,dp[id[i][cnt-1]]);
            }
            mx=max(mx,(ll)(i+m)^f[m]);
        }
        cout<<mx<<'\n';
    }
    return 0;
}

Extra 管道调温 (Hard version)

观察转移。考虑从左到右更新dp值，发现dp的转移只和 1.前一列 $[max(1,i-k),i-1]$ 的最近管道头的dp值 2.前一列的原始热量值有关。

第一个形式是单点修区间查max线段树。第二个形式转换一下就变成给定 $x$ ，查询 $x$ 对 $[l,r]$ 中数的异或最大值。第二个形式是经典的，考虑把 $[l,r]$ 的数放到01tire上去看看，发现我们从高位到低位贪心就行了。具体来说，用一个 $pre$ 求合法的前缀，每次贪心放 $x$ 的第 $i$ 位的取反，判断这个前缀构成的最大范围是否与 $[l,r]$ 有交即可。

时间复杂度 $O(\sum cnt \times \log n)$

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <array>
#include <unordered_map>
#include <numeric>
#include <functional>
#include <ranges>
#include <iomanip>
#include <chrono>
#include <random>
//#define int long long //赫赫 要不要龙龙呢
using ll=long long;
using namespace std;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
template<class Info,class Tag>
class SegTree{
    public:
    int n;
    vector<Info> info;
    vector<Tag> tag;
    SegTree(int n):n(n),info((n<<2)+5),tag((n<<2)+5){}
    SegTree(const vector<Info> &a):n(a.size()-1){
        //a 1-Based
        info.resize((n<<2)+5);
        tag.resize((n<<2)+5);
        bd(1,1,n,a);
    }
    inline void pushup(int p){
        info[p]=info[lc(p)]+info[rc(p)];
    }
    inline void apply(int p,int l,int r,const Tag &v){
        info[p].apply(l,r,v);
        tag[p].apply(v);
    }
    inline void pushdown(int p,int l,int r){
        if(!tag[p].has_tag()) return;
        int m=(l+r)>>1;
        apply(lc(p),l,m,tag[p]);
        apply(rc(p),m+1,r,tag[p]);
        tag[p]=Tag();
    }
    void bd(int p,int l,int r,const vector<Info> &a){
        if(l==r){
            info[p]=a[l];
            return;
        }
        int m=(l+r)>>1;
        bd(lc(p),l,m,a);
        bd(rc(p),m+1,r,a);
        pushup(p);
    }
    void upd(int p,int l,int r,int x,int y,const Tag &v){
        if(x>r||y<l||x>y) return;
        if(x<=l&&r<=y){
            apply(p,l,r,v);
            return;
        }
        pushdown(p,l,r);
        int m=(l+r)>>1;
        if(x<=m) upd(lc(p),l,m,x,y,v);
        if(m<y) upd(rc(p),m+1,r,x,y,v);
        pushup(p);
    }
    void mdf(int p,int l,int r,int x,const Info &v){
        if(l==r){
            info[p]=v;
            return;
        }
        pushdown(p,l,r);
        int m=(l+r)>>1;
        if(x<=m) mdf(lc(p),l,m,x,v);
        else mdf(rc(p),m+1,r,x,v);
        pushup(p);
    }
    Info qry(int p,int l,int r,int x,int y){
        if(x>r||y<l||x>y) return Info();
        if(x<=l&&r<=y) return info[p];
        pushdown(p,l,r);
        int m=(l+r)>>1;
        Info res=Info();
        if(x<=m) res=res+qry(lc(p),l,m,x,y);
        if(m<y) res=res+qry(rc(p),m+1,r,x,y);
        return res;
    }
    int findfirst(int p,int l,int r,int x,int y,
        Info &v,const function<bool(const Info&)> &chk){
        if(r<x||y<l) return n+1;
        if(x<=l&&r<=y){
            Info cmb=v+info[p];
            if(!chk(cmb)) {
                v=cmb;
                return n+1;
            }
            if(l==r) return l;
            pushdown(p,l,r);
            int m=(l+r)>>1;
            int res=findfirst(lc(p),l,m,x,y,v,chk);
            if(res!=n+1) return res;
            return findfirst(rc(p),m+1,r,x,y,v,chk);
        }
        pushdown(p,l,r);
        int m=(l+r)>>1;
        int res=findfirst(lc(p),l,m,x,y,v,chk);
        if(res!=n+1) return res;
        return findfirst(rc(p),m+1,r,x,y,v,chk);
    }
    int findlast(int p,int l,int r,int x,int y,
        Info &v,const function<bool(const Info&)> &chk){
            if(r<x||y<l) return 0;
            if(x<=l&&r<=y){
                Info cmb=v+info[p];
                if(!chk(cmb)) {
                    v=cmb;
                    return 0;
                }
                if(l==r) return l;
                pushdown(p,l,r);
                int m=(l+r)>>1;
                int res=findlast(rc(p),m+1,r,x,y,v,chk);
                if(res!=0) return res;
                return findlast(lc(p),l,m,x,y,v,chk);
            }
            pushdown(p,l,r);
            int m=(l+r)>>1;
            int res=findlast(rc(p),m+1,r,x,y,v,chk);
            if(res!=0) return res;
            return findlast(lc(p),l,m,x,y,v,chk);
    }
    int _findfirst(int p,int l,int r,int x,int y,
        const function<bool(const Info&)> &chk){
            if(r<x||y<l) return n+1;
            if(!chk(info[p])) return n+1;
            if(l==r) return l;
            pushdown(p,l,r);
            int m=(l+r)>>1;
            int res=_findfirst(lc(p),l,m,x,y,chk);
            if(res!=n+1) return res;
            return _findfirst(rc(p),m+1,r,x,y,chk);
    }
    int _findlast(int p,int l,int r,int x,int y,
        const function<bool(const Info&)> &chk){
            if(r<x||y<l) return 0;
            if(!chk(info[p])) return 0;
            if(l==r) return l;
            pushdown(p,l,r);
            int m=(l+r)>>1;
            int res=_findlast(rc(p),m+1,r,x,y,chk);
            if(res!=0) return res;
            return _findlast(lc(p),l,m,x,y,chk);
    }
    void upd(int l,int r,const Tag &v){
        upd(1,1,n,l,r,v);
    }
    void mdf(int x,const Info &v){
        mdf(1,1,n,x,v);
    }
    Info qry(int l,int r){
        return qry(1,1,n,l,r);
    }
    //寻找在[l,r]的第一个[l,k] 满足Info{l,k}满足chk e.g.[1,4]的[1,2]满足sum(1,2)<10
    //异常值: n+1
    int findfirst(int l,int r,const function<bool(const Info&)> &chk){
        Info tp=Info();
        return findfirst(1,1,n,l,r,tp,chk);
    }
    //寻找在[l,r]的最后一个[k,r] 满足Info{k,r}满足chk e.g.[1,4]的[3,4]满足sum(3,4)<10
    //异常值: 0
    int findlast(int l,int r,const function<bool(const Info&)> &chk){
        Info tp=Info();
        return findlast(1,1,n,l,r,tp,chk);
    }
    //寻找在[l,r]的第一个k 满足Info k满足chk e.g.[1,4]的第一个k=2满足info k<10
    //异常值: n+1
    int _findfirst(int l,int r,const function<bool(const Info&)> &chk){
        return _findfirst(1,1,n,l,r,chk);
    }
    //寻找在[l,r]的最后一个k 满足Info k满足chk e.g.[1,4]的最后一个k=3满足info k<10
    //异常值: 0
    int _findlast(int l,int r,const function<bool(const Info&)> &chk){
        return _findlast(1,1,n,l,r,chk);
    }
};
// Tag 结构体：定义懒标记
// 需要实现:
// 1. 成员变量: 存储懒标记信息
// 2. 默认构造函数: 表示无标记状态
// 3. apply(const Tag& v): 将另一个标记 v 合并到当前标记
// 4. has_tag(): 判断当前是否是无标记状态
struct Tag{
    int tag;
    Tag():tag(0){}
    void apply(const Tag &v){
        
    }
    bool has_tag(){
        return tag!=0;
    }
};
// Info 结构体：定义节点信息
// 需要实现:
// 1. 成员变量: 存储节点维护的信息
// 2. 默认构造函数: Info 的单位元 (例如求和的0, 求积的1)
// 3. apply(int l, int r, const Tag& v): 将懒标记 v 应用到当前节点信息上
// 4. operator+(const Info& other): 合并两个子节点的信息
struct Info{
    //...
    ll info;
    Info():info(0){}
    Info(ll x):info(x){}
    void apply(int l,int r,const Tag &v){
        
    }
};
Info operator+(const Info &a,const Info &b){
    //...
    Info c;
    c.info=max(a.info,b.info);
    return c;
};
signed main()
{
    auto T_start=chrono::steady_clock::now();
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    auto get=[&](int a,int l,int r){
        int res=0,ans=0;
        for(int i=30;i>=0;i--){
            int b=(a>>i)&1;
            int p=res|((b^1)<<i);
            if(p<=r&&p+(1<<i)-1>=l){
                res=p;
                ans+=(1<<i);
            }
            else{
                res|=(b<<i);
            }
        }
        return ans;
    };
    int t;cin>>t;
    while(t--){
        int n,m,k,q;cin>>n>>m>>k>>q;
        vector<int> f(m+1);
        for(int i=1;i<=m;i++){
            cin>>f[i];
        }
        vector<vector<int>> b(m+1);
        while(q--){
            int r,cnt;cin>>r>>cnt;
            while(cnt--){
                int c;cin>>c; 
                b[c].push_back(r);         
            }
        }
        vector<Info> a(n+1,0);
        SegTree<Info,Tag> seg(a);
        vector<ll> dp(n+1,0);
        for(int j=1;j<=m;j++){
            for(auto i:b[j]){
                dp[i]=(i+j)^f[j];
                if(j>=2&&i>=2){
                    dp[i]=max(dp[i],seg.qry(max(1,i-k),i-1).info+(i^f[j]));
                    dp[i]=max(dp[i],(ll)get(f[j-1],j-1+max(1,i-k),j-1+i-1)+(i^f[j]));
                }
            }
            for(auto i:b[j]){
                seg.mdf(i,dp[i]);
            }
        }
        ll mx=0;
        for(int i=1;i<=n;i++){
            mx=max(mx,dp[i]);
            mx=max(mx,(ll)(i+m)^f[m]);
        }
        cout<<mx<<'\n';
    }
    return 0;
}