AcWing Weekly-84

发布于 2022-12-24  1133 次阅读


因为C题被我一眼原了。。所以又rank4了

奇偶

给定一个由小写字母组成的字符串，请你统计其中包含的不同小写字母数量。

如果给定字符串中包含奇数个不同小写字母，则输出 odd。

如果给定字符串中包含偶数个不同小写字母，则输出 even。

输入格式

共一行，一个由小写字母组成的字符串。

输出格式

共一行，按题目要求输出答案。

如果给定字符串中包含奇数个不同小写字母，则输出 odd。

如果给定字符串中包含偶数个不同小写字母，则输出 even。

数据范围

所有测试点满足，给定字符串的长度范围 [1,100]。

输入样例1：

wjmzbmr

输出样例1：

even

输入样例2：

xiaodao

输出样例2：

odd

输入样例3：

sevenkplus

输出样例3：

even

就没什么可说的吧，去重看一下长度

#include <bits/stdc++.h>

using namespace std;
/*
 * author: Paren
 * time:2022/12/18 Sun
 */
#define all(c) (c).begin(), (c).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define Sum(a) accumulate((a).begin(), (a).end() , 0ll)
#define Min(a) *std::min_element((a).begin(), (a).end())
#define Max(a) *std::max_element((a).begin(), (a).end())
#define rev(a) reverse((a).begin(), (a).end())
#define each(x, a) for(auto& x : a)
#define mst(a, x) memset(a, x, sizeof(a))
#define rep(i, from, to) for(ll i = from;i<to;i++)
#define rrep(i, from, to) for(ll i = from;i>=to;i--)
#define to_uni(a) a.erase(unique(begin(a), end(a)), end(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
#define ll long long
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1e9 + 7;
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int N = 1e6 + 10;

void solve() {
    string s;
    cin >> s;
    set<char> m(all(s));
    if (sz(m) % 2 == 0) {
        cout << "even";
    } else {
        cout << "odd";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

闯关

某综艺频道推出了一个闯关活动。

活动一共包含$n$个关卡（编号 1∼n），其中 $m$ 个关卡为特殊关卡。

每个关卡都有一个通关分数，其中第 i 个关卡的通关分数为$a_i$。

挑战者可以自由决定所有关卡的具体挑战顺序，并且每通过一个关卡就可以获得该关卡的通关分数。

值得注意的是，当挑战者即将挑战的关卡是特殊关卡时，如果挑战者当前已经获得的总分数大于该特殊关卡的通关分数，则挑战者可以对该关卡的通关分数进行一次修改，修改后的新分数不能小于原分数，也不能大于挑战者当前已经获得的总分数。

请你计算并输出挑战者通过所有关卡获得的总分数的最大可能值。

输入格式

第一行包含两个整数 $n,m$。

第二行包含 n 个整数 $ a_1,a_2,…,a_n$，表示每个关卡的通过分数。

第三行包含 m 个整数$ b_1,b_2,…,b_m$，表示每个特殊关卡的编号。

输出格式

一个整数，表示挑战者通过所有关卡获得的总分数的最大可能值。

保证最终答案不超过 $2^{64}−1$。

数据范围

前 4 个测试点满足 $1≤n≤4$。
所有测试点满足 $1≤n,m≤100，m≤min(n,30)，1≤a_i≤10^7，1≤b_i≤n_1≤b_i≤n$，$b_i$ 两两不同。

输入样例1：

4 1
1 3 7 5
3

输出样例1：

18

输入样例2：

3 2
10 3 8
2 3

输出样例2：

40

输入样例3：

2 2
100 200
1 2

输出样例3：

400

输入样例4：

1 1
1
1

输出样例4：

1

对于所有的非特殊关卡，我们注意到他最终对答案的贡献度是一致的，因此我们只需要保证特殊关卡的贡献度最大化

对于特殊关卡，我们可以换一种思考方法，已知$a_i$是其实际贡献度，要使贡献度之和最大，可以转化为求贡献度与实际值差值的最大求法

假设最终贡献度为 $c_i$，则有期望值为$\sum_0^{m}(c_i-a_i)$。

由此可以想到要让尽量多的值为*2的贡献度，

由此采用堆思想，将尽量少的特殊关卡作为直接加贡献度，即优先让高的贡献度的进行贡献，最终升序的个数*2即可

#include <bits/stdc++.h>

using namespace std;
/*
 * author: Paren
 * time:2022/12/18 Sun
 */
#define all(c) (c).begin(), (c).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define Sum(a) accumulate((a).begin(), (a).end() , 0ll)
#define Min(a) *std::min_element((a).begin(), (a).end())
#define Max(a) *std::max_element((a).begin(), (a).end())
#define rev(a) reverse((a).begin(), (a).end())
#define each(x, a) for(auto& x : a)
#define mst(a, x) memset(a, x, sizeof(a))
#define rep(i, from, to) for(ll i = from;i<to;i++)
#define rrep(i, from, to) for(ll i = from;i>=to;i--)
#define to_uni(a) a.erase(unique(begin(a), end(a)), end(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
#define ll long long
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1e9 + 7;
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int N = 1e6 + 10;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    priority_queue<ll> pq;
    for (int i = 0; i < m; i++) {
        int t;
        cin >> t;
        pq.push(a[t - 1]);
        sum -= a[t - 1];
    }
    while (!pq.empty()) {
        if (sum >= pq.top()) {
            sum <<= 1;
        } else {
            sum += pq.top();
        }
        pq.pop();
    }
    cout << sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

构造序列

对于一个长度为 nn 的正整数序列$ a_1,a_2,…,a_n$，我们这样规定该序列的价值：

  • 如果 n 为偶数，则序列价值为$$gcd(a_1,a_2)+gcd(a_3,a4)+…+gcd(a{n−1},a_n)$$。
  • 如果 n 为奇数，则序列价值为$$gcd(a_1,a_2)+gcd(a_3,a4)+…+gcd(a{n−2},a_{n−1})$$。

请你构造一个长度为 nn 的正整数序列 $ a_1,a_2,…,a_n$，要求：

  1. $a_i$ 两两不同。
  2. $1≤a_i≤10^9$。
  3. 序列价值恰好为 mm。

输入格式

共一行，两个整数 $n,m$ 。

输出格式

共一行，如果序列不存在，则输出 -1，否则输出$ a_1,a_2,…,a_n$。

如果答案不唯一，输出任意合理答案均可。

数据范围

前 7 个测试点满足 $1≤n≤10$。
所有测试点满足 $1≤n≤10^5$。

输入样例1：

5 2

输出样例1：

1 2 3 4 5

输入样例2：

5 3

输出样例2：

2 4 3 7 1

输入样例3：

7 2

输出样例3：

-1

所有奇数按照顺序排列不就是两两互质吗？

#include <bits/stdc++.h>

using namespace std;
/*
 * author: Paren
 * time:2022/12/18 Sun
 */
#define all(c) (c).begin(), (c).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define Sum(a) accumulate((a).begin(), (a).end() , 0ll)
#define Min(a) *std::min_element((a).begin(), (a).end())
#define Max(a) *std::max_element((a).begin(), (a).end())
#define rev(a) reverse((a).begin(), (a).end())
#define each(x, a) for(auto& x : a)
#define mst(a, x) memset(a, x, sizeof(a))
#define rep(i, from, to) for(ll i = from;i<to;i++)
#define rrep(i, from, to) for(ll i = from;i>=to;i--)
#define to_uni(a) a.erase(unique(begin(a), end(a)), end(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
#define ll long long
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1e9 + 7;
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int N = 1e6 + 10;

void solve() {
    int n, k;
    cin >> n >> k;
    if (n / 2 > k || (k == 0 && n >= 2) || (n == 1 && k != 0)) {
        cout << -1;
        return;
    }
    if (k != 0) {
        int x = 1 + k - n / 2, h1 = x, h2 = 3 * x, s = 2;
        if (x) cout << h1 << " " << h2 << " ";
        else cout << "1 3 ", h1 = 1, h2 = 3;
        int nn = n % 2 == 0 ? n / 2 : n / 2;
        int i;
        for (i = 1; s <= nn; i += 4) {
            if (i != h1 && i + 2 != h2 && i != h2 && i + 2 != h1) {
                cout << i << " " << i + 2 << " ";
                s++;
            }
        }
        if (n % 2 == 1) {
            cout << (i > max(h1, h2) ? i + 2 : 2 + max(h1, h2));
        }
    } else {
        cout << 1;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

绝对不是恋爱脑！