郑轻19级新生周赛（6）-申璞专场题解_给出一个24小时制的时间,输出x分钟后的时间。

题目链接：http://acm.zzuli.edu.cn/problem.php?id=2579

A：落落大方2

题意：

给定$m$个数（$a_i\le 10^9$），问你能否将这些数分成两组和相等。（$0\le m\le 15$）

思路：

首先如果和是奇数肯定不行，其次m的范围比较小，直接$dfs$暴力看能否组成$\frac{sum}{2}$就行，注意和会爆int。

参考代码：

#include<cstdio>
int n,a[20];
long long sum;
int dfs(int i,int ans) {
	if(i==n)return ans==sum;
	if(dfs(i+1,ans))return 1;
	if(dfs(i+1,ans+a[i]))return 1;
	return 0;
}

int main() {
	while(~scanf("%d",&n)) {
		sum = 0;
		for(int i=0; i<n; i++) {
			scanf("%lld",&a[i]);
			sum+=a[i];
		}
		if(sum&1) {
			printf("NO\n");
		} else {
			sum>>=1;
			if(dfs(0,0))	{
				printf("YES\n");
			} else {
				printf("NO\n");
			}
		}
	}
	return 0;
}
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

B：落落大方3

题意：

给定$n$个数（$a_i\le 100$），问你能否将这些数分成两组和相等。（$0\le n\le 100$）

思路：

大一学有余力可以看看$dp$，这里用01背包，把$\frac{sum}{2}$作为背包容量，判断能否组成$\frac{sum}{2}$即可。

参考代码：

#include<cstdio>
#include<cstring>
int n,a[105];
bool dp[10005];
int main() {
	while(~scanf("%d",&n)) {
		int sum = 0;
		for(int i=0; i<n; i++) {
			scanf("%d",&a[i]);
			sum+=a[i];
		}
		if(sum&1) {
			printf("NO\n");
		} else {
			sum>>=1;
			memset(dp, false, sizeof(dp));
			dp[0] = true;
			for(int i = 0; i < n; i ++) {
				for(int j = sum; j >= a[i]; j--) {
					dp[j] |= dp[j - a[i]];
				}
			}
			printf("%s\n",dp[sum]?"YES":"NO") ;
		}
	}
	return 0;
}
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

C:逆转进制位

题意：

输出$n$（$0\le n\le 10^9$）的$m(2\le m\le 16)$进制逆转的十进制数。

思路：

在将数进行进制转化时，直接计算答案即可。

参考代码：

#include<cstdio>
int n,m;
int main() {
	while(~scanf("%d%d",&n,&m)) {
		long long ans = 0;
		do {
			ans = ans * m + n % m;
			n /= m;
		} while(n > 0);
		printf("%lld\n",ans);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

D：服务优化

题意：

给定一个序列，求最多能有多少人不失望，失望就是说自己的接受时间小于前面一个接受服务的总和。

思路：

贪心，对所有人需要的服务时间升序的进行排列，将队伍调整完成后统计不失望的人即可。

参考代码：

#include <cstdio>
#include <algorithm>
using namespace std;
int n,a[100005];
int main(){
	while(~scanf("%d",&n)){
		for(int i=0;i<n;i++)scanf("%d",&a[i]);
		long long ans=0,sum=0;
		sort(a,a+n);
		for(int i=0;i<n;i++){
			if(sum<=a[i]){
				sum+=a[i];
				ans++;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

E：时间

题意：

给出一个24小时制的时间，输出X分钟后的时间。

思路：

先转化为分钟，加上x后，对一整天的时间取余，即对24*60取余，然后将其转化为小时输出即可，格式用%02d即可，或者直接公示计算x分钟后的h和m，输出即可。

参考代码：

#include <cstdio>
int main() {
	int h, m, x;
	while(~scanf("%d:%d", &h, &m)) {
		scanf("%d", &x);
		h = (h + x / 60 + (x%60+m >= 60)) % 24;
		m = (m + x) % 60;
		printf("%02d:%02d\n", h, m);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11

F:括号匹配

（包括下一题新生可以学一下STL）

题意：

给定一个$n$，现在要求$n$对括号的所有合法序列。

思路：

对于合法的匹配，前面已有的’(‘一定大于等于’)’的数量，所以依次枚举每一位，递归输出所有结果即可。

参考代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
vector<string> v;
char s[500];

void dfs(int l, int r, int i) {
	if(l == 0 && r == 0) {
		v.push_back(s);
		return;
	}
	if(l > 0) {
		s[i] = '(';
		dfs(l-1, r, i+1);
	}
	if(r > 0 && l < r) {
		s[i] = ')';
		dfs(l, r-1, i+1);
	}
}

void solve(int n) {
	v.clear();
	memset(s,0,sizeof(s));
	dfs(n, n, 0);
	sort(v.begin(), v.end());
	for(int i = 0; i < v.size(); i ++)
		cout << v[i] << endl;
}

int main() {
	bool isFirst = true;
	int n;
	while(cin >> n) {
		if(!isFirst)//控制换行 
			cout << endl;
		isFirst = false;
		solve(n);
	}
	return 0;
}
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

G：字符串排序

题意：

使用26个数字重新定义每个小写英文字母的权重，然后给出N个仅包含26个小写英文字母的字符串。
使用给出的字母的权重，对这N个字符串按照字典序排序后，升序输出。

思路：

运用自定义排序。

参考代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
using namespace std;

int a[26],n;
vector<string> v;

int cmp(string x,string y) {
	for(int i = 0; x[i] && y[i]; i ++) {
		if(x[i] != y[i]) {
			return a[ x[i]-'a' ] < a[ y[i]-'a' ];
		}
	}
	return x.size() < y.size();
}

int main() {
	int t;
	cin >> t;
	while(t--) {
		for(int i = 0; i < 26; i ++)
			cin >> a[i];
		v.clear();
		cin >> n;
		for(int i = 0; i < n; i ++) {
			string s;
			cin >> s;
			v.push_back(s);
		}
		sort(v.begin(), v.end(), cmp);
		for(int i = 0; i < n; i ++) {
			cout << v[i] << endl;
		}
	}
	return 0;
}
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

H:矩形面积

题意：

矩形面积交。

思路：

首先分别计算两个矩形的面积和，然后减去他们公共的面积即可。他们公共的面积可以分别计算x轴和y轴的公共长度，然后求乘积。对于某一轴，四个点，可以算出两个矩形对应边的长度，然后减去四个点中相距最远的两个点的长度，如果小于0，则说明不相交，将其算为0.

参考代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
using namespace std;

long long x[4], y[4];

long long area(long long x1, long long y1, long long x2, long long y2) {
	return abs(x1-x2)*abs(y1-y2);
}

long long overlap(long long x1, long long y1, long long x2, long long y2, long long x3, long long y3, long long x4, long long y4) {
	long long dx = min(x2, x4) - max(x1, x3);
	long long dy = min(y1, y3) - max(y2, y4);
	return dx >= 0 && dy >= 0 ? dx * dy : 0;
}

int main() {
	int t;
	cin >> t;
	while(t--) {
		for(int i = 0; i < 4; i ++) {
			cin >> x[i] >> y[i];
		}
		long long ans = 0;
		ans += area(x[0], y[0], x[1], y[1]);
		ans += area(x[2], y[2], x[3], y[3]);
		ans -= overlap(x[0], y[0], x[1], y[1], x[2], y[2], x[3], y[3]);
		cout << ans << endl;
	}
	return 0;
}
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