A. Optimal Currency Exchange

 

要尽可能多地用掉卢布,而美元以1为单位,欧元以5为单位,所以要n(ax+by)n-(a\cdot x+b\cdot y)尽可能小,且x,y为整数,则枚举x,剩余的卢布数为(nax)modb(n-a\cdot x)\mod b

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<queue>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 2e6 + 5;
int n, d, e;
int res = 0x3f3f3f3f;
int main() {
cin >> n >> d >> e;
for (int i = 0; i <= n / d; i++) {
res = min(res, (n - i * d) % (5 * e));
}
cout << res;
return 0;
}

 

B. Badges

 

算出男生最多和女生最多的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
#define ll long long
int a, b, n;
int main() {
cin >> a >> b >> n;
int ans = min(n, a) - (n - min(n, b)) + 1;
cout << ans;
return 0;
}

 

C. Bad Sequence

 

有两种情况不合法

  • 过程中某一时刻 ’ ) ’ 数量比 ’ ( ’ 数量多出大于1个,此时仅靠一次交换时无法调整的。
  • 整条串中左右括号数量不同。
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
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
using namespace std;
#define ll long long
int n;
char c;
map<char, int>mp;
int t;
bool flg;
int main() {
mp['('] = 1; mp[')'] = -1;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
cin >> c;
t += mp[c];
if (t < -1) {
cout << "No";
return 0;
}
}
if (t != 0)cout << "No";
else cout << "Yes";
return 0;
}

 

D. Treasure Island

 

观察发现只要在(1,1)右和下都堵上,就绝对无法走出,所以答案只可能是0,1,2。

先跑一遍dfs以先下后右的原则找到一条路(这么贪心是为了限制只找到一条路),若不能跑到终点,则答案为0;在跑的同时把所有经过的点都标记为不可走,再跑一边dfs,若不能跑到终点,则答案为1,否则为2.

在跑第一遍dfs的时候一定要把所有经过的点都标记为不可走,无论它是否在最终得到的路径上。原因在于,由于我们贪心地寻找路径,所以最终找到地一定是一条路径,而其它所有过程中经过的点都是不在正确的路径上的(即这点是死胡同),所以为了节约时间,下一次dfs时一定是不希望经过这些死胡同点的,所以干脆标记为不可走。

起初,我错误地认为只要验证堵住(1,1)的右,下两点即可,这是错误的。因为堵住了右点,可能仍有路径达到终点,导致我的答案为2,而堵住另外某一点,可能直接封死,答案为1.

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 1e6 + 5;
int n, m, ans;
string mz[maxn];
bool dfs(int x, int y) {
if (x >= n || y >= m || mz[x][y] == '#')return false;
if (x == n - 1 && y == m-1)return true;
if (x || y) mz[x][y] = '#';
return dfs(x + 1, y) || dfs(x, y + 1);
}
int main() {
cin.sync_with_stdio(false);
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> mz[i];
}
if (!dfs(0, 0))cout << 0;
else {
if (!dfs(0, 0))cout << 1;
else cout << 2;
}
return 0;
}