「解题报告」AtCoder Beginner Contest 178

人生 AK 第一场,不过我还是这么的菜……

比赛链接

A. Not

考察输入输出。

1
2
3
#include<iostream>
using namespace std;
int main() {int x; cin >> x; x ^= 1; cout << x;}

B. Product Max

对四个值取个 $\max$ 即可。

1
2
3
4
5
6
7
8
9
10
#include<iostream>
using namespace std;
#define LL long long
LL a, b, c, d, x, y;
int main()
{
cin >> a >> b >> c >> d;
x = max(a * c, a * d), y = max(b * c, b * d);
cout << max(x, y);
}

C. Ubiquity

简单容斥一下即可。

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>
using namespace std;
const int P = 1e9 + 7;
int qp(int a,int b) {int r = 1; while(b) {if(b & 1) r = 1ll * r * a % P; a = 1ll * a * a % P; b >>= 1;} return r;}
int n;
int main()
{
cin >> n;
int ans = qp(10, n), k = 2ll * qp(9, n) % P;
ans = (ans - k + P) % P, k = qp(8, n), ans = (ans + k) % P;
cout << ans;
}

D. Redistribution

枚举数列的长度,然后简单插板即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
#include<cstring>
#include<iostream>
const int P = 1e9 + 7;
using namespace std;
const int CN = 2e3 + 100;
int C[CN][CN];
void pcal(int n){
C[0][0] = 1;
for(int i = 1; i <= n; i++){
C[i][0] = 1;
for(int j = 1; j <= i; j++) C[i][j] = ( C[i - 1][j] +0ll+ C[i - 1][j - 1] ) % P;
}
}
int n, ans = 0;
int main()
{
ios :: sync_with_stdio(false);
cin >> n, pcal(n);
int ans = 0;
for(int l = 1; l * 3 <= n; l++) ans = (ans + C[n - l * 2 - 1][l - 1]) % P;
cout << ans << endl;
}

E. Dist Max

求平面曼哈顿距离的最大值,有一个经典的技巧是把曼哈顿距离的绝对值拆成四个值的 $\max$,即有:
$$|x-x’|+|y-y’|=\max x-x’+y-y’, x-x’+y’-y, x’-x+y-y’, x’-x+y’-y$$ 于是维护一下 $x+y$ 和 $x-y$ 的最大最小值更新答案即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
#define int long long
const int CN = 2e5 + 5;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n, x[CN], y[CN], mx = -INF, mn = INF, ans = -INF;
signed main()
{
ios :: sync_with_stdio(false);
freopen("_in.in", "r", stdin);
cin >> n;
for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];
for(int i = 1; i <= n; i++) mx = max(mx, x[i] + y[i]), mn = min(mn, x[i] + y[i]);
ans = max(ans, mx - mn);
mx = -INF, mn = INF;
for(int i = 1; i <= n; i++) mx = max(mx, x[i] - y[i]), mn = min(mn, x[i] - y[i]);
ans = max(ans, mx - mn);
cout << ans;
}

F. Contrast

大概拿set维护一下就好,但是我的做法好像假了,不过考场上瞎搞过去了……
做法先咕着吧。

先贴一份假代码:

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<set>
using namespace std;
const int CN = 2e5 + 5;
int read(){
int s = 0,ne = 1; char c = getchar();
while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
return s * ne;
}
int n, a[CN], b[CN]; int cnt[CN]; set<int, greater<int> > S;
int main()
{
n = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 1; i <= n; i++) b[i] = read(), S.insert(b[i]), cnt[ b[i] ]++;
memset(b, 0, sizeof(b));

bool flag = true;
for(int i = 1; i <= n && flag; i++){
bool has = false;
for(set<int> :: iterator it = S.begin(); it != S.end(); it++){
int val = *it;
if(val ^ a[i]){
b[i] = val, has = true, cnt[val]--;
if(!cnt[val]) S.erase(it); break;
}
}
flag &= has;
}

if(!flag) puts("No");
else{
puts("Yes");
for(int i = 1; i <= n; i++) printf("%d ", b[i]);
}
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×