CodeForces - 1422

A题目链接：https://vjudge.net/contest/399211#problem/A

题意：给出a,b,c三条边，让你组成一个四边形，需要添加边的长度d为多少？（任意一个就可以）

思路：固定任一条边，假如固定边a，让b，c垂直于a

求fabs ( b - c )的平方加上a的平方，再开方求出d即可，这时候d可能是个小数，向上取整就可。

AC代码：

#include<bits\stdc++.h>
using namespace std;typedef long long ll;const int N=100010;int n;
ll a,b,c;int main()
{int T;scanf("%d",&T);while(T--){scanf("%lld%lld%lld",&a,&b,&c);ll k=sqrt(a*a+fabs(b-c)*fabs(b-c));printf("%lld\n",k+1);}
}

B题目链接：https://vjudge.net/contest/399211#problem/B

题意：给一个 n * m 的矩阵，你每次操作可以将矩阵中的任一一个数加一或减一，求多少次可以使矩阵每一行每一列都为回文．

思路：假设给出以下4*4的矩阵，我们首先要使 a，d，m，p 这四个数相同，然后再让b，c，n，o，相同，遍历一遍即可。怎样让这四个数相同呢？我们可以让四个数排序，选出中间的两个相加除2即可。因为两边的两个数到达任意一点的贡献都是一样的。

AC代码：

#include<bits\stdc++.h>
using namespace std;typedef long long ll;const int N=110;int n,m;
ll s[N][N];int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)scanf("%lld",&s[i][j]);ll sum=0;int x=1,y=n;while(y>=x){int a=1,b=m;while(b>=a){int w[4];w[0]=s[x][a],w[1]=s[x][b];w[2]=s[y][a],w[3]=s[y][b];sort(w,w+4);ll k=(w[1]+w[2])/2;ll h=fabs(k-s[x][a])+fabs(k-s[x][b])+fabs(k-s[y][a])+fabs(k-s[y][b]);if(a==b||x==y)h=h/2;sum+=h;a++;b--;}x++;y--;}printf("%lld\n",sum);}
}

C题目链接：https://vjudge.net/contest/399211#problem/C

题意：给你一个数 a ,你可以从这个数中选择一段子串并删掉，两端再拼成一个新数，问所有可能的新数的和对1000000007取余。

思路：借鉴一下大佬的思路，

例8 4 3 2 1

对1来说，后面没有，那么贡献是0

对2来说，后面拿1，贡献是2

对3来说，后面拿1和2，贡献是3，后面拿1，贡献是30，后面拿2，贡献是30.

对4来说，后面拿123，贡献是4；后面拿23，21，贡献是40，40；后面拿3，2，1，贡献是400，400，400；

求出所有贡献出现的次数乘以贡献数。

AC代码：

#include<bits\stdc++.h>
using namespace std;typedef long long ll;#define mod 1000000007const int N=110000;int n,m;
char s[N];int main()
{scanf("%s",s+1);ll len=strlen(s+1);ll ans=0;ll sum=0;ll p=1;for(ll i=len;i>=1;i--){ll k=i*(i-1)/2;ans=(ans%mod+(s[i]-48)*p%mod*k%mod)%mod;ans=(ans%mod+(s[i]-48)*sum%mod)%mod;sum=(sum%mod+(len-i+1)*p%mod)%mod;p=p*10%mod;}printf("%lld\n",ans);}