【比賽記錄】2025CSP-S模擬賽1
A. Alice 和璀璨花
做法和正常 LIS 類似。設 \(dp_{i,j}\) 表示在前 \(i\) 個中選 \(j\) 個的最小結尾顯然對于相同的 \(i\)，\(dp\) 值單調遞增。二分出 \(dp_{i-1}\) 中第一個 \(\ge i\) 的位置 \(k\)。對于 \([0,k-1]\) 的部分，顯然不用轉移；對于 \([k+1,n]\) 的部分，\(a_i\) 顯然不可能大于 \(dp\times b\)。于是只在 \(k\) 處做轉移即可。滾掉一維，空間復雜度 \(O(n)\)，時間復雜度 \(O(n\log n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define lwrb lower_bound
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e6+5;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n;
ll a[maxn],b[maxn],dp[maxn];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
freopen("alice.in","r",stdin);
freopen("alice.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
memset(dp,0x3f,sizeof dp);
dp[0]=0;
for(int i=1,tmp;i<=n;i++){
tmp=lwrb(dp,dp+n+1,a[i])-dp;
if(dp[tmp-1]*b[tmp-1]<a[i]){
dp[tmp]=a[i];
}
}
for(int i=n;i;i--){
if(dp[i]<inf){
cout<<i;
return 0;
}
}
return 0;
}
}
int main(){return asbt::main();}
B. Bob 與幸運日
\(n\le 10^3\) 的點直接枚舉。
式子：
\[\begin{cases}
\begin{align}
&(x-1)d+y\equiv a&\pmod w&\\
&(y-1)d+x\equiv b&\pmod w&
\end{align}
\end{cases}
\]
\((1)+(2)\)，得
\[(x+y)(d+1)\equiv a+b+2d\pmod w
\]
\((1)-(2)\)，得
\[(x-y)(d-1)\equiv a-b\pmod w
\]
移項求逆元即可（如果有逆元）。數據隨機那個包就是給這個的。
50pts Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
int T,m,d,w,a,b;
il int qpow(int x,int y,int p){
int res=1;
while(y){
if(y&1){
(res*=x)%=p;
}
(x*=x)%=p,y>>=1;
}
return res;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
freopen("bob.in","r",stdin);
freopen("bob.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>m>>d>>w>>a>>b;
int n=min(m,d);
if(n<=1e3){
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(((i-1)*d+j-1)%w==a-1&&((j-1)*d+i-1)%w==b-1){
ans++;
}
}
}
cout<<ans<<"\n";
continue;
}
int p=(a+b+2*d)%w*qpow(d+1,w-2,w)%w;
int q=(b-a)%w*qpow(d-1,w-2,w)%w;
(p+=w)%=w,(q+=w)%=w;
int x=(p+q)%w*qpow(2,w-2,w)%w;
int y=(p-q)%w*qpow(2,w-2,w)%w;
(x+=w)%=w,(y+=w)%=w;
int nx=n/w,ny=n/w;
if(n%w>=x){
nx++;
}
if(n%w>=y){
ny++;
}
cout<<nx*ny<<"\n";
}
return 0;
}
}
signed main(){return asbt::main();}
浙公網安備 33010602011771號