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

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

codeforces

# A.GCD Sum

## Solution:

#include<bits/stdc++.h>using namespace std;#define ll long longinline bool ck(ll x){    ll sum=0;    ll tmp=x;    while(x) {        sum+=x%10;x/=10;    }    return __gcd(tmp,sum)==1;}int main(){    int n;    scanf("%d",&n);    long long x;    for(int i=1;i<=n;i++){        scanf("%lld",&x);        for(ll i=x;i;i++) if(!ck(i)){             printf("%lld\n",i);             break;        }    }}

# B.Box Fitting

## Solution:

#include<bits/stdc++.h>using namespace std;#define ll long longconst int N=1e5+7;int n,W,w[N],ans;priority_queue<int> q;inline bool cmp(int a,int b){    return a>b;}int main(){    int t;    scanf("%d",&t);    while(t--){        scanf("%d%d",&n,&W);        ans=0;        while(!q.empty()) q.pop();        for(int i=1;i<=n;i++) scanf("%d",&w[i]);        sort(w+1,w+1+n,cmp);        for(int i=1;i<=n;i++){            if(q.empty()) {                q.push(W);                ans++;            }            if(q.top()<w[i]){                ans++;                q.push(W);            }            int x=q.top()-w[i];            q.pop();            q.push(x);        }        cout<<ans<<endl;    }}

# C. Planar Reflections

## 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].

#include <cstring>#include <iostream>#include <vector>using namespace std;const int N = 1001;const int K = 1001;int n, k;const int mod = 1e9 + 7;int dp[N][K][2];int solve(int curr, int k, int dir) {    if (k == 1) {        return 1;    }    if (dp[curr][k][dir] != -1) {        return dp[curr][k][dir];    }    int ans = 2;  // me and my copy    if (dir == 1) {        if (curr < n)            ans += solve(curr + 1, k, dir) — 1;        ans %= mod;        if (curr > 1)            ans += solve(curr — 1, k — 1, 1 — dir) — 1;        ans %= mod;        dp[curr][k][dir] = ans;    } else {        if (curr > 1)            ans += solve(curr — 1, k, dir) — 1;        ans %= mod;        if (curr < n)            ans += solve(curr + 1, k — 1, 1 — dir) — 1;        ans %= mod;        dp[curr][k][dir] = ans;    }    return ans;}int main() {    int t;    cin >> t;    while (t--) {        cin >> n >> k;        memset(dp, -1, sizeof(dp));        cout << solve(1, k, 1) << endl;    }}

• 私有
• 公开
• 删除