2019春节前爆炸掉分的一夜

A. Superhero Transformation

Description:

We all know that a superhero can transform to certain other superheroes. But not all Superheroes can transform to any other superhero. A superhero with name $s$s can transform to another superhero with name $t$t if $s$s can be made equal to $t$t by changing any vowel in $s$s to any other vowel and any consonant in $s$s to any other consonant. Multiple changes can be made.
In this problem, we consider the letters ‘a’, ‘e’, ‘i’, ‘o’ and ‘u’ to be vowels and all the other letters to be consonants.
Given the names of two superheroes, determine if the superhero with name $s$s can be transformed to the Superhero with name $t$t.

Input:

The first line contains the string $s$s having length between $1$1 and $1000$1000, inclusive.
The second line contains the string $t$t having length between $1$1 and $1000$1000, inclusive.
Both strings $s$s and $t$t are guaranteed to be different and consist of lowercase English letters only.

Output

Output “Yes” (without quotes) if the superhero with name $s$s can be transformed to the superhero with name $t$t and “No” (without quotes) otherwise.
You can print each letter in any case (upper or lower).

Sample Input:

a
u

Sample Output:

Yes

Sample Input:

abc
ukm

Sample Output:

Yes

Sample Input:

akm
ua

Sample Output:

No

题目链接

元音可变为任意元音、辅音可变为任意辅音，判断字符串 $S$S 是否能变为字符串 $T$T

暴力枚举判断即可

AC代码:

#include <bits/stdc++.h>
using namespace std;

string S, T;

bool Check(char X) {
    if (X == 'a' || X == 'e' || X == 'i' || X == 'o' || X == 'u')
        return true;
    return false;
}

int main(int argc, char *argv[]) {
    cin >> S >> T;
    if ((int)S.size() != (int)T.size()) {
        printf("No\n");
        return 0;
    }
    for (int i = 0; i < (int)S.size(); ++i) {
        if ((Check(S[i]) && !Check(T[i])) || (!Check(S[i]) && Check(T[i]))) {
            printf("No\n");
            return 0;
        }
    }
    printf("Yes\n");
    return 0;
}

B. Average Superhero Gang Power

Description:

Every superhero has been given a power value by the Felicity Committee. The avengers crew wants to maximize the average power of the superheroes in their team by performing certain operations.
Initially, there are $n$n superheroes in avengers team having powers $a_1,a_2,\dots ,a_n$a1​,a2​,…,an​, respectively. In one operation, they can remove one superhero from their team (if there are at least two) or they can increase the power of a superhero by $1$1. They can do at most $m$m operations. Also, on a particular superhero at most $k$k operations can be done.
Can you help the avengers team to maximize the average power of their crew?

Input:

The first line contains three integers $n$n, $k$k and $m$m ( $1\le n\le 10^5$1≤n≤105, $1\le k\le 10^5$1≤k≤105, $1\le m\le 10^7$1≤m≤107) — the number of superheroes, the maximum number of times you can increase power of a particular superhero, and the total maximum number of operations.
The second line contains $n$n integers $a_1,a_2,\dots ,a_n$a1​,a2​,…,an​ ( $1\le a_i\le 10^6$1≤ai​≤106) — the initial powers of the superheroes in the cast of avengers.

Output

Output a single number — the maximum final average power.
Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$10−6.
Formally, let your answer be $a$a, and the jury’s answer be $b$b. Your answer is accepted if and only if $\frac{\mid a-b\mid }{\max (1,\mid b\mid )}\le 10^{-6}$max(1,∣b∣)∣a−b∣​≤10−6.

Sample Input:

2 4 6
4 7

Sample Output:

11.00000000000000000000

Sample Input:

4 2 6
1 3 2 3

Sample Output:

5.00000000000000000000

题目链接

$n$n 个数的数列，可以进行删除一个数或对一个数加一的才做，最多 $m$m 次操作且最多对一个数字操作 $k$k 次，求最后的最大平均数。

枚举删除数字个数（显然优先删除最小的数），取平均数最大值（计算时会爆 $int$int ）。

这道题赛时通过 $3000+$3000+ 但只有 $700+$700+ 通过了终测…

AC代码:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double db;
const int maxn = 1e6 + 5;

ll N, K, M;
ll A[maxn];
ll Prefix[maxn];
db Ans;

int main(int argc, char *argv[]) {
    scanf("%lld%lld%lld", &N, &K, &M);
    for (int i = 1; i <= N; ++i) scanf("%lld", &A[i]);
    sort(A + 1, A + N + 1);
    for (int i = 1; i <= N; ++i) Prefix[i] = Prefix[i - 1] + A[i];
    for (ll k = 0; k <= min(M, N - 1); ++k) {
       Ans = max(Ans, (db)(Prefix[N] - Prefix[k] + min(M - k, (N - k) * K)) / (db)(N - k));
    }
    printf("%.20Lf\n", Ans);
    return 0;
}

C. Creative Snap

Description:

Thanos wants to destroy the avengers base, but he needs to destroy the avengers along with their base.
Let we represent their base with an array, where each position can be occupied by many avengers, but one avenger can occupy only one position. Length of their base is a perfect power of $2$2. Thanos wants to destroy the base using minimum power. He starts with the whole base and in one step he can do either of following:
if the current length is at least $2$2, divide the base into $2$2 equal halves and destroy them separately, or burn the current base. If it contains no avenger in it, it takes $A$A amount of power, otherwise it takes his $B\cdot n_a\cdot l$B⋅na​⋅l amount of power, where $n_a$na​ is the number of avengers and $l$l is the length of the current base. Output the minimum power needed by Thanos to destroy the avengers’ base.

Input:

The first line contains four integers $n$n, $k$k, $A$A and $B$B ( $1\le n\le 30$1≤n≤30, $1\le k\le 10^5$1≤k≤105, $1\le A,B\le 10^4$1≤A,B≤104), where $2^n$2n is the length of the base, $k$k is the number of avengers and $A$A and $B$B are the constants explained in the question.
The second line contains $k$k integers $a_1,a_2,a_3,\dots ,a_k$a1​,a2​,a3​,…,ak​ ( $1\le a_i\le 2^n$1≤ai​≤2n), where $a_i$ai​ represents the position of avenger in the base.

Output

Output one integer — the minimum power needed to destroy the avengers base.

Sample Input:

2 2 1 2
1 3

Sample Output:

6

Sample Input:

3 2 1 2
1 7

Sample Output:

8

题目链接

总共有 $2^n$2n 个位置编号为 $1$1 至 $2^n$2n ，其中有 $k$k 个位置上有人，对于区间 $[l,r]$[l,r] 可以将它分为左右均等的两部分销毁也可以直接销毁，销毁区间 $[l,r]$[l,r] 若有人则销毁花费为 $b\times 区间内人数\times 区间长度$b×区间内人数×区间长度 ，若没人则销毁花费为 $a$a ，求销毁区间 $[1,2^n]$[1,2n] 的最小花费。

对区间 $\left[l.r\right]$[l.r] 进行深搜，用二分计算区间内人数，最后计算结果取最小值即可。

这么简单的深搜题赛时居然把区间计数写错了…太菜了

AC代码:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll N, K, A, B;
vector<ll> Pos;

ll Count(int Left, int Right) {
    return upper_bound(Pos.begin(), Pos.end(), Right) - lower_bound(Pos.begin(), Pos.end(), Left);
}

ll Dfs(ll Left, ll Right) {
    ll Cnt = Count(Left, Right);
    if (Cnt == 0) return A;
    ll Ans = B * Cnt * (Right - Left + 1);
    if (Left == Right) return Ans;
    ll Mid = (Left + Right) / 2;
    return min(Ans, Dfs(Left, Mid) + Dfs(Mid + 1, Right));
}

int main(int argc, char *argv[]) {
    scanf("%lld%lld%lld%lld", &N, &K, &A, &B);
    for (ll i = 1, X; i <= K; ++i) {
        scanf("%lld", &X);
        Pos.push_back(X);
    }
    sort(Pos.begin(), Pos.end());
    printf("%lld\n", Dfs(1, (1 << N)));
    return 0;
}