Codeforces Round #675 (Div. 2) A~D

Codeforces Round #675 (Div. 2) A~D

A. Fence

思路：

手模一下，将最小值和最大值当成对边，中间值放在底部，顶边就是要求的边。根据三角形两边之和小于即可求解；

代码：

int main(){ int _=read; while(_--){ ll a[3]; rep(i,0,2) a[i]=read; sort(a,a+2); write(a[1]+a[2]-a[0]+1);puts(""); } return 0;}

Nice Matrix

思路：

代码：

int a[110][110],vis[110][110]; int main(){ int _=read; while(_--){ int n=read,m=read; rep(i,1,n) rep(j,1,m) a[i][j]=read,vis[i][j]=0; ll ans=0; rep(i,1,n) rep(j,1,m){ if(vis[i][j]) continue; vectorv; if(vis[i][j]==0){ v.push_back(a[i][j]);vis[i][j]=1; } if(vis[i][m-j+1]==0){ vis[i][m-j+1]=1;v.push_back(a[i][m-j+1]); } if(vis[n-i+1][j]==0){ vis[n-i+1][j]=1;v.push_back(a[n-i+1][j]); } if(vis[n-i+1][m-j+1]==0){ vis[n-i+1][m-j+1]=1;v.push_back(a[n-i+1][m-j+1]); } if(v.size()==0) continue; sort(v.begin(),v.end()); for(auto t:v){ ans=ans+abs(t-v[v.size()/2]); } v.clear(); } write(ans);puts(""); } return 0;}

C. Bargain

思路：

代码：

const ll mod=1e9+7; int main(){ string s;cin>>s; ll n=s.size(); ll ans=0,p=1,sum=0; for(ll i=n;i;i--){ ll now=(i-1)*i/2%mod; ans=(ans+p*(s[i-1]-'0')%mod*now%mod)%mod; ans=(ans+sum*(s[i-1]-'0')%mod)%mod; sum=(sum+p*(n-i+1)%mod)%mod; p=p*10%mod; } write(ans); return 0;}

Returning Home

思路：

代码：

const int maxn=4e6+7,mod=1e9+7; ll h[maxn],idx;struct node{ int e,ne; ll w;}edge[maxn]; void add(int u,int v,ll w){ edge[idx]={v,h[u],w};h[u]=idx++;}int n,m,sx,sy,fx,fy,x[maxn],y[maxn],vx[maxn],vy[maxn];ll dis[maxn];bool st[maxn]; int get_x_id(int t){ return lower_bound(-1,-1+m,t)-vx;} int get_y_id(int t){ return lower_bound(vy+1,vy+1+m,t)-vy;} ll dijkstra(int s){ memset(dis,0x3f,sizeof dis); dis[s]=0; ///建立一个维护最小值的优先队列 priority_queue,greater>heap; heap.push({s,0ll});///起始点放入队列 while(heap.size()){ auto t=heap-();///最小值 heap.pop(); ll ver=t.second,d=t.first; if(st[ver]) continue;///该点更新 st[ver]=true; for(int i=h[ver];i!=-1;i=edge[i].ne){ int j=edge[i].e; if(dis[j]>d+edge[i].w){ dis[j]=d+edge[i].w; heap.push({dis[j],j}); } } } return dis[3*m+1];} int main(){ memset(h,-1,sizeof h); n=read,m=read; sx=read,sy=read,fx=read,fy=read; rep(i,1,m){ x[i]=read,y[i]=read; vx[i]=x[i];vy[i]=y[i]; } sort(-1,-1+m);sort(vy+1,vy+1+m); rep(i,1,m){//起点向跳跃点 add(0,i+m,abs(sx-vx[i])); add(0,i+2*m,abs(sy-vy[i])); } //vx.erase(unique(vx.begin(),vx.end()),vx.end()); // vy.erase(unique(vy.begin(),vy.end()),vy.end()); rep(i,1,m){ add(i,3*m+1,abs(fx-x[i])+abs(fy-y[i]));//2 终点向跳跃点 int xid=get_x_id(x[i])+m; add(i,xid,0);add(xid,i,0);//5 跳跃点到x轴 int yid=get_y_id(y[i])+2*m; add(i,yid,0);add(yid,i,0);//6跳跃点到y轴 // add(0,xid,abs(sx-x[i]));add(0,yid,abs(sy-y[i]));//1 } add(0,3*m+1,abs(sx-fx)+abs(sy-fy));//起点向终点 for(int i=2;i<=m;i++)//x轴之间 add(i+m,i+m-1,abs(vx[i]-vx[i-1])),add(i+m-1,i+m,abs(vx[i]-vx[i-1])); for(int i=2;i<=m;i++)//y轴之间 add(i+2*m,i+2*m-1,abs(vy[i]-vy[i-1])),add(i+2*m-1,i+2*m,abs(vy[i]-vy[i-1])); dijkstra(0); write(dis[3*m+1]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。