CF1618A Polycarp and Sums of Subsequences 题解

题目大概是 「USACO21OPEN」 Do You Know Your ABCs? 的弱化版

题目大意

给出 7 个数, 他们分别代表

\[a, b, c, a + b, a + c, b + c, a + b + c \]

下文中用 \(A\) 数组表示输入的数。

求 \(a, b, c\)。

注意:那7个数是经过排序的, 所以答案不一定是\(A_1,A_2,A_3\)

题解

可以发现, 虽然有一些数的位置不确定, 但是有一些数是固定的, 比如 \(A_1, A_7, A_5\) 一定是 \(a, a + b + c, a + c\)。

根据这三个数顺着往下推就有:

\[a = A_1 \]

尝试化简以上的式子

\[b = (a + b + c) - (a + c) = A_7 - A_5 \]

\[c = (a + c) - a = A_5 - A_1 \]

这道题应该是有SPJ的, 所以 \(a, b, c\) 的顺序不用保证

Code

想明白了代码就有了。

// the code is from zxy
#include <bits/stdc++.h>

int a[8];
inline int read() {int x; scanf("%d", &x); return x;}
inline void solve() {
	int n = 7;
	for (int i = 1; i <= n; i++) a[i] = read();
	printf("%d %d %d\n", a[1], a[7] - a[5], a[5] - a[1]);
}

int main() {
	int T = read();
	while(T--) solve();
	return 0;
}
上一篇:Practical Recommender Systems 2019.1


下一篇:论文阅读:matrix factorization techniques for recommender systems—我的第一篇博客