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

A. Silent Classroom

  • 统计每个首字母出现的次数,设为n, 然后累加C(n, 2)
  • ac代码
/*************************************************************************
    > 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代码
/*************************************************************************
    > 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代码
/*************************************************************************
    > 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;
}