A
题目
这个没什么好说的,就先输出一个 1
,再输出
n
n
n 个 01
就大功告成了。
AC Code:
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
int n;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
cout << 1;
for (int i = 1; i <= n; i ++) cout << "01";
return 0;
}
B
题目
要获取更多
x
x
x 国货币,只能用
x
−
1
x - 1
x−1 国货币换。
所以我们可以从
1
1
1 国一直换到
n
n
n 国,输出,结束。
AC Code:
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
int n;
long long a[200100];
int s[200100], t[200100];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i < n; i ++) cin >> s[i] >> t[i];
for (int i = 1; i < n; i ++) {
a[i + 1] += t[i] * (a[i] / s[i]);
}
cout << a[n];
return 0;
}
C
题目
你会发现, 50 0 3 < 2 ⋅ 1 0 8 500^3<2\cdot10^8 5003<2⋅108,所以可以暴力枚举高桥所在的位置,如果他行进的过程中没有经过海洋就将答案加一。如果经过海洋了就直接枚举下一个点。
AC Code:
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
int h, w, n;
char m[510][510];
string s;
map<char, int> dir;
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
int ans;
bool check(int x, int y) {
for (int i = 0; i < n; i ++) {
int nx = x + dx[dir[s[i]]], ny = y + dy[dir[s[i]]];
if (nx > 0 && nx <= h && ny > 0 && ny <= w && m[nx][ny] == '.') {
x = nx;
y = ny;
}
else return 0;
}
return 1;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> h >> w >> n;
cin >> s;
for (int i = 1; i <= h; i ++) {
for (int j = 1; j <= w; j ++) cin >> m[i][j];
}
dir['L'] = 0, dir['R'] = 1, dir['U'] = 2, dir['D'] = 3;
for (int i = 1; i <= h; i ++) {
for (int j = 1; j <= w; j ++) {
if (m[i][j] == '.') {
ans += check(i, j);
}
}
}
cout << ans;
return 0;
}
D
题目
这个题并不难,但是细节很多,仔细看!我因为一些零碎的细节卡了 40min!
首先,我们先讨论那些“有规律”的部分。我们发现,对于两个数 n n n 和 m m m,在 n m nm nm 范围内有 n + m − 2 × gcd ( n , m ) n + m - 2\times\gcd(n, m) n+m−2×gcd(n,m) 个数满足只被 n n n 和 m m m 中的一个数字整除。
这个结论怎么来的呢?
首先,对于可以被 n n n 整除的一共有 n m n \frac{nm}{n} nnm 共 m m m 个,可以被 m m m 整除的一共有 n m m \frac{nm}{m} mnm 共 n n n 个。
那么 − 2 × gcd ( n , m ) -2\times\gcd(n, m) −2×gcd(n,m) 又是怎么来的呢?
首先, n m nm nm 范围内有 n m n m gcd ( n , m ) \frac{nm}{\frac{nm}{\gcd(n, m)}} gcd(n,m)nmnm 个数即 gcd ( n , m ) \gcd(n,m) gcd(n,m) 个数可以被 n n n 和 m m m 整除。我们要在可以被 n n n 整除的部分减去它,还要在可以被 m m m 整除的部分减去它。所以是 − 2 × gcd ( n , m ) -2\times\gcd(n,m) −2×gcd(n,m)。
然后我们就可以将答案直接跳到 n m ( k / ( n + m − 2 gcd ( n , m ) ) ) nm(k/(n + m - 2\gcd(n, m))) nm(k/(n+m−2gcd(n,m))),此时 k k k 变成 k m o d ( n + m − 2 gcd ( n , m ) ) k \mod (n + m - 2\gcd(n, m)) kmod(n+m−2gcd(n,m))。
我们继续讨论,可以枚举,用 k 1 k1 k1 和 k 2 k2 k2 两个变量依次跳到答案。如果 k 1 k1 k1 跳的远就跳 k 2 k2 k2,否则跳 k 1 k1 k1。如果两个跳的一样远就都跳依次,这两次不算在跳的次数内。一共跳 k k k 次后,较大的就是满足条件的,加到答案上即可。
你以为这就完了?
如果减掉前面“有规律”的部分后,发现 k k k 等于 0 0 0 时,不加任何特判会输出一个 n m nm nm 的倍数的数。但是我们要的是最大的比上述不合法答案小的答案。此时如果我们把 k k k 设为 n + m − 2 gcd ( n , m ) n+m-2\gcd(n, m) n+m−2gcd(n,m),答案减去 n m nm nm 就可以解决这个问题。
还有一个很重要的东西:long long
!
时间复杂度分析:
按最坏情况来说, gcd ( n , m ) = 1 \gcd(n, m)=1 gcd(n,m)=1,此时时间复杂度就是 n + m n+m n+m,而且跑不到这么多,所以执行次数不会超过 2 ⋅ 1 0 8 2\cdot10^8 2⋅108,合格。
AC Code:
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
long long n, m, k;
long long gcd(long long x, long long y) {
return x % y == 0ll ? y : gcd(y, x % y);
}
long long ans;
long long cnt;
long long cnt1;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> k;
long long g = gcd(n, m);
ans = n * m * (k / (n + m - g * 2));
k = k % (n + m - g * 2);
if (k == 0) {
ans -= n * m;
k += n + m - g * 2;
}
long long k1 = 0ll, k2 = 0ll;
cnt1 = 0ll;
for (long long i = 1; i <= k; i ++) {
if (k1 + n < k2 + m) {
k1 += n;
}
else if (k1 + n > k2 + m) {
k2 += m;
}
else {
k1 += n;
k2 += m;
i--;
}
}
ans += max(k1, k2);
cout << ans;
return 0;
}
E
什么,不是 A-D题解吗?怎么还有 E?文章来源:https://www.toymoban.com/news/detail-826816.html
我才不会给出详细的解法的,我只给一个小小的提示:懒标线段树!文章来源地址https://www.toymoban.com/news/detail-826816.html
到了这里,关于ABC341A-D题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!