[Offer收割]编程练习赛67

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const LL mod = 1e9 + 7;
 5 
 6 int main() {
 7     int n, p;
 8     scanf("%d %d", &n, &p);
 9     if(n >= p) puts("0");
10     else {
11         LL ans = 1;
12         for(int i = 1; i <= n; ++i) ans = ans * (p - i) % mod;
13         printf("%lld
", ans);
14     }
15     return 0;
16 }

Aguin

B.彩球

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 
 5 __int128 qpow(__int128 a, __int128 b, __int128 mod) {
 6     __int128 ret = 1LL;
 7     while (b) {
 8         if (b & 1) ret = ret * a % mod;
 9         a = a * a % mod;
10         b >>= 1;
11     }
12     return ret;
13 }
14 
15 int main() {
16     LL n, k, P;
17     scanf("%lld %lld %lld", &n, &k, &P);
18     LL ans = qpow(k, n, P);
19     printf("%lld
", ans);
20     return 0;
21 }

Aguin

C.最优子段

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const LL INF = 1e18;
 5 const int maxn = 1e6 + 10;
 6 LL a[maxn], sum[maxn];
 7 set<LL> S;
 8 
 9 int main() {
10     int n, A, B;
11     scanf("%d %d %d", &n, &A, &B);
12     S.insert(0);
13     LL m = INF, M = -INF;
14     for(int i = 1; i <= n; ++i) {
15         scanf("%lld", a + i), sum[i] = sum[i-1] + a[i];
16         m = min(m, sum[i] - *S.rbegin());
17         M = max(M, sum[i] - *S.begin());
18         S.insert(sum[i]);
19     }
20     printf("%lld
", max(A * m, A * M) + B);
21     return 0;
22 }

Aguin

D.公路收费

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 vector<int> G[1111], D[1111];
 5 int a[1111];
 6 
 7 vector<LL> vec;
 8 LL sz[1111];
 9 void dfs(int x, int f) {
10     sz[x] = a[x];
11     for(int i = 0; i < G[x].size(); ++i) {
12         int to = G[x][i], d = D[x][i];
13         if(to == f) continue;
14         dfs(to, x);
15         sz[x] += sz[to];
16         vec.push_back(sz[to] * d);
17     }
18 }
19 
20 int main() {
21     int n, k;
22     scanf("%d %d", &n, &k);
23     for(int i = 1; i <= n; ++i) scanf("%d", a + i);
24     for(int i = 1; i < n; ++i) {
25         int u, v, w;
26         scanf("%d %d %d", &u, &v, &w);
27         G[u].push_back(v), D[u].push_back(w);
28         G[v].push_back(u), D[v].push_back(w);
29     }
30     LL ans = 1e18;
31     for(int i = 1; i <= n; ++i) {
32         vec.clear(), dfs(i, 0);
33         sort(vec.begin(), vec.end());
34         LL tmp = 0;
35         for(int j = 0; j < vec.size() - k; ++j) tmp += vec[j];
36         ans = min(ans, tmp);
37     }
38     printf("%lld
", ans);
39     return 0;
40 }

Aguin