【比賽記錄】2025CSP-S模擬賽14
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 50 | 17 | - | 20 | 87 | 5/21 |
A. 魔力屏障
區(qū)間 DP，設(shè) \(f_{l,r,x}\) 表示擊破 \([l,r]\)，向右傳遞 \(x\) 的最小花費(fèi)。轉(zhuǎn)移分為先擊破右區(qū)間再擊破左區(qū)間、用左區(qū)間的剩余擊破右區(qū)間兩種。（第二個(gè)轉(zhuǎn)移可以簡化為用 \([l,r-1]\) 擊破 \(r\)。)
（區(qū)間 DP）帶有 \(\frac{1}{8}\) 的小常數(shù)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
int n,a[75],f[75][75][155];
il void upd(int &x,int y){
x=min(x,y);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++){
cin>>a[i];
f[i][i][a[i]>>1]=a[i];
}
for(int len=2;len<=n;len++){
for(int l=1,r=len;r<=n;l++,r++){
/*bb*/
for(int x=a[r]>>1;x<=150;x++){
for(int i=l;i<r;i++){
for(int y=a[i]>>1;y<=150;y++){
upd(f[l][r][x],f[l][i][y]+f[i+1][r][x-y]);
}
}
}
for(int x=a[r-1]>>1;x<=150;x++){
upd(f[l][r][max(x,a[r])>>1],f[l][r-1][x]+max(a[r]-x,0));
}
}
}
for(int i=1;i<=n;i++){
cout<<*min_element(f[1][i],f[1][i]+151)<<" ";
}
return 0;
}
}
int main(){return asbt::main();}
B. 詭秘之主
C. 博弈
首先強(qiáng)制 \(T\) 為根。設(shè) \(f_u\) 表示在 \(u\) 的子樹中走下去再走上來的最小操作次數(shù)，通過樹形 DP 可以求出。再設(shè) \(g_u\) 表示從 \(u\) 走到根要剪掉的邊。考慮二分答案，check 出能不能在 \(mid\) 的操作次數(shù)內(nèi)使小 N 走到根即可。具體方式為刪去若進(jìn)入則必定超過 \(mid\) 的子樹，考察此時(shí)的操作次數(shù)是否夠用。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
namespace IO{
const int bufsz=1<<20;
char ibuf[bufsz],*p1=ibuf,*p2=ibuf;
#define getchar() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,bufsz,stdin),p1==p2)?EOF:*p1++)
il int read(){
char ch=getchar();
while(ch<'0'||ch>'9'){
ch=getchar();
}
int x=0;
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
#undef getchar
}
using IO::read;
const int maxn=1e6+5;
int n,T,S,f[maxn],g[maxn],deg[maxn],fa[maxn];
vector<int> e[maxn];
il void dfs(int u){
int hp[5]={0};
int son=deg[u]-(fa[u]?1:0);
if(fa[u]){
g[u]+=son-1;
}
for(int v:e[u]){
if(v==fa[u]){
continue;
}
fa[v]=u;
g[v]=g[u];
dfs(v);
hp[3]=f[v];
sort(hp+1,hp+4,greater<int>());
}
if(!son){
f[u]=0;
}
else if(son==1){
f[u]=1;
}
else{
f[u]=hp[2]+son;
}
}
il bool check(int x){
int u=S,las=-1,res=0,cnt=1;
while(u!=T){
int lar=res;
for(int v:e[u]){
if(v!=fa[u]&&v!=las&&f[v]+g[u]+lar+(las==-1)>x){
res++;
}
}
if(res>cnt||res>x){
return 0;
}
las=u,u=fa[u],cnt++;
}
return 1;
}
int main(){
n=read(),T=read(),S=read();
// cout<<n<<T<<S<<"\n";
for(int i=1,u,v;i<n;i++){
u=read(),v=read();
// cout<<u<<" "<<v<<"\n";
e[u].pb(v),e[v].pb(u);
deg[u]++,deg[v]++;
}
dfs(T);
// for(int i=1;i<=n;i++){
// cout<<f[i]<<" "<<g[i]<<"\n";
// }
int l=0,r=n;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)){
r=mid;
}
else{
l=mid+1;
}
}
cout<<l;
return 0;
}
}
int main(){return asbt::main();}
D. 地雷
設(shè) \(f_{l,r,x,y}\) 表示 \([l,r]\) 刪完時(shí) \(l-1\) 和 \(r+1\) 都沒有刪，\(x\) 左側(cè)的都比 \(x\) 刪的早，\(y\) 是 \(r+1\) 右側(cè)第一個(gè)沒有刪的位置的最大代價(jià)。
于是有轉(zhuǎn)移：
\[f_{l,r,x,y}=\max\{f_{l,i-1,x,k}+cost(l-1,i,r+1,y)+f_{i+1,r,k,y}\}
\]
代碼具體實(shí)現(xiàn)細(xì)節(jié)多的要死。
復(fù)雜度 \(O(n^6)\)，但常數(shù)非常小，可以通過。
實(shí)測只會(huì)轉(zhuǎn)移 2e8 次。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
int n,p[75],q[75],r[75],s[75],f[75][75][75][75];
il int sq(int x){
return x*x;
}
il int calc(int a,int b,int c,int d){
return sq(p[a]-q[b])+sq(p[b]-r[c])+sq(p[c]-s[d]);
}
il void upd(int &x,int y){
x=x<y?y:x;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i];
}
for(int i=1;i<=n;i++){
cin>>q[i];
}
for(int i=1;i<=n;i++){
cin>>r[i];
}
for(int i=1;i<=n;i++){
cin>>s[i];
}
memset(f,-0x3f,sizeof(f));
for(int i=1;i<=n+1;i++){
f[i][i-1][i-1][i]=0;
for(int j=i+1;j<=n+1;j++){
f[i][i][i][j]=f[i][i][i-1][j]=calc(i-1,i,i+1,j);
f[i][i-1][i-1][j]=0;
}
}
for(int len=2;len<=n;len++){
for(int l=1,r=len;r<=n;l++,r++){
for(int x=l-1;x<=r;x++){
for(int y=r+1;y<=n+1;y++){
int &res=f[l][r][x][y];
for(int i=max(x,l);i<=r;i++){
int j=i==x?l-1:x,tmp=calc(l-1,i,r+1,y);
upd(res,f[l][i-1][j][r+1]+tmp+f[i+1][r][i][y]);
for(int k=i+1;k<=r;k++){
upd(res,f[l][i-1][j][k]+tmp+f[i+1][r][k][y]);
}
}
}
}
}
}
cout<<f[1][n][0][n+1];
return 0;
}
}
int main(){return asbt::main();}
浙公網(wǎng)安備 33010602011771號(hào)