AcWing Weekly-84

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



因为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;
}

绝对不是恋爱脑!