资讯详情

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-\)

算法标签：贪心，启发式合并