Algorithms Weekly 6

A noi week

  • codeforces round 637div2([Thanks, Ivan Belonogov!])

    Final score:

    Problem D.

    D题的题意是有\(n\)个八数码管,即每个八数码管由八根LED管组成,可以表示\(0-9\)\(10\)个数字,现在可以任选\(k\)根LED管点亮,问最大所能表示的数字是几。

    思路就是先\(dp\)记录可行状态,然后再贪心的选取即可。令\(dp_{i,j}\)代表截止到第\(i\)个八数码管,还有\(j\)次点亮的机会的可行性,那么\(dp_{n+1,0}=1\),然后倒着\(dp\)即可。处理完之后对每个八数码管贪心的选取最大的能点亮的数字即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    /*
    * @author: codancer
    * @createTime: 2020-04-24, 00:27:50
    */
    #include<bits/stdc++.h>

    using namespace std;
    typedef long long ll;
    const ll mod = 1e9+7;
    #define pb push_back
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    #define rep(i,a,b) for(int i=(a);i<=(b);i++)
    #define fep(i,a,b) for(int i=(a);i>=(b);i--)
    typedef vector<int> VI;
    typedef vector<ll> VII;
    typedef pair<int,int> pii;
    string lights[20]={"1110111","0010010","1011101","1011011","0111010","1101011","1101111","1010010","1111111","1111011"};
    string s[20000];
    int lastcost;
    bool dp[2002][20000];//boolean cost j after approach i
    int cost(int a,int b){// the cost of s[a]->lights[b]
    int ans=0;
    for(int j=0;j<7;j++){
    if(s[a][j]>lights[b][j]){
    return -1;
    }
    ans+=lights[b][j]-s[a][j];
    }
    return ans;
    }
    int main(){
    int n,k;
    cin>>n>>k;
    rep(i,1,n) cin>>s[i];
    dp[n+1][0]=1;
    lastcost=0;
    fep(i,n,1){
    fep(j,lastcost,0){
    if(dp[i+1][j]==0) continue;
    rep(k,0,9){
    int costs=cost(i,k);
    if(costs!=-1) dp[i][j+costs]|=dp[i+1][j];
    lastcost=max(lastcost,j+costs);
    }
    }
    }
    vector<int> ans;
    bool ok=1;
    rep(i,1,n){
    bool found=false;
    fep(j,9,0){
    int costs=cost(i,j);
    if(costs!=-1&&costs<=k){
    if(dp[i+1][k-costs]){
    ans.pb(j);
    k-=costs;
    found=true;
    break;
    }
    }
    }
    if(found==false){
    ok=0;
    break;
    }
    }
    if(ok){
    for(int v:ans) cout<<v;
    cout<<endl;
    }else{
    puts("-1");
    }
    return 0;
    }
  • Noi online

    因为太怂没敢打提高组,打了普及组。比赛的时候提交了两道题,在洛谷上测试了民间数据都通过了。

    预计成绩为\(200\)分。

    • T1是个简单的二分,考虑每次启用距离山顶最近的魔法机关,然后二分最少次数即可。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      /*
      * @author: codancer
      * @createTime: time
      */
      #include<bits/stdc++.h>

      using namespace std;
      typedef long long ll;
      const ll mod = 1e9+7;
      #define pb push_back
      #define fi first
      #define se second
      #define SZ(x) ((int)(x).size())
      #define rep(i,a,b) for(int i=(a);i<=(b);i++)
      #define fep(i,a,b) for(int i=(a);i>=(b);i--)
      typedef vector<int> VI;
      typedef vector<ll> VII;
      typedef pair<int,int> pii;
      const int N = 2e5+100;
      ll n,L,v,a[N],q,tt,predis[N];

      bool cmp(ll x,ll y){
      return x>y;
      }
      int main(){
      // freopen("endless.in","r",stdin);
      // freopen("endless.out","w",stdout);
      scanf("%lld %lld %lld",&n,&L,&v);
      rep(i,1,n){
      scanf("%lld",&a[i]);
      }
      sort(a+1,a+n+1,cmp);
      rep(i,1,n) predis[i]=predis[i-1]+a[i];
      scanf("%lld",&q);
      while(q--){
      scanf("%lld",&tt);
      ll l=0;
      ll r=n+1;
      bool ok=0;
      rep(i,1,30){
      ll mid=(l+r)/2;
      if(predis[mid]+L>tt*v){
      r=mid;
      ok=1;
      }else{
      l=mid;
      }
      }
      if(ok){
      printf("%lld\n",r);
      }else{
      puts("-1");
      }
      }
      return 0;
      }
    • T3题意是你需要构造\(2n\)个建筑,前\(n\)个建筑的高度单调不减,后\(n\)个建筑的高度单调不增,每个建筑的高度在\([1,m]\)内,并且第\(x\)和第\(y\)座建筑的高度相同,计算方案数。

      长度为\(n\)的数组,每个数字单调不减的方案书为\(C(n+m-1,n)\),讨论\(x\)\(y\)的位置即可。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      /*
      * @author: codancer
      * @createTime: 2020-04-25, 15:24:40
      */
      #include<bits/stdc++.h>

      using namespace std;
      typedef long long ll;
      const ll mod = 998244353;
      #define pb push_back
      #define fi first
      #define se second
      #define SZ(x) ((int)(x).size())
      #define rep(i,a,b) for(ll i=(a);i<=(b);i++)
      #define fep(i,a,b) for(ll i=(a);i>=(b);i--)
      typedef vector<int> VI;
      typedef vector<ll> VII;
      typedef pair<int,int> pii;
      const int N = 2e5+100;
      ll n,m,x,y;
      ll fact[N],inv[N],factinv[N];
      void init(){
      fact[0]=inv[1]=factinv[0]=inv[0]=fact[1]=factinv[1]=1;
      for(int i=2;i<=200010;i++){
      fact[i]=(fact[i-1]%mod*i%mod)%mod;
      inv[i]=(mod-mod/i)*inv[mod%i]%mod;
      factinv[i]=factinv[i-1]*inv[i]%mod;
      }
      }
      ll c(ll n,ll m){
      return fact[n]*factinv[m]%mod*factinv[n-m]%mod;
      }
      ll solve(ll n,ll m){// the number of lengtn n and each number belongs [1,m]
      if(m+n-1<n) return 0;
      return c(m+n-1,n);
      }
      int main(){
      // freopen("city.in","r",stdin);
      // freopen("city.out","w",stdout);
      init();
      scanf("%lld%lld%lld%lld",&m,&n,&x,&y);
      if(y<=n){
      ll left=0;
      rep(i,1,m){
      ll xx=solve(x-1,i);
      ll yy=solve(n-y,m-i+1);
      left+=(xx*yy)%mod;
      left%=mod;
      }
      ll right=solve(n,m);
      printf("%lld\n", (left*right)%mod);
      return 0;
      }
      if(x>n){
      ll left=solve(n,m);
      ll right=0;
      x=2*n+1-x;
      y=2*n+1-y;
      swap(x,y);
      rep(i,1,m){
      ll xx=solve(x-1,i);
      ll yy=solve(n-y,m-i+1);
      right+=(xx*yy)%mod;
      right%=mod;
      }
      printf("%lld\n", (left*right)%mod);
      return 0;
      }
      ll ans=0;
      ll left=0;
      ll right=0;
      y=2*n+1-y;
      rep(i,1,m){
      left=solve(x-1,i);
      left*=solve(n-x,m-i+1);
      left%=mod;
      right=solve(y-1,i);
      right*=solve(n-y,m-i+1);
      right%=mod;
      ans+=(left*right)%mod;
      ans%=mod;
      }
      printf("%lld\n",ans);
      return 0;
      }