19.5.17 CF #561 (Div. 2) 解题报告(3 / 6)

A. Silent Classroom

  • 统计每个首字母出现的次数,设为n, 然后累加C(n, 2)
  • ac代码
    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
    /*************************************************************************
    > File Name: a.cpp
    > Author: Wqr_
    > Mail: xueduanwei@126.com
    > Created Time: 2019年05月17日 星期五 22时54分30秒
    ************************************************************************/

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<vector>
    #include<algorithm>
    #include<map>
    #include<queue>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    const int MAXN = 200200;
    int n;
    int nums[300];
    int s(int in){
    return (in * (in - 1)) / 2;
    }
    int main(){
    cin >> n;
    string in;
    for(int i = 0; i < n; i++){
    cin >> in;
    nums[(int)in[0]]++;
    }
    int ans = 0;
    for(int i = 0; i < 300; i++){
    int tmp = nums[i] / 2;
    ans += s(tmp);
    ans += s(nums[i] - tmp);
    }
    cout << ans << endl;
    return 0;
    }

B. All the Vowels Please

  • 模拟输出即可
  • ac代码
    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
    42
    43
    44
    45
    46
    47
    48
    /*************************************************************************
    > File Name: b.cpp
    > Author: Wqr_
    > Mail: xueduanwei@126.com
    > Created Time: 2019年05月17日 星期五 23时20分52秒
    ************************************************************************/

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<vector>
    #include<algorithm>
    #include<map>
    #include<queue>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    int k;
    char cs[5] = {'a', 'e', 'i', 'o', 'u'};
    int main(){
    cin >> k;
    if(k < 25){
    cout << -1 << endl;
    return 0;
    }
    bool flag = 0;
    int book = 0;
    for(int i = 5; i <= sqrt(k); i++){
    if(k % i == 0){
    flag = 1;
    book = i;
    break;
    }
    }
    if(!flag){
    cout << -1 << endl;
    return 0;
    }
    int x = book;
    int y = k / book;
    for(int i = 0; i < x; i++){
    for(int j = 0; j < y; j++){
    cout << cs[(i + j) % 5];
    }
    }
    return 0;
    }

C. A Tale of Two Lands

  • 首先注意到两个数相比较, 如果第二个数使得判断条件为假, 则第一个数比第二个数大的数相比较肯定为假, 所以具有单调性, 可以用二分解决, 朴素算法会t(t了(泣))
  • 这题要注意数据范围为阶乘级, 所以要用long long类型输出答案(因为这个wa了(泣))
  • ac代码
    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
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    /*************************************************************************
    > File Name: c.cpp
    > Author: Wqr_
    > Mail: xueduanwei@126.com
    > Created Time: 2019年05月17日 星期五 23时47分45秒
    ************************************************************************/

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<vector>
    #include<algorithm>
    #include<map>
    #include<queue>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    int n;
    int a[200200];
    int p(int a, int b){
    int t1 = abs(a - b);
    int t2 = abs(a + b);
    if(min(t1, t2) <= min(a, b) && max(t1, t2) >= max(a, b)){
    return 1;
    }
    return 0;
    }
    int c(int in){
    int lb = in, ub = n;
    int mid;
    int ans;
    while(ub >= lb){
    mid = (lb + ub) >> 1;
    if(p(a[in], a[mid])) ans = mid, lb = mid + 1;
    else ub = mid - 1;
    }
    return ans - in;
    }
    int main(){
    cin >> n;
    int in;
    for(int i = 0; i < n; i++){
    scanf("%d", &in);
    a[i] = abs(in);
    }
    sort(a, a + n);
    long long ans = 0;
    for(int i = 0; i < n; i++){
    ans += c(i);
    }
    cout << ans << endl;
    return 0;
    }