Codeforces Round 951 (Div. 2) A - C题解

这是一篇提前写的博客，因为时间不够，花了四十分钟做了A-C，因为题目A - C比较简单，所以简单说一说吧。

A. Guess the Maximum

题意：给你n个数字，选择i和j满足，如果其中的最大值大于k，那么Bob赢，其他情况Alice赢，问Alice全部获胜的最大k是多少。

题解：很明显可以想到，数字区间越大，那么最大值是不会变小的，一定会越来越大，所以想要找到最大的k，直接枚举相邻两个数字，求出所有数字的最大值的最小值即可，当然最后要减一。

代码：

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 2e6 + 7 ;
const int mod = 998244353 ;
inline ll read() {ll x = 0, f = 1 ;char c = getchar() ;while (c > '9' || c < '0') {if (c == '-')f = -1 ;c = getchar() ;}while (c >= '0' && c <= '9') {x = x * 10 + c - '0' ;c = getchar() ;}return x * f ;
}ll a[maxn] , b[maxn] , n , m , t ;
ll sum[maxn] , Sum[maxn] , ssum[maxn] , SSum[maxn] , A[maxn] , B[maxn] ;
char s[maxn] ;
void solve(){n = read() ;for(int i = 1 ; i <= n ; i ++){a[i] = read() ;}ll Min = LONG_LONG_MAX ;for(int i = 1 ; i <= n - 1 ; i ++){Min = min(Min , max(a[i] , a[i + 1])) ;}cout << Min - 1 << endl ;
}
int main(){t = read() ;while(t --){solve() ;}return 0 ;
}

B. XOR Sequences

题意：给你a和b的两个排列，给你n和m，让a序列所有数字异或n，让b序列所有数字异或m，问满足的连续序列最长是多少。

题解：这道题很明显的结论，就是2的n异或m的最小一位数字1次方，简单来说，比如说第一组样例8异或4等于12，他的二进制是10100，所以答案就是4。得解。

代码：

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 2e6 + 7 ;
const int mod = 998244353 ;
inline ll read() {ll x = 0, f = 1 ;char c = getchar() ;while (c > '9' || c < '0') {if (c == '-')f = -1 ;c = getchar() ;}while (c >= '0' && c <= '9') {x = x * 10 + c - '0' ;c = getchar() ;}return x * f ;
}ll a[maxn] , b[maxn] , n , m , t ;
ll sum[maxn] , Sum[maxn] , ssum[maxn] , SSum[maxn] , A[maxn] , B[maxn] ;
char s[maxn] ;
void solve(){n = read() ;m = read() ;ll xx = n xor m ;ll rt = -1 ;	for(ll i = 0 ; i <= 32 ; i ++){ll len = (xx >> i) & 1 ;if(len == 1){rt = i ;break ;}}if(rt == -1){cout << 1 << endl ;return ;}cout << (ll)pow(2ll , rt) << endl ;
}
int main(){t = read() ;while(t --){solve() ;}return 0 ;
}

C. Earning on Bets

题意：给你n个数字，每个数字都有初始数字，每个数字对应一个k值，如果他每次获胜，那么会获得的收益，题目给你每个k的值，他想问，构造序列a，满足a的每个数字都能满足。

题解：求出所有数字的最小公倍数，然后算出是否满足条件即可，如果不满足，那必然永远不会满足，输出-1，如果满足输出答案即可。

代码：

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 2e6 + 7 ;
const int mod = 998244353 ;
inline ll read() {ll x = 0, f = 1 ;char c = getchar() ;while (c > '9' || c < '0') {if (c == '-')f = -1 ;c = getchar() ;}while (c >= '0' && c <= '9') {x = x * 10 + c - '0' ;c = getchar() ;}return x * f ;
}ll a[maxn] , b[maxn] , n , m , t ;
ll sum[maxn] , Sum[maxn] , ssum[maxn] , SSum[maxn] , A[maxn] , B[maxn] ;
char s[maxn] ;
void solve(){n = read() ;for(int i = 1 ; i <= n ; i ++){a[i] = read() ;}ll lcm = 1 ;for(int i = 1 ; i <= n ; i ++){lcm = (lcm * a[i]) / __gcd(lcm , a[i]) ;}for(int i = 1 ; i <= n ; i ++){b[i] = lcm / a[i] ;}ll ans = 0 ;for(int i = 1 ; i <= n ; i ++){ans += b[i] ;}if(ans >= lcm){cout << -1 << endl ;return ;}else{for(int i = 1 ; i <= n ; i ++){cout << b[i] << " " ; }cout << endl ;}
}
int main(){t = read() ;while(t --){solve() ;}return 0 ;
}

喜欢作者的记得点赞收藏加关注哦~

作者会持续更新算法和技巧!