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

2025 --【J+S 二十连测】-- 第四套 总结

总结

T1

考场上很快想出了正解,并打出了代码,没什么问题

T2

考场上很快就打出了正解,但是由于精度问题,导致失分

T3

考场上没有想到解法,打了个部分分,但是挂0

T4

考场上打了个部分分,哪全了

题解

T1

不难发现,修改的方式一定如下:

  1. 确定分界线
  2. 分界线以左的 B 改成 A
  3. 分界线以右的 A 改成 B

枚举分界线,预处理前缀 B 的个数,后缀 A 的个数即可

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=1e6+5;
int a[maxn],b[maxn];
signed main()
{freopen("string.in","r",stdin);freopen("string.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);string s;cin>>s;int n=s.size(),ans=inf;s=' '+s;for(int i=1;i<=n;i++) a[i]=a[i-1]+(s[i]=='B');for(int i=n;i>=1;i--) b[i]=b[i+1]+(s[i]=='A');for(int i=1;i<=n;i++) ans=min({ans,b[i]+a[i-1],a[i]+b[i+1]});cout<<ans;return 0;
}

T2

令我想骂人的题面

由于题面过于不是人看难懂,在重说一下:

\(n\) 个人,每个人有一个恒定的速度和初始位置,求让所有人到一个点时,到底最晚的人最早到的时间


考虑二分答案,二分最晚的人到的时间,那么每个人在规定的时间内跑的距离一定是一个区间(大不了原地等)看是否存在一个点,使得所有人都能到,有就往小找,并记录答案,没有就往大找即可

十年OI一场空,精度不够见祖宗

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
const double eps=1e-6; 
int x[maxn],v[maxn],n;
double l[maxn],r[maxn];
bool check(double tmp)
{for(int i=1;i<=n;i++) l[i]=x[i]-v[i]*tmp*1.0,r[i]=x[i]+v[i]*tmp*1.0;double lt=0,rt=inf;for(int i=1;i<=n;i++) lt=max(lt,l[i]),rt=min(rt,r[i]);return rt-lt>=eps;
}
signed main()
{freopen("meeting.in","r",stdin);freopen("meeting.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>x[i];for(int i=1;i<=n;i++) cin>>v[i];double l=0,r=1e9,ans=inf;while(r-l>eps){double mid=(l+r)/2;if(check(mid)==0) l=mid;else ans=mid,r=mid;}printf("%.5lf",ans);return 0;
}

T3

考虑将题目弱化一下,变成不能建道路,那么此时就是先判连通性,即那个点能到那个点,在枚举一个点,看有那些点满足两个点能互相到的,统计后取最大即可

现在考虑原题,不难发现:如果我建了一条边的反边,那么就相当于将两点合起来,那么接下来同上即可

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2000+5,maxm=40005;
vector<int> g[maxn];
int vis[maxn],ans=-inf,n,m,f[maxn][maxn],u[maxm],v[maxm];
void dfs(int x,int s)
{f[s][x]=1;for(auto to:g[x]) if(!f[s][to]) dfs(to,s);
}
signed main()
{freopen("travel.in","r",stdin);freopen("travel.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n>>m;for(int i=1;i<=m;i++){cin>>u[i]>>v[i];g[u[i]].push_back(v[i]);}for(int i=1;i<=n;i++) dfs(i,i);for(int x=1;x<=m;x++){int i=u[x],j=v[x],sum=0;for(int k=1;k<=n;k++) if((f[i][k]||f[j][k])&&(f[k][j]||f[k][i])) sum++;ans=max(ans,sum);}if(!m) ans=1;cout<<ans;return 0;
}

T4

先考虑 \(O(t^4)\) 的做法:

对于一给正方形,只要三个信息就能得到,即:上边的位置和左,右边的位置

还有一个观察:题目求的正方形的左上角一定卡在障碍物或边界上

于是,在四个角加障碍物,枚举三边在判合法即可


\(O(t^3)\) 的做法

发现,其实我只要左,上边的位置即可,右,下边可以在判合法找到,于是枚举上,左边即可

代码(\(O(t^3)\)

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
int x[maxn],y[maxn],dx[maxn],dy[maxn];
signed main()
{freopen("discover.in","r",stdin);freopen("discover.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n,t,ans=0;cin>>n>>t;for(int i=1;i<=t;i++) cin>>dx[i]>>dy[i],x[++x[0]]=dx[i]+1,y[++y[0]]=dy[i]+1;x[++x[0]]=1,y[++y[0]]=1;for(int i=1;i<=x[0];i++){for(int j=1;j<=y[0];j++){int a=x[i],b=y[j],sum=min(n-a+1,n-b+1);for(int k=1;k<=t;k++){if(dx[k]>=a&&dy[k]>=b) sum=min(sum,max(dx[k]-a,dy[k]-b));}ans=max(ans,sum);}}cout<<ans;return 0;
}

T5

考虑40分的做法:

发现以前做过类似的题目,不难发现一个值的贡献是 \(C_a^b\) 的,又通过提示卢卡斯定理得 \(C_n^m \mod 2=(n\& m=m)\)

故求二进制子集即可


100分的做法

不难发现:如果知道了某一行,那么后面的行无需看第1行,直接看那一行即可,故预处理前512行即可,后续同上

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=1e5+5;
int a[512][maxn];
int f(int x,int y)
{if(x<512) return a[x][y];else{int len=1<<(int)log2(x);return f(x-len,y)^f(x-len,y+len);}
}
signed main()
{freopen("xor.in","r",stdin);freopen("xor.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n,q;cin>>n>>q;for(int i=0;i<n;i++) cin>>a[0][i];for(int i=1;i<512;i++) for(int j=0;j<n-i;j++) a[i][j]=a[i-1][j]^a[i-1][j+1];while(q--){int x,y;cin>>x>>y;cout<<f(x,y)<<endl;}return 0;
}
http://www.hskmm.com/?act=detail&tid=23143

相关文章:

  • Websocket+cpolar:如何轻松实现服务远程访问? - 教程
  • 如何用C语言实现5种基本的排序算法
  • 函数-装饰器基础知识+推导式
  • VUE - 实战 2
  • QBXT2025S刷题 Day1
  • 2025多校冲刺CSP模拟赛1(螳臂复活祭)
  • mobvista三月之旅(In Peking)
  • 大学生HTML期末大作业——HTML+CSS+JavaScript购物商城(草莓) - 指南
  • P6782 [Ynoi2008] rplexq
  • AT_agc040_b [AGC040B] Two Contests
  • AT_arc084_b [ABC077D] Small Multiple 题目分析
  • 287. 寻找重复数
  • 福州市 2025 国庆集训 Day2 前三题题解
  • 2025 年马赛克厂家 TOP 企业品牌推荐排行榜,陶瓷,游泳池,喷墨,冰裂,拼花,防滑,复古,家装马赛克推荐这十家公司!
  • oppoR9m刷Linux系统: 手动备份系统与基带IMEI/NVRAM/QCN
  • 原来你是这样的claude code aciton:没想象中好
  • 实用指南:【Python】正则表达式
  • FlareOn1 -- 5get_it
  • 2025 年阀门厂家 TOP 企业品牌推荐排行榜,管道阀门,气动,调节,电动执行器,生产,电磁,不锈钢,进口,耐高温阀门推荐这十家公司
  • 深入解析:Ceph 分布式存储学习笔记(二):池管理、认证和授权管理与集群配置(下)
  • tcp与udp 协议 - 摘星
  • 赛前训练4 extra 字典树
  • CF1450E Capitalism
  • 二分图最大匹配 匈牙利算法
  • 2025 年脱硫剂厂家 TOP 企业品牌推荐排行榜,氧化铁,羟基氧化铁,常温氧化铁,沼气,天然气,煤气,煤层气,液化气,二氧化碳,氨气脱硫剂公司推荐
  • 2025 年砝码厂家 TOP 企业品牌推荐排行榜,不锈钢,标准,校准,天平,无磁,锁型,蓬莱,铸铁,定制,单双钩砝码公司推荐!
  • Java 在Word 文档中添加批注:高效文档协作的利器 - 指南
  • 2025雨棚生产厂家 TOP 企业品牌推荐排行榜,西安,陕西,西北推拉雨棚,推拉,移动,活动,户外,电动伸缩雨棚推荐这十家公司!
  • 关于整除分块
  • 2025 年木工机械设备厂家 TOP 企业品牌推荐排行榜,深度剖析木工机械设备推荐这十家公司!