当前位置： 首页 > news >正文

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

news 2025/8/2 20:09:45

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

1. 1002 小抹爱锻炼

image

 

知识点：贪心上下界判断

计算出训练次数的下限和上限，判断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;
}
View Code

 

 

2. 1004 三带一

image

 

知识点：二分

上界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)>=minlif (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;
}
View Code

 

 

3. 1007 性质不同的数字

image

 

知识点：扫描线+哈希

可以给所有的线段一个随机值，加入(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;
}
View Code

 

 

4. 1012核心共振

image

 

知识点：坐标变换

image

 

#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;
}
View Code

 

 

5. 1008 01环

image

 

知识点：模拟分析

存在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;
}
View Code

 

 

 

http://www.wuyegushi.com/news/427.html

相关文章：

  • VMware Windows Linux Macos网盘下载
  • ZBrush 2025 中文版免费下载，附图文安装指南，小白也能快速上手！
  • k8s network
  • hyprland初尝试
  • 正则表达式 更新常用则表达式-----loading
  • 幼儿园小班线段树
  • 树02
  • 深入ADC采样
  • 学习笔记：MySQL ：eq_range_index_dive_limit参数
  • Python字符串知识点总结
  • SQL Server 2025年7月更新 - 修复 CVE-2025-49718 Microsoft SQL Server 信息泄露漏洞
  • 读书笔记：Oracle数据库内存结构：系统全局区(SGA)详解
  • 小飞标签
  • 服务器配置的精细化控制(3960)
  • TCP连接优化的实战经验(7340)
  • 家庭主妇人到中年的生活困境很难突破防
  • 中间件架构的优雅实现(0454)
  • 梦醒时分
  • Hyperlane框架最全教学(6165)
  • 并发处理能力的巅峰对决：异步编程的艺术(3501)
  • 实战项目：全栈在线群聊系统(7048)
  • HTTP响应处理的灵活设计(0782)
  • Rust异步Web框架性能突破之路(6359)
  • 服务器配置的精细化控制(7138)
  • 内存使用效率的终极对决：零拷贝技术的实战应用(0345)
  • 明源相关漏洞自查清单（2025）
  • TCP连接优化的实战经验(3513)
  • 异步编程在Web开发中的应用(3842)
  • Proxmox Backup Server 4.0 Beta - 开源企业级备份解决方案
  • Proxmox Mail Gateway 8.2 - 全面的开源邮件安全平台