部分题解(A、B、H、K)
A 小沙の好客
思路:
前缀和+sort+二分 (c++可用low_bound和upper_bound函数来二分)
直接用一个循环算结果过不去(应该是超时,不知道为什么报答案错误)
用新数组存好前缀和,算出位置,处理一下就好
代码:
#include <bits/stdc++.h>
using namespace std;
int main() {
long long int n, q, k, x, res, flag, a[100005], sum[100005];
cin >> n >> q;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
sum[0]=0;
for (int i = 0; i < n; i++) {
sum[i+1]=sum[i]+a[i];
}
while (q--) {
res=0;
cin>>k>>x;
flag=upper_bound(a,a+n,x)-a;
if(flag<k){
res=sum[flag];
}else{
res=sum[flag]-sum[flag-k];
}
cout<<res<<endl;
}
}
B 小沙の博弈
思路:
博弈论,就是在最经典的博弈论(先手必赢)上套个皮
简单理解就是为使序列最小,双方每次只拿1个(不知道说的对不对)
n是偶数就平局,不然先手(小雅)必赢
代码:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
if(n%2==0){
cout<<"win-win!";
}else{
cout<<"Yaya-win!";
}
}
H 小沙の店铺
思路:
感觉也没什么特别的,记得处理卖的钱不够T的情况
代码:
#include <bits/stdc++.h>
using namespace std;
int main() {
long long int x , y , k , n , t, r = 0, num = 0, sum=0, nn;
cin >> x >> y >> k >> n >> t;
nn = n;
while(n--){
if(r >= t){
break;
}else{
r += (x + (num * y)) *(n + 1);
sum = sum + n + 1;
num = sum / k;
}
}
if(r < t){
cout<<"-1";
}else{
cout<<nn-n-1;
}
}
K 小沙の抱团 easy
思路:
想要淘汰最多的人,就以 一半多一点 的人为单位抱团就行
那样只能留下 一半多一点 的人 ,淘汰 一半少一点 的人
(暂时没有想到什么一步到位的公式写法)
代码:
#include <bits/stdc++.h>
using namespace std;
int main() {
long long int n,k,c=0;
cin>>n;
k=n;
if(n==1||n==2){
cout<<"0";
}else{
while(k>2){
k=k/2+1;
c++;
}
cout<<c;
}
}