Codeforces Round #513 by Barcelona Bootcamp (rated, Div. 1 + Div. 2) （A B C）

2023-05-16

链接： http://codeforces.com/contest/1060

Codeforces Round #513

A. Phone Numbers（水题）
B. Maximum Sum of Digits（打表找规律、思维贪心）
C. Maximum Subrectangle（思维卡时间）

A. Phone Numbers（水题）

题意： 第一位是字符 ′ 8 ′ '8' ′8′ 并且长度正好 11 11 11 位的字符串是合法的。给你一个字符串，问有多少个合法的子串（子串可以相同）。

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
	int n;
	string s;
	cin>>n>>s;
	if(n < 11) {
		cout<<0<<endl;
		return 0;
	}
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		if(s[i] == '8') cnt++;
	}
	cout<<min(cnt, n/11)<<endl;
	return 0;
}

B. Maximum Sum of Digits（打表找规律、思维贪心）

题意： 定义一个函数 S ( x ) S(x) S(x) ，它的值为 x x x 的每一位数相加，比如 S ( 123 ) = 1 + 2 + 3 S(123) = 1+2+3 S(123)=1+2+3 。现在给你一个数 n ( 1 ≤ n ≤ 1 0 12 ) n (1 \leq n \leq 10^{12}) n(1≤n≤1012)，求最大的 S ( a ) + S ( b ) ( a + b = n , 0 ≤ a , b ≤ n ) S(a) + S(b) \ \ (a+b=n \ ,0 \leq a,b \leq n) S(a)+S(b) (a+b=n ,0≤a,b≤n) 。
思路：
思路1 ： 思考后可以发现，两个数 a ， b a，b a，b，因为和为定值， a a a 加 1 1 1， b b b 减 1 1 1，在没有进位、退位的情况下，答案是不变的，直到 a a a 变成全是 9 9 9 这种数（比如 9999999 9999999 9999999），进位之后答案变小了，所以分解成（ 99999999 ）（99999999）（99999999）一定是最优的。
思路2： 还有一种思路，打表观察发现 t t t 个 9 9 9 的这种数（比如 9999999 9999999 9999999），最大值一定是 t ∗ 9 t*9 t∗9，那么我们假设就尽可能的分出 9 9 9 ，这样分解最大。验证后确实如此。
打表代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main(int argc, char const *argv[])
{
    for (LL n = 1; n <= 10000; ++n) {
        LL ans = -1;
        for (LL i = 0; i <= (n+1)/2; ++i) {
            LL tmp = dig(i) + dig(n-i);
            //cout<<i<<" "<<tmp<<endl;
            ans = max(ans, tmp);
        }
        cout<<ans<<endl;
    }
    return 0;
}

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL dig(LL x) {
	LL res = 0;
	while(x) {
		res += x%10;
		x /= 10;
	}
	return res;
}
int main(int argc, char const *argv[])
{
	LL n;
	cin>>n;
	if(n < 10) {
		cout<<n<<endl;
		return 0;
	}
	LL tmp = n;
	LL cnt = 0;
	while(tmp) {
		cnt++;
		tmp /= 10;
	}
	tmp = 0;
	for (int i = 0; i < cnt-1; ++i) {
		tmp *= 10;
		tmp += 9;
	}
	LL ans = dig(tmp) + dig(n-tmp);
	cout<<ans<<endl;
	return 0;
}

C. Maximum Subrectangle（思维卡时间）

题意： 给出数组 a , b a, b a,b ，定义矩阵 c c c， c [ i ] [ j ] = a [ i ] ∗ b [ j ] c[i][j] = a[i] * b[j] c[i][j]=a[i]∗b[j]。现在想让你找一个子矩阵 ( 1 ≤ x 1 ≤ x 2 ≤ n , 1 ≤ y 1 ≤ y 2 ≤ m ) (1 \leq x1 \leq x2 \leq n\ , 1 \leq y1 \leq y2 \leq m) (1≤x1≤x2≤n ,1≤y1≤y2≤m)使得 ∑ i = x 1 x 2 ∑ j = y 1 y 2 c [ i ] [ j ] ≤ x \sum _{i=x1} ^{x2} \sum _{j=y1} ^{y2} c[i][j] \leq x ∑i=x1x2∑j=y1y2c[i][j]≤x，求最大的 s = ( y 2 − y 1 + 1 ) ∗ ( x 2 − x 1 + 1 ) s = (y2-y1+1) * (x2-x1+1) s=(y2−y1+1)∗(x2−x1+1)。
思路：
∑ i = x 1 x 2 ∑ j = y 1 y 2 c [ i ] [ j ] = ∑ i = x 1 x 2 ∑ j = y 1 y 2 a [ i ] ∗ b [ j ] = ( ∑ i = x 1 x 2 a [ i ] ) ∗ ( ∑ j = y 1 y 2 b [ j ] ) \sum _{i=x1} ^{x2} \sum _{j=y1} ^{y2} c[i][j] = \sum _{i=x1} ^{x2} \sum _{j=y1} ^{y2} a[i]*b[j] = (\sum _{i=x1} ^{x2} a[i])* (\sum _{j=y1} ^{y2} b[j]) i=x1∑x2j=y1∑y2c[i][j]=i=x1∑x2j=y1∑y2a[i]∗b[j]=(i=x1∑x2a[i])∗(j=y1∑y2b[j])
矩阵的和就是横向所有数的和乘以纵向所有数的和。
思路1：
预处理一个方向（比如横向）的长度为 i i i 的最小子段和，然后排序。暴力另一个方向（纵向）所有子段，二分找合法的最大横向子段和。复杂度 O ( m a x ( m 2 l o g n , n 2 ) ) O(max(m^2 logn, n^2)) O(max(m2logn,n2)) 。
思路2：
分别预处理 a , b a, b a,b 的长度为 i i i 的最小子段和。然后分别枚举长度。复杂度 O ( m a x ( n ∗ m , n 2 , m 2 ) ) O(max(n*m, n^2, m^2)) O(max(n∗m,n2,m2))。

个人推荐思路2

思路 1 A C 代码思路1AC代码思路1AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAXN = 2100;
const int INF = 0x3f3f3f3f;
LL lena[MAXN*MAXN];
struct node {
	LL val;
	LL num;
	friend bool operator < ( node a, node b ) {
          return a.val<b.val;
    }
};

int main(int argc, char const *argv[])
{
	LL n, m, a[MAXN], b[MAXN], x;
	cin>>n>>m;
	for (LL i = 1; i <= n; ++i) {
		cin>>a[i];
	}
	for (LL i = 1; i <= m; ++i) {
		cin>>b[i];
	}
	cin>>x;
	LL suma[MAXN], sumb[MAXN];
	suma[0] = 0;
	for (LL i = 1; i <= n; ++i) {
		suma[i] = suma[i-1] + a[i];
	}
	sumb[0] = 0;
	for (LL i = 1; i <= m; ++i) {
		sumb[i] = sumb[i-1] + b[i];
	}
	std::vector<node > sumaz; 
	memset(lena, INF, sizeof(lena));
	for (LL i = 1; i <= n; ++i) {
		for (LL j = i; j <= n; ++j) {
			lena[j-i+1] = min(lena[j-i+1], suma[j] - suma[i-1]);
		}
	}
	for (LL i = 1; i <= n; ++i) {
		sumaz.push_back((node){lena[i], i});
	}
	sort(sumaz.begin(), sumaz.end());
	LL s = 0;
	for (LL i = 1; i <= m; ++i) {
		for (LL j = i; j <= m; ++j) {
			node tmp;
			tmp.val = x/(sumb[j] - sumb[i-1]);
			vector<node >::iterator it = lower_bound(sumaz.begin(), sumaz.end(), tmp);
			if(it != sumaz.end()) {
				if(((*it).val)*(sumb[j] - sumb[i-1]) <= x)
					s = max(s, (j-i+1)*((*it).num));
				else {
					if(it != sumaz.begin()){
						it--;
						s = max(s, (j-i+1)*((*it).num));	
					}
				}
			}
			else {
				it--;
				s = max(s, (j-i+1)*((*it).num));
			}
		}
	}
	cout<<s<<endl;
	return 0;
}

思路 2 A C 代码思路2AC代码思路2AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 2100;
const int INF = 0x3f3f3f3f;
LL lena[MAXN*MAXN];
LL lenb[MAXN*MAXN];

int main(int argc, char const *argv[])
{
	LL n, m, a[MAXN], b[MAXN], x;
	cin>>n>>m;
	for (LL i = 1; i <= n; ++i) {
		cin>>a[i];
	}
	for (LL i = 1; i <= m; ++i) {
		cin>>b[i];
	}
	cin>>x;
	LL suma[MAXN], sumb[MAXN];
	suma[0] = 0;
	for (LL i = 1; i <= n; ++i) {
		suma[i] = suma[i-1] + a[i];
	}
	sumb[0] = 0;
	for (LL i = 1; i <= m; ++i) {
		sumb[i] = sumb[i-1] + b[i];
	}
	memset(lena, INF, sizeof(lena));
	for (LL i = 1; i <= n; ++i) {
		for (LL j = i; j <= n; ++j) {
			lena[j-i+1] = min(lena[j-i+1], suma[j] - suma[i-1]);
		}
	}
	
	memset(lenb, INF, sizeof(lenb));
	for (LL i = 1; i <= m; ++i) {
		for (LL j = i; j <= m; ++j) {
			lenb[j-i+1] = min(lenb[j-i+1], sumb[j] - sumb[i-1]);
		}
	}
	LL s = 0;
	for (LL i = 1; i <= n; ++i) {
		for (LL j = 1; j <= m; ++j) {
			if(lena[i] * lenb[j] <= x) {
				s = max(s, i*j);
			}
		}
	}
	cout<<s<<endl;
	return 0;
}

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)