A.小沙の好客
题意：
有一家超市，超市里面有 n 件商品，X现在有 Q 个问题，X 让你帮忙挑选最多 k 个价值不大于 x 的商品，问每次最大价值是多少？
数据范围：
ai表示商品的价格
$$1\leq n \leq 10^5,1\leq Q \leq 10^5$$
$$1\leq a_i \leq 10^9$$
$$1 \leq k \leq n,1 \leq x \leq10^9$$
题解：二分，前缀和
对商品价值排序之后，通过前缀和进行计算，最后通过二分，找到 x 所在a的位置。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| void JiuCherish(){
int n,q;
std::cin >> n >> q;
for(int i=1;i<=n;i++) std::cin >> a[i];
std::sort(a + 1,a + 1 + n);
for(int i=1;i<=n;i++) pre[i] = pre[i - 1] + a[i];
while(q --) {
int x,k;
std::cin >> x >> k;
int l = 0,r = n;
int mid = 0;
while(l < r) {
mid = l + r + 1 >> 1;
if(a[mid] <= k) {
l = mid;
} else {
r = mid - 1;
}
}
if(l <= x) {
std::cout << pre[l] << endl;
} else {
std::cout << pre[l] - pre[l - x] << endl;
}
}
}
|
B.小沙の博弈
题意：
在两人A与B都十分聪明的情况，他们会选择最优的胜利方式，桌上有 n 个石子，他们两个人面前均有排成一行的若干个格子，每个格子都可以置放无限多个石子。
A先走，每次拿任意正整数个石子，放在第一个没有石子的格子里。
当桌上石子数为 0 的时候游戏结束，按照两人各自中石子数目组成序列的字典序判断胜负，字典序小的人获胜。
数据范围：
$$1 \leq n \leq 10^5$$
输出一个字符串。
当A获胜时输出：”Sajin-win!”(不含引号)。
当B获胜时输出：”Yaya-win!”(不含引号)。
如果都没获胜，输出”win-win!”(不含引号)。
题解：博弈
当石子数目为偶数的时候，双方的字典序必然是相同的，当石子数为奇数的时候，先手必输即字典序大。
代码：
1
2
3
4
5
6
7
8
9
| void JiuCherish(){
int n;
std::cin >> n;
if(n & 1) {
std::cout << "Yaya-win!" << endl;
} else {
std::cout << "win-win!" << endl;
}
}
|
C. 小沙の不懂
D.小沙の赌气
E.小沙の印章
F.小沙の串串
G.小沙の编码
H.小沙の店铺
I. 小沙の金银阁
J.小沙の最短路
K.小沙の抱团 easy
L.小沙の抱团 hard