Codeforces Round #675 (Div. 2) A,B,C

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_1{a}_2...a_n$，第$i$列的累加值为$res$，可推得公式： $$res=i\ast \sum _{i=1}^{n-i}{a}_i+a_{n-i+1}\ast \sum _{i=1}^{n-i}i$$

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

最后，按照以下公式遍历求和即可： $$re{s}^{\prime }=(i\ast \sum _{i=1}^{n-i}{a}_i+a_{n-i+1}\ast \sum _{i=1}^{n-i}i)\ast 10^{i-1}，i\in [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 */