Panasonic Programming Contest 2024（AtCoder Beginner Contest 375）
\(A\) Seats \(AC\)
-
基础字符串。
点击查看代码
int main() { int n,ans=0,i; string s; cin>>n>>s; for(i=0;i<n;i++) { ans+=(s[i]=='#'&&s[i+1]=='.'&&s[i+2]=='#'&&i+2<n); } cout<<ans<<endl; return 0; }
\(B\) Traveling Takahashi Problem \(AC\)
-
循环结构。
点击查看代码
double x[200010],y[200010]; int main() { int n,i; double ans=0; cin>>n; for(i=1;i<=n;i++) { cin>>x[i]>>y[i]; ans+=sqrt((x[i]-x[i-1])*(x[i]-x[i-1])+(y[i]-y[i-1])*(y[i]-y[i-1])); } ans+=sqrt(x[n]*x[n]+y[n]*y[n]); printf("%.12lf",ans); return 0; }
\(C\) Spiral Rotation
-
暂且先不管 \(x,y \in [i,n+1-i]\) 的限制，手摸一下替换过程，发现循环节长度为 \(4\) 。
- \((x,y) \to (y,n+1-x) \to (n+1-x,n+1-y) \to (n+1-y,x) \to (x,y) \to \dots\)
-
若 \(x,y \in [i,n+1-i]\) 相应地有 \(n+1-y,n+1-x \in [i,n+1-i]\) 。
-
又因为使得 \(x,y \in [i,n+1-i]\) 的最大的 \(i\) 等于 \(\min(x,y,n+1-x,n+1-y)\) ，处理出 \((x,y)\) 最终能替换的位置即可。
点击查看代码
char a[3010][3010],b[3010][3010]; int main() { int n,x,y,nx,ny,i; cin>>n; for(x=1;x<=n;x++) { for(y=1;y<=n;y++) { cin>>a[x][y]; } } for(x=1;x<=n;x++) { for(y=1;y<=n;y++) { nx=x; ny=y; for(i=1;i<=min({x,y,n+1-x,n+1-y})%4;i++) { swap(nx,ny); ny=n+1-ny; } b[nx][ny]=a[x][y]; } } for(x=1;x<=n;x++) { for(y=1;y<=n;y++) { cout<<b[x][y]; } cout<<endl; } return 0; }
\(D\) ABA \(AC\)
-
考虑枚举 \(i,k\) ，那么任意的 \(j \in (i,k)\) 都合法，统计一下贡献即可。
点击查看代码
string s; vector<int>pos[30]; int main() { ll ans=0,i,j,k; cin>>s; for(i=0;i<s.size();i++) { pos[s[i]-'A'+1].push_back(i+1); } for(i=1;i<=26;i++) { if(pos[i].size()>=2) { ans-=(pos[i].size()-1)*pos[i].size()/2; for(j=0;j<pos[i].size();j++) { ans+=(j+j+1-(ll)pos[i].size())*pos[i][j]; } } } cout<<ans<<endl; return 0; }
\(E\) 3 Team Division \(AC\)
-
观察到 \(\sum\limits_{i=1}^{n}b_{i} \le 1500\) ，考虑暴力 \(DP\) 。
-
设 \(f_{i,j,k,h}\) 表示处理到第 \(i\) 个人使得第 \(1,2,3\) 组的力量分别为 \(j,k,h\) 最少移动人的次数。
-
压缩 \(j+k+h=\sum\limits_{i=1}^{n}b_{i}\) 加滚动数组后即可通过。
点击查看代码
int a[110],b[110],sum[4],f[2][3010][3010]; int main() { int n,num=0,i,j,k; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]>>b[i]; sum[a[i]]+=b[i]; num+=b[i]; } if(num%3==0) { memset(f,0x3f,sizeof(f)); f[0][sum[1]][sum[2]]=0; for(i=1;i<=n;i++) { if(a[i]==1) { for(j=0;j<=num;j++) { for(k=0;k<=num;k++) { f[i&1][j][k]=f[(i-1)&1][j][k]; if(k-b[i]>=0) { f[i&1][j][k]=min(f[i&1][j][k],f[(i-1)&1][j+b[i]][k-b[i]]+1); } if(num-j-k-b[i]>=0) { f[i&1][j][k]=min(f[i&1][j][k],f[(i-1)&1][j+b[i]][k]+1); } } } } if(a[i]==2) { for(j=0;j<=num;j++) { for(k=0;k<=num;k++) { f[i&1][j][k]=f[(i-1)&1][j][k]; if(j-b[i]>=0) { f[i&1][j][k]=min(f[i&1][j][k],f[(i-1)&1][j-b[i]][k+b[i]]+1); } if(num-j-k-b[i]>=0) { f[i&1][j][k]=min(f[i&1][j][k],f[(i-1)&1][j][k+b[i]]+1); } } } } if(a[i]==3) { for(j=0;j<=num;j++) { for(k=0;k<=num;k++) { f[i&1][j][k]=f[(i-1)&1][j][k]; if(j-b[i]>=0) { f[i&1][j][k]=min(f[i&1][j][k],f[(i-1)&1][j-b[i]][k]+1); } if(k-b[i]>=0) { f[i&1][j][k]=min(f[i&1][j][k],f[(i-1)&1][j][k-b[i]]+1); } } } } } if(f[n&1][num/3][num/3]==0x3f3f3f3f) { cout<<-1<<endl; } else { cout<<f[n&1][num/3][num/3]<<endl; } } else { cout<<-1<<endl; } return 0; }
\(F\) Road Blocked
-
删边最短路不会写，遂考虑倒序加边。
-
观察到至多删除 \(300\) 条边，而 \(Floyd\) 每次加入一条边更新最短路的时间复杂度为 \(O(n^{2})\) ，可以通过。
- 每加入一条边只有以这条边的两个端点作为中转点的最短路会得到更新，故时间复杂度为 \(O(n^{2})\) 。
点击查看代码
ll dis[310][310],pd[200010],x[200010],y[200010],u[200010],v[200010],w[200010],vis[200010],ans[200010]; int main() { ll n,m,q,i,j,k; cin>>n>>m>>q; for(i=1;i<=m;i++) { cin>>u[i]>>v[i]>>w[i]; } for(i=1;i<=q;i++) { cin>>pd[i]>>x[i]; if(pd[i]==1) { vis[x[i]]=1; } else { cin>>y[i]; } } memset(dis,0x3f,sizeof(dis)); for(i=1;i<=m;i++) { if(vis[i]==0) { dis[u[i]][v[i]]=dis[v[i]][u[i]]=min(dis[u[i]][v[i]],w[i]); } } for(k=1;k<=n;k++) { for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } } } for(k=q;k>=1;k--) { if(pd[k]==1) { dis[u[x[k]]][v[x[k]]]=dis[v[x[k]]][u[x[k]]]=min(dis[u[x[k]]][v[x[k]]],w[x[k]]); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { dis[i][j]=min(dis[i][j],dis[i][u[x[k]]]+dis[u[x[k]]][j]); } } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { dis[i][j]=min(dis[i][j],dis[i][v[x[k]]]+dis[v[x[k]]][j]); } } } else { ans[k]=dis[x[k]][y[k]]; } } for(i=1;i<=q;i++) { if(pd[i]==2) { cout<<((ans[i]==0x3f3f3f3f3f3f3f3f)?-1:ans[i])<<endl; } } return 0; }
\(G\) Road Blocked 2
-
考虑建出从 \(1 \sim n\) 的最短路 \(DAG\) ，然后等价于询问这个 \(DAG\) 上的必经边，当无向图处理出割边即可。
点击查看代码
struct node { ll nxt,to,w,id; }e[400010]; ll head[400010],dis[400010],vis[400010],cut[400010],dfn[400010],low[400010],cnt=0,tot=0; vector<pair<ll,ll> >pre[400010],E[400010]; void add(ll u,ll v,ll w,ll id) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; e[cnt].w=w; e[cnt].id=id; head[u]=cnt; } void dijkstra(ll s) { memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); priority_queue<pair<ll,ll> >q; dis[s]=0; q.push(make_pair(-dis[s],s)); while(q.empty()==0) { ll x=q.top().second; q.pop(); if(vis[x]==0) { vis[x]=1; for(ll i=head[x];i!=0;i=e[i].nxt) { if(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)); } } } } } void build(ll n) { for(ll x=1;x<=n;x++) { for(ll i=head[x];i!=0;i=e[i].nxt) { if(dis[e[i].to]==dis[x]+e[i].w) { pre[e[i].to].push_back(make_pair(x,e[i].id)); } } } } void dfs(ll x) { if(vis[x]==0) { vis[x]=1; for(ll i=0;i<pre[x].size();i++) { dfs(pre[x][i].first); E[pre[x][i].first].push_back(make_pair(x,pre[x][i].second)); E[x].push_back(make_pair(pre[x][i].first,pre[x][i].second)); } } } void tarjan(ll x,ll fa) { ll flag=0; tot++; dfn[x]=low[x]=tot; for(ll i=0;i<E[x].size();i++) { if(dfn[E[x][i].first]==0) { tarjan(E[x][i].first,x); low[x]=min(low[x],low[E[x][i].first]); if(low[E[x][i].first]>dfn[x]) { cut[E[x][i].second]=1; } } else { if(E[x][i].first==fa&&flag==0) { flag=1; } else { low[x]=min(low[x],dfn[E[x][i].first]); } } } } int main() { ll n,m,u,v,w,i; cin>>n>>m; for(i=1;i<=m;i++) { cin>>u>>v>>w; add(u,v,w,i); add(v,u,w,i); } dijkstra(1); build(n); memset(vis,0,sizeof(vis)); dfs(n); tarjan(1,1); for(i=1;i<=m;i++) { if(cut[i]==0) { cout<<"No"<<endl; } else { cout<<"Yes"<<endl; } } return 0; }
总结
- 误认为 \(AT\) 加火车头后就能跑得飞快，致使 \(C,D\) 先交了一发暴力，然后就吃罚时了。
- \(E\) 数组开小了，吃了一发罚时。
- \(G\) 最后 \(30 \min\) 开始码，写完后发现不会求 \(1 \sim n\) 的最短路 \(DAG\) ，只胡了个建出全图的最短路 \(DAG\) 再从 \(n\) 倒着建回来。比赛结束时也没有调完。