牛客周赛46（思路待补）

比赛链接：牛客周赛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;
}