Educational Codeforces Round 94 (A - D题题解）

https://codeforces.com/contest/1400/problem/A

Example

input

4
1
1
3
00000
4
1110000
2
101

output

1
000
1010
00

思路：先贴下代码，有事要去医院，等会补上思路。

AC代码：

#include<bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
void solve() {
    int n; string s;
    cin >> n >> s;
    for (int i = 0; i < n; ++i)
        cout << s[n - 1];
    cout << endl;
}
int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--)solve();
}

https://codeforces.com/contest/1400/problem/B

Example

input

3
33 27
6 10
5 6
100 200
10 10
5 5
1 19
1 3
19 5

output

11
20
3

思路：

AC代码：

#include<bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof a)
using namespace std;
const int N = 1e5 + 100;
typedef long long ll;
ll n, m, a[N];
void solve() {
    int p, f;
    cin >> p >> f;
    int cnts, cntw, s, w;
    cin >> cnts >> cntw >> s >> w;
    if (s > w) {
        swap(s, w);
        swap(cnts, cntw);
    }
    int maxi = 0;
    for (int i = 0; i <= min(cnts, p / s); i++) {
        int a = min(cntw, (p - i * s) / w);
        int b = min(cnts - i, f / s);
        int c = min(cntw - a, (f - b * s) / w);
        maxi = max(maxi, a + b + c + i);
    }
    cout << maxi << '\n';
}
int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--)solve();
}

https://codeforces.com/contest/1400/problem/C

Example

input

3
101110
2
01
1
110
1

output

111011
10
-1

思路：

AC代码：

#include<bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof a)
using namespace std;
const int N = 1e5 + 100;
typedef long long ll;
ll n, m, a[N];
void solve() {
    ll x; string s, ss = "";
    cin >> s >> x;
    int n = s.size();
    for (int i = 0; i < n; ++i) ss += '1';
    for (int i = 0; i < n; ++i) {
        if (s[i] == '0' && i + x < n)ss[i + x] = '0';
        if (s[i] == '0' && i - x >= 0)ss[i - x] = '0';
    }
    bool flag = true;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '1') {
            bool ok = false;
            if (i + x < n && ss[i + x] == '1') ok = true;
            if (i - x >= 0 && ss[i - x] == '1') ok = true;
            if (!ok) flag = false;
        }
    }
    if (!flag)cout << -1 << endl;
    else cout << ss << endl;
}
int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--)solve();
}

https://codeforces.com/contest/1400/problem/D

Example

input

2
5
2 2 2 2 2
6
1 3 3 1 2 3

output

5
2

思路：

AC代码： 使用map，900+ms

#include<bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof a)
using namespace std;
const int N = 1e5 + 100;
typedef long long ll;
ll a[N];
map<int, int>m1, m2;
void solve() {
    m1.clear();
    int n; cin >> n;
    for (int i = 0; i < n; ++i)cin >> a[i];
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        m2.clear();
        for (int j = n - 1; j > i; --j)
            ans += m1[a[j]] * m2[a[i]], ++m2[a[j]];
        ++m1[a[i]];
    }
    cout << ans << endl;
}
int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--)solve();
}