比赛链接：牛客周赛46
赛时感受
本场参加的是内测，多亏了内测群的佬提供的思路，得以AK。
ABC都是简单的签到题，D稍微需要分类一下，EF有点算法知识，E可以使用前缀和+二分搜索过掉，但是听说好像还能使用离散化树状数组等等，F是数学知识，隔板法和求质数、求组合。
一开始脑袋懵了，以为C题的数据太大暴力过不了，转去写欧拉筛求质数妄图通过质数求出x的小于n的因子个数，后面发现更难处理了，后面突然想起直接对x暴力求解是O(n½)的时间复杂度，然后直接暴力过掉。F题思考了很久，最开始连暴力的思路也没有，后面求出了x可以拆出来的质数个数，本来想对每个位置求组合，但是对于x = 4, y = 3，x = 2 * 2，可能第一个乘数排列得到第一个2，第二个乘数可能排列得到第二个2，但是同样可能第一个乘数排列取到第二个2，第二个乘数排列取到第一个二，但是此时两种情况是相同的，重复计算了同一种情况，一直卡在这个点，还是数学薄弱了。
A
思路
在有热的抹茶的时候先吃热抹茶，再吃冰抹茶，当冰抹茶吃完但是热抹茶还有时，需要判断当前还能吃热抹茶吗，若热抹茶吃完了病抹茶还没吃完，就直接吃掉剩下所有的冰抹茶。
题解
# python
s = list(map(int, input().split()))
if s[0] > s[1] * 2:
print(s[1] + s[0])
else :
print(s[0] + s[0] // 2)
B
思路
将输入的第x种茶的美味值赋值为0，然后对没位置数组进行排序，计算没位置最大的茶的种数就可以知道有多少种红茶可以选择了。
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
ll a[N];
int main() {
int n, x;
cin >> n >> x;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
a[x] = 0;
sort(a + 1, a + 1 + n);
int i = n;
while (i >= 1) {
if (a[i] == a[i - 1]) {
i--;
} else {
break;
}
}
cout << n - i + 1 << endl;
return 0;
}
C
思路
题解
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
int main() {
ll n, x, ans = 0;
cin >> n >> x;
for (int i = 1; i <= x / i; i++) {
if (x % i == 0 && i <= n) {
ans++;
if (i != (x / i) && x % (x / i) == 0 && (x / i) <= n) {
ans++;
}
}
}
cout << (ans % 2 == 0 ? "OFF" : "ON") << endl;
return 0;
}
D
思路
题解
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
int main() {
int t;
cin >> t;
while (t--) {
ll a[4], k;
cin >> a[1] >> a[2] >> a[3] >> k;
{
sort(a + 1, a + 4);
if (a[1] == k || a[2] == k || a[3] == k) {
cout << 0 << endl;
}
else if (k == 0) {
cout << 1 << endl;
}
else if (k == 1) {
if (a[1] == 0 && (a[2] != 1 || a[3] != 1)) {
cout << 1 << endl;
}
else {
cout << 2 << endl;
}
}
else if (k == 2) {
if (a[1] == 0 && (a[2] == 1 || a[3] == 1)) {
cout << 1 << endl;
}
else if (a[1] == 0) {
cout << 2 << endl;
}
else if (a[1] == 1) {
cout << 2 << endl;
}
else {
cout << 3 << endl;
}
}
else {
cout << -1 << endl;
}
}
}
return 0;
}
E
思路
题解
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
struct p {
int a, b;
}food[N];
bool cmp(struct p x, struct p y) {
return x.b < y.b;
}
ll all_sum[N], sum[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> food[i].a;
}
for (int j = 1; j <= n; j++) {
cin >> food[j].b;
}
sort(food + 1, food + 1 + n, cmp);
for (int i = 1; i <= n; i++) {
all_sum[i] = food[i].a * food[i].b + all_sum[i - 1];
sum[i] = food[i].a + sum[i - 1];
}
int q;
cin >> q;
for (int i = 1; i <= n; i++) {
ll l = 1, r = n, res = 0, mid;
int k;
cin >> k;
while (l <= r) {
mid = (l + r) >> 1;
if (food[mid].b <= k) {
res = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
cout << all_sum[res] + (sum[n] - sum[res]) * k << endl;
}
return 0;
}
F
思路
题解
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
bool vis[N];
int isprime[N];
void prime() {
for (int i = 2; i <= 5e4; i++) {
if (vis[i] == false) isprime[++isprime[0]] = i;
for (int j = 1; j <= isprime[0] && i * isprime[j] <= 5e4; j++) {
vis[i * isprime[j]] = true;
if (i % isprime[j] == 0) break;
}
}
}
ll qsm(ll x, ll y) {
ll res = 1;
while (y) {
if (y & 1) {
res *= x;
res %= mod;
}
x *= x;
y >>= 1;
x %= mod;
}
return res;
}
ll inverse(ll x) {
return qsm(x, mod - 2);
}
ll c(ll n, ll m) {
ll res = 1;
for (ll i = n; i > (n - m); i--) {
res *= i;
res %= mod;
}
ll x = 1;
for (ll i = 1; i <= m; i++) {
x *= i;
x %= mod;
}
res *= inverse(x);
return res % mod;
}
int main() {
int t;
cin >> t;
prime();
while (t--) {
ll x, y, ans = 0, res = 1;
cin >> x >> y;
for (int i = 1; i <= isprime[0]; i++) {
if (isprime[i] > x) break;
if (x % isprime[i] == 0) {
while (x % isprime[i] == 0) {
x /= isprime[i];
ans++;
}
}
if (ans == 0) continue;
res *= c(ans + y - 1, ans);
res %= mod;
ans = 0;
}
if (x > 1) {
res *= y;
res %= mod;
}
cout << res << endl;
}
return 0;
}