2023.10.1
T1：
思路
- 展环为链
- 用前缀和记录异或和
- \(O(1)\) 查询
T2
思路
按题意模拟即可
T3
思路
\(O(\sqrt{n})\) 枚举b1的因子，并判断
T4
思路
dp
30pts
dp[i]表示到达i时最少的踩到的石子数
100pts
因为\(m \le 100\) 且 \(l \le 10^9\) 所以石子与石子之间的距离很远，考虑离散化
代码
#include<bits/stdc++.h>
using namespace std;
int dp[202500];
bool is[202500];//判断位置上是否有石子
int a[202500];
int l,s,t,m,len;
int main(){
cin >> l >> s >> t >> m;
for(int i=1;i<=m;i++) cin >> a[i];
sort(a+1,a+1+m);
for(int i=1;i<=m;i++){
while(a[i]-a[i-1]>2025 ) a[i]-=2025;
is[a[i]]=true;
len=a[i];
}
memset(dp,0x3f,sizeof dp);
dp[0]=0;
for(int i=1;i<=len+t;i++)
for(int j=s;j<=t;j++)
if(i-j>=0)
dp[i]=min(dp[i],dp[i-j]+is[i]);
int ans=INT_MAX;
for(int i=len;i<=len+t;i++)
ans=min(ans,dp[i]);
cout << ans;
return 0;
}