http://codeforces.com/contest/1288

B. Yet Another Meme Problem

 

题意：找到给定范围 1≤a≤A,1≤b≤B1≤a≤A, 1≤b≤B 中满足下图所示的数对个数。

a⋅b+a+b=a⋅10p+ba\cdot b+a+b=a\cdot 10^p +b，其中 pp 为 bb 的十进制下位数。

得到 b=10p−1b=10^p-1 ，即 bb 为 9,99,999⋯9,99,999\cdots， aa 任意。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int T;
ll a, b;
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%I64d%I64d", &a, &b);
		int cnt = 0;
		ll tmp = 9;
		while (b >= tmp) {
			tmp *= 10;
			tmp += 9;
			cnt++;
		}
		printf("%I64d\n", a*cnt);
	}
	return 0;
}

 

C. Two Arrays

 

题意：确定两个长度为 mm 的数列，a数列非递减，b数列非递增，且b对应位置大于a。a，b元素都在 11 到 nn 之间。

先考虑 m=2m=2 的情况，有：

{b1≥a1b2≥a2b1≥b2a2≥a1\begin{cases} b_1\geq a_1\\ b_2\geq a_2\\ b_1\geq b_2\\ a_2\geq a_1 \end{cases}

即

a1≤a2≤b2≤b1a_1\leq a_2\leq b_2\leq b_1

mm 更大的情况也可以大胆推测，就是求一个包含 2m2m 个元素，每个元素都在 11 到 nn 的数列个数。

dp[i] [j] 表示元素为 11 到 ii ，有 jj 个元素的情况数，可以很快发现，也可以打表得到，dp[i] [j]=dp[i-1] [j]+dp[i] [j-1]

最后取dp[n] [2m]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
int n, m;
ll dp[1010][100];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)dp[i][1] = i;
	for (int j = 1; j <= 2 * m; j++)dp[1][j] = 1;
	for (int j = 2; j <= 2 * m; j++) {
		for (int i = 2; i <= n; i++)dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
	}
	cout << dp[n][2 * m] << endl;
	return 0;
}

 

D. Minimax Problem

 

题意：给出n个含m个元素的数组。可以任取两个数组，将对应位置变为其中大的那个，合成为一个新的数组，要使新的数组中最小元素最大。

最小最大问题还是二分。

直接二分答案，最终的最小元素值。则是要两个数组，第一个中有某些位置大于二分值，第二个也是，则这两个数组的位置必须要互补。就是check时要判断的。

由于m很小，直接状压。

二分时若取mid=(L+R+1)/2，由于最小元素为0也是可能的，所以要取初始L=-1。注意这里是因为mid=0时也要check一边，而正常的二分这里可以不用check直接跳出了，所以如果只是要得到结果，初始化L=0是对的。

若取L=mid+1，R=mid-1，则while(L<=R),因为L=R时的mid也要check到。这里是不论怎样都要的，因为需要即使只要结果，也需要更新ans=L=R。

还要记得清空check数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 3e5 + 10;
int n, m;
int a[maxn][10];
int id[maxn];
int ans1, ans2;
bool check(int mid) {
	memset(id, 0, sizeof(id));
	for (int i = 1; i <= n; i++) {
		int s = 0;
		for (int j = 0; j < m; j++) {
			if (a[i][j] >= mid)s |= (1 << j);
		}
		id[s] = i;
	}
	for (int i = (1 << m) - 1; i; i--) {
		for (int j = 0; j < m; j++)if (id[i]&&(i&(1 << j)))id[i ^ (1 << j)] = id[i];
	}
	for (int i = 0; i < (1 << m); i++)if (id[i] && id[((1 << m) - 1) ^ i]) {
		ans1 = id[i]; ans2 = id[((1 << m) - 1) ^ i];
		return 1;
	}
	return 0;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < m; j++)scanf("%d", &a[i][j]);
	}
	int L = -1, R = 1e9;
	while (L < R) {
		int mid = (L + R + 1) / 2;
		if (check(mid))L = mid;
		else R = mid - 1;
	}
	printf("%d %d\n", ans1, ans2);
	return 0;
}