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$ 设计的状态空间不够用，要想一想能不能滚动数组
