T1:面试
牛牛内推了好多人去牛客网参加面试，面试总共分四轮，每轮的面试官都会对面试者的发挥进行评分。评分有 A B C D 四种。如果面试者在四轮中有一次发挥被评为 D，或者两次发挥被评为 C，就不会通过面试。如果面试者没有一次被评为 D，并且有三个或以上的 A，则会获得 special offer。其余情况会获得普通 offer。
现在告诉你一些面试者的发挥，请你算一算，他们的面试结果分别是什么。
输入描述:
第一行输入一个 T，代表面试者的个数。
接下来有 T 行，每行都有一个长度为 4 的字符串，每个位置的字符分别代表面试者每一轮的发挥。
输出描述:
输出 T 行，分别表示 T 个面试者的面试结果。如果面试失败，输出failed，如果面试通过，但不是 special offer，则输出offer，否则输出 sp offer。
样例输入：
2
AAAB
ADAA
样例输出：
sp offer
failed
题解：
一道简单模拟注意不要看错题即可。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std
;
string a
;
int t
, suma
, sumb
, sumc
, sumd
;
int main() {
scanf("%d", &t
);
while(t
--) {
suma
= 0;sumb
= 0;sumc
= 0;sumd
= 0;
cin
>>a
;
int lena
= a
.size();
for(int i
= 0;i
< lena
; i
++) {
if(a
[i
] == 'A') suma
++;
if(a
[i
] == 'B') sumb
++;
if(a
[i
] == 'C') sumc
++;
if(a
[i
] == 'D') sumd
++;
}
if(sumd
> 0 || sumc
>= 2) printf("failed\n");
else if(sumd
== 0 && suma
>= 3) printf("sp offer\n");
else printf("offer\n");
}
}
T2:纸牌游戏
公司举办团建活动，许多人在一起玩一个纸牌游戏。规则如下：
总共有 n 个人，每个人初始有 n 张牌。每一轮从第一个人开始轮流操作，第 i 个人每次操作必须选择
m
i
n
(
p
e
o
p
l
e
−
1
,
a
i
)
min(people-1,a_i)
min(people−1,ai)个不同的人，分别从他们手中拿走一张牌。其中people 为游戏现存人数，手上没有牌的人立即被淘汰出局。大家希望有尽可能多的人出局，游戏无限的进行下去，问最终游戏中最少还有几个人没有出局。 注意：不能从自己手中拿牌
输入描述:
第一行输入一个数字 n， 代表游戏的总人数。接下来输入 n 个数字，分别代表
a
i
a_i
ai
输出描述:
输出一行一个整数表示游戏最终最少剩几个人。
样例输入：
2
1 2
样例输出：
2
题解：
题意：n个人每个人可以拿除他以外的min(a[i], n - 1)，人不能重复且每人只能拿一张牌，求最后至少剩多少人。 因为题目要求剩最少的人，所以不难想到一种极端选法：让所有人都去拿一个人的牌，那么一轮可以拿
n
−
1
n-1
n−1张（及除他以外所有人），若被取的人的
a
[
i
]
>
=
n
−
1
a[i] >= n-1
a[i]>=n−1，则说明每轮
n
−
1
n-1
n−1个人取完他都可以把牌取回去，即他永远不会被淘汰，反之若
a
[
i
]
<
n
−
1
a[i] < n-1
a[i]<n−1那么第i个人必定会在某轮被取完。 值得注意的是按照我们的方法来说，a[i]小的人是可以最快取完的，所以先对a[i]排序，其次就是若一个人被淘汰那么n也要相应的减少一个人。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std
;
const int MAXN
= 1e5 + 5;
int n
, m
, a
[MAXN
], qian
[MAXN
];
bool cmp(int x
, int y
) {
return x
< y
;
}
int main() {
scanf("%d", &n
);
for(int i
= 1;i
<= n
; i
++) {
scanf("%d", &a
[i
]);
if(a
[i
] > n
- 1) {
a
[i
] = n
- 1;
}
}
sort(a
+ 1, a
+ 1 + n
, cmp
);
int sum
= 0;
int k
= n
;
for(int i
= 1;i
<= n
; i
++) {
if(a
[i
] < k
- 1) {
sum
++;
k
--;
}
}
printf("%d", n
- sum
);
return 0;
}
T3:加薪
公司中总共有 n 个人，其中第 i 个人的初始工资为
a
i
a_i
ai 。公司根据每个人的绩效(工作表现)来评定每个人的涨薪幅度。每年有 x 个人绩效为 A，工资可以变为原来的 3 倍；y 个人绩效为 B，工资可以变为原来的 2 倍，其余人绩效为 C，工资不变，连续两年绩效为 C 会被开除。(保证
x
+
y
≤
n
)
x+y \le n)
x+y≤n)
假如公司没有一直招聘新员工，请问 m 年后，公司需要给所有在职员工支付的工资总和最多为多少。由于答案可能很大，请输出对
1
0
9
+
7
10^9 + 7
109+7取模后的结果。
输入描述:
输入第一行包含四个正整数 n, m,x,y，意义如题面所示。 接下来一行包含 n 个正整数，第 i 个正整数为
a
i
a_i
ai代表第 i 个人的初始工资。
输出描述:
输出一行一个整数表示 m 年后工资总和对
1
0
9
+
7
10^9+7
109+7取模后的结果。
样例输入：
2 1 1 1
5 3
样例输出：
21
题解：
一道简单贪心，因为要选x个人和y个人去乘3和乘2，所以不难想到选人选最大的，因为这样乘出来的数才最大，得出的和也就最大，至于另外的人乘出来一定没有乘最大值大，所以开除也无所谓。 所以先对a[i]从大到小排序，在取前x个3，区x+1—x+y2，剩下如果未被开除就加上即可。 还有记得加上快速幂。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std
;
const int MAXN
= 1e5 + 5, mod
= 1e9 + 7;
long long n
, m
, x
, y
, a
[MAXN
];
bool cmp(long long x
, long long y
) {
return x
> y
;
}
long long powr(long long a
, long long b
) {
if(b
== 0) return 0;
long long sum
= 1;
for(; b
; b
= b
>> 1) {
if(b
& 1) {
sum
= (sum
* a
) % mod
;
}
a
= (a
* a
) % mod
;
}
return sum
;
}
int main() {
scanf("%lld %lld %lld %lld", &n
, &m
, &x
, &y
);
for(int i
= 1;i
<= n
; i
++) scanf("%lld", &a
[i
]);
sort(a
+ 1, a
+ 1 + n
, cmp
);
long long sum
= 0;
int len1
= min(x
, n
), len2
= min(x
+ y
, n
);
if(x
> 0) for(int i
= 1; i
<= len1
; i
++) sum
+= (a
[i
] * powr(3, m
)) % mod
;
if(y
> 0)for(int i
= x
+ 1; i
<= len2
; i
++) sum
+= (a
[i
] * powr(2, m
)) % mod
;
if(m
< 2) for(int i
= x
+ y
+ 1;i
<= n
; i
++) sum
+= a
[i
] % mod
;
printf("%lld", sum
% mod
);
return 0;
}
T4:变换
给出一个序列A，其中第 i 个数字为
a
i
a_i
ai，你每次操作可以选择一个数字不变，其他数字乘以 x，其中 x 为任意素数 无需考虑这些数字在变换过程中是否超过 long long 的存储范围。请回答：最少经过多少次操作，可以使得序列中所有数字全部相同。
输入描述:
第一行包含一个正整数 n，代表序列长度。 接下来一行包含 n 个正整数，描述序列中的每一个元素。
输出描述:
输出一行一个正整数表示答案。
样例输入：
2
5 7
样例输出：
2
题解：
因为将除x以外的质数，等于让x除以一个x质数，所以题目可转化为将某个数除以它的质因子，求最少几次后n个数为同一个数。 如果有了这样的想法，那么我们不难知道操作完后得到的数是
g
c
d
(
a
[
1
]
,
a
[
2
]
,
a
[
3
]
.
.
.
.
a
[
n
]
)
gcd(a[1], a[2], a[3]....a[n])
gcd(a[1],a[2],a[3]....a[n])把它记为zgcd，那么最后就是求a[1~n]/zgcd共有多少个质因子。 计算质因子推荐用质数筛筛一遍，再一个一个试。
代码：
#include <iostream>
#include <cstdio>
using namespace std
;
int n
, m
, x
, b
[100000005], k
, _max
= -0x3f3f3f3f, a
[1000005];
bool vis
[100000005], l
[100000005];
void sushuols(int s
) {
for (int i
= 2; i
<= s
; i
++) {
if (!vis
[i
]) {
b
[++k
] = i
;
l
[i
] = 1;
}
for (int j
= 1; j
<= k
; j
++) {
if (i
* b
[j
] > s
)
break;
vis
[i
* b
[j
]] = 1;
if (i
% b
[j
] == 0)
break;
}
}
}
int gcd(int a
, int b
) {
if(b
== 0) return a
;
return gcd(b
, a
% b
);
}
int main() {
scanf("%d", &n
);
for(int i
= 1; i
<= n
; i
++) {
scanf("%d", &a
[i
]);
_max
= max(_max
, a
[i
]);
}
sushuols(_max
);
int zgcd
= a
[1];
for(int i
= 2; i
<= n
; i
++) zgcd
= gcd(zgcd
, a
[i
]);
int sum
= 0;
for(int i
= 1;i
<= n
;i
++) {
int k
= a
[i
] / zgcd
, j
= 1;
while(!l
[k
]) {
if(b
[j
] == 0) break;
if(k
% b
[j
] == 0){
sum
++;
k
/= b
[j
];
}
else j
++;
}
if(k
> 1 && l
[k
]) sum
++;
}
printf("%d", sum
);
return 0;
}
