19.5.14 CF #560 (Div. 3) 解题报告(4 / 7)

A. Remainder

  • 在倒数x个位置中找出除了在位置y以外所有 1 的个数, 然后再加上倒数y取反
  • 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
    /*************************************************************************
    > File Name: a.cpp
    > Author: Wqr_
    > Mail: xueduanwei@126.com
    > Created Time: 2019年05月14日 星期二 22时16分46秒
    ************************************************************************/

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<vector>
    #include<algorithm>
    #include<map>
    #include<queue>
    #include<cmath>
    #define MAX_N 200100
    using namespace std;
    typedef long long ll;
    int n, x, y;
    int a[MAX_N];
    int b[MAX_N];
    int main(){
    cin >> n >> x >> y;
    string in;
    cin >> in;
    for(int i = 0; i < n; i++){
    a[i] = in[i] - '0';
    }
    int ans = 0;
    for(int i = 0; i < x + 1; i++){
    b[i] = a[n - 1 - i];
    }
    for(int i = 0; i < x + 1; i++){
    if(i == x || i == y) continue;
    if(b[i]) ans++;
    }
    if(!b[y]) ans++;
    cout << ans << endl;
    return 0;
    }

B. Polycarp Training

  • 题意忘了
  • 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
/*************************************************************************
> File Name: b.cpp
> Author: Wqr_
> Mail: xueduanwei@126.com
> Created Time: 2019年05月14日 星期二 22时48分55秒
************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
#define MAX_N 200100
using namespace std;
typedef long long ll;
int n;
int a[MAX_N];
int main(){
cin >> n;
priority_queue<int, vector<int>, greater<int> > q;
for(int i = 0; i < n; i++){
scanf("%d", a + i);
q.push(a[i]);
}
int ans = 0;
for(int i = 0; i < n; i++){
int num = q.top();
q.pop();
while(num < i + 1 && !q.empty()){
num = q.top();
q.pop();
}
if(num >= i + 1) ans++;
if(q.empty()){
break;
}
}
cout << ans << endl;
return 0;
}

C. Good String

  • 用一个链表高效的模拟即可
  • 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
    55
    56
    57
    58
    59
    /*************************************************************************
    > File Name: c.cpp
    > Author: Wqr_
    > Mail: xueduanwei@126.com
    > Created Time: 2019年05月14日 星期二 23时15分14秒
    ************************************************************************/

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<vector>
    #include<algorithm>
    #include<map>
    #include<queue>
    #include<cmath>
    #include<list>
    #define MAXN 200100
    using namespace std;
    typedef long long ll;
    int n;
    int main(){
    string in;
    cin >> n;
    if(!n){
    cout << 0 << endl;
    return 0;
    }
    cin >> in;
    list<char> l;
    for(int i = 0; i < in.length(); i++){
    l.push_back(in[i]);
    }
    int w = 1;
    int ans = 0;
    for(auto it = l.begin(); it != l.end(); it++){
    if(w % 2){
    auto it2 = it;
    it2++;
    if(*it2 == *it){
    l.erase(it2);
    ans++;
    it--;
    w--;
    }
    }
    w++;
    }
    if(l.size() % 2) {
    ans++;
    l.pop_back();
    }
    cout << ans << endl;
    for(auto n : l){
    cout << n;
    }
    cout << endl;
    return 0;
    }

D. Almost All Divisors

  • 题意 : 给出一个数除了 1 以及其自身以外的可能所有的因数, 问这个数是什么, 如果输入不合法或者输入的因数少, 则输出-1
  • 思路 : 首先对输入进行排序, 最小数与最大的数乘积即为可能的ans, 然后遍历, 先判断输入中是否有不是ans因数的数, 有就输出-1. 然后判断因数的个数是否足够, 如果不够就输出-1, 否则输出ans
  • 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
    55
    56
    /*************************************************************************
    > File Name: d.cpp
    > Author: Wqr_
    > Mail: xueduanwei@126.com
    > Created Time: 2019年05月16日 星期四 15时40分11秒
    ************************************************************************/

    #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;
    ll a[340];
    int main(){
    int t;
    cin >> t;
    while(t--){
    cin >> n;
    ll ans = 0;
    for(int i = 0; i < n; i++){
    cin >> a[i];
    }
    sort(a, a + n);
    ans = a[0] * a[n - 1];
    bool flag = 0;
    for(int i = 0; i < n; i++){
    if(ans % a[i] != 0) {
    flag = 1;
    break;
    }
    }
    if(flag) {
    cout << -1 << endl;
    continue;
    }
    ll num = 0;
    for(ll i = 2; i <= sqrt(ans); i++){
    if(ans % i == 0){
    num++;
    if(ans / i != i) num++;
    }
    }
    if(num == n)
    cout << ans << endl;
    else
    cout << -1 << endl;
    }
    return 0;
    }