2024牛客寒假算法基础集训营3
A 智乃与瞩目狸猫、幸运水母、月宫龙虾
题意
给出若干组字符串，判断无视大小写，判断首字母是否相同
思路
如果首字母相同，则直接用 \(==\) 比较即可，如果首字母只有大小写的区别，则ASCII码值相差 \(32\)
代码
/*******************************
| Author: AlwaysBeShine
| Problem: 智乃与瞩目狸猫、幸运水母、月宫龙虾
| Contest: NowCoder
| URL: https://ac.nowcoder.com/acm/contest/67743/A
| When: 2024-02-07 13:00:42
|
| Memory: 524288 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
string s,t;
cin >> s >> t;
if(s[0] == t[0] ||abs((int)(s[0]-t[0])) == 32){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while(T--){
solve();
}
return 0;
}
L 智乃的36倍数(easy version)
题意
定义了一种运算\(f\)，它表示将两个正整数按照字面值从左到右拼接。
例如\(f(1,1)=11\)，\(f(114,514)=114514\)。
一个大小为 \(n\) 的正整数数组 \(a\)，第\(i\)个元素为\(a_{i}\)，现在他从中想选出两个正整数进行前后拼接，使得它们拼接后是一个\(36\)的倍数，问智乃有多少种可行的方案。
思路
简单版范围足以可以暴力通过
设 有 \(a_i\) 和 \(a_j\) 两元素，分别为 \(x\) 和 \(y\) 位数，则将 \(f(a_i,a_j) = a_i * 10^y + a_j\)，遍历所有可能判断是否是 36 的倍数即可。
代码
/*******************************
| Author: AlwaysBeShine
| Problem: 智乃的36倍数(easy version)
| Contest: NowCoder
| URL: https://ac.nowcoder.com/acm/contest/67743/L
| When: 2024-02-07 13:04:54
|
| Memory: 524288 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
std::vector<int> a(n);
for(int i = 0; i < n;i++){
cin >> a[i];
}
int cnt = 0;
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
int temp = a[j];
int num = 0;
while(temp){
num++;
temp /= 10;
}
//cout << a[j] + (int)pow(10,num)*a[i] << endl;
if( (a[j] + (int)pow(10,num)*a[i]) % 36 == 0 ){
cnt++;
}
}
}
cout << cnt << endl;
return 0;
}
D chino's bubble sort and maximum subarray sum(easy version)
题意
简单版
从一个数组\(a\)中取出一段连续的非空数组区间\([l,r]\)，最大化数组区间的和\(\sum_{i=l}^{r}a_{i}\)。
有一个长度大小为\(N\)的数组，数组中元素的值有正有负。她想要先进行恰好 \(K\) 次相邻元素的交换操作，再求整个数组的最大子段和。她想要让最后求出的最大子段和尽可能的大，算出最终可能的最大子段和有多大。
思路
简单版的 \(K\) 不是 \(1\) 就是 \(0\)
当 \(K = 0\) 时，直接求一遍最大字段和即可。
当 \(K = 1\) 时，数据范围足以遍历每种交换可能，分别求一次最大字段和，求最大值
代码
/*******************************
| Author: AlwaysBeShine
| Problem: chino's bubble sort and maximum subarray sum(easy version)
| Contest: NowCoder
| URL: https://ac.nowcoder.com/acm/contest/67743/D
| When: 2024-02-07 13:36:41
|
| Memory: 1048576 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,k;
cin >> n >> k;
std::vector<ll> a(n+1,0);
for(int i = 1;i <= n;i++){
cin >> a[i];
}
ll m = -2000000000;
if(k == 1){
for(int i = 1;i < n;i++){
vector<ll>b;
b = a;
vector<ll>s(n+2,0);
std::swap(b[i],b[i+1]);
// for(int k = 1;k <= n;k++){
// cout << b[k] << " ";
// }
// cout << endl;
for(int j = 1;j <= n;j++){
s[j] = s[j-1] + b[j];
}
for(int j = 1;j <=n;j++){
for(int k = 0;k < j;k++){
m = max(m,s[j]-s[k]);
}
}
}
}else{
vector<ll>s(n+2,0);
for(int j = 1;j <= n;j++){
s[j] = s[j-1] + a[j];
}
for(int j = 1;j <= n;j++){
for(int k = 0;k < j;k++){
m = max(m,s[j]-s[k]);
}
}
}
cout << m << endl;
return 0;
}
G 智乃的比较函数(easy version)
题意
在 c++ 标准库中，存在一个叫做 std::sort 的函数，使用 sort 时需要定义一个比较函数\(cmp(x,y)\) 他表示比较在排序的过程中\(x\)的顺序是否严格小于\(y\)的顺序
如果\(x\)的顺序严格小于 \(y\) 的顺序，则\(cmp(x,y)=1\)，反之\(cmp(x,y)=0\)，在\(x\)和\(y\)的值相等时令\(cmp(x,y)=1\) 。
给出若干组的 \(2\) 个数 \(a,b\) 和它们之间的约束关系 \(cmp(a,b)\) ，判断是否出现冲突
思路
当 $cmp(x,y) = 0 $ 时， $ x \ge y$
当 $cmp(x,y) = 1 $ 时，$ x \lt y $
判断是否出现冲突的逻辑如下：
当 \(cmp(x,y) == cmp(y,x)\) 时，如果 \(cmp(x,y) = 1\) 或 \(cmp(y,x) = 1\) 时，发生冲突
当 读入数据与已存数据值不同 时，发生冲突。
代码
/*******************************
| Author: AlwaysBeShine
| Problem: 智乃的比较函数(easy version)
| Contest: NowCoder
| URL: https://ac.nowcoder.com/acm/contest/67743/G
| When: 2024-02-07 15:51:26
|
| Memory: 524288 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
int n;
cin >> n;
int gx[5][5];
int x,y,z;
for(int i = 1;i <= 3;i++){
for(int j = 1;j <= 3;j++){
gx[i][j] = -1;
}
}
bool ck = true;
for(int i = 0;i < n;i++){
cin >> x >> y >> z;
if(gx[x][y] == -1){
gx[x][y] = z;
}
if(gx[x][y] != z || gx[y][x] + z == 2){
ck = false;
}
}
if(ck){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while(T--){
solve();
}
return 0;
}
H 智乃的比较函数(hard version)
题意
相较简单版，涉及的元素达到 \(3\) 个，
思路
但是所有的可能性，最多也只有 \(3^3\) 种，预处理打表一下，再判断是否属于某一种情况即可。
代码
/*******************************
| Author: AlwaysBeShine
| Problem: 智乃的比较函数(normal version)
| Contest: NowCoder
| URL: https://ac.nowcoder.com/acm/contest/67743/H
| When: 2024-02-07 16:24:03
|
| Memory: 524288 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int cmp(int a,int b){
if(a < b){
return 1;
}else{
return 0;
}
}
void solve(){
int n;
cin >> n;
bool ck = true;
int x,y,z;
set<pair<int,int>>st;
map<pair<int,int>,int>mp;
int gx[4][4];
for(int i = 1;i <= 3;i++){
for(int j = 1;j <= 3;j++){
gx[i][j] = 0;
}
}
for(int i = 0;i < n;i++){
cin >> x >> y >> z;
st.insert({x,y});
if(mp.count({x,y}) == 0){
mp[{x,y}] = z;
}else if((mp.count({x,y}) == 1 && mp[{x,y}] != z) || (mp.count({y,x}) == 1 && mp[{y,x}] + z == 2)){
ck = false;
}
if(x == y && z != 0)ck =false;
}
if(ck == false){
cout << "No" << endl;
return;
}else{
for(int i = 1;i <= 3;i++){
for(int j = 1;j <= 3;j++){
for(int k = 1;k <= 3;k++){
gx[1][1] = 0;
gx[1][2] = cmp(i,j);
gx[1][3] = cmp(i,k);
gx[2][1] = cmp(j,i);
gx[2][2] = 0;
gx[2][3] = cmp(j,k);
gx[3][1] = cmp(k,i);
gx[3][2] = cmp(k,j);
gx[3][3] = 0;
int cnt = 0;
for(auto& [a,b]:st){
if(gx[a][b] == mp[{a,b}]){
cnt++;
}
}
if(cnt == st.size()){
ck = true;
cout << "Yes" << endl;
return;
}
// cout << "cmp" << i << " " << j << " " << cmp(i,j) << endl;
// cout << "cmp" << i << " " << k << " " << cmp(i,k) << endl;
// cout << "cmp" << j << " " << i << " " << cmp(j,i) << endl;
// cout << "cmp" << j << " " << k << " " << cmp(j,k) << endl;
// cout << "cmp" << k << " " << i << " " << cmp(k,i) << endl;
// cout << "cmp" << k << " " << j << " " << cmp(k,j) << endl;
// cout << endl;
}
}
}
cout << "No" << endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while(T--){
solve();
}
return 0;
}