codeforces竞赛1141题解
【摘要】
竞赛链接：http://codeforces.com/contest/1141
A. Game 23
题目大意：
对于两个数n,m,求n通过乘2或者乘3变成m所需要的次数。无解输出-1. 例如120...
竞赛链接：http://codeforces.com/contest/1141
A. Game 23
题目大意：
对于两个数n,m,求n通过乘2或者乘3变成m所需要的次数。无解输出-1.
例如120 51840需要7次变换。
解题思路：
如果m%n不等于0，则无解。
如果n>m,则无解。
那么n到达m需要乘的步长为p = m / n，这个如果这个p能被2 3全部整除，则说明有解，否则无解。
AC代码：
//
// Created by jal on 2019-05-21.
//
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
if(n > m || m % n){
cout << -1 << endl;
return 0;
}
int p = m / n;
int cnt = 0;
while(p%2==0){
cnt++;
p/=2;
}
while(p%3==0){
cnt++;
p/=3;
}
if(p==1){
cout << cnt << endl;
}else{
cout << -1 << endl;
}
}
- 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
B. Maximal Continuous Rest
题目大意：
长度为n的01数组（至少包含一个0），这个数组序列会不断重复下去。求最长的连续1的个数。
解题思路：
考虑到数组的首尾元素都是1的话，最后的一个元素是与这个数组下一次的第一个元素拼接，所以索性将数组扩大为长度为2*n的，后一半的数组内容同前一半。然后求最长的1的个数即可。
AC代码：
//
// Created by jal on 2019-05-21.
//
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<int>v(2*n);
for(int i = 0; i < n; i++){
cin >> v[i];
v[n+i] = v[i];
}
int cnt = 0;
int res = 0;
for(int i = 1; i < 2 * n; i++){
if(v[i] == 0){
cnt = 0;
}else{
if(v[i] == v[i-1]){
cnt++;
}else{
cnt=1;
}
}
res = max(res, cnt);
}
cout << res << endl;
}
- 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
C. Polycarp Restores Permutation
题目大意：
一个n的排列 p 1 , p 2 , . . . , p n p_{1},p_{2}, ..., p_{n} p1,p2,...,pn进行差分后得到 q 1 , q 2 , . . . , q n − 1 q_{1}, q_{2} ,... ,q_{n-1} q1,q2,...,qn−1，现在给出数字n和差分序列 q 1 , q 2 , . . . , q n − 1 q_{1}, q_{2} ,... ,q_{n-1} q1,q2,...,qn−1，求出原排列 p 1 , p 2 , . . . , p n p_{1},p_{2}, ..., p_{n} p1,p2,...,pn
解题思路：
- 第一种方法 O ( N l o g ( N ) ) O(Nlog(N)) O(Nlog(N))：
由于差分序列只有n-1个数，那我们可以在1~n范围内二分枚举排列中的第一个元素 p 1 p_{1} p1，然后通过第一个元素和差分序列就可以在线性时间复杂度内求出排列的其他所有元素。至于为什么可以二分枚举呢， 因为我们所求的所有排列元素的和S是相对 p 1 p_{1} p1单调递增的，所以可以二分。当 S = n ∗ ( n + 1 ) / 2 S=n*(n+1)/2 S=n∗(n+1)/2的时候，说明此时的 p 1 p_{1} p1就是正解，二分结束。一直到最后都找不到的话，则无解。 - 第二种方法 O ( N ) O(N) O(N)：
递推法直接求出 p 1 p_{1} p1，因为 p 1 = p 1 , p 2 = q 1 + p 1 , p 3 = q 2 + q 1 + p 1 , . . . , p n = q n − 1 + q n − 1 + . . . + q 1 + p 1 p_1=p_1, p_2=q_1+p_1,p_3=q_2+q_1+p_1,...,p_n=q_{n-1}+q_{n-1}+...+q_1+p_1 p1=p1,p2=q1+p1,p3=q2+q1+p1,...,pn=qn−1+qn−1+...+q1+p1，而排列的和是 n ∗ ( n + 1 ) / 2 n*(n+1)/2 n∗(n+1)/2,所以累加所有的 P i P_i Pi可以得出等式： n ∗ p 1 + ( n − 1 ) ∗ q 1 + ( n − 2 ) ∗ q 2 + . . . + 1 ∗ q n − 1 = n ∗ ( n + 1 ) / 2 {n*p_1+(n-1)*q_1+(n-2)*q_2}+...+1*q_{n-1} = n*(n+1)/2 n∗p1+(n−1)∗q1+(n−2)∗q2+...+1∗qn−1=n∗(n+1)/2
因此可以求出 P 1 P_1 P1,通过 P 1 P_1 P1和差分序列就可以在线性时间复杂度内求出排列的其他所有元素。
注意：
- 上面两种方法都可以AC，不过需要注意的是，本题数据量会达到64位整数，所以变量要定义成long long类型。 n ∗ ( n + 1 ) / 2 n*(n+1)/2 n∗(n+1)/2可能会溢出int，所以要写成 1 L L ∗ n ∗ ( n + 1 ) / 2 1LL*n*(n+1)/2 1LL∗n∗(n+1)/2。
- 要判断生成的排列是否合理。也就是生成的序列是不是一个排列，如果不是则输出-1.
AC代码：
- 第一种方法 O ( N l o g ( N ) ) O(Nlog(N)) O(Nlog(N))：
//
// Created by jal on 2019-05-21.
//
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
// ifstream cin("input.txt");
int n;
cin >> n;
LL s1 = 1LL*n * (n+1)/2;
vector<LL>p(n),q(n-1);
for(auto &i : q){
cin >> i;
}
int flag = 0;
int left = 1, right = n;
while(left <= right){
p[0] = (left + right )>>1;
LL sum = p[0];
for(int i = 1; i < n; i++){
p[i] = p[i-1] + q[i-1];
sum += p[i];
}
if(sum == s1){
flag = 1;
map<int,int>mp;
for(auto i:p){
mp[i]++;
}
for(int i = 1; i <= n; i++){
if(mp[i] != 1){
flag = 0;
break;
}
}
if(flag){
for(auto i: p){
cout << i << " ";
}
cout << endl;
}
break;
}
if(sum > s1){
right = p[0]-1;
}else{
left = p[0]+1;
}
}
if(flag == 0){
cout << -1 << endl;
}
}
- 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
- 第二种方法 O ( N ) O(N) O(N)：
//
// Created by jal on 2019-05-21.
//
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
// ifstream cin("input.txt");
int n;
cin >> n;
vector<int>d(n-1);
for(int i = 0; i < n-1; i++){
cin >> d[i];
}
vector<int>a(n);
LL s = 1LL*n * (n+1)/2;
for(int i = 1; i < n; i++){
s -= 1LL * i * d[n-i-1];
}
map<int, int>mp;
a[0] = s / n;
mp[a[0]] = 1;
LL sum = a[0];
for(int i = 1; i < n; i++){
a[i] = a[i-1] + d[i-1];
mp[a[i]]++;
sum += a[i];
}
int flag = 1;
for(int i = 1; i <= n; i++){
if(mp[i] != 1){
flag = 0;
break;
}
}
if(flag){
for(auto i : a){
cout << i << " ";
}
cout <<endl;
}else{
cout << -1 << endl;
}
}
- 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
D. Colored Boots
题目大意：
给出两个长度为n的字符串，只有小写字母和问号，相同的小写字母可以匹配，问号可以跟任意小写字母和问号匹配。求最大的匹配的对数，并且输出下标。每个字母不可以被二次匹配。
解题思路：
每个小写字母和问号都关联一个链表，初始时将每次字母和问号所在的下标存到对应字符的链表里。然后先匹配小写字母，小写字母无法与小写字母匹配，就与问号匹配，最后剩下问号就与问号匹配。看下面代码即可一目了然。
AC代码：
//
// Created by jal on 2019-05-22.
//
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
map<char, list<int> >mp1, mp2;
vector<pair<int, int> >v;
string s1,s2;
cin >> s1 >> s2;
for(int i = 0; i < n; i++){
mp1[s1[i]].push_back(i+1);
mp2[s2[i]].push_back(i+1);
}
for(int i = 'a'; i <= 'z'; i++){
while(mp1[i].size() > 0 && mp2[i].size() > 0){
v.push_back({mp1[i].front(), mp2[i].front()});
mp1[i].pop_front();
mp2[i].pop_front();
}
while(mp1[i].size() > 0 && mp2['?'].size() > 0){
v.push_back({mp1[i].front(), mp2['?'].front()});
mp1[i].pop_front();
mp2['?'].pop_front();
}
while(mp1['?'].size() > 0 && mp2[i].size() > 0){
v.push_back({mp1['?'].front(), mp2[i].front()});
mp1['?'].pop_front();
mp2[i].pop_front();
}
}
while(mp1['?'].size() > 0 && mp2['?'].size() > 0){
v.push_back({mp1['?'].front(), mp2['?'].front()});
mp1['?'].pop_front();
mp2['?'].pop_front();
}
cout << v.size() << endl;
for(auto i : v){
cout << i.first << " " << i.second << endl;
}
}
- 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
E. Superhero Battle
题目大意：
使h降到0以下，依次通过数组v的每一位，都要进行h+v[i],v[i]有正有负。这个数组持续循环下去。
解题思路：
先求数组v的前缀和sum数组，sum[n-1]就是v数组的全部项的累加和。设MIN为sum数组的最小值。
- 如果sum[n-1]大于0且h+MIN大于0，则一定无解。因为此时h只会增加不会减少
- 如果h+MIN小于0，则经过整场数组的轮数cnt为0，否则为 c n t = c e i l ( 1.0 ∗ ( h + M I N ) / ( − s u m [ n − 1 ] ) ) cnt=ceil(1.0*(h+MIN) / (-sum[n-1])) cnt=ceil(1.0∗(h+MIN)/(−sum[n−1])).剩下的 h = h + s u m [ n − 1 ] ∗ c n t h =h+ sum[n-1]*cnt h=h+sum[n−1]∗cnt，前面的cnt轮走过的步数为 c n t ∗ n cnt * n cnt∗n。剩下的步数一定可以在一轮数组遍历中使得h降到0以下，所以遍历sum数组，找到 h + s u m [ i ] < = 0 h + sum[i] <= 0 h+sum[i]<=0即可。
AC代码：
//
// Created by jal on 2019-05-22.
//
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
// ifstream cin("input.txt");
LL h;
int n;
cin >> h >> n;
vector<LL>v(n);
for(int i = 0; i < n; i++){
cin >> v[i];
}
vector<LL>sum(n);
partial_sum(v.begin(), v.end(), sum.begin());
LL cnt = 0;
LL MIN = v[0];
for(int i = 1; i < n; i++){
if(sum[i] < MIN){
MIN = sum[i];
}
}
if(sum[n-1] >= 0 && h + MIN > 0){
cout << -1 << endl;
return 0;
}
cnt = ceil(1.0*(h+MIN) / (-sum[n-1]));
if((h+MIN) < 0)cnt = 0;
h += sum[n-1]*cnt;
cnt *= n;
for(int i = 0; i < n; i++){
if(h + sum[i] <= 0){
cnt += i+1;
cout << cnt << endl;
break;
}
}
}
- 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
文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/jal517486222/article/details/90416469
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）