https://ac.nowcoder.com/acm/contest/923

A. 小w的a+b问题

 

题意：两个32位整型的正数相加后溢出得到负数，现给出负数，求一组正数。

把负数加2*2147483648得到对应的正数，然后随便凑一组即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
ll x, ans;
int main() {
	ans = 2147483647ll + 2147483647ll + 2ll;
	cin >> x;
	if (x == -1)puts("No solution");
	else cout << ans + x- 2147483647ll << ' ' << 2147483647 << endl;
	return 0;
}

 

B. 小w的a=b问题

 

题意：两个数组，问 ∏i=1na[i]\prod_{i=1}^na[i] 是否等于 ∏i=1mb[i]\prod_{i=1}^mb[i]。

刚开始想用log换成加，但是试了几次发现精度还是有问题，gg。

直接用几个mod，或者找个牛逼的mod。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const double eps = 1e-10;
double fac[N];
int T, n, m;
int main() {
	fac[0] = fac[1] = 0;
	for (int i = 2; i <= 100000; i++) {
		fac[i] = fac[i - 1] + log(1.0*i)/log(11);
	}
	scanf("%d", &T);
	while (T--) {
		double a = 0, b = 0;
		scanf("%d%d", &n, &m);
		for (int i = 0; i < n; i++) {
			int x;
			scanf("%d", &x);
			a += fac[x];
		}
		for (int i = 0; i < m; i++) {
			int x;
			scanf("%d", &x);
			b += fac[x];
		}
		if (a==b)puts("equal");
		else puts("unequal");
	}
	return 0;
}

 

C. 小w的糖果

 

题意：一个长为n，初始都为0的数组，有三种操作，第一种从pos开始后面都加1，第二种从pos开始后面分别加 1,2,3,⋯1,2,3,\cdots，第三种从pos开始后面分别加 $1^2,2^2,3^2,\cdots $，问最终数组。

差分

第一种操作就是一阶差分，第二种是二阶，第三种是三阶。

三阶就是做三次差分前缀和即可，因为一位与前一位的差是等差数列，而求等差数列可以通过公差的前缀和得到，即在二阶上再加一阶。

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
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int T, n, m, op, p;
ll a[7][N];
int main() {
	scanf("%d", &T);
	while (T--) {
		memset(a, 0, sizeof(a));
		scanf("%d%d", &n, &m);
		for (int i = 0; i < m; i++) {
			scanf("%d%d", &op, &p);
			if (op == 1) {
				a[1][p]++;
			}
			else if (op == 2) {
				a[2][p]++;
			}
			else {
				a[3][p] += 2; a[4][p]++; a[5][p]++;
			}
		}
		for (int j = 1; j <= n; j++) {
			a[1][j] = (a[1][j] + a[1][j - 1]) % mod;
			a[2][j] = (a[2][j] + a[2][j - 1]) % mod;
			a[3][j] = (a[3][j] + a[3][j - 1]) % mod;
			a[4][j] = (a[4][j] + a[4][j - 1]) % mod;
		}
		for (int j = 1; j <= n; j++) {
			a[2][j] = (a[2][j] + a[2][j - 1]) % mod;
			a[3][j] = (a[3][j] + a[3][j - 1]) % mod;
		}
		for (int j = 1; j <= n; j++) {
			a[3][j] = (a[3][j] + a[4][j]) % mod;
		}
		for (int j = 1; j <= n; j++) {
			a[5][j] = (a[5][j] + a[5][j - 1] + a[3][j - 1]) % mod;
		}
		for (int i = 1; i <= n; i++) {
			printf("%lld%s", (a[1][i] + a[2][i] + a[5][i]) % mod, i == n ? "\n" : " ");
		}
	}
	return 0;
}

 

E. 小w的矩阵前k大元素

 

题意：给定两个数组a，b，矩阵 c[i][j]=a[i]+b[j]c[i][j]=a[i]+b[j]，从(0,0)出发，三种操作：向右走，向下走，询问当前位置与(0,0)构成的矩形中所有数从小到大排序后前面k个数。1≤n,m,∑k≤1051\leq n,m,\sum k\leq 10^5

维护两个multiset存储当前矩形区域涉及到的 a[i],b[i]a[i],b[i]，再模拟找到前面k个。

优先队列每次取最小值，然后把最小值拓展开，每次可以向前挪动以保证尽量小，a[i]+b[j]  ⟹  a[i+1]+b[j],a[i]+b[j+1]a[i]+b[j]\implies a[i+1]+b[j],a[i]+b[j+1]

但是还有问题，可能有重复枚举到，所以要规定只能当 i=0i=0 时 jj 才能移动，这样限制了一维，就不会有重复情况了。

还试过map去重，但是 multiset::iterator 没有比较函数，没法用map。

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
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int n, m, q, k, x = 1, y = 1;
char op;
int a[N], b[N];
typedef multiset<int>::iterator sit;
multiset<int>A, B;
struct pii{
	sit fir, sec;
	bool operator<(const pii& b)const {
		return *fir + *sec > *b.fir + *b.sec;
	}
};
void solve(int k) {
	priority_queue<pii>q;
	vector<int>ans;
	q.push(pii{ A.begin(), B.begin() });
	pii tmp;
	while ((int)ans.size() < k) {
		tmp = q.top(); q.pop();
		ans.push_back(*tmp.fir + *tmp.sec);
		if (++tmp.fir != A.end()) {
			q.push(tmp);
		}
		--tmp.fir;
		if (tmp.fir == A.begin() && ++tmp.sec != B.end()) {
			q.push(tmp);
		}
	}
	for (int i = 0; i < k; i++)
		printf("%d%s", ans[i], i == k - 1 ? "\n" : " ");
}
int main() {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 0; i < n; i++)scanf("%d", &a[i]);
	for (int i = 0; i < m; i++)scanf("%d", &b[i]);
	A.insert(a[0]); B.insert(b[0]);
	while (q--) {
		scanf(" %c %d", &op, &k);
		if (op == 'D')
			for (int i = 0; i < k&&x < n; i++, x++)
				A.insert(a[x]);
		else if (op == 'R')
			for (int i = 0; i < k&&y < m; i++, y++)
				B.insert(b[y]);
		else
			solve(k);
	}
	return 0;
}