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
思路：
每个点对应的都有三个点，将这四个点变成一样的就满足题意的回文矩阵了
问题转变成：给4个数，每次可以+ 1 , − 1，问最小的操作次数；
排序后取中位数，计算答案；
注意做标记，不要重复计算；
代码：
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; vector<int>v; 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
思路：
算贡献的好题
对答案进行分类，再算贡献；
比如当时枚举到第i位时，答案有三种情况，分别考虑贡献：
删去的连续子串在i前面
删去的连续子串在i后面
删去的连续子串包括i
第三种的贡献肯定是不计的；
第一种只需要看有多少种方案数就好了；
第二种要看删去几位和删数的方案数
代码：
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
思路：
n<=1e9，直接建边显然不现实
m < = 1 e 5 ，可以从传送门下手考虑建边
由于相同x坐标或相同y坐标的传送门可以互相传送，也就是说不同x轴的传送门的代价为x坐标的差值。
考虑下面的建边：
假设起点为0，传送门为[ 1 , m ]，x轴为[ m + 1 , 2 m ]，y轴为[ 2 m + 1 , 3 m ]，终点为3 m
起点向传送门的x坐标和y坐标分别建单向边；代价为某个坐标的绝对值之差。
传送门向终点建立单向边，代价为曼哈顿距离。
x坐标相邻点建立边，双向，代价为0
y坐标相邻点建立边，双向，代价为0
传送门向x轴建边，双向
传送门向y轴建边，双向
建图后跑最短路
代码：
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(vx+1,vx+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<PLL,vector<PLL>,greater<PLL>>heap; heap.push({s,0ll});///起始点放入队列 while(heap.size()){ auto t=heap.top();///最小值 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(vx+1,vx+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; }
