【比賽記錄】2025CSP-S模擬賽46
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 100 | 68 | 32 | 30 | 230 | 8/25 |
A. 雷暴（storm）
對每種顏色記錄最左/右/上/下即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,m,kk;
int lf[maxn],rt[maxn],up[maxn],dw[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>kk;
memset(lf,0x3f,sizeof(lf));
memset(up,0x3f,sizeof(up));
for(int i=1,x;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>x;
lf[x]=min(lf[x],j),rt[x]=max(rt[x],j);
up[x]=min(up[x],i),dw[x]=max(dw[x],i);
}
}
for(int i=1;i<=kk;i++){
if(!rt[i]){
cout<<0<<'\n';
}
else{
int t=max(dw[i]-up[i]+1,rt[i]-lf[i]+1);
cout<<t*t<<'\n';
}
}
return 0;
}
}
int main(){return asbt::main();}
B. 神力 (god)
不得不寫寫我考場上的做法了。
首先考慮一個 DP：\(f_{i,j}\) 表示到第 \(i\) 步走到了 \(j\) 的概率，于是轉移是顯然的。但是我們發現這樣會算重，因為如果在第 \(i\) 步到了 \(j\)，那么在第 \(k>i\) 步到 \(j\) 的概率就不應該算入了。于是我們再定義 \(g_{i,j,k}\) 表示第 \(i\) 步在 \(0\)，第 \(j\) 步在 \(k\) 的概率。于是我們可以統計答案，但是是 \(O(n^3)\) 的。拼幾個特殊性質可以得 \(68pts\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int mod=1e9+7;
il int pls(int x,int y){
return x+y<mod?x+y:x+y-mod;
}
il void add(int &x,int y){
x=pls(x,y);
}
il int sub(int x,int y){
return x<y?x-y+mod:x-y;
}
il void mns(int &x,int y){
x=sub(x,y);
}
il int qpow(int x,int y=mod-2){
int res=1;
while(y){
if(y&1){
res=res*1ll*x%mod;
}
x=x*1ll*x%mod,y>>=1;
}
return res;
}
int n,p,q,a[5005],b[10005],g[305][305][605],f[305][605];
int C[5005][5005],pp[5005],qq[5005];
il bool chk1(){
for(int i=1;i<=n;i++){
if(a[i]==1){
return 0;
}
}
return 1;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>p;
for(int i=1;i<=n;i++){
cin>>a[i];
}
if(p==100){
for(int i=1;i<=n;i++){
cout<<0<<' ';
}
cout<<1<<' ';
for(int i=1;i<=n;i++){
cout<<0<<' ';
}
return 0;
}
if(p==0){
int cur=n+1;
b[n+1]=1;
for(int i=1;i<=n;i++){
cur+=a[i];
b[cur]=1;
}
for(int i=1;i<=2*n+1;i++){
cout<<b[i]<<' ';
}
return 0;
}
p=p*1ll*qpow(100)%mod,q=(1-p+mod)%mod;
if(chk1()){
for(int i=0;i<=n;i++){
C[i][0]=1;
for(int j=1;j<=i;j++){
C[i][j]=pls(C[i-1][j-1],C[i-1][j]);
}
}
pp[0]=qq[0]=1;
for(int i=1;i<=n;i++){
pp[i]=pp[i-1]*1ll*p%mod;
qq[i]=qq[i-1]*1ll*q%mod;
}
for(int i=n;i;i--){
int ans=0;
for(int j=i;j<=n;j++){
ans=(C[j-1][i-1]*1ll*pp[j-i]%mod*qq[i]+ans)%mod;
}
cout<<ans<<' ';
}
cout<<1<<' ';
for(int i=1;i<=n;i++){
cout<<0<<' ';
}
return 0;
}
for(int i=0;i<=n;i++){
g[i][i][n+1]=1;
for(int j=i+1;j<=n;j++){
for(int k=1;k<=2*n+1;k++){
g[i][j][k]=(g[i][j-1][k]*1ll*p+g[i][j-1][k-a[j]]*1ll*q)%mod;
}
}
}
f[0][n+1]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=2*n+1;j++){
f[i][j]=(f[i-1][j]*1ll*p+f[i-1][j-a[i]]*1ll*q)%mod;
}
}
for(int i=1;i<=2*n+1;i++){
int ans=0;
for(int j=0;j<=n;j++){
for(int k=0;k<j;k++){
mns(f[j][i],f[k][i]*1ll*g[k][j][n+1]%mod);
}
add(ans,f[j][i]);
}
cout<<ans<<' ';
}
return 0;
}
}
int main(){return asbt::main();}
考慮正解，我們發現那個 \(f\) 的 DP 不好統計答案的原因就是前面的操作會影響后面，這提示我們倒過來 DP。設 \(f_{i,j}\) 表示經過后 \(i\) 個操作走到了離原點距離為 \(j\) 的概率。此時唯一受影響的就是 \(j=0\) 的情況，強制令 \(f_{i,0}=1\) 即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=5e3+5,mod=1e9+7;
il int pls(int x,int y){
return x+y<mod?x+y:x+y-mod;
}
il void add(int &x,int y){
x=pls(x,y);
}
il int sub(int x,int y){
return x<y?x-y+mod:x-y;
}
il void mns(int &x,int y){
x=sub(x,y);
}
il int qpow(int x,int y=mod-2){
int res=1;
while(y){
if(y&1){
res=res*1ll*x%mod;
}
x=x*1ll*x%mod,y>>=1;
}
return res;
}
int n,p,q,a[maxn],f[maxn][maxn<<1];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>p;
p=p*1ll*qpow(100)%mod,q=sub(1,p);
for(int i=1;i<=n;i++){
cin>>a[i];
}
f[n+1][n+1]=1;
for(int i=n;i;i--){
for(int j=1;j<=2*n+1;j++){
f[i][j]=(f[i+1][j]*1ll*p+f[i+1][j-a[i]]*1ll*q)%mod;
}
f[i][n+1]=1;
}
for(int i=1;i<=2*n+1;i++){
cout<<f[1][i]<<' ';
}
return 0;
}
}
int main(){return asbt::main();}
C. 之緣千里（fate）
Lemma：括號序列合法等價于左括號位置序列能被 \(\{1,3,5,\dots,2n-1\}\) 偏序。
證明顯然。于是我們即需要將所有左括號的位置與 \(\{1,3,5,\dots,2n-1\}\) 進行匹配。具體地，如果 \(i\) 的答案還沒有確定，那么考察 \(i\) 對應的右面那個點 \(nxt_i\) 能否做左括號。若是，則從可以進行匹配的位置中選擇兩個最小的進行匹配。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define lwrb lower_bound
using namespace std;
namespace asbt{
const int maxn=2e6+5;
int n,a[maxn],b[maxn],c[maxn];
set<int> S;
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1,x;i<=n<<1;i++){
cin>>x;
if(a[x]){
b[a[x]]=i;
}
else{
a[x]=i;
}
}
for(int i=1;i<=n<<1;i+=2){
S.insert(i);
}
for(int i=1;i<=n<<1;i++){
if(b[i]&&S.size()&&*S.rbegin()>=b[i]){
S.erase(S.lwrb(b[i]));
if(*S.rbegin()>=i){
S.erase(S.lwrb(i));
}
else{
cout<<":(";
return 0;
}
c[i]=c[b[i]]=1;
}
}
if(S.size()){
cout<<":(";
return 0;
}
for(int i=1;i<=n<<1;i++){
cout<<(c[i]?'(':')');
}
return 0;
}
}
int main(){return asbt::main();}
D. 怒氣沖天（rectangle）
考慮將相交的矩形連邊，于是要求互無連邊的三元組 \((a,b,c)\) 的數量。
考慮容斥，設恰有一條連邊的三元組數量為 \(c1\)，類似地有 \(c2\) 和 \(c3\)，于是答案即為 \({n\choose3}-c1-c2-c3\)。
設每個點的度數為 \(d_i\)。于是有 \(\sum_{i=1}^{n}d_i(n-2)=2c1+4c2+6c3\)，\(sum_{i=1}^{n}{d_i\choose2}=c2+3c3\)，于是我們可以得到 \(c1+c2\)。于是只需求 \(d_i\) 和 \(c3\)。
考慮掃描線。對于 \(d_i\)，其值就等于上邊下面的下邊個數減去下邊下面的上邊個數。而關于線段下面的線段數量，其值又等于右端點左邊的左端點個數減去左端點左邊的右端點個數，開四個樹狀數組維護即可。
對于 \(c3\)，我們考慮在三個矩形中在 \(x1\) 最大的那個計算貢獻。此時由于 \(x1_b\le x1_a\le x2_b\)，\(x1_c\le x1_a\le x2_c\)，我們只需要滿足 \(y\) 坐標相交。假設 \(x1_a\) 以下與 \(a\) 相交的矩形有 \(cnt\) 個，考慮再容斥，貢獻即為 \({cnt\choose2}\) 減去 \(a\) 與 \(b\) 和 \(c\) 分別相交但 \(b\) 和 \(c\) 不相交的數量。不妨令 \(y2_b<y1_c\)，于是有 \(y1_a\le y2_b<y1_c\le y2_a\)，再用線段樹維護即可。具體地，對于每個區間維護左端點數、右端點數和右端點小于左端點的二元組數即可。時間復雜度線性對數。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define lwrb lower_bound
using namespace std;
namespace asbt{
const int maxn=4e5+5;
int n,lsh[maxn],tot,cnt,d[maxn],ans;
struct node{
int x,y1,y2,typ,id;
node(int x=0,int y1=0,int y2=0,int typ=0,int id=0)
:x(x),y1(y1),y2(y2),typ(typ),id(id){}
il bool operator<(const node &b)const{
return x<b.x||x==b.x&&typ<b.typ;
}
}a[maxn];
struct BIT{
#define lowbit(x) (x&-x)
int tr[maxn];
il void add(int p,int v){
for(;p<=tot;p+=lowbit(p)){
tr[p]+=v;
}
}
il int query(int p){
int res=0;
for(;p;p-=lowbit(p)){
res+=tr[p];
}
return res;
}
#undef lowbit
};
struct DS{
BIT L,R;
il void add(int l,int r,int v){
L.add(l,v),R.add(r,v);
}
il int query(int l,int r){
return L.query(r)-R.query(l-1);
}
}D1,D2,D3;
struct seg{
int ll,rr,sum;
seg(int ll=0,int rr=0,int sum=0)
:ll(ll),rr(rr),sum(sum){}
il seg operator+(const seg &x)const{
return seg(ll+x.ll,rr+x.rr,sum+x.sum+rr*x.ll);
}
};
struct STR{
seg tr[maxn<<2];
#define lid id<<1
#define rid id<<1|1
#define ll(id) tr[id].ll
#define rr(id) tr[id].rr
#define sum(id) tr[id].sum
il void pushup(int id){
tr[id]=tr[lid]+tr[rid];
}
il void addl(int id,int l,int r,int p,int v){
if(l==r){
ll(id)+=v;
return ;
}
int mid=(l+r)>>1;
if(p<=mid){
addl(lid,l,mid,p,v);
}
else{
addl(rid,mid+1,r,p,v);
}
pushup(id);
}
il void addr(int id,int l,int r,int p,int v){
if(l==r){
rr(id)+=v;
return ;
}
int mid=(l+r)>>1;
if(p<=mid){
addr(lid,l,mid,p,v);
}
else{
addr(rid,mid+1,r,p,v);
}
pushup(id);
}
il seg query(int id,int L,int R,int l,int r){
if(L>=l&&R<=r){
return tr[id];
}
int mid=(L+R)>>1;
if(r<=mid){
return query(lid,L,mid,l,r);
}
if(l>mid){
return query(rid,mid+1,R,l,r);
}
return query(lid,L,mid,l,r)+query(rid,mid+1,R,l,r);
}
#undef lid
#undef rid
#undef ll
#undef rr
#undef sum
}S;
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1,x1,x2,y1,y2;i<=n;i++){
cin>>x1>>x2>>y1>>y2;
lsh[++tot]=y1,lsh[++tot]=y2;
a[++cnt]=node(x1,y1,y2,0,i);
a[++cnt]=node(x2,y1,y2,1,i);
}
sort(lsh+1,lsh+tot+1);
tot=unique(lsh+1,lsh+tot+1)-lsh-1;
for(int i=1;i<=cnt;i++){
a[i].y1=lwrb(lsh+1,lsh+tot+1,a[i].y1)-lsh;
a[i].y2=lwrb(lsh+1,lsh+tot+1,a[i].y2)-lsh;
}
sort(a+1,a+cnt+1);
ans=n*(n-1)*(n-2)/6;
for(int i=1,l,r,typ,id;i<=cnt;i++){
l=a[i].y1,r=a[i].y2,typ=a[i].typ,id=a[i].id;
if(typ){
D2.add(l,r,1);
d[id]+=D1.query(l,r)-1;
S.addl(1,1,tot,l,-1);
S.addr(1,1,tot,r,-1);
D3.add(l,r,-1);
}
else{
D1.add(l,r,1);
d[id]-=D2.query(l,r);
int tmp=D3.query(l,r);
ans-=tmp*(tmp-1)/2-S.query(1,1,tot,l,r).sum;
S.addl(1,1,tot,l,1);
S.addr(1,1,tot,r,1);
D3.add(l,r,1);
}
}
int res=0;
for(int i=1;i<=n;i++){
res+=(n-2)*d[i]-d[i]*(d[i]-1);
}
cout<<ans-res/2;
return 0;
}
}
signed main(){return asbt::main();}
浙公網安備 33010602011771號