2025“钉耙编程”中国大学生算法设计春季联赛 - 热身赛

67天前 · 题解 · 101次阅读

本场据说是hdu的新生赛，好多题目读题难度远远大于做题难度。

1001 氯化钠

本题和 F. We Be Summing 这题极为相似，本题是给定 $k$ ，要求满足 $min(a_l,\dots ,a_r)+max(a_l,\dots ,a_r)\leq k$ 的区间个数。

首先求区间问题一般都会转换为固定左端点求右端点/固定右端点求左端点的题目。

任何区间左端点和右端点一定是唯一的，同理任何区间最靠前的最小值也一定是唯一的。我们一般可以通过这种唯一性来处理所有区间，比如上面的固定左端点求所有合法的右端点来组成一个区间。

本题是另一种思路，我们转换为固定 区间最前面的最小值 ，枚举每个数作为某个区间最前面的最小值，用单调栈处理出来这个点左边第一个 小于等于 $a_i$ 的数的位置存到 $sl$ 里面作为左端点的范围（也就是表示枚举了所有以当前这个数字作为最前面最小值的所有区间），再用一次单调栈处理出来这个点右边第一个 小于 $a_i$ 的数的位置存到 $sr$ 作为可选的右端点的范围。

上面这种方法能够保证我们可以不重不漏的找到所有区间，对于每一类区间（也就是所有以某个位置的数作为最前面的最小值的区间）我们再检验是否合理，每一类区间最靠前的最小值我们已经知道了（我们定这个位置为 $pos$ ），我们要求满足 $min(a_l,\dots ,a_r)+max(a_l,\dots ,a_r)\leq k$ 的区间个数，只要 $[l,pos]$ 或者 $[pos,r]$ 有一个数大于 $k-a[pos]$ 即可满足，当两端区间都不满足才不满足，为了防止重复我们可以转换成这一类区间个数减去 $[l,pos]$ 与 $[pos,r]$ 的数字都不大于 $k-a[pos]$ 的区间个数。

对于每一类区间他的总数是 $(pos-l+1)*(r-pos+1)$ ，我们可以通过二分得到$L,R$ ，$L$ 满足区间 $[L,pos]$ $[pos,R]$都小于$k-a[pos]$ ，所以可以得到最终答案$(pos-l+1)*(r-pos+1)-(pos-L+1)*(R-pos+1)$ 。

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct ST {
    const int n, k;
    vector<int> in;
    vector<vector<int>> Max, Min;
    ST(int n) : n(n), in(n + 1), k(__lg(n)) {
        Max.resize(k + 1, vector<int>(n + 1));
        Min.resize(k + 1, vector<int>(n + 1));
    }
    void init() {
        for (int i = 1; i <= n; i++) {
            Max[0][i] = in[i];
            Min[0][i] = in[i];
        }
        for (int i = 0, t = 1; i < k; i++, t <<= 1) {
            const int T = n - (t << 1) + 1;
            for (int j = 1; j <= T; j++) {
                Max[i + 1][j] = max(Max[i][j], Max[i][j + t]);
                Min[i + 1][j] = min(Min[i][j], Min[i][j + t]);
            }
        }
    }
    int getMax(int l, int r) {
        if (l > r) {
            swap(l, r);
        }
        int k = __lg(r - l + 1);
        return max(Max[k][l], Max[k][r - (1 << k) + 1]);
    }
    int getMin(int l, int r) {
        if (l > r) {
            swap(l, r);
        }
        int k = __lg(r - l + 1);
        return min(Min[k][l], Min[k][r - (1 << k) + 1]);
    }
 };
void solve() {
    int n,k;cin>>n>>k;
    vector<int> a(n+2);
    for(int i=1;i<=n;i++)cin>>a[i];
    stack<int> st;
    vector<int> sl(n+2),sr(n+2);
    vector<int> bl(n+2),br(n+2);
    //向左找作为最小能拓展到的位置
    while(st.size())st.pop();st.push(0);a[0]=-1;
    for(int i=1;i<=n;i++){
        while(a[i]<a[st.top()])st.pop();
        sl[i]=st.top()+1;
        st.push(i);
    }
    while(st.size())st.pop();st.push(n+1);a[n+1]=-1;
    for(int i=n;i>=1;i--){
        while(a[i]<=a[st.top()])st.pop();
        sr[i]=st.top()-1;
        st.push(i);
    }

    ST sta(n);
    for(int i=1;i<=n;i++)sta.in[i]=a[i];
    sta.init();
    
    auto check=[&](int x){
        int cnt=0;
        //某个数作为最前面的最小值
        for(int i=1;i<=n;i++){
            int l=sl[i],r=i;
            while(l<r){
                int mid=l+r>>1;
                if(sta.getMax(mid,i)>=x-a[i])l=mid+1;
                else r=mid;
            }
            int L=0;
            if(sta.getMax(l,i)<x-a[i])L=i-l+1;
            l=i,r=sr[i];
            while(l<r){
                int mid=l+r+1>>1;
                if(sta.getMax(i,mid)<x-a[i])l=mid;
                else r=mid-1;
            }
            int R=0;
            if(sta.getMax(i,l)<x-a[i])R=l-i+1;
            cnt+=(i-sl[i]+1)*(sr[i]-i+1)-L*R;
            int tmp=(i-sl[i]+1)*(sr[i]-i+1)-L*R;
        }
        return cnt>=k;
    };
    int l=0,r=2e9;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    cout<<l<<'\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin>>T;
    while(T--)solve();

    return 0;
}

1002 小猫钓鱼

模拟题，注意 JQK 牌也算得分

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
    int n;cin>>n;
    string a,b;cin>>a>>b;
    a=' '+a;b=' '+b;
    stack<char> st;
    map<char,stack<int>> pos;
    auto play=[&](char op){
        int ans=0;
        if(op>='1'&&op<='9'){
            if(pos[op].size()){
                if(pos['Q'].size()&&pos['Q'].top()>pos[op].top()){
                    pos['Q'].pop();
                    st.push(op);
                    pos[op].push(st.size());
                }
                else{
                    ans++;
                    while(st.top()!=op){  
                        if(st.top()>='1'&&st.top()<='9')pos[st.top()].pop();
                        ans++;
                        st.pop();
                    }
                    ans++;
                    st.pop();
                    pos[op].pop();
                }
            }
            else{
                st.push(op);
                pos[op].push(st.size());
            }
        }
        else if(op=='Q'){
            st.push(op);
            pos[op].push(st.size());
        }
        else if(op=='J'){
            ans++;
            while(st.size()&&(pos['Q'].empty()||st.size()!=pos['Q'].top())){
                if(st.top()>='1'&&st.top()<='9')pos[st.top()].pop();
                ans++;
                st.pop();
            }
            if(st.size()){
                ans++;
                st.pop();
                pos['Q'].pop();
            }
        }
        else{
            if(pos['Q'].size())pos['Q'].pop();
            st.push(op);
        }
        return ans;
    };
    int A=0,B=0;
    for(int i=1;i<=n;i++){
        A+=play(a[i]);
        B+=play(b[i]);
    }
    cout<<A<<' '<<B<<'\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin>>T;
    while(T--)solve();
    return 0;
}

1003 找回x

签到题，注意到答案就是$\frac{sumC-sumB}{sumA}$

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
    int n;cin>>n;
    vector<int> a(n+1);
    map<int,int> mp;
    int cnt=0;
    vector<int> A(n+1),B(n+1),C(n+1);
    int suma=0,sum=0;
    for(int i=1;i<=n;i++)cin>>A[i],suma+=A[i];
    for(int i=1;i<=n;i++)cin>>B[i];
    for(int i=1;i<=n;i++)cin>>C[i],sum+=C[i]-B[i];
    cout<<sum/suma<<'\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin>>T;
    while(T--)solve();
    return 0;
}

1004 并非博弈

这里直接贴上题解解释

并非博弈

#include <bits/stdc++.h>
using namespace std;
#define int long long
int ans=0;
void solve() {
    int n;cin>>n;
    int sum=0;
    auto get=[&](int x)->int{
        if(x%4==1)return 1;
        if(x%4==2)return x+1;
        if(x%4==3)return 0;
        if(x%4==0)return x;
    };
    ans^=(int)ceill(n*2/(1+sqrtl(5)));

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin>>T;
    while(T--)solve();
    cout<<ans<<'\n';
    return 0;
}

1005 最小集合

非常恶心的dp套dp，首先注意到模m相等的数应该一块处理。然后只考虑模m相等的数变成至少 $k$ 个不同的数至少要花费多少钱。

首先用 $dp[i][j]$ 处理出来模m相等的一堆数中排序后前 $i$ 个至少有 $k$ 种不同的数需要多少花费。

转移方程

$$ dp[r][j]= min_{l=1}^i\left(dp[r][j],dp[l-1][j-1]+cost(l,r) \right)\\ cost\left(l,r\right)= sum[r]-sum[mid]-(sum[mid-1]-sum[l-1])\\ +((r-l+1)\%2?0:-a[mid]) $$

然后这样能得到模m相等的数变成至少 $k$ 个不同的数至少要花费多少钱，将模m相同的取出来作为一组背包，再次使用分组背包。

一开始意味这题最终只输出一个数字，WA了非常多发，最后发现原来是一个测试样例输出一个ans。

#include <bits/stdc++.h>
using namespace std;

#define int long long
int ans=0;
void solve() {
    int n,m;cin>>n>>m;
    vector<vector<int>> pos(m,vector<int>(1,0));
    vector<int> q(n+1);
    vector<vector<array<int,2>>> bag(1);
    for(int i=1;i<=n;i++){
        cin>>q[i];
        pos[q[i]%m].push_back(q[i]/m);
    }
    for(int t=0;t<m;t++){
        auto& a=pos[t];
        if(a.size()==1)continue;
        vector<array<int,2>> b;
        sort(a.begin(),a.end());
        int cnt=a.size()-1;
        vector<int> sum(cnt+1);
        for(int i=1;i<=cnt;i++){
            sum[i]=sum[i-1];
            sum[i]+=a[i];
        }
        //前i个数字中最多有j个不同的数字需要花费的价值
        vector<vector<int>> dp(cnt+1,vector<int>(cnt+1,1e18));
        dp[0][0]=0;
        for(int r=1;r<=cnt;r++){
            for(int j=1;j<=cnt;j++){
                for(int l=1;l<=r;l++){
                    int mid=(l+r>>1);
                    int tmp=sum[r]-sum[mid]-(sum[mid-1]-sum[l-1])+((r-l+1)%2?0:-a[mid]);
                    dp[r][j]=min(dp[r][j],dp[l-1][j-1]+tmp);
                }
            }
        }
        for(int i=1;i<=cnt;i++){
            b.push_back({i,dp[cnt][i]});
        }
        bag.push_back(b);
    }
    int nb=bag.size()-1;
    //前i组背包中有j个不同的数字最小花费
    vector<vector<int>> dp(nb+1,vector<int>(n+1,1e18));
    dp[0][0]=0;
    for(int i=1;i<=nb;i++){
        for(int j=1;j<=n;j++){
            for(auto [k,w]:bag[i]){
                if(j-k<0)continue;
                dp[i][j]=min(dp[i][j],dp[i-1][j-k]+w);
            }
        }
    }
    int t;cin>>t;
    while(t--){
        int x;cin>>x;
        int l=1,r=n;
        while(l<r){
            int mid=l+r>>1;
            if(dp[nb][mid]<=x)r=mid;
            else l=mid+1;
        }
        ans=(ans*13331+l)%998244353;
    }
    cout<<ans<<'\n';ans=0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin>>T;
    while(T--)solve();
    return 0;
}

1006 对吗？对的对的 不对不对

模拟题，一开始写了个线段树维护但是T了，后来换成前缀和过的。

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
    string s;cin>>s;
    int n=s.size();
    s=' '+s+' ';
    vector<int> py(n+2),pe(n+2),ps(n+2),pye(n+2),pyes(n+2);
    vector<int> pn(n+2),po(n+2),pno(n+2);
    vector<int> sy(n+2),se(n+2),ss(n+2),ses(n+2),syes(n+2);
    vector<int> sn(n+2),so(n+2),sno(n+2);
    
    for(int i=1;i<=n;i++){
        py[i]=py[i-1];pe[i]=pe[i-1];ps[i]=ps[i-1];
        pye[i]=pye[i-1];pyes[i]=pyes[i-1];
        po[i]=po[i-1];pn[i]=pn[i-1];pno[i]=pno[i-1];
        if(s[i]=='Y')py[i]++;
        if(s[i]=='E')pe[i]++,pye[i]+=py[i-1];
        if(s[i]=='S')ps[i]++,pyes[i]+=pye[i-1];
        if(s[i]=='N')pn[i]++;
        if(s[i]=='O')po[i]++,pno[i]+=pn[i-1];
    }
    for(int i=n;i>=1;i--){
        sy[i]=sy[i+1];se[i]=se[i+1];ss[i]=ss[i+1];
        ses[i]=ses[i+1];syes[i]=syes[i+1];
        so[i]=so[i+1];sn[i]=sn[i+1];sno[i]=sno[i+1];
        if(s[i]=='Y')sy[i]++,syes[i]+=ses[i+1];
        if(s[i]=='E')se[i]++,ses[i]+=ss[i+1];
        if(s[i]=='S')ss[i]++;
        if(s[i]=='N')sn[i]++,sno[i]+=so[i+1];
        if(s[i]=='O')so[i]++;
    }
    cout<<pyes[n]<<' '<<pno[n]<<'\n';
    if(pyes[n]>pno[n]){
        for(int i=1;i<=n;i++){
            int cnty=0;
            if(s[i]=='Y')cnty-=ses[i+1];
            if(s[i]=='E')cnty-=py[i-1]*ss[i+1];
            if(s[i]=='S')cnty-=pye[i-1];
            if(s[i]=='N')cnty+=so[i+1];
            if(s[i]=='O')cnty+=pn[i-1];
            cnty-=max(so[i+1],pn[i-1]);
            if(pyes[n]+cnty<pno[n]){
                return cout<<"O BUDUI BUDUI\n",void();
            }
        }
        cout<<"DUI DE\n";
    }
    else if(pyes[n]<pno[n]){
        for(int i=1;i<=n;i++){
            int cnty=0;
            if(s[i]=='Y')cnty-=ses[i+1];
            if(s[i]=='E')cnty-=py[i-1]*ss[i+1];
            if(s[i]=='S')cnty-=pye[i-1];
            if(s[i]=='N')cnty+=so[i+1];
            if(s[i]=='O')cnty+=pn[i-1];
            cnty+=max(ses[i+1],max(py[i-1]*ss[i+1],pye[i-1]));
            if(pyes[n]+cnty>pno[n]){
                return cout<<"O DUI DE\n",void();
            }   
        }
        cout<<"BUDUI BUDUI\n";
    }
    else cout<<"DUI DUI DUIMA\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin>>T;
    while(T--)solve();
    return 0;
}

1007 划分

一个好玩的dp题目，首先肯定能想到 $n^2$ 的dp方法

  1. $dp[i]$ 表示某个位置的答案，需要 $n^2$ 转移。肯定会T。

  2. 注意到 $a_i$ 范围很小，并且是异或，数肯定不会超过1024。

    $dp[i][j]$ 第一维表示前缀异或和，第二维表示位置（实际上这个状态设计是重复的，写题时大脑宕机了），还是 $n^2$ 转移。

  3. 再次观察第一次的式子

    $$ dp[i]=max_{j=1}^i(dp[i],dp[j]+(sum[i]\oplus sum[j])*(i-j)) $$

    他可以整理成

    $$ dp[i]=max_{j=1}^i(dp[i],i*(sum[i]\oplus sum[j])+dp[j]-(sum[i]\oplus sum[j])*j) $$

    而 $i*(sum[i]\oplus sum[j])$ 在 $sum[j]$ 确定时是固定值，我们这时候如果能快速确定 $dp[j]-(sum[i]\oplus sum[j])*j)$ 的最大值即可在 $O(1024n)$ 范围内解决这个题目，于是可以开个1024*1024的数组暴力维护。

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
    int n;cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<int> sum(n+1);
    for(int i=1;i<=n;i++){
        sum[i]=a[i];
        sum[i]^=sum[i-1];
    }
    vector<vector<int>> w(1025,vector<int>(1025,-1e18));
    for(int i=0;i<=1024;i++)w[0][i]=0;
    int ans=0;
    for(int i=1;i<=n;i++){
        int maxx=0;
        for(int j=0;j<1024;j++){
            maxx=max(maxx,w[j][sum[i]]+(j^sum[i])*i);
        }
        for(int j=0;j<1024;j++){
            w[sum[i]][j]=max(w[sum[i]][j],maxx-(j^sum[i])*i);
        }
        ans+=maxx;
    }
    cout<<ans<<'\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

1008 金牌

签到题

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
    int n;cin>>n;
    map<string,int> mp;
    for(int i=1;i<=n;i++){
        string s;cin>>s;
        mp[s]++;
    }
    cout<<mp["Au"]+min(mp["Ag"],mp["Cu"])<<'\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin>>T;
    while(T--)solve();
    return 0;
}

1009 A进制

写了umap以为会比数组更快，但是后来发现并没有……

最终暴力bitset过的

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n,P,x;cin>>n>>P>>x;
    unordered_set<int> se;
    se.insert(x);
    auto get=[&](int a,int b)->array<int,3>{
        int ans1=0,ans2=0,ans3=0;
        int p=1;
        while(a||b){
            int ma=a%P,mb=b%P;
            ans1+=min(ma,mb)*p;
            ans2+=max(ma,mb)*p;
            ans3+=(ma+mb)%P*p;
            p*=P;
            a/=P,b/=P;
        };
        return {ans1,ans2,ans3};
    };
    bitset<30000> a;
    a[x]=1;
    for(int i=1;i<=n;i++){
        bitset<30000> b;
        int o;cin>>o;
        for(int i=0;i<30000;i++){
            if(a[i]){
                auto [x,y,z]=get(o,i);
                b[x]=1;
                b[y]=1;
                b[z]=1;
            }
        }
        a=b;
    }
    int ans=0;
    for(int i=0;i<30000;i++){
        if(a[i])ans+=i;
    }
    cout<<ans<<'\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin>>T;
    while(T--)solve();
    return 0;
}

1010 绝对值

题意很迷的签到题

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
    int n;cin>>n;
    vector<int> a(n+1);
    int ans=0;
    for(int i=1;i<=n;i++)cin>>a[i],a[i]=abs(a[i]),ans+=(n-i+1)*a[i];
    cout<<ans<<'\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    while(T--)solve();
    return 0;
}
👍 11

none

最后修改于64天前

评论

目录

avatar

coolarec

你好，未曾谋面的陌生人

31

文章数

16

评论数

5

分类

那就出发吧！

❤ 99

  • 赛事游记
  • 日常
  • coding
  • 全部