| 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-\)
算法标签：贪心，启发式合并