A . Fence
给与三个数字，返回一个数，使得能组成一个四边形
众所周知跟三角形一样就可以。
D=A+B+C-1
即可。
int main(){ int t; scanf("%d",&t); while(t--){ int a,b,c; scanf("%d%d%d",&a,&b,&c); int s=max(a,max(b,c)); printf("%d ",s); } }
B .Nice Matrix
要使得矩阵的每行每列都是回文串，则要满足四边形四边的值要相同即可，遍历四个角的值返回
ll a[105][105]; int main(){ int t; scanf("%d",&t); while(t--){ int r,c; scanf("%d%d",&r,&c); for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ scanf("%lld",&a[i][j]); } } ll sum=0; for(int i=1;i<=r/2;i++){ for(int j=1;j<=c/2;j++){ int b[4]; b[0]=a[i][j]; b[1]=a[r-i+1][j]; b[2]=a[i][c-j+1]; b[3]=a[r-i+1][c-j+1]; sort(b,b+4); sum+=(b[3]-b[0]+b[2]-b[1]); } } if(r%2==1||c%2==1){ if(r%2==1){ ll x=r/2+1; for(int j=1;j<=c/2;j++){ sum+=abs(a[x][j]-a[x][c-j+1]); } } if(c%2==1){ int y=c/2+1; for(int j=1;j<=r/2;j++){ sum+=abs(a[j][y]-a[r-j+1][y]); } } } printf("%lld ",sum); } }
C .Bargain
给与一串数字，能删除一个连续的区间，问所有不同的删去方法之后的数之和
明显的算贡献，可发现对于 i的点，左边的区间删去对它没有影响，而右边区间删去才有影响，但是右边的又可以进行预处理，就解决了
ll ten[123456]; ll tal[123456]; ll inv2; ll ksm(ll x,ll y){ ll res=1; while(y){ if(y&1)res=(res*x)%MOD; x=(x*x)%MOD; y>>=1; } return res; } void init(){ inv2=ksm(2,MOD-2); ten[0]=1; tal[1]=1; for(ll i=1;i<=1e5;i++){ ten[i]=(ten[i-1]*10)%MOD; if(i>=2){ tal[i]=(tal[i-1]+ten[i-1]*i)%MOD; } } } int main(){ init(); string s; cin>>s; int sz=(int)s.size(); ll sum=0; for(int i=0;i<sz;i++){ ll l=i-0; ll r=sz-i-1; ll op=sz-i-1; sum=(sum+(ll)(s[i]-'0')*ten[op]%MOD*((l+1)*(l)%MOD*inv2%MOD)%MOD)%MOD; sum=(sum+(ll)(s[i]-'0')*tal[r]%MOD)%MOD; } printf("%lld ",sum); }
D .Returning Home
给与一系列的点，横坐标 或 纵坐标 相同的点 可以传送(无消耗).
1.起点可以直接与 这一系列点 传送，而终点不行，只能走过去。
2.将 这一系列的点 分点建图，将x坐标 排序，将y坐标排序 建边，这样可以省去建许多边。
3.起点与每个点的 距离都是 x坐标之差 或者 y坐标之差，而终点建边需要 abs(dx-x)+abs(dy-y),因为终点不能传送到达。
以上即可。
#include<bits/stdc++.h> using namespace std; typedef long long ll; struct node{ ll to,w,ne; }e[4023756]; struct point{ ll x,y; int dex; }t[4023756]; int cnt; int head[4027456]; bool cmp(point a,point b){ return a.x<b.x; } bool cmp1(point a,point b){ return a.y<b.y; } void add(int x,int y,ll w){ e[cnt].to=y,e[cnt].w=w,e[cnt].ne=head[x],head[x]=cnt++; e[cnt].to=x,e[cnt].w=w,e[cnt].ne=head[y],head[y]=cnt++; } ll dis[1023456]; typedef pair<ll, ll> P; int dij(){ memset(dis,0x3f,sizeof dis); dis[1]=0; priority_queue<P,vector<P>, greater<P> > que; que.push(P(dis[1], 1)); // while(!que.empty()) { P p = que.top();que.pop(); int u = p.second, v, w; if(p.first > dis[u])continue; for(int i=head[u];~i;i=e[i].ne){ v = e[i].to, w = e[i].w; if(dis[v] > dis[u]+w){ dis[v] = dis[u]+w; que.push(P(dis[v], v)); } } } return dis[2]; } int main(){ memset(head,-1,sizeof head); int n,m; scanf("%d%d",&n,&m); scanf("%lld%lld",&t[1].x,&t[1].y);//起点 t[1].dex=1; scanf("%lld%lld",&t[2].x,&t[2].y);//终点 t[2].dex=2; add(1,2,abs(t[1].x-t[2].x)+abs(t[1].y-t[2].y)); for(int i=3;i<=m+2;i++){ ll x,y; scanf("%lld%lld",&x,&y); t[i]={x,y,i}; add(i,i+123456,0);//分为 i 和 i+123456 两个点 add(1,i,abs(t[1].x-x)); //x坐标到起点的距离 add(1,i+123456,abs(t[1].y-y)); //y坐标到起点的距离 add(2,i,abs(t[2].x-x)+abs(t[2].y-y));//到终点的距离 } sort(t+3,t+3+m,cmp);//x坐标排序 for(int i=4;i<=m+2;i++){ add(t[i].dex,t[i-1].dex,abs(t[i].x-t[i-1].x));//建边 } sort(t+3,t+3+m,cmp1);//y坐标排序 for(int i=4;i<=m+2;i++){ add(t[i].dex+123456,t[i-1].dex+123456,abs(t[i].y-t[i-1].y));//建边 } cout<<dij()<<endl; }