2025“钉耙编程”中国大学生算法设计暑期联赛（3）

1. 1002 小抹爱锻炼

知识点：贪心上下界判断

计算出训练次数的下限和上限，判断M是否在上下限中即可

下限：从左到右贪心取最小=max(b[i],last)

上限：从右到左贪心取最大=min(c[i],last)

#include<bits/stdc++.h> #define in inline #define re register #define ll long long #define db double #define ls(a) a<<1 #define rs(a) a<<1|1 #define sz(a) int(a.size()) #define inf 0x3f3f3f3f #define me(a,num) memset(a,num,sizeof(a)) #define mc(a,b) memcpy(a,b,sizeof(a)) #define For(i,a,n) for(re int (i)(a);(i)<=(n);(i)=-~(i)) #define Bor(i,n,a) for(re int (i)(n);(i)>=(a);--(i)) #define debug cout<<"QWQ"<<endl #define Time cout<<(db)clock()/CLOCKS_PER_SEC<<endl #define int long long using namespace std; const int R=1<<21,N=1e6+10; int b[N],c[N]; in int qread() { re int s=0,op=0; re char ch=getchar(); while(!isdigit(ch))op|=ch=='-',ch=getchar(); while(isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar(); return op?-s:s; } in void solve(int n,int m) { int mins=0,maxs=0; int last=0; For(i,1,n) { if(b[i]>=last) { mins+=b[i]; last=b[i]; } else if(c[i]<last) { cout<<"NO"<<endl; return; } else { mins+=last; } } last=inf; Bor(i,n,1) { if(c[i]<=last) { maxs+=c[i]; last=c[i]; } else if(b[i]>last) { cout<<"NO"<<endl; return; } else { maxs+=last; } } if(m>maxs||m<mins) { cout<<"NO"<<endl; return; } else { cout<<"YES"<<endl; return; } } signed main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); int T; T=qread(); while(T--) { int n,m; n=qread(),m=qread(); For(i,1,n)b[i]=qread(); For(i,1,n)c[i]=qread(); solve(n,m); } return 0; } 

2. 1004 三带一

知识点：二分

上界S/4，二分答案，每次对13种牌各确定可用三的上下界，来确实true/false

#include<bits/stdc++.h> #define in inline #define re register #define ll long long #define db double #define ls(a) a<<1 #define rs(a) a<<1|1 #define sz(a) int(a.size()) #define inf 0x3f3f3f3f #define me(a,num) memset(a,num,sizeof(a)) #define mc(a,b) memcpy(a,b,sizeof(a)) #define For(i,a,n) for(re int (i)(a);(i)<=(n);(i)=-~(i)) #define Bor(i,n,a) for(re int (i)(n);(i)>=(a);--(i)) #define debug cout<<"QWQ"<<endl #define Time cout<<(db)clock()/CLOCKS_PER_SEC<<endl using namespace std; const int R=1<<21,N=1e6+10; in ll qread() { re ll s=0,op=0; re char ch=getchar(); while(!isdigit(ch))op|=ch=='-',ch=getchar(); while(isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar(); return op?-s:s; } struct { int maxn,lef; }b[N]; in bool check(ll x,vector<ll>& a,ll S) { if (4*x>S) { return 0; } ll totalL=0; ll totalR=0; For(i,0,12) { ll maxR=min(x,a[i]/3); ll t =3*x+a[i]-S; ll minl=0; if (t>0) {minl=(t+1)/2; }//(S-mid*3)-(a[i]-3minl)>=minl if (minl>maxR) {return 0;} totalL+=minl; totalR+=maxR; } if (totalL<=x&&x<=totalR) { return 1; } return 0; } int main() { int T; T=qread(); while(T--) { vector<ll>a(13); ll S=0; For(i,0,12)a[i]=qread(),S+=a[i]; ll Ri=S/4; ll Le=0; ll ans=0; while (Le<=Ri) { ll mid=(Le+Ri)/2; if (check(mid,a,S)) { ans=mid; Le=mid+1; } else { Ri=mid-1; } } printf("%lld\n",ans); } return 0; }

3. 1007 性质不同的数字

知识点：扫描线+哈希

可以给所有的线段一个随机值，加入(l, rand_vals[i])和(r + 1, rand_vals[i])，排序，从左向右扫，通过异或来加入和删除线段，unordered_set判断扫描过程加入线段和删除线段的变化，产生新变化就count++

#include<bits/stdc++.h> #define in inline #define re register #define ll long long #define ull unsigned long long #define db double #define ls(a) a<<1 #define rs(a) a<<1|1 #define sz(a) int(a.size()) #define inf 0x3f3f3f3f #define me(a,num) memset(a,num,sizeof(a)) #define mc(a,b) memcpy(a,b,sizeof(a)) #define For(i,a,n) for(re int (i)(a);(i)<=(n);(i)=-~(i)) #define Bor(i,n,a) for(re int (i)(n);(i)>=(a);--(i)) #define debug cout<<"QWQ"<<endl #define Time cout<<(db)clock()/CLOCKS_PER_SEC<<endl using namespace std; const int R=1<<21,N=1e6+10; in ll qread() { re ll s=0,op=0; re char ch=getchar(); while(!isdigit(ch))op|=ch=='-',ch=getchar(); while(isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar(); return op?-s:s; } int main() { static mt19937_64 gen(random_device{}()); static uniform_int_distribution<unsigned long long> dis; int t; t=qread(); while (t--) { int n; n=qread(); if (n == 0) { printf("1\n"); continue; } vector<ull> rand_vals(n); For(i,0,n-1)rand_vals[i] = dis(gen); vector<pair<ll, ull> > events; events.reserve(2 * n); for (int i = 0; i < n; i++) { ll l, r; scanf("%lld %lld", &l, &r); events.emplace_back(l, rand_vals[i]); events.emplace_back(r + 1, rand_vals[i]); } sort(events.begin(), events.end()); ull current = 0; unordered_set<ull> seen; seen.insert(0); int count = 1; for (int i=0;i<events.size(); ) { ll pos=events[i].first; int j=i; while (j<events.size()&&events[j].first==pos) { current^=events[j].second; j++; } if (seen.find(current)==seen.end()) { seen.insert(current); count++; } i=j; } printf("%d\n", count); } return 0; }

4. 1012核心共振

知识点：坐标变换

#include<bits/stdc++.h> #define in inline #define re register #define ll long long #define db double #define ls(a) a<<1 #define rs(a) a<<1|1 #define sz(a) int(a.size()) #define inf 0x3f3f3f3f #define me(a,num) memset(a,num,sizeof(a)) #define mc(a,b) memcpy(a,b,sizeof(a)) #define For(i,a,n) for(re int (i)(a);(i)<=(n);(i)=-~(i)) #define Bor(i,n,a) for(re int (i)(n);(i)>=(a);--(i)) #define debug cout<<"QWQ"<<endl #define Time cout<<(db)clock()/CLOCKS_PER_SEC<<endl using namespace std; const ll R=1<<21,N=1e6+10,mod=1e9+7,inv2=500000004; in ll qread() { re ll s=0,op=0; re char ch=getchar(); while(!isdigit(ch))op|=ch=='-',ch=getchar(); while(isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar(); return op?-s:s; } in ll solve(vector<ll>uu,vector<ll>a,ll n) { vector<ll>anss(n,0),sum(n,0); vector<ll>x=uu; sort(x.begin(),x.end()); sum[0]=x[0]; For(i,1,n-1)sum[i]=sum[i-1]+x[i]; // debug; // For(i,0,n-1)cout<<x[i]<<" "; // cout<<endl; ll ans=0,ansl=0,ansr=0; For(i,0,n-1) { ansl=0,ansr=0; ll zb=uu[i]; ll l=lower_bound(x.begin(),x.end(),zb)-x.begin(); ll r=upper_bound(x.begin(),x.end(),zb)-x.begin(); if(l>0)ansl=l*zb-sum[l-1]; if(r<n)ansr=(sum[n-1]-sum[r-1])-(n-r)*zb; anss[i]=ansl+ansr; } // For(i,0,n-1)cout<<anss[i]<<" "; For(i,0,n-1)ans=(ans+(a[i]%mod)*(anss[i]%mod))%mod; return ans; } int main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); ll t=qread(); while(t--) { ll n=qread(); vector<ll>u(n),v(n),a(n); For(i,0,n-1) { ll x,y,val; x=qread(),y=qread(),val=qread(); u[i]=x+y,v[i]=y-x,a[i]=val; } ll ansu=0,ansv=0; ansu=solve(u,a,n); // debug;cout<<ansu<<endl; ansv=solve(v,a,n); // debug;cout<<ansv<<endl; ll ans=(ansu+ansv)%mod*inv2%mod; printf("%lld\n",ans); } return 0; } 

5. 1008 01环

知识点：模拟分析

存在101010和010101两种合法情况，对两种情况分别判断给出序列的不正确位置，对于连续长L的不正确段要至少操作（L+1）/2次

#include<bits/stdc++.h> #define in inline #define re register #define ll long long #define db double #define ls(a) a<<1 #define rs(a) a<<1|1 #define sz(a) int(a.size()) #define inf 0x3f3f3f3f #define me(a,num) memset(a,num,sizeof(a)) #define mc(a,b) memcpy(a,b,sizeof(a)) #define For(i,a,n) for(re int (i)(a);(i)<=(n);(i)=-~(i)) #define Bor(i,n,a) for(re int (i)(n);(i)>=(a);--(i)) #define debug cout<<"QWQ"<<endl #define Time cout<<(db)clock()/CLOCKS_PER_SEC<<endl using namespace std; const int R=1<<21,N=1e6+10; in int qread() { re int s=0,op=0; re char ch=getchar(); while(!isdigit(ch))op|=ch=='-',ch=getchar(); while(isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar(); return op?-s:s; } int n; char s[N]; bool ch[N]; in int nxt(int u) { return (u==n)?1:u+1; } in int lst(int u) { return (u==1)?n:u-1; } in int op(int type) { For(i,1,n) { int u=(i+type)&1; int val=(s[i]=='1'); ch[i]=u^val; } int num=0; For(i,1,n)num+=ch[i]; if(num==n)return n; num=0; For(i,1,n) { if(ch[i]&&!ch[lst(i)]) { int cnt=0; for(int j=i;ch[j];j=nxt(j))++cnt; num+=(cnt+1)/2; } } // debug; return num; } int main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); int t; t=qread(); while(t--) { n=qread(); scanf("%s",s+1); cout<<min(op(0),op(1))<<endl; } For(i,1,n) return 0; }