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

NOIP2025模拟赛23

T1 T2 T3 T4
\(\color{#52C41A} 普及+/提高\) \(\color{#3498DB} 提高+/省选-\) \(\color{#52C41A} 普及+/提高\) \(\color{#9D3DCF} 省选/NOI-\)

参赛网址:https://oj.33dai.cn/d/TYOI/contest/689d2670c5d9c2f14c2250d7

T2,T4未完成搭建

T1 粉丝[2022NOIP模拟赛T1]

题目传送门

题目难度:\(\color{#52C41A} 普及+/提高\)

算法标签:数据结构,并查集,BFS

思路

::cute-table{tuack}

测试点编号 \(p \leq\) \(t \leq\) \(k \leq\) 时限
\(1 \sim 7\) \(10^5\) \(10^3\) < \(100ms\)
\(8 \sim 10\) \(10^6\) ^ ^ ^
\(11 \sim 30\) \(10^{18}\) \(k\) \(10^3\) \(2000ms\)
\(31\) ^

赛后添加了一组 hack(31) 数据

首先考虑测试点 \(1 \sim 10\)

我们可以轻松考虑到动态规划,\(dp_i\) 表示 \(p=i\) 时的答案。

\(dp_i=\min(dp_i,dp_j) \forall j \in [i-t,i-1]\)

\(dp_i=\min(dp_i,dp_{i \div k})\) 当且仅当 \(i\mod k =0\)

然后就可以得到 56 分。

在考虑使用单调队列优化,获得 80 分。

最后考虑贪心:

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;const int maxn=1e6+5;
int t,k,p;
int f[maxn];
deque<int> Q;signed main(){ios::sync_with_stdio(false);cin.tie(0);cin>>t>>k>>p;if (k==1)    cout<<(p-1+t-1)/t+1;else if (p<=maxn){memset(f,0x3f,sizeof(f));f[1]=1;Q.push_back(1);for (int i=2;i<=p;i++){f[i]=min(f[i],f[Q.front()]+1);if (i%k==0) f[i]=min(f[i],f[i/k]+1);while (Q.size()>0&&f[i]<=f[Q.back()])  Q.pop_back();Q.push_back(i);while (Q.size()>0&&Q.front()<=i-t)    Q.pop_front();}cout<<f[p];}else {int ans=0;while (p>=k){int d=(p%k+t-1)/t+1;ans+=d;p=(p-p%k)/k;}ans+=(p-1+t-1)/t+1;cout<<ans;}return 0;
}

T2 射击[2022NOIP模拟赛T2]

题目传送门

题目难度:\(\color{#3498DB} 提高+/省选-\)

算法标签:数据结构,树套树,STL

T3 怪物猎人[2022NOIP模拟赛T3]

题目传送门

题目难度:\(\color{#52C41A} 普及+/提高\)

算法标签:贪心,DP,二分

思路

对于此题,考虑如果同时打了2个怪:

设第一只怪是 \(a_1\),\(b_1\)

第二只是 \(a_2\),\(b_2\)

如果我想先打第一只,再打第二只,即:

\(a_1 \times b_1+(a_2+d)\times(b_2+d) \le a_2\times b_2+(a_1+d)\times(b_1+d)\)

\(a_1\times b_1+a_2\times b_2 + (a_2+b_2) \times d + d^2 \le a_2\times b_2+a_1\times b_1 + (a_1+b_1) \times d + d^2\)

化简

\((a_2+b_2) \times d \le (a_1+b_1) \times d\)

\(a_2+b_2 \le a_1+b_1\)

然后dp即可,\(dp_{i,j}\) 考虑前 \(i\) 只怪打了 \(j\) 只的最小代价。

对于每组询问直接二分。

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;const int maxn=3005;
const int inf=1e18;
int n,m,d;
struct ST{int a,b;friend bool operator < (const ST &x,const ST &y){return x.a+x.b>y.a+y.b;}
}a[maxn];
int ans[maxn];
int dp[maxn][maxn];signed main(){ios::sync_with_stdio(false);cin.tie(0); cin>>n>>m>>d;for (int i=1;i<=n;i++)  cin>>a[i].a;for (int i=1;i<=n;i++)  cin>>a[i].b;sort(a+1,a+n+1);for (int i=0;i<=n;i++){for (int j=1;j<=n;j++){dp[i][j]=inf;}}for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]+(a[i].a+d*(j-1))*(a[i].b+d*(j-1)));}}for (int i=1;i<=n;i++)  ans[i]=dp[n][i];for (int i=1;i<=m;i++){int hp;cin>>hp;int t=lower_bound(ans+1,ans+n+1,hp)-ans-1;cout<<t<<" ";}return 0;
}

T4 树上异或路径[2022NOIP模拟赛T4]

题目传送门

题目难度:\(\color{#9D3DCF} 省选/NOI-\)

算法标签:贪心,启发式合并

http://www.hskmm.com/?act=detail&tid=19368

相关文章:

  • step
  • 2025 呼和浩特店推荐:丽格门窗,用 20 年技术沉淀守护家的温度
  • 深入解析:浏览器端音视频处理新选择:Mediabunny 让 Web 媒体开发飞起来
  • 2025 宁波门窗店推荐:丽格门窗,甬城品质家居的安心之选
  • 2025 贵阳门窗店优选:丽格门窗,用 20 年匠心适配高原宜居需求
  • 2025 济南门窗店选购指南:丽格门窗凭硬实力圈粉品质家庭
  • “鹏云杯”第十二届山东省大学生网络安全技能大赛 -- Crypto -- WriteUp
  • 服务器系统时间不对?Linux系统时间修改与同步全面指南
  • 9/27
  • 2025 常熟门窗店优选:丽格门窗,20 年技术沉淀的品质之选
  • 2025上海门窗店选购选丽格!20 年系统门窗经验,徐汇宜山路店品质之选
  • 实用指南:Apache、Nginx 和 Tomcat 的区别
  • python+uniapp基于微信小程序美食点餐实用的系统
  • JavaDoc
  • parted command for linuxg
  • 如何在不绑定Apple账号的情况下备份florr.io
  • AI智能体框架怎么选?7个主流工具详细对比解析
  • 原创OI试题 - L
  • 《深入浅出WPF》:8.3.2 自定义路由事件 事件注册类型为 EventHandlerReportTimeEventArgs,但.NET 事件包装器类型为 RoutedEventHandler
  • day 6
  • 2025 自动售货机工厂推荐 配备 Bystronic 激光切割机,快速周转准时交货
  • 7.WPF 的 TextBox 和 TextBlock 控件 - 实践
  • 从中序与后序遍历序列构建二叉树的迭代解法
  • 安装 HuggingFace datasets 模块、包、库
  • 使用 SignalR 向前端推送图像
  • 隐私保护与联邦学习文献阅读
  • Java实习模拟面试|离散数学|概率论|金融英语|数据库实战|职业规划|期末冲刺|今日本科计科要闻速递:技术分享与学习指南 - 实践
  • 学术写作
  • 2025.9.27
  • 9.27(课后作业