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

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

总结

T1

考场上很快写出了正解,没有问题

T2

考场上很快写出了正解,但提交时交了两边,故0分

T3

考场上很快写出了正解,没有问题

T4

考场上很快写出了部分分,拿满了,没有问题

题解

T1

照题意模拟即可

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
string f(string s,int x)
{int n=s.size()-1;int d=(s[x]>='5');for(int i=x;i<=n;i++) s[i]='0';for(int i=x-1;i>1;i--){int ns=s[i]-'0'+d;if(ns<=9) d=0,s[i]=ns+'0';else d=1,s[i]=ns-10+'0';}if(d==1&&s[1]=='9') s.insert(1,"1"),s[2]='0';else if(d==1) s[1]=s[1]+1;return s;
}
signed main()
{freopen("Number.in","r",stdin);freopen("Number.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int t;cin>>t;while(t--){int n;cin>>n;string s;cin>>s;cout<<s;s=' '+s;int fds=1;for(int i=n;i>fds;i--){s=f(s,i);if(s.size()>n+1&&fds==1) fds=2,i++;cout<<" ->"<<s;}cout<<endl;}return 0;
}

T2

因为是纵切,所以看其对称区域是否有即可

多测不清空,亲人两行泪

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
map<pair<int,int>,int> mp;
signed main()
{freopen("Color.in","r",stdin);freopen("Color.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int t;cin>>t;while(t--){mp.clear();int n,m,k;cin>>k>>n>>m;for(int i=1;i<=k;i++){int tmp;cin>>tmp;int x=(tmp+m-1)/m,y=tmp-m*(x-1);mp[{x,y}]=1;}int f=1;for(auto x:mp){pair<int,int> y=x.first;y.second=m-y.second+1;if(mp.find(y)==mp.end()){f=0;break;}}if(f) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}

T3

如果将题目弱化成模板LIS,大家一定会做

其实对于本题是一个道理,只是更新时要新开一个临时数组即可

要用二分法,因为总量为 \(10^6\) 的量级

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=5e3+5;
int dp[maxn],a[maxn][maxn],now[maxn];
signed main()
{freopen("yet.in","r",stdin);freopen("yet.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n,m,ans=0;cin>>m>>n;for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];for(int i=1;i<=n;i++) dp[i]=-1;for(int i=1;i<=n;i++){int f=0;for(int j=1;j<=n;j++) now[j]=inf;for(int j=1;j<=m;j++){if(dp[ans]<a[i][j]) f=1,dp[ans+1]=now[ans+1]=min(now[ans+1],a[i][j]);else{int p=lower_bound(dp+1,dp+1+ans,a[i][j])-dp;now[p]=min(now[p],a[i][j]);}}if(f) ans++;for(int j=1;j<=ans;j++) dp[j]=min(dp[j],now[j]);}cout<<ans;return 0;
}

T4

由于是第 \(k\) 大,而求第 \(k\) 大其实只有两种:

  • 枚举
  • 二分

显然这道题是二分,因为 \(k\) 太大了

那么对于二分答案,必然二分“答案”(v),即求有多少个数对 \((i,j),1\le i\le j\le n\),满足 \(\frac{x_i\times y_i+x_j\times y_j}{x_i+ x_j}\ge v\)

那么将原式变一下,即:

\[\frac{x_i\times y_i+x_j\times y_j}{x_i+ x_j}\ge \frac{v}{1} \]

利用交叉相乘得

\[x_i\times y_i+x_j\times y_j\ge (x_i+ x_j)\times v \]

利用乘法分配律得:

\[x_i\times y_i+x_j\times y_j\ge x_i\times v+x_j\times v \]

再移个项:

\[x_i\times y_i-x_i\times v\ge x_j\times v-x_j\times y_j \]

那么直接对比即可

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
#define exp 1e-3
using namespace std;
const int maxn=2e5+5;
int a[maxn],c[maxn],n,k;
double p[maxn],q[maxn];
bool check(double t)
{int j=0,ans=0;for(int i=1;i<=n;i++){double x=a[i]*1.0*c[i],y=t*a[i]; p[i]=x-y;q[i]=y-x; if(q[i]-p[i]<exp) ans--;}sort(p+1,p+n+1);sort(q+1,q+n+1);for(int i=1;i<=n;i++){while((q[j+1]-p[i])<exp&&j+1<=n) j++;ans+=j;}return (ans/2<k);
}
signed main()
{freopen("Function.in","r",stdin);freopen("Function.out","w",stdout);cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i]>>c[i];double l=0,r=1e18,mid;while((r-l)>exp){double mid=(l+r)/2;if(check(mid)) r=mid;else l=mid;}printf("%.3lf",l);return 0;
}

T5

有一个道理:断开一个点和去掉以这个点为根的子树是差不多的

有一个发现:\(0\le a_i\le 2\)!

有一个观察:如果去掉一个叶子,那么原树不会断开

有一个公理:如果有一棵大小大于2的数,叶子节点移动大于2

合起来就会发现:我每次通过若干去掉叶子移动能使原树的权值和减0或2

那么我直接判奇偶性,若当前子树大于k且奇偶性相同,则答案加一并断开即可

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=1e6+5;
vector<int> g[maxn];
int dp[maxn][2],ans,n,k,a[maxn];
void dfs(int x,int fa)
{dp[x][0]=-inf;dp[x][1]=-inf;dp[x][a[x]%2]=a[x];for(auto to:g[x]){if(fa==to) continue;dfs(to,x);int s[2]={};s[0]=max(dp[x][0]+dp[to][0],dp[x][1]+dp[to][1]);s[1]=max(dp[x][1]+dp[to][0],dp[to][1]+dp[x][0]);dp[x][0]=s[0],dp[x][1]=s[1];}if(dp[x][k%2]>=k){ans++;dp[x][0]=0;dp[x][1]=-inf;}dp[x][0]=max(dp[x][0],0ll);
}
signed main()
{freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int t;cin>>t;while(t--){cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i],g[i].clear();for(int i=1;i<n;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}ans=0;dfs(1,-1);cout<<ans<<endl;}return 0;
}
http://www.hskmm.com/?act=detail&tid=23397

相关文章:

  • LSTM
  • 调和级数
  • 【实验报告】华东理工大学随机信号处理实验报告 - 详解
  • 页面置换算法
  • 推进电子设计革新:仿真(Emulation)如何引领下一代验证方式
  • AT_abc309_g [ABC309G] Ban Permutation
  • 在Mac上运行Windows 365的完整指南
  • 摩刻S10 动感单车 速度传感器故障及更换!
  • 2025盐酸优质厂家权威推荐榜:高纯度盐酸的品质之选
  • 2025硫酸优质厂家权威推荐榜:高品质与强供应口碑之选
  • 2025冰乙酸供应厂家权威推荐榜:品质卓越与市场口碑双重保障
  • 工业氨水优质厂家推荐:实力制造商深度解析与选购指南
  • 2025液碱厂家权威推荐榜:实力供应商深度解析与选择指南
  • 2025片碱厂家权威推荐榜:优质供应与实力生产口碑之选
  • 2025阳离子聚丙烯酰胺厂家推荐榜:高效絮凝与定制解决方案
  • 2025硫铵厂家权威推荐榜:实力生产与优质供应口碑之选
  • 2025年硫酸铵厂家权威推荐榜:实力生产与优质供应口碑之选
  • 2025年硫化钠厂家权威推荐榜:优质供应商与实力制造商精选
  • 2025 年热压机厂家 TOP 企业品牌推荐排行榜,深度剖析河北热压机,廊坊热压机,霸州热压机推荐这十家公司!
  • 【Anthropic好文】AI 代理的高效上下文工程
  • 请求分页管理方式
  • vim中leader和localleader对比
  • 详细介绍:[论文阅读] AI + 软件工程 | 从“事后补救”到“实时防控”,SemGuard重塑LLM代码生成质量
  • 2025 年转基因小鼠公司 TOP 企业品牌推荐排行榜,传统 KO 转基因小鼠,条件性 cKO 转基因小鼠,ROSA26 位点基因 KI 小鼠,Tol2 转基因小鼠模型,点突变敲入转基因小鼠公司推荐!
  • 2025 年人源化小鼠公司 TOP 企业品牌推荐排行榜,基因,免疫系统,抗体,临床前 CRO 型,基因,精准医疗型,创新型人源化小鼠,人源化小鼠动物模型公司推荐!
  • 国产GPU/AI芯片第三篇 - 沐曦
  • 2025防撞护栏厂家 TOP 企业品牌推荐排行榜,铝合金,Q235 桥梁,Q355B 桥梁,景观桥梁,灯光桥梁,河道桥梁,公路桥梁,喷塑桥梁,道路桥梁防撞护栏公司推荐!
  • 摩尔线程之后,看燧原科技,相关公司梳理
  • 读人形机器人29未来10年
  • 01分数规划