6f03636c987a0c5fa8.jpg

A - Curtain

翻译练习
高桥的房间的窗户宽A，有两个窗帘悬挂在窗户上，每一个窗帘水平长度为B（竖直方向足够长可以覆盖整个窗户），我们将关闭窗户，以尽量减少窗帘未遮挡部分的总水平长度。求窗户无遮挡部分的水平总长度。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x= x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

signed main() {
	int a = read(), b = read();
	cout << max(0LL, a - 2 * b) << endl;
	return 0;
}

B - TAKOYAKI FESTIVAL 2019

翻译练习
现在是 “高崎节”（TAKOYAKI FESTIVAL）的季节！
今年，$N$章鱼烧（一种球状食物，里面有一块章鱼）将会上桌。$i$章鱼烧的_美味程度是$d_i$。
众所周知，当你同时吃下两个美味度为$x$和$y$的章鱼烧时，就能恢复$x \times y$点健康值。
从$N$个章鱼烧中选择两个的方法有$\frac{N \times (N - 1)}{2}$种。请找出每种选择吃两个章鱼烧所恢复的健康点数，然后计算这$\frac{N \times (N - 1)}{2}$个值的总和。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x= x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

signed main() {
	int n = read();
	vector<int> a(n);
	int ans = 0;
	for(int i = 0; i < n; i++) a[i] = read();
	for(int i = 0; i < n; i++)
		for(int j = i + 1; j < n; j++)
			ans += a[i] * a[j];
	cout << ans << endl;
	return 0;
}

C - Slimes

字符会发生多少次变化

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 int long long
int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x= x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

signed main() {
	int n = read();
	string s;
	cin >> s;
	int ans = 1;
	for(int i = 1; i < s.size(); i++)
	{
		if(s[i] != s[i - 1]) ans++;
	}
	cout << ans << endl;
	return 0;
}

D - Triangles

先确定两个，剩下的一个二分确定范围

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x= x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

signed main() {
	int n = read();
	vector<int> l(n);
	for(int i = 0; i < n; i++) l[i] = read();
	sort(l.begin(), l.end());
	int ans = 0;
	for(int i = 0; i < n; i++)
		for(int j = i + 1; j < n; j++)
		{
			int x = (lower_bound(l.begin(), l.end(), l[i] + l[j]) - l.begin());
			ans += x - j - 1;
		}
		cout << ans << endl;
	return 0;
}

E - Travel by Car

先Floyd一遍
求每个的最短路
然后遍历所有点对
如果距离小于等于油箱限制在1次满油可以直接到达，如果不行不能直接到达
然后再做一次floyd这次边权就变成加油次数

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x= x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}


const int N = 310, M = N * N;
int dis[N][N], h[N], idx;
/**
struct Edge
{
	int e, ne, w;
}E[M];

void add(int a, int b, int c)
{
	E[idx] = {b, h[a], c};
	h[a] = idx++;
}
*/
signed main()
{
	int n = read(),  m = read(), l = read();
	memset(dis, 0x3f, sizeof dis);
	for(int i = 0; i < m; i++)
	{
		int a = read(), b = read();
		dis[a][b] = dis[b][a] = read();
	}
	for (int i = 1; i <= n; i++) dis[i][i] = 0;
	for (int k = 1; k <= n; k++) 
		for (int i = 1; i <= n; i++) 
			for (int j = 1; j <= n; j++)
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
		{
			if (i == j) dis[i][j] = 0;
			else if (dis[i][j] <= l) dis[i][j] = 1;
			else dis[i][j] = 0x3f3f3f3f;
		}
	for (int k = 1; k <= n; k++) 
		for (int i = 1; i <= n; i++) 
			for (int j = 1; j <= n; j++)
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
	int q = read();
	for(int i = 0; i < q; i++)
	{
		int s = read(), t = read();
		if(dis[s][t] == 0x3f3f3f3f) cout << -1 << endl;
		else cout << dis[s][t] - 1 << endl;
	}
	return 0;
}

F

不会，看的题解