2020-11-05

2015 ACM/ICPC, Asia Changchun Regional

字数统计: 5.4k字 | 阅读时长: 28分

solved	A	B	C	D	E	F	G	H	I	J	K	L	M
7 / 13	Ø	·	·	·	Ø	O	Ø	Ø	·	Ø	·	O	·

O：比赛时通过
Ø：赛后通过
!：比赛时尝试了未通过
·：比赛时未尝试

REPLY

Sstee1XD:

为啥签到题多了两小时的罚时？这一切的背后到底是因为我太菜了，还是我太菜了。
遇事不决网络流，完全背包都看不出来Orz。

比赛链接

A - Too Rich

【思维 + 贪心】

solved by Sstee1XD. (-)

题意： 给你一定数量的面值分别为 $1,5,10,20,50,100,200,500,1000,2000$ 的货币，要你用最多数量货币正好凑出 $p$ 元。

题解： 要凑出最多的货币比较难写，所以我们运用反向思维，求出所有货币的总值 $sum$ ，求用最少数量的货币凑出 $sum - p$ 元，最后的答案就是货币总数减去使用的数量。现在乍一看还是很难写，这时我们观察它给我们的货币种类，发现去除 $50$ 和 $500$ 面值的货币之后，剩下的货币面值都有倍数关系，这时就可以用贪心的方法，优先去选择面值大的货币，就能算出最小的使用数量。我们可以通过枚举使用 $50$ 和 $500$ 面值货币数量的奇偶来处理所有情况，用偶数数量的50和500去凑 $100$ 和 $1000$ ，奇数数量则先用对应的 $1$ 个货币。注意用 $50$ 和 $500$ 去凑的时候，求出来的数量要乘以 $2$ 。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err() { cout << endl; }
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' '; err(args...);
}

typedef long long ll;
const int inf = 0x3f3f3f3f;

int p, c[2500];
int go[] = {1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000};

void solve() {
    cin >> p;
    int sum = 0, tot = 0, res = inf;
    for (int i = 0; i < 10; ++i) cin >> c[go[i]], sum += c[go[i]] * go[i], tot += c[go[i]];
    int tmp = sum - p;
    if (tmp < 0) {
        cout << -1 << endl;
        return;
    }
    for (int k = 1; k <= 4; ++k) {
        int tt = tmp;
        int num = 0;
        if (k == 1) {
            if (c[50] && tt >= 50) tt -= 50, num = 1, c[50]--;
            else continue;
        } 
        if (k == 2) {
            if (c[500] && tt >= 500) tt -= 500, num = 1, c[500]--;
            else continue;
        }
        if (k == 3) {
            if (c[50] && c[500] && tt >= 550) tt -= 550, num = 2, c[50]--, c[500]--;
            else continue;
        }
        int now;
        for (int i = 9; i >= 0; --i) {
            if (go[i] == 50 || go[i] == 500) {
                now = min(tt / go[i] / 2, c[go[i]] / 2);
                tt -= now * go[i] * 2;
                num += now * 2;
            }
            else {
                now = min(tt / go[i], c[go[i]]);
                tt -= now * go[i];
                num += now;
            }
        }
        if (tt == 0) res = min(res, num);
        if (k == 1) c[50]++;
        if (k == 2) c[500]++;
        if (k == 3) c[50]++, c[500]++;
    }
    
    if (res == inf) {
        cout << -1 << endl;
        return;
    }
    cout << tot - res << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int _T;
    cin >> _T;
    while (_T--) solve();
    return 0;
}

【正向思维的贪心 + DFS】

solved by lllllan. (-)

反向遍历：例如手里有6张十元和一张五十元，要求凑出70元。如果从十元开始贪，是凑不出70元的。所以只能反向遍历，先对面值较大的货币进行贪心，而后对面值较小的进行贪心。
贪多：不一样的是这题希望用更过的货币数量来凑出零钱，又因为需要反向遍历，所以出现了一些处理上的小困难。定义sum[i] 表示前i种货币一共能够凑出的价值，通过这个我们能够轻松地知道至少需要多少第(i + 1)种货币。
不成倍数关系无法贪心：前一个例子种进行方向遍历还能完成贪心，但是如果是手里有三张20和一张50，要求凑数50元，反向遍历进行贪心又凑不出来了.针对这种“事故”，需要强制选择一张50。
新的问题： 例如手里有六张20元和两张50元，要求凑出140元。通过前面的“教训”，我们会强制选择一张50元，然后去选择20元，发现坏了，20元不能凑出90元，还是不行。其实我们肉眼观察就知道这种情况需要强制选择两张50元。
然后开始思考，情况复杂时，我到底需要强制选择多少张50元？答案是最多强制选择两张就够了，因为20和50不成倍数关系所以需要强制选择，但是20和两张50则构成了倍数关系，所以再之后就不用管了。至于需要强制选择一张还是两张，则进行两次DFS即可。

AC代码

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

int _T, p, ans;
int sum[12], num[12];
int val[] = {0, 1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000};

void dfs(int res, int idx, int cnt) {	//剩余价值res，第idx种货币，货币数量cnt
	if(res < 0) return;
	if(idx == 0) {
		if(res == 0)	ans = max(ans, cnt);
		return;
	}
	int cur = max(res - sum[idx - 1], 0);
	int cur_cnt = cur / val[idx] + (cur % val[idx] ? 1 : 0); //如果除不尽，需要强制多选一张货币
	if(cur_cnt <= num[idx])	//保证该种货币数量充足才能进行dfs
		dfs(res - cur_cnt * val[idx], idx - 1, cnt + cur_cnt);
	cur_cnt++;	//可能需要强制多选两张货币
	if(cur_cnt <= num[idx])
		dfs(res - cur_cnt * val[idx], idx - 1, cnt + cur_cnt);
}

void run() {
	ans = -1;
	scanf("%d", &p);
	for(int i = 1; i <= 10; i++) {
		scanf("%d", num + i);
		sum[i] = sum[i - 1] + val[i] * num[i];	//前i种货币一共能够凑出的价值
	}
	dfs(p, 10, 0);
	printf("%d\n", ans);
}

int main() {
	scanf("%d", &_T);
	while(_T--)	run();
    return 0;
}

【逆向思维的贪心 + DFS】

solved by lllllan. (-)

求sum - p：用尽可能多的货币去凑出p，反过来当我们知道所有货币一共能够凑出的总价值sum，题目就可以变成求用最少的货币数量去凑出sum - p。
强制选择 ：强制选择方面，则是变成了强制少选一张，细节处理上类似。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;

int _T, p, ans;
int num[12], val[] = {0, 1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000};

void dfs(int tot, int idx, int cnt) {
	if(tot < 0)	return;
	if(idx == 0) {
		if(tot == 0) ans = min(cnt, ans);
		return;
	}
	int tmp = min(num[idx], tot / val[idx]);
	dfs(tot - tmp * val[idx], idx - 1, cnt + tmp);
	if(tmp) dfs(tot - (tmp - 1) * val[idx], idx - 1, cnt + tmp - 1);	//强制少选一张
}

void run() {
	ans = inf;
	int tot = 0, cnt = 0;
	scanf("%d", &p);
	for(int i = 1; i <= 10; i++) {
		scanf("%d", num + i);
		cnt += num[i];
		tot += val[i] * num[i]; 
	}
	dfs(tot - p, 10, 0);
	printf("%d\n", ans == inf ? -1 : cnt - ans);
}

int main() {
	scanf("%d", &_T);
	while(_T--)	run();
    return 0;
}

E - Rebuild

solved by Tryna. (-)

题意： 给出一系列点，这些点依次相连，最后一个点和第一个点相连，形成一个多边形。问以每个点为圆心画一个圆（半径可为0），是否存在当前的圆与相邻的两个圆都相外切，如果有，则找到使总面积最小的方案，如果没有则输出“IMPOSSIBLE”。

题解： 我们设圆的半径为r[1] 到 r[n]，设多边形的边长为d[1] 到 d[n]。于是就有 r[1] + r[2] = d[1] , r[2] + r[3] = d[2] ,
r[3] + r[4] = d[3], r[n-1] + r[n] = d[n-1], r[n] + r[1] = d[n]。
到这里我们可以发现当n为奇数的情况和n为偶数的情况是不一样的。
①. n为奇数，这里我们以n = 3 为例，那就有r[1] + r[2] = d[1] , r[2] + r[3] = d[2]，r[3] + r[1] = d[3], 容易化简得出 r[1] = (d[1] - d[2] + d[3]) / 2。r[1]如果求出来了，那么剩下的所有r都很容易可以得到，那么面积就是固定的。不过这里需要注意如果出现r < 0的情况，那么就输出“IMPOSSIBLE”。

②. n为偶数，这里我们以n = 4为例，那么就有r[1] + r[2] = d[1] , r[2] + r[3] = d[2] , r[3] + r[4] = d[3], r[4] + r[1] = d[4], 满足 d[1] + d[3] = d[2] + d[4], 也就是说只有在这种情况下才有可能有答案。
r[1] = r[1]
r[2] = d[1] - r[1]
r[3] = d[2] - d[1] + r[1]
r[4] = d[3] - d[2] + d[1] - r[1]
我们可以通过这些公式来求出r[1]的范围，因为r是非负数，所以
r[1] >= 0, d[1] - r[1] >= 0, d[2] - d[1] + r[1] >= 0 ,
d[3] - d[2] + d[1] - r[1]>= 0
容易得到r[1]的范围，如果r[1]的左端点大于右端点，那么也输出"IMPOSSIBLE"，我们已知 r[1] + r[2], r[2] + r[3] , r[3] + r[4] ...r[n-1] + r[n],要求min(r[1]^2 + r[2]^2 + r[3]^2 + r[4]^2 +...+ r[n]^2, 其他的r全都可以转化成r[1]，这就变成了一个关于r[1]的二次函数，所以就可以用三分r[1]的方法来找到最小的面积。

AC代码

// #include<bits/stdc++.h>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<iomanip>
using namespace std;    
const double pi = acos(-1.0);
#define inf 0x3f3f3f3f
#define ll long long
#define eps 1e-10
const int maxn = 10010;
const int mod = 1e9 + 7;
#define endl "\n"
int moven2[10][5] = {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}}; 
int moven1[10][5] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int t, n;
double d[maxn], r[maxn];

int sgn(double x){               
    if(fabs(x) < eps) return 0;
    else return x < 0?-1:1;
}

struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
    Point operator + (Point B){return Point(x + B.x,y + B.y);}
    Point operator - (Point B){return Point(x - B.x,y - B.y);}
}P[maxn];

double Dist(Point A,Point B){
    return sqrt((A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y));
}

double f(double radius){
	double Sum = radius * radius;
	r[1] = radius;
	for(int i = 1; i < n; i++){
		Sum += (d[i] - r[i]) * (d[i] - r[i]);
		r[i + 1] = d[i] - r[i];
	}
	return Sum * pi;
}

double sanfen(double L, double R){
	double midl, midr;
	while(R - L > eps){
		midl = L + (R - L)/ 3.0;
		midr = R - (R - L)/ 3.0;
		if(f(midl) > f(midr)) L = midl;
		else R = midr;
	}
	return f(R);
}

int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(0);cout.tie(0);
	scanf("%d", &t);
	while(t--){
		memset(r, 0, sizeof(r));
        memset(d, 0, sizeof(d));
		scanf("%d", &n);
		for(int i = 1; i <= n; i++){
			scanf("%lf%lf", &P[i].x, &P[i].y);
			if(i >= 2){
				d[i - 1] = Dist(P[i - 1], P[i]);
			}
		}
		d[n] = Dist(P[1], P[n]);
		if(n % 2){
			bool f = 1;
			double sum1 = 0;
			for(int i = 1; i < n; i++){
				if(i % 2) sum1 = sum1 + d[i];
				else sum1 = sum1 - d[i];
			}
			r[1] = (sum1 + d[n]) / 2.0;
			for(int i = 1; i < n; i++){
				r[i + 1] = d[i] - r[i];
			}
			for(int i = 1; i <= n; i++){
				if(sgn(r[i]) < 0){
					f = 0;
					break;
				}
			}
			if(f == 0){
				puts("IMPOSSIBLE");
				continue;
			}
			double sum = 0;
			for(int i = 1; i <= n; i++) sum += r[i] * r[i];
			printf("%.2f\n", sum * pi);
			for(int i = 1; i <= n; i++) printf("%.2f\n", r[i]);
		}
		else{
			double left = 0, right = d[1], pre = d[1];
			for(int i = 2; i <= n; i++){
				pre = d[i] - pre;
				if(i % 2) right = min(right, pre);
				else left = max(left, -pre);
			}
			double ans = sanfen(left, right);
			if(fabs(r[1] + r[n]) - d[n] > eps || left > right) puts("IMPOSSIBLE");
			else{
				printf("%.2f\n",ans);
          		for(int i = 1; i <= n; i++)
            		printf("%.2f\n",r[i]);
			}
		}
	}
	return 0;
}

F - Almost Sorted Array

solved by Sstee1XD & lllllan. 1:19(+3)

题意： 给你一个序列，问你是否可以只移除一个数字使序列有序。

题解： 非递增非递减都判断一下。注意判断要删哪个点。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
#define endl "\n"
int a[maxn];
int n;

void solve() {
	int f = 0;
	int ch = 0;
	for (int i = 2; i <= n; ++i) {
		if (a[i] < a[i - 1]) {
			if (f) break;
			f = 1;
			ch = i;
		}
		if (i == n) {
			if (!f || ch == n || ch == 2 || a[ch - 1] <= a[ch + 1] || a[ch - 2] <= a[ch]) {
				puts("YES");
				return;
			}
		}
	}
	f = 0;
	ch = 0;
	for (int i = 2; i <= n; ++i) {
		if (a[i] > a[i - 1]) {
			if (f) break;
			f = 1;
			ch = i;
		}
		if (i == n) {
			if (!f || ch == n || ch == 2 || a[ch - 1] >= a[ch + 1] || a[ch - 2] >= a[ch]) {
				puts("YES");
				return;
			}
		}
	}
	puts("NO");
}
int main() {
	int _T;
	scanf("%d", &_T);
	while (_T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i) {
			scanf("%d", &a[i]);
		}
		solve();
	}
	return 0;
}

G - Dancing Stars on Me

solved by Tryna. (-)

题意： 给出n个点，问这n个点是否能构成正多边形

题解： 比赛中一共试了两种方法，一个是老老实实按照题意来判断，另外一个是后面想到的，因为给出的点都是整数，所以只能构成正四边形。最后没有通过的原因是因为极角排序写的有问题，对板子的理解还不够深刻，本来能一发A的，我反思。下面把两种代码都贴一下

AC代码

//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 110;
#define eps 1e-8
int sgn(double x){
	if(fabs(x) < eps) return 0;
	else return x < 0? -1 : 1;
}

int dcmp(double x, double y){
	if(fabs(x - y) < eps) return 0;
	else return x < y ? -1 : 1;
}

struct Point{
	double x, y;
	Point(){}
	Point(double x, double y):x(x),y(y){}
	Point operator - (Point B){
		return Point(x - B.x, y - B.y);
	}
}P[maxn];

double Dist(Point A, Point B){
	return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

double Dot(Point A, Point B){
	return A.x*B.x + A.y * B.y;
}

double Len(Point A){
	return sqrt(Dot(A,A));
}

double Angle(Point A, Point B){
	return acos(Dot(A,B)/Len(A)/Len(B));
}

double Cross(Point A, Point B){
	return A.x * B.y - A.y * B.x;
}

int cmp(Point A, Point B){
	return Cross(A - P[0], B - P[0]) > 0;
}
int t, n;
int main() {
	scanf("%d", &t);
	while(t--){
		scanf("%d", &n);
		int f = 1;
		for(int i = 0; i < n; i++) scanf("%lf%lf", &P[i].x, &P[i].y);
		sort(P, P + n, cmp);
		P[n].x = P[0].x;
		P[n].y = P[0].y;
		P[n + 1].x = P[1].x;
		P[n + 1].y = P[1].y;
		for(int i = 2; i <= n; i++){
			if(dcmp(Dist(P[i], P[i - 1]), Dist(P[i - 1], P[i - 2])) != 0){
				f = 0;
				break;
			} 
		}
		if(f == 0){
			puts("NO");
			continue;
		}
		double ang1 = Angle(P[2] - P[1], P[1] - P[0]);
		for(int i = 3; i <= n + 1; i++){
			if(dcmp(ang1, Angle(P[i] - P[i - 1], P[i - 1] - P[i - 2])) != 0){
				f = 0;
				break;
			}
		}
		if(f == 0){
			puts("NO");
			continue;
		}
		for(int i = 2; i <= n + 1; i++){
			if(Cross(P[i - 2] - P[i - 1], P[i - 1] - P[i]) < 0){
				f = 0;
				break;
			}
		}
		if(f == 0){
			puts("NO");
			continue;
		}
		puts("YES");
	}
    return 0;
}

AC代码

//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 110;
#define eps 1e-8
int sgn(double x){
	if(fabs(x) < eps) return 0;
	else return x < 0? -1 : 1;
}

int dcmp(double x, double y){
	if(fabs(x - y) < eps) return 0;
	else return x < y ? -1 : 1;
}

struct Point{
	double x, y;
	Point(){}
	Point(double x, double y):x(x),y(y){}
	Point operator - (Point B){
		return Point(x - B.x, y - B.y);
	}
}P[maxn];
Point ch[maxn];
double Dist(Point A, Point B){
	return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

double Dot(Point A, Point B){
	return A.x*B.x + A.y * B.y;
}

double Len(Point A){
	return sqrt(Dot(A,A));
}

double Angle(Point A, Point B){
	return acos(Dot(A,B)/Len(A)/Len(B));
}

double Cross(Point A, Point B){
	return A.x * B.y - A.y * B.x;
}

int cmp(Point A, Point B){
	return Cross(A - P[0], B - P[0]) > 0;
}

int t, n;
int main() {
	scanf("%d", &t);
	while(t--){
		memset(P, 0, sizeof(P));
		scanf("%d", &n);
		int f = 1;
		for(int i = 0; i < n; i++) scanf("%lf%lf", &P[i].x, &P[i].y);
		if(n != 4) puts("NO");
		else{
			sort(P, P + n, cmp);
			P[n].x = P[0].x;
			P[n].y = P[0].y;
			P[n + 1].x = P[1].x;
			P[n + 1].y = P[1].y;
			for(int i = 2; i <= n + 1; i++){
				if(dcmp(Dist(P[i], P[i - 1]), Dist(P[i - 1], P[i - 2])) != 0){
					f = 0;
					break;
				} 
			}
			if(f == 0){
				puts("NO");
				continue;
			}
			for(int i = 2; i <= n + 1; i++){
				if(dcmp(1.57079633, Angle(P[i] - P[i - 1], P[i - 2] - P[i - 1])) != 0){
					f = 0;
					break;
				}
			}
			if(f == 0){
				puts("NO");
				continue;
			}
			puts("YES");
		}
		
	}
    return 0;
}

H - Partial Tree

solved by Sstee1XD. (-)

题意： 给你 $n$ 个点和度数为 $1$ ~ $n-1$ 度的点的点权，让你构成一棵树，使其点权最大。

题解： 对于一棵 $n$ 个点构成的树来说，点的总度数为 $2n - 2$ 。我们先让 $n$ 个点每个点的度数为 $1$ ，再去分配剩下来的 $n-2$ 个度数，每个度数对应的权值为 $a_{i + 1} - a_1$ ，即可转换成一个完全背包问题。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 21;
int dp[maxn], a[maxn], n;
int main() {
    int _T;
    scanf("%d", &_T);
    while (_T--) {
        scanf("%d", &n);
        for (int i = 1; i < n; ++i) {
            scanf("%d", &a[i]);
        }
        memset(dp, -0x3f, sizeof(dp));
        dp[0] = 0;
        for (int i = 1; i <= n - 2; ++i) {
            for (int j = i; j <= n - 2; ++j) {
                dp[j] = max(dp[j - i] + a[i + 1] - a[1], dp[j]);
            }
        }
        printf("%d\n", n * a[1] + dp[n - 2]);
    }
    return 0;
}

J - Chip Factory

solved by Sstee1XD. (-)

题意： 给你 $n$ 个数字，求 $\mathop{max}\limits_{i,j,k}(s_i+s_j){\bigoplus}s_k,i\not=j\not=k$ 。

题解： 求异或最大值，很容易想到用01字典树，但是在建树和查找时一直想不到好的时空平衡。这里我们可以先将所有数字插入字典树中，然后枚举 $i,j$ ，先将 $i,j$ 对应的数字从字典树中删除，找到最大值，然后再插入回去，这样就在能 $O(n^2)$ 的复杂度下解决。

AC代码

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

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err() { cout << endl; }
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' '; err(args...);
}
const int maxn = 1e3 + 7;
typedef long long ll;

struct Trie{
    struct Node{
        int nx[3];
        int cnt;
        ll v;
        void init() {
            memset(nx, -1, sizeof(nx));
            cnt = 0;
            v = 0;
        }
    }t[maxn * 31];

    int tot, root;

    int newnode() {
        ++tot;
        t[tot].init();
        return tot;
    }
    void init() {
        tot = 0;
        root = newnode();
    }
    void insert(ll c) {
        int now = root;
        for (int i = 31; i >= 0; --i) {
            int f = (c >> i) & 1;
            if (t[now].nx[f] == -1) t[now].nx[f] = newnode();
            now = t[now].nx[f];
            t[now].cnt++;
        }
        t[now].v = c;
    }
    void clear(ll c) {
        int now = root;
         for (int i = 31; i >= 0; --i) {
            int f = (c >> i) & 1;
            now = t[now].nx[f];
            t[now].cnt--;
        }
    }
    ll query(ll c) {
        int now = root;
        for (int i = 31; i >= 0; --i) {
            int f = (c >> i) & 1;
            if (t[now].nx[f ^ 1] != -1 && t[t[now].nx[f ^ 1]].cnt) now = t[now].nx[f ^ 1];
            else now = t[now].nx[f];
        }
        return t[now].v ^ c;
    }
}trie;

ll a[maxn];
int n;
void solve() {
    trie.init();
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        trie.insert(a[i]);
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        trie.clear(a[i]);
        for (int j = i + 1; j <= n; ++j) {
            trie.clear(a[j]);
            ans = max(trie.query(a[i] + a[j]), ans);
            trie.insert(a[j]);
        }
        trie.insert(a[i]);
    }
    printf("%lld\n", ans);
}
int main() {
    int _T;
    scanf("%d", &_T);
    while (_T--) solve();
    return 0;
}

L - House Building

solved by Tryna. 00:39(+)

题意： 给出一个由若干个正方体堆放而成的几何体，求其表面积。

题解： 第一个想到的就是用所有面积减去那些被遮挡住的面积，总面积是正方体的个数乘6。遮挡的部分一共有三块：1.底面（与地面相接触的那一面），2.两个相邻的正方体左右遮挡住的部分，3.两个相邻的正方体上下遮挡住的部分。

AC代码

//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 60;
int t, n, m, mp[maxn][maxn];
int moven[10][5] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool check(int x, int y){
	if(x < 1 || x > n || y < 1 || y > m || mp[x][y] == 0) return false;
	return true;
}
int main() {
	scanf("%d", &t);
	while(t--){
		int sum1 = 0, sum2 = 0, sum = 0;
		scanf("%d %d", &n, &m);
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				scanf("%d", &mp[i][j]);
				if(mp[i][j]){
					sum = sum + mp[i][j];
					sum1++;
					sum2 += (mp[i][j] - 1);
				} 
			}
		}
		sum = sum * 6;
		sum = sum - sum1;
		sum = sum - 2 * sum2;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				for(int k = 0; k < 4; k++){
					int mx = i + moven[k][0];
					int my = j + moven[k][1];
					if(check(mx, my)) sum = sum - min(mp[i][j], mp[mx][my]);
				}
			}
		}
		printf("%d\n", sum);
	}
    return 0;
}