2024牛客寒假算法基础集训营3

A 智乃与瞩目狸猫、幸运水母、月宫龙虾

考点：语法题

思路：判断首字母是否相同或互为大小写即可，先全部转化为同一种形式

#include <bits/stdc++.h>
using namespace std;
string s1,s2;
int main()
{
    cin >> s1 >> s2;
    if(toupper(s1[0]) == toupper(s2[0])) puts("Yes");
    else puts("No");
    return 0;
}

B-智乃的数字手串

考点：博弈论，贪心
思路：从必胜倒推，举几个例子即可看出来

#include <bits/stdc++.h>
using namespace std;
const int N = 30;
int a[N]={0};
int main()
{
    int n;cin >> n;
    for(int i = 0;i < n;i ++) cin >> a[i];
    if(n & 1) 
        cout << "qcjj" << '\n';
    else 
        cout << "zn" << '\n';
    return 0;
}

D- chino's bubble sort and maximum subarray sum(easy version)

考点：模板（最大子数组和），动态规划
思路：套板子

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (k == 0) 
    {
        i64 ans = -1e18, res = 0;
        for (int i = 1; i <= n; i++) 
        {
            res = max(res + a[i], 1ll * a[i]);
            ans = max(ans, res);
        }
        cout << ans << '\n';
    } 
    else 
    {
        i64 ans = -1e18;
        for (int i = 1; i < n; i++) 
        {
            swap(a[i], a[i + 1]);
            i64 res = 0;
            for (int j = 1; j <= n; j++) 
            {
                res = max(res + a[j], 1ll * a[j]);
                ans = max(ans, res);
            }
            swap(a[i], a[i + 1]);
        }
        cout << ans << '\n';
    }
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    t = 1;
    while (t--) 
    {
        solve();
    }
    return 0;
}

L-智乃的36倍数(easy version)

考点：枚举，预处理
思路：用哈希表来保存数字出现的次数，长度1可以忽略数据范围只有1-10，很小

#include <bits/stdc++.h>
using namespace std;
//用哈希表保存数字和出现次数
unordered_map<int, int> Hash;
int main(){
    int res = 0;
	int n;cin >> n;
	for(int i = 1, x; i <= n; ++i) cin >> x,Hash[x]++;
    //1-10:能组成的36倍数只有36，72，108
	res += Hash[3] * Hash[6];
    res += Hash[7] * Hash[2];
	res += Hash[10] * Hash[8];
	cout << res << '\n';
	return 0;	
}

M-智乃的36倍数(normal version)

考点：枚举，预处理，动态规划思路：用动态规划的思想，跟前面有启发的思路，第一位保存数字长度，第二位保存对36取模的次数，便于快速遍历

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
i64 i,j,k,n,m,t,dp[21][36]; // 定义变量和数组，dp用于统计数的长度和对36求模的结果次数
i64 res = 0,pw[21];
//ab一对，cd一对
void solve(i64 a,i64 b,i64 c,i64 d)
{ 
    //不是36倍数直接返回
    if((b * pw[c] + d) % 36) return;
    //是就加一
    res += dp[a][b] * dp[c][d];
    
    res -= (a == c && b == d) ? dp[a][b] : 0; // 如果a等于c且b等于d，则需要减去重复计算的方案
}
int main()
{
    ios::sync_with_stdio(false); 
    cin.tie(nullptr);
    //预处理模数，不能少  
    pw[0]=1;
    for(i = 1;i <= 20;i ++) pw[i] = (pw[i - 1] * 10) % 36;
    //预处理dp数组
    cin >> n; 
    for(i = 1;i <= n;i ++)
    {
        i64 x; cin >> x;
        string s = to_string(x); 
        dp[s.size()][x % 36] ++; // 按数的长度和对36求模的结果次数进行分类统计，存储在dp数组中
    }
    //ij kt 分别处理
    for(i = 1;i <= 18;i ++)
        for(j = 0;j < 36;j ++)
        {
            for(k = 1;k <= 18;k ++)
                for(t = 0;t < 36;t ++)
                {
                    solve(i,j,k,t); 
                }
        }
    cout << res << '\n'; 
    return 0;
}