2021年08月21日 CSP-J模拟赛讲解

T1-面试

直接按照题目意思模拟一下，记录每个字符串中 $C, \ D, \ A$ 的个数，条件语句判断一下即可。

说明一下同学们犯的错误：

判断条件写错了
没换行
没清空计数器
数组开小了（数组不是乱开的，最好开的比题目要求的大一点点就好。开太大了会MLE，正式比赛MLE会爆零。小了会RE或者WA）

T2-Excel计数法

对于 $40$ 分的做法，模拟一下数数的过程。从 $1$ 数到 $n$ ，按照题意把每个数字对应的字母给数出来，最后输出 $n$ 的对应字母就行了。

对于 $100$的做法，观察一下数字与字母对应大的关系。可以对数字进行类似进制转化的操作。可以看成与$26$进制的转化。注意$Z$ 不是 $0$，是 $26$ 。如果发现末尾为 $Z$ ，那么下一次的 $n$ 要减一。

while(n) {
    int x = n%26;
    n = n/26;
    if(x == 0) {
        ans += 'Z';
        n--;
    }
    else ans += (x-1+'A');
}

最后将 ans 倒序输出。

T3-纸牌游戏

给出结论：在现存 $Q$ 个人的情况下，对于第 $i$ 个人，如果 $a[i] < Q-1$ ，那么第 $i$ 个人必然会被淘汰出局，反之则永远不会被淘汰出局。

因为在每一轮游戏中，第 $i$ 个人必然会损失掉 $Q-1$ 张牌，最多补充 $min(a[i], \ Q-1)$ 张牌。

所以可以按照 $a[]$ 从小到大排序，对于永远不会踢出的第 $i$ 个人而言，第$i+1$ 到第 $n$ 个人也必然不会被踢出局。

$a[i]$ 越小越容易被淘汰

sort(a+1, a+n+1);
for(int i=1; i<=n; ++i) {
    if(a[i]>=n-i) {
        ans = n-i+1;
        break;
    }
}

怎么写部分分？

分段

保证你的部分分做法不出错误的时候，前面分段写部分分做法。后面再写满分或者骗分的代码。

这样保证自己最低可以拿到部分分。

if(n<=2){
    printf("%d\n", n);
}
else if(n==3) {
    if(a[1]>=2 && a[2]>=2 && a[3]>=2)
        printf("3\n");
    else printf("2\n");
}
else { // 写正解或者骗分的代码 
    sort(a+1, a+n+1);
    for(int i=1; i<=n; ++i) {
        if(a[i]>=n-i) {
            ans = n-i+1;
            break;
        }
    } 
}

T4-涨薪

对于第三档的 $20$ 分， $x+y==n$ 表示不存在绩效为 $C$ 人。那么直接算出$m$ 年之后绩效 $A, \ \ B$ 两类人的工资总和即可。

对于第四档的 $20$分，在第三档的基础上用快速幂 计算出 $2^m$ 与 $3^m $ 即可。这样你就拿到了 $40$ 分了。

考虑 $100$ 做法，可以知道基础工资越高的人留下来，对于 $m$ 年后的总工资和就越大。所以可以直接贪心，将 $a[i]$ 排序。按照 $a[i]$ 的值从大到小去分配 $A,\ B,\ C$ 三种绩效。最后加上快速幂求出答案。

T5-富有数

我们去掉非富有数不会影响求解题目的答案。

那么直接记录下每种富有数的个数$t_i$。（离散化或者$map$）

设 $dp[i][j]$ 表示前 $i$ 种富有数里面选 $j$ 个的方案数。

初始状态有： $dp[0][0] = 1$;

状态转移：

不用第 $i$ 种，$dp[i][j] = dp[i-1][j]$;
用第 $i$ 种， $dp[i][j] = dp[i-1][j-1]*t_i$;

$dp[i][j] = dp[i-1][j]+dp[i-1][j-1]*t_i$

离散化：

void discrete()
{
    sort(a+1,a+n+1); // 排序 
    for(int i=1; i<=n; ++i) //去重
    {
        if(i==1 || a[i]!=a[i+1]) {
            b[++m] = a[i];
        }
     } 
}

int query(int x) {  //  查询x映射为哪一个 1~m 之间的整数 
    return lower_bound(b+1, b+m-1, x) - b;
}

map

#include<bits/stdc++.h> 
#include <map>
using namespace std;
const int maxn = 1e6+10;
typedef long long LL;
LL a[maxn];
int n;

// map<key_type, value_type> name; 键是不能重复的，值可以重复  
map<long long, int> mp; // 定义一个键为long long类型，值为 int类型的map容器
map<long long, bool> v1;
map<string, int> v2;
map<pair<int, int>, vector<int>> v3; // 键必须要稳定状态的数据类型或者容器,不可修改

void count()
{
    for(int i=1; i<=n; i++) { // 键是富有数这个数字，值是这个富有数的个数 
        mp[a[i]]++; // 修改也是log的 
    }
} 

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; ++i)
        scanf("%lld", &a[i]);
    count();
    printf("%d\n", mp[a[1]]); // mp[a[i]] 表示 a[i]为键对应的值 ，每次查找都是log(n)的 
    // 输出所有的a[i]与其对应的个数，遍历所有的键
    map<long long, int>::iterator i; // 定义一个名字为 i 的迭代器 
    for(i=mp.begin(); i!=mp.end(); ++i) { // 默认按照键升序来排序 
        printf("%lld  %d\n", i->first, i->second); / i表示一个键值对的指针 
    }
    return 0;
}

注意事项:

比赛开数组的时候一定要计算使用的内存
认真的研究每档部分分，在你想的满分做法不能保证是正解时，一定要写分段。分段保平安！！！
map和离散化的代码要多看看，非常实用的知识点！！！
$dp$ 设计的状态空间不够用，要想一想能不能滚动数组

chunzhen的博客

博客