Codeforces Round #675 (Div. 2)

目录：

A. FenceB. Nice MatrixC. Bargain

A. Fence

签到题

题设：给定三个代表三条边的值：a，b，c，求出任意一个能和这三条边构成一个四边形的长度d。思路：构成合法四边形的规则是任意三边和要绝对大于第四条边。 输出a+b+c-1即可，注意范围，全用long long。 因用int存a，b，c导致计算时数据溢出wa了一发，就临时想了个稍微绕弯但可行的思路，如下： 因数据范围是三个1e9，为了防止溢出采用了保守方法。先计算a，b，c中较小两个值的和sum和a，b，c中最大值max，若这个sum已经比a，b，c中最大值max还大了，输出d=1即可，否则，令d=max-sum+1。 ——AC代码

B. Nice Matrix

思维题

题设：给定一个n×m大小的矩阵，每次可对其中任意一个位置的元素进行+1或者-1操作，问最少多少次操作能使这个矩阵，每一行每一列都回文（中心对称）。思路：

根据行列均回文可判断出每个元素和哪些位置的其他元素有关联，不难推算出，对于简单情况下的a[ i ][ j ]，另外三个位置上的元素a[ i ][ m-j+1 ]，a[ n-i+1 ][ j ]，a[ n-i+1 ][ m-j+1 ]必须与其相等才符合条件。那特殊情况下，当每次遍历到行列的中间元素时，不难得出： 列数为偶数，行数为奇数：只需要a[ i ][ j ] == a[ i ][ m-j+1 ] 列数为奇数，行数为偶数：只需要a[ i ][ j ] == a[ n-i+1 ][ j ] 列数为奇数，行数为奇数：不需要操作，a[ i ][ j ]无关联元素，可为任意值。

判断完哪些元素相互关联后，就需要通过操作使关联元素全部相等，即推算出最后这四个元素相等的特殊值X。

根据图辅助理解可知，四段红线权值即为需要的总操作数，那么只有当X属于a2—a3范围内时总操作数最少，注意：因为a2—a3范围内不一定包含（a1+a4）/2，这里简便化，取X值为a3（或a2）。 ——AC代码：

#include<bits/stdc++.h> #define ll long long #define gcd(a,b) __gcd(a,b) #define lcm(a,b) a*b/(__gcd(a,b)) #define rep(i,s,e) for(int i=s;i<e;i++) #define mem(a,n) memset(a, n ,sizeof a) #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int INF= 0x3f3f3f3f; priority_queue <int,vector<int>,less<int> > Q; int a[110][110]; int find(int x1,int x2,int x3,int x4) { int M=max(x1,max(x2,max(x3,x4))); if(x1==M) return max(x2,max(x3,x4)); if(x2==M) return max(x1,max(x3,x4)); if(x3==M) return max(x1,max(x2,x4)); if(x4==M) return max(x1,max(x2,x3)); } int main() { IOS; int t,n,m; cin>>t; while(t--) { cin>>n>>m; rep(i,1,n+1) rep(j,1,m+1) cin>>a[i][j]; ll ans=0; int midN=n/2+n%2; int midM=m/2+m%2; int a1,a2,a3,a4,M; for(int i=1;i<=midN;i++) { for(int j=1;j<=midM;j++) { //a1,a2,a3,a4; if(i==n-i+1 && j==m-j+1) continue; if(i==n-i+1) { ans+= abs(a[i][j]-a[i][m-j+1]); continue; } if(j==m-j+1) { ans+= abs(a[i][j]-a[n-i+1][j]); continue; } a1=a[i][j]; a2=a[i][m-j+1]; a3=a[n-i+1][j]; a4=a[n-i+1][m-j+1]; M=find(a1,a2,a3,a4); ans+= abs(a1-M)+ abs(a2-M)+ abs(a3-M)+ abs(a4-M); } } cout<<ans<<endl; } return 0; }

C. Bargain

数论

题设：输入一数n，1 <= n < (10¹⁰)⁵，可从这个总位数为len的数n中任意抽出 1~len-1 位连续的数字，抽完后（各个位上的数发生相应变化）前后两段聚拢变成一个新的数m，求出所有所有抽出情况m的总和，答案对 1e9+7 取模。思路：首先数n较大，且涉及到各个位上数字的变化，采用字符串进行读取和操作。这里我们令s[ i ] 表示第 i 位的数字，然后，对于抽出任意长度的连续数字，有两种情况： 抽出的数字全在这个数字的前面，即抽出后不会影响s[ i ]的位次，可简化问题为s[ i ]前的各个数字任意抽取有多少种情况，定义情况总数变量为lth，每个情况都要算上一次s[ i ]×它原始位次的倍数k。抽出的数字全在这个数字的后面，此时就会对s[ i ]的位次产生影响，这里定义一个sum变量，表示每个数字在这种情况下，会在它的原始位次的后面出现多少次，每次加上s[ i ]× sum。这里对于这个sum的累加更新需要用到位次k。 ——AC代码： #include<bits/stdc++.h> #define ll long long #define gcd(a,b) __gcd(a,b) #define lcm(a,b) a*b/(__gcd(a,b)) #define rep(i,s,e) for(int i=s;i<e;i++) #define mem(a,n) memset(a, n ,sizeof a) #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int INF= 0x3f3f3f3f; priority_queue <int,vector<int>,less<int> > Q; const int mod= 1e9+7; int main() { IOS; string s; cin >> s; ll len=s.size(); reverse(s.begin(),s.end());//反转整个字符串 ll ans=0, sum=0, k=1; for(int i=0;i<len;i++) { ll shu= s[i]-'0'; ll lth= ( (len-i-1)*(len-i)/2 ) % mod; //lth表示当前shu在各个子串中相对位次不变时 出现的次数 ans = (ans + shu * lth * k) % mod; //sum计算的是shu在各个子串中相对位次变化时 出现的次数 ans = (ans + shu * sum) % mod; sum = (sum + k*(i+1)) % mod; k = k*10 % mod; } cout<<ans; return 0; }