Atcoder abc258

發表於 更新於 分類於 ， Disqus： 文章字數： 1.1k 所需閱讀時間 ≈ 4 分鐘
F(暴力)G(bitset)H/Ex(dp,矩阵快速幂)

F

题目

https://atcoder.jp/contests/abc258/tasks/abc258_f

网格,4临移动

如果 x=Bn的线上移动或者y=Bn的线上移动,(B的倍数), 单位距离代价1

其它情况单位距离代价k

求(sx,sy) -> (gx,gy) 的最小代价

范围

t 2e5 测试点

b,k [1,1e9]

sx,sy,gx,gy [0,1e9]

3s

1024mb

题解

我的思路

显然是个数学处理一下, 就做的题

两个点分开考虑

一个点计算它本身, 四个方向到x=bn or y=bn , 的点,再到四个角的点

点类型 (普通0,边点1,十字交点2)

(0-任何) 直接距离乘k

(边点 - 边/十字) = 在方向上同bn, 则x1, 否则直接距离乘k

(十字-十字) = 距离x1

写了二十多分钟

代码

https://atcoder.jp/contests/abc258/submissions/32973579

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
86
87
88
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

ll b;
ll k;

const int T_NORMAL = 0; // 普通
const int T_SIDE = 1; // 边
const int T_CROSS = 2; // 角

int calctype(ll i,ll j){
  return (int)(i%b == 0) + (int)(j%b == 0);
}

vector<array<ll,3> > calc(ll i,ll j){  // i , j , dis
  vector<ll> ai = {i};
  vector<ll> aj = {j};
  if(i%b) {
    ai.pb((i/b)*b);
    ai.pb((i/b+1)*b);
  }
  if(j%b) {
    aj.pb((j/b)*b);
    aj.pb((j/b+1)*b);
  }
  vector<array<ll,3> > res;
  for(auto ni:ai){
    for(auto nj:aj){
      if(ni != i && nj != j){
        res.pb({ni,nj, (abs(ni-i) + abs(nj-j) - max(abs(ni-i), abs(nj-j)))*k + max(abs(ni-i), abs(nj-j)) });
      }else{
        if(i % b != 0 && j%b != 0){
          res.pb({ni,nj, (abs(ni-i) + abs(nj-j))*k});
        }else{
          res.pb({ni,nj, (abs(ni-i) + abs(nj-j))});
        }
      }
    }
  }
  return res;
}

void w(){
  b = read();
  k = read();
  ll si = read();
  ll sj = read();
  ll gi = read();
  ll gj = read();
  auto ijds = calc(si,sj);
  auto ijdg = calc(gi,gj);
  ll ans = 0x3f3f3f3f3f3f3f3f;

  for(auto [i0,j0,d0]:ijds){
    int t0 = calctype(i0,j0);
    for(auto [i1,j1,d1]:ijdg){
      int t1 = calctype(i1,j1);
      if(t0 == T_NORMAL || t1 == T_NORMAL){
        ans = min(ans,d0+d1+ (abs(i1-i0) + abs(j1-j0))*k);
      }else if(t0 == T_SIDE || t1 == T_SIDE){
        if(i0 == i1 && i0 % b == 0){
          ans = min(ans,d0+d1+abs(j1-j0));
        }else if(j0 == j1 && j0 % b == 0){
          ans = min(ans,d0+d1+abs(i1-i0));
        }else{
          ans = min(ans,d0+d1+(abs(i1-i0)+abs(j1-j0))*k);
        }
      }else{ // == CROSS
        ans = min(ans,d0+d1+abs(i1-i0)+abs(j1-j0));
      }
    }
  }
  printf("%lld\n",ans);
}

int main(){
  int t = read();
  while(t--) w();
  return 0;
}

H/Ex

https://atcoder.jp/contests/abc258/tasks/abc258_h

序列X满足

  1. 所有元素正奇数
  2. 和为s
  3. X前缀和的值不在集合A中, 集合A大小为N

求满足的要求的序列X的个数

范围

n 1e5

ai [1,1e18]

s [1,1e18]

题解

我的思路

果然读错题, 读成了需要序列X长度也是N

实际上对序列长度无要求

不考虑X而是直接考虑X的前缀和

dp[v] = 构成v的方案数

dp[Aj] = 0

dp[0] = 1

递推关系

dp[v] = sum{dp[v-1]+dp[v-3]+ dp[v-5]+...}

令f[i] = dp[i] + dp[i-2] + dp[i-4]

有dp[v] = f[v-1] f[v] = dp[v] + f[v-2] = (v in A ? 0 :f[v-1]) + f[v-2]

所以可以直接算f 矩阵快速幂

然后问题是要处理掉v 在 A中的情况, 并且注意到v在A中是dp[v] == 0 并不意味f[v-1] == 0

1
2
3
(f[v-1] f[v-2]) (f[v] f[v-1])
                (1/0    1   )
                ( 1     0   )

代码

https://atcoder.jp/contests/abc258/submissions/32981204

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
86
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

int n;
ll s ;

ll a[100010];

// Wi = (f[i]  f[i-1])

// (f[v] f[v-1]) = (f[v-1] f[v-2]) *
//                                (1/0    1   )
//                                ( 1     0   )

vector<vector<ll> > mul(vector<vector<ll> >m0,vector<vector<ll> >m1){
  vector<vector<ll> > r = vector<vector<ll> >(m0.size(), vector<ll>(m1[0].size(),0));
  assert(m0[0].size() == m1.size());
  rep(i,0,m0.size()){
    rep(j,0,m1[0].size()){
      rep(k,0,m0[0].size()){
        (r[i][j] += m0[i][k] * m1[k][j] % MOD) %= MOD;
      }
    }
  }
  return r;
}

vector<vector<ll> > mypow(vector<vector<ll> >m0,ll pwr){
  vector<vector<ll> > r = {
    {1,0},
    {0,1}
  };
  while(pwr){
    if(pwr%2) r = mul(r,m0);
    m0 = mul(m0,m0);
    pwr/=2;
  }
  return r;
}


int main(){
  n = read();
  s = read();
  rep(i,0,n) a[i] = read();
  a[n] = s; // dp[s] = f[s-1] =>  w[s][1]
  n++;
  vector<vector<ll> > w; // w[iw] = {f[iw], f[iw-1]}
  ll iw = 1;
  if(a[0] == 1) w = { {0,1} };
  else w = { {1,1} };

  rep(i,0,n){
    ll ai = a[i];
    if(iw == ai)continue;
    if(iw == ai-1){
      w = mul(w,{
          {0,1},
          {1,0}
          });
      iw = ai;
    }else{
      w = mul(
          mul(w,mypow({
              {1,1},
              {1,0}
              }, ai-iw-1)),{
          {0,1},
          {1,0}
          });
      iw = ai;
    }
    // printf("w[%lld] = {%lld %lld}\n",iw, w[0][0],w[0][1]);
  }
  printf("%lld\n",w[0][1]);
  return 0;
}

总结

F

没啥难的

G

内置 bitset 优化一下效率就行了

Ex

也没啥难的

参考

官方题解