暑假集训CSP提高模拟19
\(T1\) P173. 数字三角形 \(20pts\)
- 原题： CF1517C Fillomino 2
- 部分分
-
\(20pts\) ：剪枝搜索。
点击查看代码
int p[510],c[510],ans[510][510],dx[5]={0,1,-1,0,0},dy[5]={0,0,0,-1,1}; void dfs(int pos,int x,int y,int num,int n) { if(pos==n+1) { for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { cout<<ans[i][j]<<" "; } cout<<endl; } exit(0); } else { if(num==0) { dfs(pos+1,pos+1,pos+1,c[pos+1],n); } else { for(int i=1;i<=4;i++) { int nx=x+dx[i]; int ny=y+dy[i]; if(1<=nx&&nx<=n&&1<=ny&&ny<=x&&ans[nx][ny]==0) { ans[nx][ny]=p[pos]; dfs(pos,nx,ny,num-1,n); ans[nx][ny]=0; } } } } } int main() { int n,i,j; cin>>n; memset(ans,-1,sizeof(ans)); for(i=1;i<=n;i++) { cin>>p[i]; ans[i][i]=p[i]; c[i]=p[i]-1; } for(i=1;i<=n;i++) { for(j=1;j<=i-1;j++) { ans[i][j]=0; } } dfs(1,1,1,c[1],n); return 0; }
-
- 正解
-
通过打表，我们可以发现合法方案中同一个数向右延伸一定不优，向左延伸比向下延伸更优。
-
所以填数时优先向左延伸，否则向下延伸。
点击查看代码
int p[510],c[510],ans[510][510]; void dfs(int pos,int x,int y,int num,int n) { if(pos==n+1) { for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { cout<<ans[i][j]<<" "; } cout<<endl; } exit(0); } else { if(num==0) { dfs(pos+1,pos+1,pos+1,c[pos+1],n); } else { if(y-1>=1&&ans[x][y-1]==0) { ans[x][y-1]=p[pos]; dfs(pos,x,y-1,num-1,n); } else { if(x+1<=n&&ans[x+1][y]==0) { ans[x+1][y]=p[pos]; dfs(pos,x+1,y,num-1,n); } } } } } int main() { int n,i; cin>>n; for(i=1;i<=n;i++) { cin>>p[i]; ans[i][i]=p[i]; c[i]=p[i]-1; } dfs(1,1,1,c[1],n); return 0; }
-
\(T2\) P160. 那一天她离我而去 \(0pts\)
- 部分分
- \(76pts\) ： \(Dijkstra\) 求解最小环。
-
枚举 \(1\) 的所有出边，钦定这条边是环上的边，删掉这条边后再求到这个点的最短路长度，加上被删的边的长度与答案取 \(\min\) 即可。
-
若不限制起点，则需要枚举边 \((u,v,w) \in E\) ，删掉这条边后 \(u \to v\) 的最短路长度 \(+w\) 与答案取 \(\min\) 即可。时间复杂度为 \(O(m(n+m)\log n)\) 。
点击查看代码
struct node { int nxt,to,w; }e[80010]; int head[10010],vis[10010],dis[10010],brokeu,brokev,cnt=0; vector<pair<int,int> >broke; void add(int u,int v,int w) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; e[cnt].w=w; head[u]=cnt; } bool check(int u,int v) { return ((u==brokeu&&v==brokev)||(u==brokev&&v==brokeu)); } void dijkstra(int s) { memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); priority_queue<pair<int,int> >q; dis[s]=0; q.push(make_pair(-dis[s],-s)); while(q.empty()==0) { int x=-q.top().second; q.pop(); if(vis[x]==0) { vis[x]=1; for(int i=head[x];i!=0;i=e[i].nxt) { if(check(x,e[i].to)==0&&dis[e[i].to]>dis[x]+e[i].w) { dis[e[i].to]=dis[x]+e[i].w; q.push(make_pair(-dis[e[i].to],-e[i].to)); } } } } } int main() { int t,n,m,ans,u,v,w,i,j; cin>>t; for(j=1;j<=t;j++) { cnt=0; ans=0x7f7f7f7f; broke.clear(); memset(e,0,sizeof(e)); memset(head,0,sizeof(head)); cin>>n>>m; for(i=1;i<=m;i++) { cin>>u>>v>>w; add(u,v,w); add(v,u,w); if(u==1) { broke.push_back(make_pair(v,w)); } if(v==1) { broke.push_back(make_pair(u,w)); } } for(i=0;i<broke.size();i++) { brokeu=1; brokev=broke[i].first; dijkstra(1); if(dis[brokev]!=0x3f3f3f3f) { ans=min(ans,dis[brokev]+broke[i].second); } } cout<<(ans>=0x7f7f7f7f?-1:ans)<<endl; } return 0; }
-
- \(76pts\) ： \(Dijkstra\) 求解最小环。
- 正解
\(T3\) P175. 哪一天她能重回我身边 \(20pts\)
- 部分分
-
\(20pts\) ：剪枝搜索。
点击查看代码
const ll p=998244353; ll x[100010],y[100010],cnt[200010],ans,sum; void dfs(ll pos,ll num,ll n) { if(pos==n+1) { if(num<ans) { ans=num; sum=1; } else { if(num==ans) { sum=(sum+1)%p; } } } else { cnt[x[pos]]++; if(cnt[x[pos]]==1) { dfs(pos+1,num,n); } cnt[x[pos]]--; cnt[y[pos]]++; if(cnt[y[pos]]==1) { dfs(pos+1,num+1,n); } cnt[y[pos]]--; } } int main() { ll t,n,i,j; cin>>t; for(j=1;j<=t;j++) { cin>>n; for(i=1;i<=n;i++) { cin>>x[i]>>y[i]; } ans=0x7f7f7f7f; sum=0; dfs(1,0,n); if(ans==0x7f7f7f7f) { cout<<"-1 -1"<<endl; } else { cout<<ans<<" "<<sum<<endl; } } return 0; }
-
- 正解
\(T4\) P174. 单调区间 \(60pts\)
- 原题： CF1693D Decinc Dividing
- 部分分
-
\(60pts\) ： \(O(n^{2})\) 枚举左右端点，剪枝搜索判断合不合法。
点击查看代码
ll a[200010],b[200010]; vector<ll>s1,s2; bool dfs(ll pos,ll n) { if(pos==n+1) { return true; } else { ll flag=0; if(s1.size()==0||s1[s1.size()-1]>b[pos]) { s1.push_back(b[pos]); flag|=dfs(pos+1,n); s1.pop_back(); } if(s2.size()==0||s2[s2.size()-1]<b[pos]) { s2.push_back(b[pos]); flag|=dfs(pos+1,n); s2.pop_back(); } return flag; } } bool check(ll l,ll r) { for(ll i=l;i<=r;i++) { b[i-l+1]=a[i]; } return dfs(1,r-l+1); } int main() { ll n,ans=0,i,j; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; } for(i=1;i<=n;i++) { for(j=i;j<=n;j++) { ans+=check(i,j); } } cout<<ans<<endl; return 0; }
-
- 正解
总结
- \(T1\) 赛时把结论猜出来后一直在想怎么处理边界和怎么进行 \(hack\) ，到最后也没打代码。
- \(T2\) 因为提交前忘再编译一遍了，把分号打成了冒号，因 \(CE\) 挂了 \(23pts\) ;因为知道是板子，但自己没学所以干脆没去想 \(Dijkstra\) 怎么求解最小环，可能是学的东西太多了导致的？