codeforces 898

题目链接

http://codeforces.com/contest/898

分题详解

A.Rounding

题目大意:给一个非负整数n,输出离n最近的能被10整除的整数。当然如果n本身就能被10整除,输出自身即可。如果n的末尾是5的话,向上和向下取最近整数都是正确的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
int n;
cin >> n;
if (n%10 < 5){
cout << n - n%10 << endl;
}else{
cout << n + 10 - n%10 << endl;
}
return 0;
}

B.Proper Nutrition

题目大意:给定n,a,b(n,a,b都是在[1,1e7]范围内的正整数),求x,y使得$ax+by=n$,当然x,y都是自然数。
思路分析:拓展欧几里得入门题目。

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <map>
#include <vector>

using namespace std;
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
//拓展欧几里得
void exgcd(int a, int b, int& d,int& x,int& y){
if (!b){
d = a;
x = 1;
y = 0;
}else{
exgcd(b, a%b, d, y, x);
y -= x*(a/b);
}
}
int main(){
int n, a, b;
cin >> n >> a >> b;
int d, x, y;
exgcd(a, b, d, x, y);
if (n % d){
cout << "NO" << endl;
}else{
n /= d;
a /= d;
b /= d;
long long xx = x;
long long yy = y;
xx *= n;
yy *= n;
// 调整yy,使得yy>=0
if (yy < 0){
long long w = (-yy)/a + ((-yy)%a?1:0);
xx -= w*b;
yy += w*a;
}
// 调整xx,使得xx>=0
if (xx < 0){
long long w = (-xx)/b + ((-xx)%b?1:0);
xx += w*b;
yy -= w*a;
}
if (xx < 0 or yy < 0){
cout << "NO" << endl;
}else{
cout << "YES" << endl;
cout << xx << " " << yy << endl;
}
}
return 0;
}

C.Phone Numbers

题目大意:电话本上面有n个条目,每个条目有一个名字,电话号码数量,和电话号码。当然不同的条目里面也许名字相同,任务是需要合并电话本,针对条目而言,不同条目名字相同,需要将两个条目的电话号码合并。针对电话号码而言,电话号码a是电话号码b的后缀的话,去掉a电话号码。
思路分析:模拟题目,按照题意描述操作即可

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <string>
#include <map>
#include <vector>

using namespace std;
vector<string> V[20];
map<string, vector<string>*> mp;

bool sub_check(string s1, string s2){
int len2 = s2.length();
int len1 = s1.length();
for (int i = 1; i <= len2; ++i){
if (s1[len1-i] != s2[len2-i]){
return false;
}
}
return true;
}


bool check(vector<string>& tmp_v, string s){
for(auto x : tmp_v){
if (sub_check(x, s)){
return false;
}
}
return true;
}
void myinsert(string number, vector<string> *s_v){
s_v->push_back(number);
}
bool cmp(const string& a,const string& b){
return a.length() > b.length();
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int cnt = 0;
for (int i = 0; i < n; i++){
string name;
int k;
cin >> name >> k;
if (!mp.count(name)){
mp[name]=&V[cnt];
++cnt;
}
vector<string>* s_v = mp[name];
string number;
while(k--){
cin >> number;
myinsert(number, s_v);
}
}
for (int i = 0; i < cnt; ++i){
sort(V[i].begin(), V[i].end(),cmp);
}
cout << mp.size() << endl;
for (auto k : mp){
cout << k.first;
vector<string> tmp;
for (auto ele : *(k.second)){
if (check(tmp, ele)){
tmp.push_back(ele);
}
}
cout << " " << tmp.size();
for (auto ele : tmp){
cout << " " << ele;
}
cout << endl;
}
return 0;
}

D.Alarm Clock

题目大意:给定n,m,k,n代表闹钟数量,每个闹钟会响1分钟,m代表时间区间,k代表在叫醒Vitalya需要的最少闹钟数,当然需要叫醒Vitalya的话必须在m区间内有k个闹钟响过,Vitalya才会被唤醒。
PS:不会有两个闹钟在同一时刻响。
思路分析:设置两个标记位,分别代表标记m时间区间的起始位置。然后遍历一遍按时间顺序排列好的时间表,分别更新两个标记位,同时更新响铃的闹钟数目,如果数目不小于k的话,就把当前时间的闹钟关掉。

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;
int n,m,k;
//闹钟的响铃时间数组
int clc[200020];
//闹钟状态数组
bool stat[200020];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
for (int i = 0; i < n; ++i){
cin >> clc[i];
}
sort(clc, clc+n);
int pre = 0;
int now = 0;
int ans = 0;
memset(stat, false, sizeof stat);
for (int i = 0; i < n; ++i){
++now;
while (clc[i] - clc[pre] + 1 > m){
if(stat[pre] == false){
--now;
}
++pre;
}

if (now >= k){
--now;
stat[i] = true;
++ans;
}
}
cout << ans << endl;

return 0;
}

E.Squares and not squares

题目大意:现在有$n (n % 2 \neq 0 and 2 \leq n \leq 200000)$个数,现在有两种操作分别是对一个数增加1或者是对这个数减去1,求最少操作次数,使得n个数刚好变成一半平方数和一半非平方数。
思路分析:标记每个数的状态,看是不是平方数,如果是平方数标记它变成非平方数的最少操作次数,如果是非平方数就标记它变成平方数的最少操作次数。一般的平方数变成非平方数需要操作次数是1,当时0是2。

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;


struct Node{
    // type为false表示非平方数,true表示平方数
    bool type;
    // tran表示从一种状态转变成另外一种状态需要的最少操作次数
    int tran;
    bool operator < (const Node& x)const{
        return tran < x.tran;
    }
}node[200010];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int tmp;
    long long ans = 0;
    // cnt是平方数个数和非平方数个数的差
    int cnt = 0;
    for (int i = 0; i < n; ++i){
        cin >> tmp;
        int tt = sqrt(tmp);
        if( tt*tt == tmp){
            node[i].type = true;
            cnt += 1;
            if(tmp == 0){
                node[i].tran = 2;
            }else{
                node[i].tran = 1;
            }
        }else{
            cnt -= 1;
            node[i].type = false;
            node[i].tran = min(tmp - tt*tt, (tt+1)*(tt+1)-tmp);
        }

    }
    sort(node, node+n);
    if (cnt > 0){
        for (int i = 0; i < n; ++i){
            if(node[i].type == true){
                ans += node[i].tran;
                cnt-=2;
            }
            if (cnt == 0){
                break;
            }
        }
    }else if(cnt < 0){
        for (int i = 0; i < n; ++i){
            if(node[i].type == false){
                ans += node[i].tran;
                cnt+=2;
            }
            if (cnt == 0){
                break;
            }
        }

    }
    cout << ans << endl;
    return 0;
}

总结

这次的题目整体来说模拟就可以了,B题后面讨论的时候发现暴力可过,老年人选手+太久没训练,真的是菜的难以想象了。