[关闭]
@Bei-S 2021-03-31T03:26:17.000000Z 字数 2465 阅读 157

CodeCraft-21 and Codeforces Round #711 (Div. 2)

codeforces


A.GCD Sum

题意:

给你一个n,求出大于等于n的第一个满足gcd(x,Sum of digits of x)>1的数。

Solution:

考虑3的倍数,对于3的倍数一定满足上述条件。故每三个数有一个满足,暴力

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. inline bool ck(ll x){
  5. ll sum=0;
  6. ll tmp=x;
  7. while(x) {
  8. sum+=x%10;x/=10;
  9. }
  10. return __gcd(tmp,sum)==1;
  11. }
  12. int main(){
  13. int n;
  14. scanf("%d",&n);
  15. long long x;
  16. for(int i=1;i<=n;i++){
  17. scanf("%lld",&x);
  18. for(ll i=x;i;i++) if(!ck(i)){
  19. printf("%lld\n",i);
  20. break;
  21. }
  22. }
  23. }

B.Box Fitting

题意:

给你一个宽为W的盒子和一些高为1,宽为2^x的矩形,矩形不能重叠,问盒子至少为多高可以放下所有矩形

Solution:

直接贪心,每一层放最大的,当放不下时就要新开一层。同时可以用一个优先队列记录当前每一层剩余宽度,这样保证每次找到的剩余宽度最大。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const int N=1e5+7;
  5. int n,W,w[N],ans;
  6. priority_queue<int> q;
  7. inline bool cmp(int a,int b){
  8. return a>b;
  9. }
  10. int main(){
  11. int t;
  12. scanf("%d",&t);
  13. while(t--){
  14. scanf("%d%d",&n,&W);
  15. ans=0;
  16. while(!q.empty()) q.pop();
  17. for(int i=1;i<=n;i++) scanf("%d",&w[i]);
  18. sort(w+1,w+1+n,cmp);
  19. for(int i=1;i<=n;i++){
  20. if(q.empty()) {
  21. q.push(W);
  22. ans++;
  23. }
  24. if(q.top()<w[i]){
  25. ans++;
  26. q.push(W);
  27. }
  28. int x=q.top()-w[i];
  29. q.pop();
  30. q.push(x);
  31. }
  32. cout<<ans<<endl;
  33. }
  34. }

C. Planar Reflections

题意:

有n架飞机和一个寿命为k的粒子,当粒子撞上飞机且寿命不为1时,他会产生一个方向相反的寿命为k-1的粒子,自己寿命不变并继续保持原方向穿过飞机。给你飞机数量n,k,问最后有多少个粒子。

Solution

dp,设计状态dp[i][j][d]为寿命为j的粒子以方向d撞向第i个飞机所能产生的粒子数。
How to update the DP states? If k=1, the value of dpn[d] for any n or d is obviously 1 (as no copies are produced).

So, let us consider a particle P with k>1. This particle P produces a copy P′ going in the opposite direction. We can count the number of particles produced by P′ as dp[n — 1][k — 1][1 — d], as it hits the previous plane with a smaller decay age and in the opposite direction. Moreover, the particle P itself hits the next plane and continues to produce more stuff. We can calculate its number of particles produced as dp[n + 1][k][d], as it hits the next plane with the same decay age and the same direction!

Finally, we can combine these two values to get the value of dp[n][k][d].

  1. #include <cstring>
  2. #include <iostream>
  3. #include <vector>
  4. using namespace std;
  5. const int N = 1001;
  6. const int K = 1001;
  7. int n, k;
  8. const int mod = 1e9 + 7;
  9. int dp[N][K][2];
  10. int solve(int curr, int k, int dir) {
  11. if (k == 1) {
  12. return 1;
  13. }
  14. if (dp[curr][k][dir] != -1) {
  15. return dp[curr][k][dir];
  16. }
  17. int ans = 2; // me and my copy
  18. if (dir == 1) {
  19. if (curr < n)
  20. ans += solve(curr + 1, k, dir) 1;
  21. ans %= mod;
  22. if (curr > 1)
  23. ans += solve(curr 1, k 1, 1 dir) 1;
  24. ans %= mod;
  25. dp[curr][k][dir] = ans;
  26. } else {
  27. if (curr > 1)
  28. ans += solve(curr 1, k, dir) 1;
  29. ans %= mod;
  30. if (curr < n)
  31. ans += solve(curr + 1, k 1, 1 dir) 1;
  32. ans %= mod;
  33. dp[curr][k][dir] = ans;
  34. }
  35. return ans;
  36. }
  37. int main() {
  38. int t;
  39. cin >> t;
  40. while (t--) {
  41. cin >> n >> k;
  42. memset(dp, -1, sizeof(dp));
  43. cout << solve(1, k, 1) << endl;
  44. }
  45. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注