A. Fence

任意三条边大于第四边即可构成四边形。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    ll a,b,c;
    while(T--)
    {
        cin>>a>>b>>c;
        printf("%lld\n",a+b+c-1); // 3e9,记得开long long
    }
    return 0;
}

B. Nice Matrix

将矩阵分成4个区域,对于每个左上位置,找它对称的右上、左下、右下的位置,然后求这4个数的中位数$median$,从而使得 $\sum_{i=1}^4(x_i-median)$ 最小。

注意特判行/列为奇数时,最中间的那一行/列,只要算2个数而不是4个数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=110;
ll n,m,x[6],a[N][N];
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>a[i][j];
        ll ans=0;
        ll mid1=n/2+(n&1),mid2=m/2+(m&1);
        for(int i=1;i<=mid1;i++)
        {
            for(int j=1;j<=mid2;j++)
            {
                x[1]=a[i][j]; // 左上
                x[2]=a[i][m+1-j]; // 右上
                x[3]=a[n+1-i][j]; // 左下
                x[4]=a[n+1-i][m+1-j]; // 右下
                if(i==n+1-i&&j==m+1-j)continue; // 奇数行且奇数列的时候,最中间的数不用改
                else if(i==n+1-i) // x1,x3重合; x2,x4重合
                    ans+=abs(x[1]-x[2]);
                else if(j==m+1-j) // x1,x2重合; x3,x4重合
                    ans+=abs(x[1]-x[3]);
                else
                {
                    sort(x+1,x+4+1);
                    int median=(x[2]+x[3])/2; //中位数
                    for(int k=1;k<=4;k++)
                        ans+=abs(x[k]-median);
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}
/*
1
5 5
100 1 1 1 1
1 1 1 1 1
1 1 100 1 1
1 1 1 1 1
1 1 1 1 1
ans:99
*/

C. Bargain【高精度】

考虑每列相加,假设最靠右的是第1列,从右到左模拟相加过程。

接下来考虑$O(1)$求每列的累加值。设序列转换成整数数组为$a_1a_2...a_n$,第$i$列的累加值为$res$,可推得公式:
$$res=i\sum_{i=1}^{n-i}a_i+a_{n-i+1}\sum_{i=1}^{n-i}i$$

第$i$列之后的长度为$i-1$,那么$res$还需要再乘以$10^{i-1}$(因为$res$只是第$i$列的累加数,数字后面还要添$0$才是第$i$列在答案中的实际贡献)。

最后,按照以下公式遍历求和即可:
$$res'=(i\sum_{i=1}^{n-i}a_i+a_{n-i+1}\sum_{i=1}^{n-i}i)*10^{i-1},i∈[1,n-1]$$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10,mod=1e9+7;
char s[N];
ll n,a[N],sum[N];
ll qpow(ll a,ll b)
{
    ll s=1;
    while(b)
    {
        if(b&1)s=s*a%mod;
        b/=2;
        a=a*a%mod;
    }
    return s%mod;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>s+1;
    n=strlen(s+1);
    for(int i=1;i<=n;i++)
    {
        a[i]=s[i]-'0';
        sum[i]=(sum[i-1]+a[i])%mod;
    }
    ll ans=0;
    for(ll i=1;i<=n-1;i++)
    {
        ll res=i*sum[n-i]%mod%mod;
        ll tmp=(1+n-i)*(n-i)/2%mod;
        res=(res+a[n-i+1]*tmp%mod)%mod;
        res=res*qpow((ll)10,i-1)%mod; // res是第i列的实际值
        ans=(ans+res)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}
/*
12345
ans:8220
*/